4 ms·
Can you observe the difference as a programmer? Through things like the stack-trace? Then it's not an optimization.
by chrisseaton 6y ago
Can you observe the difference as a programmer? Through things like the stack-trace? Then it's not an optimization.
- OskarS 6y agoSo you’re saying inlining doesn’t count as an optimization, then?
- chrisseaton 6y agoNo, that doesn't follow. Inlining doesn't change what a call stack looks like - the call stack frames are still there, yes possibly just a metadata annotations on real call stack frames and recovered when needed. With tail calls, the call stack frames are completely gone, and cannot be recovered. Try this thought experiment - can you implement tail calls in Java and meet the same language specification? I think you cannot. Therefore it is not an optimisation. If you can please email me how and I will implement it and you can publish the paper and get the glory!
- MaxBarraclough 6y ago> can you implement tail calls in Java and meet the same language specification? I think you cannot. Is this because Java exposes stack traces in a way most languages don't?
- chrisseaton 6y agoThat's one reason - there are also a few more minor technical places in the spec where the depth of the call stack is observable in semantics such as I think the security manager. But I don't think it's unusual for a language to expose call stacks? Ruby, Python, C#, etc all do it.
- Someone 6y agoI think a Java implementation could do tail calls, but it would have to create a fake stack trace when needed. (I haven’t looked, but I would expect modern Java implementations already make up quite a bit of the stack trace only when it is needed, for example when inlining calls) And, traditionally, it _is_ unusual to expose call stacks to calling programs for Algol-style languages (implementations typically dumped a call stack and might add a way for a program to walk its stack, but that would be implementation-dependent) Without exceptions or a repl, where would you use them, other than in a crash dump?
- chrisseaton 6y ago> (I haven’t looked, but I would expect modern Java implementations already make up quite a bit of the stack trace only when it is needed, for example when inlining calls) Yes they do. But they can't make up the stack for tail calls because the information is simply gone. If you've got a set of mutually functions that are tail calling, and you suddenly need to generate a stack trace, how do you know how many times the functions have been called and which order they were called? That info was never recorded - it's just done. Inlining is static info and much simpler - it is recorded and isn't gone.
- eru 6y agoIf you only need to know how many times things were called, you could probably record that in much less space. Something like O(log n) of the depth of the stack, instead of O(n) that you need for the actual stack frames. But I assume that kind of information is probably not enough for Java.
- Someone 6y agoYou’re not going to handle the Ackermann function that way, but for both simple recursive and mutually recursive calls, I would think you can often infer up front how many loops there will be, or just maintain a single counter counting the number of recursive calls, instead of counting using a linked list of stack frames. Now, whether that’s worth the implementation effort, of course, would depend on whether the construct is used a lot, and that’s a catch-22. For functions jumping into other functions, I guess that, when the program counter says you’re in baz while the first stack frame says foo got called, you could infer that foo called bar and bar called baz from metadata that the compiler would have to add. Now, if foo can get into baz along multiple routes, you would have to record something, but I would guess there are plenty of those simpler cases. For those, the main challenge would be to infer recursion count for a recursive call.
- MaxBarraclough 6y agoI thought C#/.Net was much more permissive than Java/JVM regarding 'lying' about the call stack, in optimised release environments. [0] From a quick search it looks like tail-call optimisation is supported in the CLR but only when the IR is tagged appropriately, which the F# compiler takes advantage of, but the C# compiler does not. [1] [0] https://www.hanselman.com/blog/release-is-not-debug-64bit-optimizations-and-c-method-inlining-in-release-build-call-stacks https://www.hanselman.com/blog/release-is-not-debug-64bit-op... , ctrl-f for this stack trace is showing the runtime reality. [1] https://github.com/dotnet/runtime/issues/2191 https://github.com/dotnet/runtime/issues/2191
- masklinn 6y ago> With tail calls, the call stack frames are completely gone, and cannot be recovered. You can absolutely record these things under TCO, in much the same way you'd record virtual stackframes when inlining.
- chrisseaton 6y agoWell I don't know what to say apart from I don't think this is true. If you think it is, then you should go ahead and publish it because you've discovered a new language implementation technique.
- OskarS 6y agoOf course you can, you just add a record whenever you do the jump, exactly like what you’re describing with inlined calls. It’s not hard to implement, it’s just that nobody does it, because it’s dumb. You seem to have a very Java-centered view of the universe, because it is absolutely not true in most languages that inlined calls preserve call stacks. Call stacks are debug information, and there’s absolutely no requirement for compilers to preserve debug information while doing optimization. Requiring that would be lunacy, and it would prohibit a huge number of optimizations (or require costly bookkeeping). I don’t know what the situation is in Java-land, but if Java preserves inlining information in call stacks using bookkeeping, then good for it, I guess. It can’t come for free, so you’re taking a performance hit for that pleasure. It’s certainly not something that is common, or commonly understood as a requirement for optimization.
- chrisseaton 6y ago> you just add a record whenever you do the jump, exactly like what you’re describing with inlined calls Add another record where? On some kind of stack of records from calls? That will grow linearly with the number of calls? So that's a call-stack is it? The whole point of TCO was to eliminate the stack and you've re-invented it there! If you have an infinite tail-call (like a web server accepting requests in a loop) you'll have an infinitely long list of records with your idea. > It’s certainly not something that is common, or commonly understood as a requirement for optimization. In many languages (Python, Ruby, Java, etc) they are not debug information - they're part of the program semantics and (from experience!) if you change them you'll break programs.
- masklinn 6y agoThere are lots of optimisations which have ultimately observable side-effects e.g. in most JS implementations the closed-over environment is optimised to just the free variables (and there's no closure at all if there's nothing being closed over statically), this is extremely noticeable if you drop into a debugger in the inner function because you will not be able to access any variable which wasn't closed over. Likewise, if the compiler decides to reuse part of the stackframe because it sees two variables are only used consecutively, you won't be able to access the first variable despite it still purportedly being "in scope".
- chrisseaton 6y ago> this is extremely noticeable if you drop into a debugger Is the debugger part of the language specification? No. When I say 'can you observe the difference as a programmer' you can mentally expand that to 'can you observe the difference as a programmer who is working off a copy of the language specification'. Otherwise someone armed with a debugger can look at the machine code and then we might as well say all implementation decisions are observable by the user, and then I think we're being a bit silly. > you won't be able to access the first variable I'm not familiar with this part of JavaScript off the top of my head sorry - do you mean using a debugger again here?
- masklinn 6y ago> Is the debugger part of the language specification? No. Neither is "the stack trace".
- chrisseaton 6y agoYou're mistaken - in many language it is. (I've worked professionally with multiple language specifications and implementing them.)
- deleted 6y ago[deleted]
- MaxBarraclough 6y agoWhat about copy-elision 'optimisations' in C++, which can result in changes to observable behaviour?
- chrisseaton 6y agoSorry I'm not an expert in C++ so I couldn't say. But on the face of it yeah if it changes observable behaviour and it isn't covered by the spec then I don't see how it can be an optimisation. Maybe the spec covers what you're talking about?
- MaxBarraclough 6y agoThe C++ standards documents are famously paywalled (and I have to admit to having never read them), but here are some summaries. [0][1][2] The kicker is that according to the spec, the compiler is permitted, but not obligated, to elide object-copy operations, even when doing so results in the elision of a call to a copy-constructor function with side-effects. Of course, the optimizer is still constrained by the spec in the obvious ways: copy operations can only be elided when the compiler can show that they are redundant (in some precise sense that the spec presumably lays out). It follows of course that this 'optimisation' may impact observable behaviour. This makes some sense as C++ code shouldn't be doing 'real work' in copy-constructors, but it's still a rather ugly concession to pragmatism. edit Which, come to think it, describes the whole C++ language ;-P [0] https://stackoverflow.com/a/12953129/ https://stackoverflow.com/a/12953129/ [1] https://en.wikipedia.org/wiki/Copy_elision#Return_value_optimization https://en.wikipedia.org/wiki/Copy_elision#Return_value_opti... [2] https://en.cppreference.com/w/cpp/language/copy_elision https://en.cppreference.com/w/cpp/language/copy_elision
- eru 6y agoThe specs are a bit weird. For example, they don't mention stack overflows at all. But since standards compliant compilers spit out code that suffers from them, I assume they are allowed. So I assume you could make a standard compliant compiler that doesn't nothing but immediately overflows the stack.
- chriswarbo 6y agoThere are many types of observation we might define. The most fundamental is whether we can write a program which halts in one case and doesn't in the other. An alternative is whether we can write an if/then/else branch to distinguish between the two cases. Note that this is less general than the above, since we can always use an if/then/else to implement a halt/no-halt program, but we can't always go the other way (due to the Halting Problem). This definition is useful, since if/then/else can cause arbitrarily-large changes to a program's behaviour; whereas we can't "use" a difference which affect halting. Another definition, which is more subjective, is whether we can do the above "reliably". For example, any optimisation that makes a program faster could be observed by a language which allows access to a clock. Whilst hackers and debuggers might find these useful, it's not the sort of thing that a "reasonable" programmer would do (i.e. code which relies on this sort of thing shouldn't pass code review). I'd probably count inspecting stack traces, or running a debugger on ourselves, in this category. The messy subjectivness of the latter is why I like to limit the capabilities of what I'm developing with: I don't have to care about timing altering the behaviour of a program which can't access a clock.
- chrisseaton 6y agoRight - but you can observe the differences reliably without a clock, through looking at the stack trace.
- eru 6y agoThat's (a small) part of the reason why Haskell didn't have stack traces for the longest time.
- beagle3 6y agoOr even more simply, by blowing up the stack. If you manage to do 2^40 calls deep without blowing up the stack, you have TCE, if you do blow up the stack, you don't. And you can tell if you blew up the stack by setting up an exception handler (or lisp condition or whatever equivalent).
- 6y ago
- deleted 6y ago[deleted]
- ragnese 6y agoI don't know if that counts... I can read the 1s and 0s of a compiled binary in any language. Does that mean nothing a C compiler does is an optimization? I wouldn't consider the memory layout of something like a stack to be part of the semantics of the language, unless that language actually includes features to directly refer to the stack (get its contents or size, etc).
- chrisseaton 6y ago> I can read the 1s and 0s of a compiled binary in any language But the 1s and 0s are not specified by the language (in almost all cases.) They're out of scope.
- ragnese 6y agoBut where is the line? Is the stack size specific by any languages? Many language's compilers will eliminate variable assignments as an optimization. Since I can view a stack trace in some of those languages, then would that make that not an optimization? Like, if I just inserted `let x = 3;` in the middle of my function, but never used `x`, it would disappear from the compiled code. If I look at the stack trace, I wont see my `x` variable. Is that an optimization or a semantic language feature? Does it matter?
- chrisseaton 6y ago> But where is the line? The line is: what has been formally specified by the language spec as being part of the language.