3 ms·

It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program. However most optimizations are very hard to observe. T

It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program. However most optimizations are very hard to observe. The vast majority of optimizations only affect code size and runtime. TCO is one of the few exceptions. It affects memory usage, and more sensitive stack memory at that. This is why a missed optimization can be so much more catastrophic and it is worth considering things like `musttail` attributes so that the code fails to compile rather than misses the optimization. I can only think of a few other optimizations that affect memory usage. Register spilling (arguably not really an optimization but a necessity), Rust's niche filling for enum discriminants and C++'s std::vec<bool> (a language-level optimization, arguably a different thing entirely). I often think about how few memory optimizations we have. The reason is most likely that they tend to be non-local so are much harder to apply than CPU optimizations that generally have no effect outside of the function they are in.

steveklabnik 2mo ago
> It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program. Depends on the semantics of the programming language itself. For some languages, it is truly an optimization, for some, it is required, and does meaningfully change observed semantics.
jmalicki 2mo ago
JVM does a lot of escape analysis to turn heap allocated memory into stack local variables. It doesn't matter if it's local since it's a VM, it's doing it at runtime and can change an entire call stack of non local code for an optimization.
- pjmlp 2mo ago
  Some fact correcting, first of all while most people refer to "The JVM", most likely impling OpenJDK, Java is a standard and there are many implementations. Which exactly in this subject varies a lot between implementations, on how well escape analysis is done, if there is a JIT cache between JVM executions, or AOT compilation. Additionally Valhalla is finally getting added to the language with a new EA made available last week, thus value classes will add yet another way to have stack values.
  - jmalicki 2mo ago
    We were talking about examples of compiler optimizations that save memory, so I gave one. Value classes are not a compiler optimization, and I wasn't talking about the standard, I was talking about an implementation.
drdexebtjl 2mo ago
The main difference is not that it affects memory usage, imo. It’s that it makes memory usage bounded when it’s on, and unbounded when it’s off. In languages that have guaranteed tail call eliminations, the semantics of tail recursion is the same as that of a loop. So you can express the same iterative algorithm without using iterative code.
tialaramex 2mo ago
std::vector<bool> is just a terrible specialisation, it isn't an optimisation. If std::vector<bool> was an optimisation we couldn't write C++ which blows up because it's actually a bitset, it would be semantically transparent - but that's easy to do even by accident because it's not transparent at all. In fact the existing std::vector<bool> should just be named std::growable_bitset or something and then std::vector<bool> would make what you actually wanted like Rust's Vec<bool> does.
lilbigdoot 2mo ago
If my program crashes without it, that's a semantic difference no?
- layer8 2mo ago
  Not in the sense of formal programming-language semantics, usually.
- qsera 2mo ago
  You program did not ask for the crash via the language constructs..semantics is defined by the language, rest is the implementation details. That is how it makes sense to me. I don't understand other people in this thread who think otherwise.
