Tail-call optimization in C is relatively recent [LWN.net]

LWN<br>.net<br>News from the source

Content Weekly Edition<br>Archives<br>Search<br>Kernel<br>Security<br>Events calendar<br>Unread comments

LWN FAQ<br>Write for us

User:<br>Password: |

Log in /<br>Subscribe /<br>Register

Tail-call optimization in C is relatively recent

Tail-call optimization in C is relatively recent

Posted Aug 21, 2025 22:11 UTC (Thu) by anton (subscriber, #25547)

Parent article: Python, tail calls, and performance

Actually tail calls in C have not been around forever. The C calling convention has been that the callee does not remove any stuff the caller has put on the stack. The caller could see the declaration int f();, the actual call could have n>0 arguments, and the actual function could have m&leq;n parameters. That would not always work if the callee removed the arguments.

So the caller had to remove the arguments between the call and the following return, turning the call into a non-tail call.

When I looked in 1994 at the C compilers of the day, they did not perform tail-call optimization for the kind of usage shown in the article. 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).

I have not looked at the issue since then (GCC's goto * was good enough (well, mostly)), and I had not much reason for assuming that something had changed wrt to GCC support for tail-calls (although one release note mentioned sibcalls, and I remember thinking that I should be checking that out.

Anyway, last year I read the paper on "Copy-and-Patch Compilation" by Xu and Kjolstad, and they use tail-call optimization. In any case, after reading that paper, I made some tests if gcc and clang can do tail-call optimization for the kind of tail calls shown in the article. And it works. And Xu and Kjolstad report that they use 100,000 code snippets, whereas we limit ourselves in Gforth to goto *-based system.

We have not gotten around to putting this into Gforth yet, so congratulations to the Python community for being there first.

to post comments

Tail-call optimization in C is relatively recent

Posted Aug 23, 2025 19:43 UTC (Sat)<br>by lafp (subscriber, #89554)<br>[Link]

For what it's worth, I recently implemented a (toy) interpreter for a variant of Forth that uses tail calls for dispatching instructions. The main gain I had was making all the built-in functions behave like instructions themselves, rather than having a "call a built-in function" instruction; it also has support for a few handfuls of super-instructions, which helped quite a bit as they're not that different than anything else. The performance is pretty decent, but it'll need a bit more work in the optimizer to reach what I need it to reach (ultimately I want this to run on a small computer, expose the interpreter through a browser, and let people write code that's then used to control a LED matrix; think of this project, but in a smaller scale: https://www.noisebridge.net/wiki/Flaschen_Taschen).

The code is here (https://github.com/lpereira/lwan/blob/master/src/samples/...) and it's a variant of the Forth Haiku language, that lets you create art with small bits and pieces of Forth code, not unlike ShaderToy is for GLSL.

Copyright &copy; 2026, Eklektix, Inc.

Comments and public postings are copyrighted by their creators.

Linux is a registered trademark of Linus Torvalds