5 ms·
cannot be considered just an "optimization", since it is functionally required Here is a C program: #include <stdio.h> int main(void) { while (1) mall
by millstone 14y ago
cannot be considered just an "optimization", since it is functionally required
Here is a C program:
#include <stdio.h>
int main(void) { while (1) malloc(64); }
With clang, when compiled with -O0, this consumes all the memory on my system. When compiled with -O2, it runs forever in constant memory, because clang has optimized out the call to malloc. If I replace the call with, say, 'malloc((size_t)(-1) >> 1)', it even changes the output of the program.
Here is another example:
int factorial(long long x) { return x * factorial(x-1); }
With gcc, when compiled with -O2, the factorial function can correctly compute the factorial of a very large number. When compiled with -O0, it cannot.
I would call both of these optimizations, even though someone may rely on either for correctness. So I don't think tail calls are unique in this respect.
make the syntax for guaranteed-eliminated-tail-call different than a regular call
Agreed.
- kragen 14y agoThe reason people are so interested in TCO/TCE is not just that someone might rely on them for correctness, which as you point out is true of any optimization, but rather that they are so predictable that you can omit looping constructs from your core language if you have them.
- baddox 14y agoIn the finite world beagle3 talks about, don't all optimizations potentially qualify as "functionally required"? If the finite world you're operating in can only run a program that requires at most N steps ("steps" being deliberately vague "computing resources," like CPU cycles or memory usage), then any optimization that makes an (N+1)-step program complete in N steps qualifies as a "functional requirement."
- bcoates 14y agoBoth of those programs are playing with C's infamously broad undefined behavior rules, the first for a non-terminating loop and the second for using too much stack (when called with a sufficiently large number). -O2 being nice to you is a coincidence, not something you should rely on. In a language which prefers diagnosing programmer error over punting both should be errors.
- beagle3 14y ago> even though someone may rely on either for correctness. That someone is playing with fire. It's the kind of optimization that might be removed in a hotfix because it turns out to break something else. It's even worse than relying on things like byte order -- and if you rely on them, you are definitely outside the realm of "C language", and into the realm of "Specifically LLVM v.37x patchlevel 2, on an SSE4 architecture"