mort96 2mo ago
If the semantics of 'while (true)' was "will crash the program after an implementation-defined but often fairly low number of iterations", I would stop using 'while (true)'.
- cmovq 2mo ago
  Note that compilers are more than happy to delete 'while (true)' if the loop doesn't have side-effects.
  - mort96 2mo ago
    Of course. I wasn't talking about empty loops. But also, I wouldn't rely on a compiler to remove empty 'while (true)' loops.
  - mpyne 2mo ago
    I think this is no longer true. C++26 implemented a change to make trivial loops like these defined behavior (and therefore will loop endlessly as you'd expect). And this example was always defined behavior in C. Both languages continue to have examples of slightly more complicated loops that can be assumed to terminate in the absence of side effects, but `while(true)` isn't one of those any longer.
- layer8 2mo ago
  It’s precisely not the semantics of the program that will crash the program, but the behavior of the language implementation. It’s similar to when a program in a GC language fails with OOM because the language implementation uses a no-op collector. That’s usually not part of programming language semantics.
  - mort96 2mo ago
    The specification allows implementations to have limits on maximum call stack depth and all sorts of other things. It's absolutely semantically meaningful in C to allocate a new stack frame.
derefr 2mo ago
I think the problem with considering it a "pure optimization" is that code that is written to use tail-calls, if not optimized, is almost always unbounded recursive code. And modern OSes tend to have relatively small stack-size limits (relative to the kinds of huge data structures modern software slings around, incl. not only individually-"wide" structures, but also "deep" trees and graphs.) Which means that "whether this naively-recursive code is actually recursive in practice" is a semantic difference, in that there is an error/failure-mode (stack overflow) that can be statically guaranteed to not happen (at least for a given compilation target) if TCO gets applied; but which cannot be guaranteed to not happen without TCO applied. --- Tangent: you could of course try to write code defensively, to guarantee that a stack overflow won't occur, by bounding recursion separately (e.g. via a passed-and-decremented recursion-limit parameter), so that in the non-TCO case, you get a software exception thrown (which you'd hopefully then handle... somehow), rather than triggering a stack overflow. And for many more-traditional recursive algorithms, this works! But doing so for the types of algorithms that are "canonically" expressed in terms of tail-calls (even in a non-tail-call-idiomatic language like C), almost always requires poking holes in the C abstract machine to see through to the micro-architectural details underneath. You can't just use something like a recursion-limit parameter as a general solution for these algorithms, as TCO is used in things like continuation-passing or threaded-code VM implementations — i.e. things that look less like visiting trees and more like visiting unboundedly-non-terminal infinite-state-machine states ["infinite" because the states are dynamic function pointers to JITted code, and more of them can appear at runtime.] You need to not track the "number of invocations deep" you are into the algorithm, but rather, how big the stack actually is at the moment. Which means you need to actually do math on addresses of the stack base pointer vs either the stack pointer, or the address of a local stack-allocated variable. There's no version of that that doesn't require writing non-portable inline assembly.
Someone 2mo ago
> I can only think of a few other optimizations that affect memory usage Java has string interning. I think that’s a hack that shouldn’t exist in an ideal world. Reason is that, as a library writer, you cannot make the call whether to intern strings (requiring more instructions for string access, thus slowing down code, but decreasing memory usage, and, because of that, possibly speeding up the code again) or not.
- vanderZwan 2mo ago
  > requiring more instructions for string access Wait, why would interned immutable strings require more instructions when doing regular string access? You can still point to the start of a zero-terminated C-string, it just requires storing extra metadata like lenght and a string hash somewhere. Which can be done at the negative indices of said pointer. Or do you refer to the extra rolling-hash pass needed when concatenating two strings to verify if it would result in an already-interned one? Because yes, that's one extra rolling hast pass over the appended string the first time a string is constructed, but after that doing so again likely saves memory and construction time, because any concatenation that would result in an already interned string would avoid actual memory allocation and copying of the string's characters. Plus string comparisons become cheap O(1) pointer comparisons this way, which is really nice in many use-cases. And that's not even considering more advanced tricks like interning short strings in the 64-bit word of the pointer to the string itself, relying on the fact that modern memory allocators never return an address with the lsb set, so it can be used to flag it as such[0]. [0] https://squoze.org/ https://squoze.org/
  - amiga386 2mo ago
    > Wait, why would interned immutable strings require more instructions when doing regular string access? Java automatically interns static strings (e.g. from class files), but does not automatically intern dynamically-allocated strings, e.g. new String(charArray) If you want it interned, you have to intentionally call e.g. new String(...).intern(). If you do this on every string you work with, you can then reliably use reference equality instead of value equality, e.g. given char[] abc = {'a','b','c'}; then new String(abc) != new String(abc) != "abc" but new String(abc).intern() == new String(abc).intern() == "abc" But if you're interning every string, you're doing extra work to maintain that string pool, and adding extra pressure on the GC, and potentially you'll be re-interning strings a lot depending on how many times they end up no longer referenced by the time GC runs.
