Tail-call optimization in C is relatively recent (2025) (lwn.net)
152 points by prakashqwerty a day ago
mark-probst 12 hours ago
> In 2001 Mark Probst implemented tail-call optimization in GCC
That's me.
The motivation back then was to allow compilers that target C to assume that tail calls will be "proper". That's different from an optimization, which is usually optional, and which compilers don't guarantee.
The LWN post briefly sketches why this is hard: C allows variable-argument functions (like printf) where only the caller knows for sure how many arguments it passed, which means that only the caller can clean up the stack, unless the stack frame size is also communicated, which "normal" C calling conventions don't do. But when the callee does a proper tail call, the stack frame that returns to the callee is not the stack frame that the callee originally sent. This is explained in more detail in my thesis starting on page 16: https://hostr.flingit.run/s/proper-tail-calls.pdf
anitil 9 hours ago
That is a very cool contribution, I actually didn't know that it required a new calling convention! I look forward to reading your thesis
kazinator 6 hours ago
Let's assume that parameter are all the same size and put on a stack.
If you know that you are an M-parameter function being called, and you want to tail cal an N-parameter function, where N <= M, then you can just place the new N parameters in the same space on the stack where you received your M parameters, and jump to that function. That function will return to your original caller, which will remove the M parameters, not caring that some of them are not the originals that it passed.
Suppose N > M. Things start to get tricky. There isn't space in our original argument space for N. If we increase the space, the original caller won't clean it up properly. If we just allocate a new space of N, we are not making a tail call.
Because we want to make a tail call, it means we don't expect to execute any code in this function any more, and are free to trash the local variables. We can move the stack down a bit to make room for N arguments above where previously we were given M by our caller. To solve the problem that our caller wants to clean up M, but we need it to clean up N could be solved by a trampoline. We prime the stack such that when the tail-called function we are targeting returns, it will not go to our caller directly but to a stub function. That stub function will clean up the N-M words of the stack, leaving M, and then return to the original caller, which cleans up M.
In this situation, we are benefiting from knowing that the caller passed M to us. In the case of a variadic function, we don't know at all. It could just be the fixed arguments (parameters before the ellipsis) like printf("hello\n'), or any number. There is a run-time protocol to discover what parameters there are; the application logic figures it out from the arbitrary conventions. That's too late and too ad hoc for compile time.
I think yuo can reason about it similarly to above. If we are a variadic with M fixed parameters, we know we are called with at least M arguments, so we can place N <= M tail-callee arguments into the variadic space and proceed accordingly. For N > M, we can extend to make up the difference and use the trampoline to clean up and return to the original caller.
sThese trampolines are not closures; they are behind-the-scenes that can be generated as static code; no executable heaps or stacks required.
drdexebtjl 20 hours ago
Unless the language can guarantee TCO, I don’t feel comfortable writing tail recursive code and being at the compiler’s/interpreter’s mercy.
I think the framing of TCO as an optimization has been very unfortunate.
kevincox 20 hours ago
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.
derefr 16 hours 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.
steveklabnik 19 hours 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.
mort96 18 hours 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)'.
leni536 15 hours ago
cmovq 17 hours ago
layer8 17 hours ago
tialaramex 19 hours 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.
genxy 10 hours 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.
lilbigdoot 19 hours ago
If my program crashes without it, that's a semantic difference no?
qsera 13 hours ago
layer8 17 hours ago
jmalicki 19 hours 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 17 hours ago
Someone 15 hours 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 13 hours ago
drdexebtjl 19 hours 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.
fsckboy 13 hours 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.
eterm 18 hours ago
C# is an interesting case because it shares a common runtime with F#, and F# guarantees TCO in most circumstances ( try / catch can stop it ) .
There is a "tail" prefix in the intermediate language (IL) bytecode that F# uses but Roslyn, the C# compiler, never emits.
So unlike F#, whether the same algorithm written in C# becomes a loop depends on JIT behaviour. This means if you're coming to a function cold in C# you can overflow the stack, while if you enter the same function fresh after it's been warmed up, it may have been optimised away by RyuJIT and if so you are able to call it safely for what would be large numbers of recursions.
pjmlp 17 hours ago
The interesting case is the Common Language Runtime, not C#.
> More than 20 programming tools vendors offer some 26 programming languages — including C++, Perl, Python, Java, COBOL, RPG and Haskell — on .NET.
https://news.microsoft.com/source/2001/10/22/massive-industr...
MSIL thus had to support all of them.
Those differences between language semantics is why CLS was also a thing back then.
https://learn.microsoft.com/en-us/dotnet/standard/language-i...
LukeShu 20 hours ago
GCC has `[[gnu::musttail]] return`.
But yes, framing TCO as an optimization is unfortunate.
vinkelhake 19 hours ago
And there's also [[clang::musttail]] and [[msvc::musttail]].
As well as an effort to get it standardized: https://isocpp.org/files/papers/D3939R0.html (in C++).
throwaway81523 13 hours ago
You can rely on it now in gcc and clang, in the sense that they support a [[musttail]] attribute that tells the compiler to report an error if a call can't be TCO'd. The language doesn't guarantee TCO but can implement it at its option. If your program uses the attribute and still compiles, it means it has compiled with proper TCO.
RossBencina 10 hours ago
Indeed. I guess this is why [[gnu::musttail]] and [[clang::musttail]] exist.
https://gcc.gnu.org/onlinedocs/gcc-15.1.0/gcc/Statement-Attr...
jimbob45 2 hours ago
Someone on here had the neat idea of a “become” keyword replacing “return” when TCO is desired. I thought it was the obvious route forward and remain confused why I still haven’t seen it adopted.
Lorkki 2 hours ago
Rust has it as an experimental feature: https://doc.rust-lang.org/stable/std/keyword.become.html
Of course it's nowhere near a guarantee that it would land in the stable language, but it's still an opportunity to try it in practice.
beagle3 2 hours ago
Same here. (Except, following 1980’s BASIC, I always expected it to be called “chain”)
throw838489448 19 hours ago
Some languages have TCO annotation, it throws compiler error if TCO fails. You want stronger type system, not smart compiler guarantees or promises!
mort96 18 hours ago
That's not a type system thing... Whether a call gets TCO'd isn't represented in the type system if it's just an annotation on a return statement.
kenjin4096 a day ago
I think Anton is replying to me in that LWN article IIRC. I personally didn't know C only had tail calls that late and learnt something new there!
On the other hand, I am pretty new to the compiler space myself, and I count early 2000s as a pretty long time ago, though again it is not that far back considering how long other language implementations had tail calls like in ML or variants since 1980-90s.
pjmlp a day ago
It still doesn't, this is a compiler specific language extension.
You won't find anything on ISO/IEC 9899:2024 about tail calls, like it happens on Scheme.
https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3220.pdf
Section 3.5 of R7RS.
wahern 21 hours ago
A formal technical specification (TS) extension is already being drafted: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3582.pdf That's a step up from the usual proposals. I'm not sure what criteria is used to decide whether to first create a TS vs just incorporating a change into the working draft of the next standard.[1] _Defer also seems to be taking the TS route.[2]
1. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3886.pdf
2. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3928.pdf
leoc 21 hours ago
pjmlp 21 hours ago
kenjin4096 19 hours ago
Woops, I meant to write tail call optimization not tail calls. Shouldn't have used the term interchangeably. Yeah I'm aware that C doesn't have proper tail calls. Thanks for the correction though.
cryptonector 11 hours ago
I think Anton is wrong. Since C89 and before C23 calling an `int f();` function with arguments not matching the definition's actuals is UB. In C23 `int f();` became the same as `int f(void);`, so calling that function with any arguments is a compile-time error.
For variadic functions, if you use `va_start()`/`va_arg()`/`va_end()` to consume all the arguments, and leave no `va_list` alive, then the compiler can correctly generate a tail call from such functions.
mmsc a day ago
and TCO was added then removed from js! https://stackoverflow.com/a/54721813
This leads to fun stack-overflow bugs too in a lot of js code (one solution is to flatten: https://joshua.hu/javascript-infinite-tail-call-recursion-st...)
pfdietz a day ago
Lack of TCO is also a common footgun for Scheme programmers using Common Lisp.
tialaramex a day ago
This footgun is the reason I'm so enthusiastic about the Rust `become` keyword.
This proposal would give Rust a specific keyword which says that you intend TCO and so two things happen: 1. The compiler goes to more length to deliver TCO even where it wouldn't "just work" and 2. If it cannot deliver TCO your code doesn't compile, because you asked for TCO.
chriswarbo a day ago
StilesCrisis a day ago
jmalicki 19 hours ago
guenthert a day ago
Only if they are using an insufficiently smart compiler. SBCL handles TCO just fine, as do a number of other implementations, see : https://0branch.com/notes/tco-cl.html
pfdietz a day ago
mort96 18 hours ago
pjmlp a day ago
Mostly because they forget Scheme is one of the few languages where TCO is part of the language standard, making it a required feature for any compliant implementation.
This has always been an issue regarding TCO support across programming languages.
pfdietz 21 hours ago
groundzeros2015 a day ago
Js really should have it. I think the shift in style from functional and manual prototype chains to Java classes is quite disappointing.
chuckadams 20 hours ago
Technically TCO is still in the spec, TC39 deadlocked over modifying it. TC39 really does not fill me with confidence in general.
webstrand 17 hours ago
ES6 class syntax is still mostly just syntax sugar overtop prototypical inheritance.
JS _does_ still have TCO (called Proper Tail Calls), Safari's JavaScriptCore implements it, and is technically the only conforming interpreter.
groundzeros2015 17 hours ago
torginus 18 hours ago
What practical patterns are enabled by TCO in C? My impression is that every tail call can written as a loop much more naturally. Tail calls are important in functional languages where you don't have mutable loop variables.
And imo they are an ugly hack even there - one of the few core constructs where its readily apparent you're not programming an abstract machine but a real, and limited computer. For example the most natural way to write factorial:
let rec factorial n = if n <= 1 then 1 else n * factorial (n - 1)
adrian_b 17 hours ago
Not every tail call is for a loop.
You can have a set of mutually recursive functions, which tail call each other.
In C you can write state machines using "goto" (the implementations with "switch" are typically much more inefficient), but in languages with guaranteed tail call optimizations you can write a state machine where each state is a function.
In general, it is frequent enough to call another function as the last step of a function, even when there is no recursion involved. It is quite stupid for a compiler to use a CALL in such instances, instead of using a JMP. The only problem is that the function calling convention must be compatible with this optimization, while traditionally the C language used an inefficient calling convention that is not compatible with optimizations. That convention is a residue of the time when functions could be used without being declared and it should never be used by modern compilers.
fluoridation 17 hours ago
I can't see why the calling convention could matter. Can you give an example?
layer8 16 hours ago
sparkie 13 hours ago
> What practical patterns are enabled by TCO in C?
Continuation Passing Style - an important construction for interpreters, but which is also useful for compilers as it's a nice way to do control flow analysis, data flow analysis and more.
The missing feature is closures - functions which capture values from their static environment, which are basically needed to make CPS useful. GCC has nested functions, but they cannot capture without making the stack executable, which is terrible. There's a proposal[1] to get closures into C, but at present you need to simulate the capturing yourself, which is cumbersome, but can be done efficiently.
[1]:https://thephd.dev/_vendor/future_cxx/papers/C%20-%20Functio...
toast0 15 hours ago
> My impression is that every tail call can written as a loop much more naturally.
Which is more natural? (please just assume my wonky pseudo code syntax makes sense)
printall(List) ->
foreach item in List {
print_item(item)
}.
printall([Head | Tail]) ->
print_item(Head),
printall(Tail);
printall([]) -> ok.
10000truths 14 hours ago
> TCO makes a lot of sense for interpreters and state machines.
The reason that performant implementations prefer TCO is because the only reliable knob that clang and gcc provide to control which locals are spilled to stack vs. kept in registers is via calling convention constraints. One could accomplish the same performance without TCO'd recursion if there existed an annotation for local variables designating them as spill/no-spill. But that doesn't exist in clang or gcc - the "register" keyword in the C standard was supposed to be for exactly that, but it's ignored in both compilers.
sparkie 11 hours ago
noelwelsh 16 hours ago
> What practical patterns are enabled by TCO in C?
It's important in interpreters. Here's an example: https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
norir 16 hours ago
It is simple to convert factorial to tail recursive form. In lua, which has tco:
local factorial do
local function impl(n, acc)
if n == 1 then
return acc
else
return impl(n - 1, acc * n)
end
end
factorial = function(n)
if n < 0 then
error("factorial input is negative")
elseif n <= 1 then
return 1
else
return impl(n - 1, n)
end
end
end
local acc = 1
repeat
acc = acc * n
n = n - 1
until n == 1
return acc
cryptonector 12 hours ago
TFA assumes pre-C89 C, I think:
> The caller could see the declaration int f();, the actual call could have n>0 arguments, and the actual function could have m≤n parameters.
Certainly if `f()` were `int f(void);` then that wouldn't be the case. But even for `int f();` C17 6.5.2.2p6 says that "If the number of arguments does not equal the number of parameters, the behavior is undefined." Near as I can tell that was made UB in C89. So TFA is a) right about K&R C, b) just wrong for pretty much all post-K&R C. C23 makes `int f();` be the same as `int f(void);`.
That calling a non-variadic function with more / fewer arguments than expected by its definition is UB is enough to make TCO possible for that function's body.
The point about K&R C is well taken though: to turn a tail call into a jump, the caller needs to know how much to pop off the stack.
For variadic if you `va_start()`, `va_arg()` as needed, then `va_end()` with no `va_copy()` left alive then you can still tail-call out correctly, otherwise you can't.
For non-variadic functions post K&R C TCO should always be possible and not UB, provided you're not triggering UB to begin with by using the incorrect number of arguments.
amavect 15 hours ago
I recently played around with what I call "manual tail-call optimization": transform a tail call to a goto to the beginning of the function. Check it out: https://godbolt.org/z/3fY1v1oeW
int factorial_loop_iterative(int n, int a){
while(n > 0){
a = a * n;
n = n - 1;
}
return a;
}
int factorial_loop_recursive(int n, int a){
if(n > 0){
return factorial_loop_recursive(n - 1, a * n);
}else{
return a;
}
}
int factorial_loop_manual(int n, int a){
tailcall:
if(n > 0){
a = a * n;
n = n - 1;
goto tailcall;
}else{
return a;
}
}
int (*factorial_loop)(int n, int a) = factorial_loop_manual;
int factorial(int n){
return factorial_loop(n, 0);
}
zamadatix 11 hours ago
Seems like a complex way to write a normal looped version. Apart from factorial_loop_manual() being one in design, its name even says as much.
throwaway81523 13 hours ago
GCC has had TCO since the 1980s I'm pretty sure. Since then it's been extended to work in more contexts.
nyeah a day ago
>That quote is the article, and it's a little surprising that it's buried so far into the content
Is it really surprising in 2026? Today's online writing style is not primarily designed to communicate. It's designed to keep the reader 'engaged' for as long as possible. The reader's time is a resource to be extracted.
I'm absolutely not poking this author individually. It's the writing style of the net.
derdi 21 hours ago
I was wondering what this was in reference to; it's not in reference to TFA here. It's a quote from https://bytecode.news/posts/2026/08/because-it-s-not-fun-eno..., so presumably you meant to post this over at https://news.ycombinator.com/item?id=49242245.
nyeah 21 hours ago
Oh, good point, thanks.
swiftcoder a day ago
> In 2001 Mark Probst implemented tail-call optimization in GCC
MSVC didn't add tail-call optimisation until sometime in the 2010s, IIRC.
I distinctly remember sending a tail-recursive C++ program to someone who developed on Windows, and it crashing, in the late mid-to-late 2000s.
throw-qqqqq 21 hours ago
MSVC stands for MicroSoft Visual C++ compiler AFAIK.
It famously doesn’t support a few features of C99.
They don’t really seem to care much about regular C support (non-C++).
pjmlp 21 hours ago
They officially saw no need for C support going forward.
https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...
Note,
"If you really need either of the following.....then we recommend that you consider using a different compiler such as Intel or gcc (short-term) and/or pressure your standards committee representatives to have ISO C++ include more of the C standard (longer-term)."
Which is kind of why nowadays clang is part of Visual Studio as well.
However, after Satya got into the whole Microsoft <3 FOSS, this changed a bit,
https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-...
There are a few blogs after that, so at least up to C17 minus the optional parts from C11, the support is there.
It remains to be seen if anything C23 or later will ever come into MSVC, and then again, clang is part of VS installer.
throw-qqqqq 19 hours ago
steveklabnik 19 hours ago
(2025)
messe a day ago
> In 2001 Mark Probst implemented tail-call optimization in GCC with a separate calling convention; he lists the limitations of the then-existing tail-call optimization in GCC in section 6.4, among them: "It cannot handle indirect calls" (which would have been used in tail calls for interpreter dispatch).
Relatively recent being a quarter of century? Or at least a fifth of a century for indirect calls[1] (GCC 3.4.6 is the earliest I see on Compiler Explorer, released March 2006).
coliveira 21 hours ago
For people who passed their 30s, everything that happened after their 20th birthday is recent. For me, September 11 is recent memory, as well as the 2008 great recession.
derdi 21 hours ago
Given that GCC was first released in 1987, that would mean that tail call optimization, including of indirect calls, has been around for more than half of GCC's lifetime. So it's indeed fair for the parent article to say that "[GCC has] had tail-call optimizations for most of [its] existence".
adrian_b 18 hours ago
That is not exactly true, because for a long time tail call optimizations had a lot of restrictions in gcc, so they could be used only seldom.
What is said in TFA is correct in the sense that only in recent years the support for tail call optimization became good enough to be able to rely on it, if you use appropriate compilation options.