fsckboy 2mo ago
>It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program it is guaranteed in Scheme, and it affects the semantics of programs in a completely positive way. Much of computer science is "pure" and "abstract" like mathematics. However, programmers are still taught to use loops to calculate factorial rather than recursion in order to avoid stack overflow. In Scheme you can use recursion without flinching. That is a semantic difference.
genxy 2mo ago
> because it doesn't affect the semantics of the program It does when you use them as a feature and not an optimization. Like in interpreters, state machines, parsers, etc. Calling tail calls an optimization set computer science back 40 years.
vrighter 1mo ago
it absolutely does affect the semantics of the program. A properly tail called function can recurse indefinitely. One without TCO will stack overflow.

steveklabnik 2mo ago

> It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program. Depends on the semantics of the programming language itself. For some languages, it is truly an optimization, for some, it is required, and does meaningfully change observed semantics.

jmalicki 2mo ago

JVM does a lot of escape analysis to turn heap allocated memory into stack local variables. It doesn't matter if it's local since it's a VM, it's doing it at runtime and can change an entire call stack of non local code for an optimization.

pjmlp 2mo ago
Some fact correcting, first of all while most people refer to "The JVM", most likely impling OpenJDK, Java is a standard and there are many implementations. Which exactly in this subject varies a lot between implementations, on how well escape analysis is done, if there is a JIT cache between JVM executions, or AOT compilation. Additionally Valhalla is finally getting added to the language with a new EA made available last week, thus value classes will add yet another way to have stack values.
- jmalicki 2mo ago
  We were talking about examples of compiler optimizations that save memory, so I gave one. Value classes are not a compiler optimization, and I wasn't talking about the standard, I was talking about an implementation.

drdexebtjl 2mo ago

The main difference is not that it affects memory usage, imo. It’s that it makes memory usage bounded when it’s on, and unbounded when it’s off. In languages that have guaranteed tail call eliminations, the semantics of tail recursion is the same as that of a loop. So you can express the same iterative algorithm without using iterative code.

tialaramex 2mo ago

std::vector<bool> is just a terrible specialisation, it isn't an optimisation. If std::vector<bool> was an optimisation we couldn't write C++ which blows up because it's actually a bitset, it would be semantically transparent - but that's easy to do even by accident because it's not transparent at all. In fact the existing std::vector<bool> should just be named std::growable_bitset or something and then std::vector<bool> would make what you actually wanted like Rust's Vec<bool> does.

lilbigdoot 2mo ago

If my program crashes without it, that's a semantic difference no?

layer8 2mo ago
Not in the sense of formal programming-language semantics, usually.
qsera 2mo ago
You program did not ask for the crash via the language constructs..semantics is defined by the language, rest is the implementation details. That is how it makes sense to me. I don't understand other people in this thread who think otherwise.

mort96 2mo ago

If the semantics of 'while (true)' was "will crash the program after an implementation-defined but often fairly low number of iterations", I would stop using 'while (true)'.

cmovq 2mo ago
Note that compilers are more than happy to delete 'while (true)' if the loop doesn't have side-effects.
- mort96 2mo ago
  Of course. I wasn't talking about empty loops. But also, I wouldn't rely on a compiler to remove empty 'while (true)' loops.
- mpyne 2mo ago
  I think this is no longer true. C++26 implemented a change to make trivial loops like these defined behavior (and therefore will loop endlessly as you'd expect). And this example was always defined behavior in C. Both languages continue to have examples of slightly more complicated loops that can be assumed to terminate in the absence of side effects, but `while(true)` isn't one of those any longer.
layer8 2mo ago
It’s precisely not the semantics of the program that will crash the program, but the behavior of the language implementation. It’s similar to when a program in a GC language fails with OOM because the language implementation uses a no-op collector. That’s usually not part of programming language semantics.
- mort96 2mo ago
  The specification allows implementations to have limits on maximum call stack depth and all sorts of other things. It's absolutely semantically meaningful in C to allocate a new stack frame.

derefr 2mo ago

I think the problem with considering it a "pure optimization" is that code that is written to use tail-calls, if not optimized, is almost always unbounded recursive code. And modern OSes tend to have relatively small stack-size limits (relative to the kinds of huge data structures modern software slings around, incl. not only individually-"wide" structures, but also "deep" trees and graphs.) Which means that "whether this naively-recursive code is actually recursive in practice" is a semantic difference, in that there is an error/failure-mode (stack overflow) that can be statically guaranteed to not happen (at least for a given compilation target) if TCO gets applied; but which cannot be guaranteed to not happen without TCO applied. --- Tangent: you could of course try to write code defensively, to guarantee that a stack overflow won't occur, by bounding recursion separately (e.g. via a passed-and-decremented recursion-limit parameter), so that in the non-TCO case, you get a software exception thrown (which you'd hopefully then handle... somehow), rather than triggering a stack overflow. And for many more-traditional recursive algorithms, this works! But doing so for the types of algorithms that are "canonically" expressed in terms of tail-calls (even in a non-tail-call-idiomatic language like C), almost always requires poking holes in the C abstract machine to see through to the micro-architectural details underneath. You can't just use something like a recursion-limit parameter as a general solution for these algorithms, as TCO is used in things like continuation-passing or threaded-code VM implementations — i.e. things that look less like visiting trees and more like visiting unboundedly-non-terminal infinite-state-machine states ["infinite" because the states are dynamic function pointers to JITted code, and more of them can appear at runtime.] You need to not track the "number of invocations deep" you are into the algorithm, but rather, how big the stack actually is at the moment. Which means you need to actually do math on addresses of the stack base pointer vs either the stack pointer, or the address of a local stack-allocated variable. There's no version of that that doesn't require writing non-portable inline assembly.

Someone 2mo ago

> I can only think of a few other optimizations that affect memory usage Java has string interning. I think that’s a hack that shouldn’t exist in an ideal world. Reason is that, as a library writer, you cannot make the call whether to intern strings (requiring more instructions for string access, thus slowing down code, but decreasing memory usage, and, because of that, possibly speeding up the code again) or not.

vanderZwan 2mo ago
> requiring more instructions for string access Wait, why would interned immutable strings require more instructions when doing regular string access? You can still point to the start of a zero-terminated C-string, it just requires storing extra metadata like lenght and a string hash somewhere. Which can be done at the negative indices of said pointer. Or do you refer to the extra rolling-hash pass needed when concatenating two strings to verify if it would result in an already-interned one? Because yes, that's one extra rolling hast pass over the appended string the first time a string is constructed, but after that doing so again likely saves memory and construction time, because any concatenation that would result in an already interned string would avoid actual memory allocation and copying of the string's characters. Plus string comparisons become cheap O(1) pointer comparisons this way, which is really nice in many use-cases. And that's not even considering more advanced tricks like interning short strings in the 64-bit word of the pointer to the string itself, relying on the fact that modern memory allocators never return an address with the lsb set, so it can be used to flag it as such[0]. [0] https://squoze.org/ https://squoze.org/
- amiga386 2mo ago
  > Wait, why would interned immutable strings require more instructions when doing regular string access? Java automatically interns static strings (e.g. from class files), but does not automatically intern dynamically-allocated strings, e.g. new String(charArray) If you want it interned, you have to intentionally call e.g. new String(...).intern(). If you do this on every string you work with, you can then reliably use reference equality instead of value equality, e.g. given char[] abc = {'a','b','c'}; then new String(abc) != new String(abc) != "abc" but new String(abc).intern() == new String(abc).intern() == "abc" But if you're interning every string, you're doing extra work to maintain that string pool, and adding extra pressure on the GC, and potentially you'll be re-interning strings a lot depending on how many times they end up no longer referenced by the time GC runs.

fsckboy 2mo ago

>It's hard to argue that it isn't an optimization, because it doesn't affect the semantics of the program it is guaranteed in Scheme, and it affects the semantics of programs in a completely positive way. Much of computer science is "pure" and "abstract" like mathematics. However, programmers are still taught to use loops to calculate factorial rather than recursion in order to avoid stack overflow. In Scheme you can use recursion without flinching. That is a semantic difference.

genxy 2mo ago

> because it doesn't affect the semantics of the program It does when you use them as a feature and not an optimization. Like in interpreters, state machines, parsers, etc. Calling tail calls an optimization set computer science back 40 years.

vrighter 1mo ago

it absolutely does affect the semantics of the program. A properly tail called function can recurse indefinitely. One without TCO will stack overflow.