6 ms·

Parsing protobuf at 2+GB/s: how I learned to love tail calls in C (2021)

366 points by fanf2 2y ago

deleted 2y ago
[deleted]
gpderetta 2y ago
> I very much hope that the attribute will catch on, spreading to GCC, Visual C++, and other popular compilers, AFAIK, attribute musttail is in the process of being added to GCC (the patch is under review) with semantics compatible with clang.
- ufo 2y ago
  What about the preserve_most attribute? Is there any chance something like that will get into GCC? Without it, the non-tail calls ruin the interpreter.
  - gpderetta 2y ago
    Maybe, but not there yet: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110899 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110899 In the meantime some inline assembly macro trickery might help. edit: code duplication can also be obviated by templating your op function with a fast/slow parameter, with the fast variant tail-calling the slow variant when it cannot perform the fast path, while guarding the slow code via the compile time parameter. The downside is yet more code obfuscation of course.
- katzinsky 2y ago
  Given some of the other scheme-like features GNUC has it's surprising they're lagging on this one.
- fweimer 2y ago
  It's a hard problem because many ABIs cannot do tail calls even for very basic stuff, like calls to extern functions with matching argument and return types. It looks like Clang has some heuristics for changing call sequences for musttail calls. For example, it switches to noplt calls on i686. None of this is mentioned in the Clang documentation: https://clang.llvm.org/docs/AttributeReference.html#musttail https://clang.llvm.org/docs/AttributeReference.html#musttail What's realistic here is that you get a diagnostic if the compiler cannot generate a tail call. For many users, that will likely be good enough. Guaranteeing a tail call as in Scheme is unlikely to happen.
irdc 2y ago
I wonder how fast this would be when using a trampoline, i.e. returning the next function as a function pointer and calling that from an outer loop. That would have the advantage of being portable C.
- chii 2y ago
  the reason i suspect tail call optimization is fast would be because the resultant loop is predictable and thus CPU instruction prefetch and memory prefetch works very well. Jumping via function pointers would probably not be as predictable, and you'd unlikely to see the same benefit. Of course, one must measure, and i haven't.
  - gpderetta 2y ago
    The tail call interpreter is also calling through a function pointer. The cost here is purely the call+ret overhead, which can be non-trivial when it is per opcode; on some micro-architectures there is also a limit on taken jumps per cycle (sometimes as low as one taken jump every other cycle). edit: trampolining would also collapse all indirect jumps to a single source address which is not ideal for branch prediction.
- soegaard 2y ago
  C is often used as target language for compiler from higher level languages. The Scheme programming language requires all tail calls not to grow the stack. Therefore implementors have explored various techniques including trampolines. I don't have a citation, but you can find the answer in the papers on compiling Scheme to C. If there is no guarantee of TCO in the target language, then the generated programs will be slower. Incidentally, this is why implementors of (especially) high level languages are annoyed that TCO was removed from the JavaScript specification. There are even solution for having TCO and still have stack inspection. https://github.com/schemedoc/bibliography/blob/master/page8.md https://github.com/schemedoc/bibliography/blob/master/page8....
TechMaverick 2y ago
[flagged]
- barrkel 2y ago
  New account, banal observation, invitation to interact. It's a pattern I've seen recently on what are apparently LLM-powered engagement bots on Twitter.
  - deleted 2y ago
    [deleted]
  - kachapopopow 2y ago
    New fear unlocked.
    - david_allison 2y ago
      Your fear is reality: https://replyguy.com/ https://replyguy.com/
  - nequo 2y ago
    What are those engagement bots for? Are they farming followers and turn into disinformation machines later? Or is that only to drive engagement to cultivate ad revenue for Twitter, or for some “brand” that is adjacent to their topic?
    - twoodfin 2y ago
      The way hn karma works, you’re incentivized to accumulate a set of bots that meet the threshold for flagging and downvoting. Barring effective anti-bot/brigading measures (some of which I’m sure exist), such a team of bots could manipulate front page content. That’s a valuable capability for a variety of nefarious aims in this space. A straightforward one would be either subtly or dramatically tilting sentiment here negative against some mid-cap public tech company and profiting from a short position. (Assuming you think investors care what gets upvoted on hn…)
stabbles 2y ago
Maybe the example is too simple, but it does not require `__attribute__((musttail))` for good code gen. Also if the error handling function is unlikely, you wouldn't care too much about how fast it is to call it? To me it seems like a structure of the form <read data> if (unlikely(malformed)) return error(); <prep more stuff> switch (data_type) { case x: return handle_x(); case y: return handle_y(); } generates a nice jump table quite reliably.
- OskarS 2y ago
  Obviously compilers have been doing tail call elimination for ever, but for this trick "generates [tail calls] quite reliably" is not enough: you have to GUARANTEE it (or fail compilation), otherwise this structure does not work (it will blow the stack immediately). That's the point of [[musttail]], tail call elimination is required, that's the only choice the compiler has.
  - stkdump 2y ago
    That means that any such code is not portable across compilers anymore. It is effectively written in a non-standard C dialect, because it requires a language extension to work correctly.
    - ufo 2y ago
      Yes. But the alternative is assembly language, which is even less portable.
      - kachapopopow 2y ago
        assembly is the most portable of them all even across platforms! (x86 to arm compilation meme)
      - Karliss 2y ago
        The portable alternative is being explicit with your loops, possibly in combination with gigantic unwieldy switch statements or some regular goto (it is still part of standard). But that comes at the cost of readability and sometimes performance.Whether it's practical depends on the usecase. For something like recursive data structure algorithms which are relatively small and self contained, I would say it's perfectly doable. Simple interpreters - maybe. Complex interpreters - here it becomes messy.
PaulRobinson 2y ago
Perhaps I've just been looking more (because I've been going back to the books to pick up C again after a 20 year absence for a side project), but it feels like in recent years there has been a little uptick in people appreciating the level of control C provides, and "going back to basics". I think the work on C23 (which would have still been C2x when this article was written), means people are starting to want to see innovation in the language again. I don't think that would have happened without Go and Rust showing some great thinking, but it's interesting that it's happening at all. Tail calls are an interesting idea, and now I want to know more about both this extension, and also how to write my code in such a way as to help a compiler optimize for tail calls even when this extension isn't present. This somehow feels more fun to me than writing more Python or Ruby...
- 38 2y ago
  [flagged]
  - verandaguy 2y ago
    C is not a dead language to literally millions of other programmers and the billions of ongoing practical applications of it. If your threshold for a language's alive-ness is the presence or absence of a package manager, you should reevaluate.
  - creata 2y ago
    1. I don't think the presence of centralized package management makes or breaks a language for most people. 2. Your platform's package manager should have plenty of C packages.
    - lwansbrough 2y ago
      I think the success of Javascript and Rust certainly tests your biases. I can say anecdotally that the lack of a standard package manager in C and C++ kept me from exploring those languages.
      - 2y ago
sp1rit 2y ago
I wonder how this behaves in combination with __attribute__((cleanup(...))). Especially if the to be cleaned variable is passed into the tail function as parameter.
- Karliss 2y ago
  You get an error that tail call can't be performed which is kind of the point of tailcall attribute. Same thing with regular c++ destructors or dozen other language features which interfere with tail calls, no need for extensions like __attribute__((cleanup()). https://godbolt.org/z/Yex74Wjz7 https://godbolt.org/z/Yex74Wjz7
fuhsnn 2y ago
A C standard proposal exists for tail call [0], in the form of "return goto (expression);". What I like about it, over standardizing [[musttail]], is that lifetimes of local objects are guaranteed to end. This makes it possible to implement without extensive escape analysis. [0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5-tail-call-elimination https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5...
- nxobject 2y ago
  As an aside, I’m excited - but also with lots of trepidation - about the new energy in adding new functionality to C. Excited because there are changes and additions that are crying to be made, even clarifying ideas… trepidation because C++’s gung ho update cadence has somehow ended up in wart patched over wart. Especially when feature reacts with feature in an unfelicitous way far earlier than anticipated. I hope the standards process finds a way to be very conservative, really thoroughly test features in large and diverse codebases, rather than just relying on rationales alone, when choosing to include feature.
  - pjmlp 2y ago
    What new energy? We have had C89, C99, C11, C17, C23 And yet, no fix in sight for proper strings, arrays, or at very least bounds checked slices, like Dennis Ritchie originally proposed to ANSI/ISO.
- haberman 2y ago
  Thanks for the pointer, I'll have to check this out. Can you elaborate on how "return goto" is easier to implement? [[musttail]] also ends the lifetime of local objects AFAICS. One thing I'll mention from a quick scan: > [The] function called in tail position must have identical type to the callee. This ensures both that the return value does not require any conversion, and also that argument passing space is available and calling convention (if relevant) is maintained. One complaint I've seen repeatedly about [[musttail]] (which I implemented in Clang) is that this constraint is unnecessarily strict, since some architectures will allow tail calls even for functions that do not perfectly match: https://github.com/llvm/llvm-project/issues/54964 https://github.com/llvm/llvm-project/issues/54964 "But then the code would be nonportable." True, but tail call optimization is inherently nonportable, since some targets fundamentally do not support tail call optimization (eg. WASM without the tail call extension).
nu11ptr 2y ago
If added to Clang then I would assume this means it got support from LLVM. If so, does this mean that Rust can now rely on tail calls in LLVM to support something like the `become` keyword?
- ori_b 2y ago
  The problem with doing it in rust is that most calls aren't tail calls, even if they look like tail calls. You need to invoke the destructors for any code path that can drop.
  - nu11ptr 2y ago
    Isn't that the purpose of `become`? I thought it was to say "this IS a tail call, error out if it is not". After that validation is done, then the compiler can drop as needed.
    - ori_b 2y ago
      The compiler can't drop as needed, because the drop prevents things from being tail calls. A single drop in a function prevents any calls from being tail calls, and therefore, they can't be eliminated. In idiomatic rust, this means very few functions can use become.
iTokio 2y ago
The remaining issue with tail calls used to switch context, is that you’re using functions that must use a calling convention. And unfortunately they waste registers to restore state on function exit. See the luajit remake blog for an exhaustive analysis and alternative using an intermediate compiler https://sillycross.github.io/2022/11/22/2022-11-22/ https://sillycross.github.io/2022/11/22/2022-11-22/
- superdimwit 2y ago
  Clang recently got a new calling convention that makes these tail calls much cheaper (avoids the need for the caller to preserve some registers). I can never remember the name - it’s either preserve_all or preserve_none (whose perspective is the preservation from?).
  - haberman 2y ago
    preserve_none is the new one. It can be applied to the functions performing tail calls to allow them use of the full register space. I even saw an enhancement recently that will make preserve_none allocate arguments in the registers that are usually callee-saved: https://github.com/llvm/llvm-project/pull/88333 https://github.com/llvm/llvm-project/pull/88333 This will make [[musttail]] + preserve_none a winning combination when used together, particularly when making non-tail calls to fallback functions that use a regular calling convention, because all the arguments to [[musttail]] functions can stay pinned in the callee-save registers. I'm delighted, because this matches what I originally proposed back in 2021, except I called it "reverse_ccc" instead of "preserve_none": https://github.com/haberman/llvm-project/commit/e8d9c75bb35ce9c802f8eac522a2c6ce003f857f https://github.com/haberman/llvm-project/commit/e8d9c75bb35c... preserve_all also exists, and has existed for a while. You could use it on fallback functions to help the tail calling functions avoid spilling. But this always seemed like an unsatisfactory solution to me, because it's too intrusive (and requires too much diligence) to tag a bunch of regular functions as preserve_all. It's much more practical to tag all the core interpreter functions as preserve_none.
    - superdimwit 2y ago
beyondCritics 2y ago
With gcc [1] and clang [2] you always had the option "-foptimize-sibling-calls", to get away with tail calls even for debug builds. Of course having this standardized, guaranteed and at the function level is a huge improvement. [1] https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html [2] https://clang.llvm.org/docs/ClangCommandLineReference.html#target-independent-compilation-options https://clang.llvm.org/docs/ClangCommandLineReference.html#t...
chmaynard 2y ago
See also: https://news.ycombinator.com/item?id=26931581 https://news.ycombinator.com/item?id=26931581
crabbone 2y ago
I wrote C Protobuf decoder / encoder as well as IML parser and bindings for Python. Here's something I have to say about measuring parsing speed. * Since this library is only offered as a binding to some managed languages there are some extra caveats that, in term of performance overshadow everything else. I cannot speak to Ruby or PHP, but with Python I saw a dramatic speed increase when not using enumerators. I.e. if you translate Protobuf's enumerators into Python's enumerators any possible gains you may have in your C code will be trampled by creation times of different Python objects. The difference is many orders of magnitude. Similarly, you could go even further and implement all the supporting data-structures in C, and only expose minimal interface to them in Python. How fair would this sort of comparison be against code that uses Python's built-in structures is the question I cannot answer. * Google's Protobuf parser for Python would be still "faster" than 2+GB/s because... it doesn't parse anything beside the top-level message. The internal structure of the message is parsed on-demand. This will be probably slower than 2+GB/s if your code instantly reads everything that was parsed, but the obvious question would be: how can you possibly compare these two approaches in practical terms? And, again, there isn't a clear answer, because the practical results will depend on the nature of your application. * In general case, Protobuf parsing cannot be streamed (because of the handling of duplicates). This means, that, in practice, code that parses Protobuf content will be bottlenecked on I/O (it needs to wait for the end of the message before any parsing starts). Independently, depending on the typical Probobuf message in your application, it might be possible to parallelize parsing, which, again, will most likely outrun any single-threaded parser, but, just as examples above, cannot be said to be a winning strategy in general. * It's usually a lot more efficient to combine parsing with creation of domain objects, which is a step an application will almost always have to take anyways. How this functionality is accessible from the parser will in many cases determine which parser will win the race. ---- Bottom line: Protobuf (or maybe parser in general) is just a bad candidate to try to measure / compare speeds. It's too low-level and poorly designed to be a good measuring stick for performance benchmarks.
- jeffbee 2y ago
  > In general case, Protobuf parsing cannot be streamed (because of the handling of duplicates) I don't see how last field wins stops you from streaming parse. Please elaborate.
pizlonator 2y ago
The way interpreters usually achieve this kind of speedup in C++ is using computed goto. Then there’s no calling convention junk on the path from one opcode to the next. Also, the main reason why interpreters get faster using either the computed goto style or the tail style versus a classic switch loop is that it reduces pressure on the branch predictor since there’s statically one indirect branch per opcode rather than statically just one indirect branch.
- tylerhou 2y ago
  (As the article claims) even with computed goto register assignment of the most frequently used variables is fragile because the CFG of the function is so complicated. Register assignment is much less fragile when each function is small and takes the most important variables by argument.
  - pizlonator 2y ago
    It's also fragile, in a different way, if you're threading state through tail calls. In my experience writing computed goto interpreters, this isn't a problem unless you have more state than what can be stored in registers. But then you'd also have that same problem with tail calls.
    - haberman 2y ago
      Fallback paths most definitely have more state than what can be stored in registers. Fallback paths will do things like allocate memory, initialize new objects, perform complicated fallback logic, etc. These fallback paths will inevitably spill the core interpreter state. The goal is for fast paths to avoid spilling core interpreter state. But the compiler empirically has a difficult time doing this when the CFG is too connected. If you give the compiler an op at a time, each in its own function, it generally does much better.
      - pizlonator 2y ago
        I get that and that’s also been my experience, just not for interpreters. In interpreters, my experience is that fallback paths are well behaved if you just make them noinline and then ensure that the amount of interpreter state is small enough to fit in callee save regs.
nly 2y ago
perhaps the always_inline attribute could be useful to encourage the compiler to do the right thing also.
highfrequency 2y ago
Could someone clarify the example where an unlikely fallback path is wrapped in a musttail? My understanding is that musttail is useful because it prevents stack frame construction and register spilling; the calling function basically says "you can re-use the existing stack and not worry about my local variables." But doesn't the stack frame construction overhead / register spilling only occur when the fallback path is actually invoked; therefore if it is unlikely and you care less about performance in this slow path it doesn't matter if you wrap the fallback path in musttail? (Is this purely a branch prediction effect, where the possibility of extra work needing to be done slows down the fast path even when the work does not need to be done?)
- fweimer 2y ago
  If the fallback path can be invoked repeatedly for one message (depending on message size), the tail call is a correctness issue because your stack is probably not going to be large enough to keep all the fallback path frames.
mbStavola 2y ago
For Rust enthusiasts, there is an old RFC[0] that would have added a "become" keyword which guaranteed tco. It was originally postponed in favor of focusing on the 2018 edition's goals (which was the right call) but the initiative has been revisited recently[1]. Maybe it'll make a comeback! [0]: https://github.com/rust-lang/rfcs/pull/1888 https://github.com/rust-lang/rfcs/pull/1888 [1]: https://github.com/rust-lang/rfcs/pull/3407 https://github.com/rust-lang/rfcs/pull/3407
MathMonkeyMan 2y ago
One of the compilation passes in a Scheme compiler (e.g. Guile or Racket) is conversion to continuation passing style. Here the author applies the pass manually as a code design decision, because later passes of the compiler (i.e. the actual C compiler) produce better code given that input. It's neat.
aidenn0 2y ago
It mentions C++ support; it would seem to me that C++ has very few tail-calls. Consider: foo() { auto a = SomeClassWithADestructor(); return bar(); // This is not a tail-call because the destruction of a happens *after* the call to bar(); }
- mxz3000 2y ago
  If the compiler can prove there isn't action-at-a-distance between those lines (this might be non-trivial), then can't the destructor be called before running bar ? Does the C++ spec necessarily say that destructors are called at the end of the block, compared to, let's say, as soon as the variable is no longer used?
  - aidenn0 2y ago
    > If the compiler can prove there isn't action-at-a-distance between those lines (this might be non-trivial), then can't the destructor be called before running bar? Yes; there is an "as-if" rule in the C++ standard that says that the implementation must emulate only the "observable behavior" of the abstract machine defined by the standard. The observable behavior is: access through volatile lvalues, data written to files, and I/O to interactive devices. Does the C++ spec necessarily say that destructors are called at the end of the block, compared to, let's say, as soon as the variable is no longer used? Yes, as long as the destructor has any side effect: > If a variable with automatic storage duration has initialization or a destructor with side effects, an implementation shall not destroy it before the end of its block nor eliminate it as an optimization, even if it appears to be unused, except that a class object or its copy/move may be eliminated as specified in 11.10 [1]. Other wise things like std::lock_guard[2] would not work; that's an example of a type that is never explicitly used after definition, but used purely for the side-effects of its constructor/destructor. 1: https://isocpp.org/files/papers/N4860.pdf https://isocpp.org/files/papers/N4860.pdf 2: https://en.cppreference.com/w/cpp/thread/lock_guard https://en.cppreference.com/w/cpp/thread/lock_guard
ok123456 2y ago
What happens if you throw an exception in a C++ [[musttail]] function? Is the exception stack completely separate?
- layer8 2y ago
  The musttail return is not allowed to occur within a try block, or within the scope of variables with nontrivial destructors [0]. (In particular, this means that the function parameters cannot have nontrivial destructors.) Otherwise, within a musttail-called function, it's as if the original caller directly called that function, so exceptional stack unwinding is unaffected. [0] https://www.mail-archive.com/gcc@gcc.gnu.org/msg95265.html https://www.mail-archive.com/gcc@gcc.gnu.org/msg95265.html
kasajian 2y ago
They can do it in C, but Google still can't do it in JS in V8 :eyeroll:
turbolent 2y ago
GCC just got musttail too: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83324#c27 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83324#c27

366 points by fanf2 2y ago

deleted 2y ago

[deleted]

> I very much hope that the attribute will catch on, spreading to GCC, Visual C++, and other popular compilers, AFAIK, attribute musttail is in the process of being added to GCC (the patch is under review) with semantics compatible with clang.

ufo 2y ago
What about the preserve_most attribute? Is there any chance something like that will get into GCC? Without it, the non-tail calls ruin the interpreter.
- gpderetta 2y ago
  Maybe, but not there yet: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110899 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=110899 In the meantime some inline assembly macro trickery might help. edit: code duplication can also be obviated by templating your op function with a fast/slow parameter, with the fast variant tail-calling the slow variant when it cannot perform the fast path, while guarding the slow code via the compile time parameter. The downside is yet more code obfuscation of course.
katzinsky 2y ago
Given some of the other scheme-like features GNUC has it's surprising they're lagging on this one.
fweimer 2y ago
It's a hard problem because many ABIs cannot do tail calls even for very basic stuff, like calls to extern functions with matching argument and return types. It looks like Clang has some heuristics for changing call sequences for musttail calls. For example, it switches to noplt calls on i686. None of this is mentioned in the Clang documentation: https://clang.llvm.org/docs/AttributeReference.html#musttail https://clang.llvm.org/docs/AttributeReference.html#musttail What's realistic here is that you get a diagnostic if the compiler cannot generate a tail call. For many users, that will likely be good enough. Guaranteeing a tail call as in Scheme is unlikely to happen.

irdc 2y ago

I wonder how fast this would be when using a trampoline, i.e. returning the next function as a function pointer and calling that from an outer loop. That would have the advantage of being portable C.

chii 2y ago
the reason i suspect tail call optimization is fast would be because the resultant loop is predictable and thus CPU instruction prefetch and memory prefetch works very well. Jumping via function pointers would probably not be as predictable, and you'd unlikely to see the same benefit. Of course, one must measure, and i haven't.
- gpderetta 2y ago
  The tail call interpreter is also calling through a function pointer. The cost here is purely the call+ret overhead, which can be non-trivial when it is per opcode; on some micro-architectures there is also a limit on taken jumps per cycle (sometimes as low as one taken jump every other cycle). edit: trampolining would also collapse all indirect jumps to a single source address which is not ideal for branch prediction.
soegaard 2y ago
C is often used as target language for compiler from higher level languages. The Scheme programming language requires all tail calls not to grow the stack. Therefore implementors have explored various techniques including trampolines. I don't have a citation, but you can find the answer in the papers on compiling Scheme to C. If there is no guarantee of TCO in the target language, then the generated programs will be slower. Incidentally, this is why implementors of (especially) high level languages are annoyed that TCO was removed from the JavaScript specification. There are even solution for having TCO and still have stack inspection. https://github.com/schemedoc/bibliography/blob/master/page8.md https://github.com/schemedoc/bibliography/blob/master/page8....

TechMaverick 2y ago

[flagged]

barrkel 2y ago
New account, banal observation, invitation to interact. It's a pattern I've seen recently on what are apparently LLM-powered engagement bots on Twitter.
- deleted 2y ago
  [deleted]
- kachapopopow 2y ago
  New fear unlocked.
  - david_allison 2y ago
    Your fear is reality: https://replyguy.com/ https://replyguy.com/
- nequo 2y ago
  What are those engagement bots for? Are they farming followers and turn into disinformation machines later? Or is that only to drive engagement to cultivate ad revenue for Twitter, or for some “brand” that is adjacent to their topic?
  - twoodfin 2y ago
    The way hn karma works, you’re incentivized to accumulate a set of bots that meet the threshold for flagging and downvoting. Barring effective anti-bot/brigading measures (some of which I’m sure exist), such a team of bots could manipulate front page content. That’s a valuable capability for a variety of nefarious aims in this space. A straightforward one would be either subtly or dramatically tilting sentiment here negative against some mid-cap public tech company and profiting from a short position. (Assuming you think investors care what gets upvoted on hn…)

stabbles 2y ago

Maybe the example is too simple, but it does not require `__attribute__((musttail))` for good code gen. Also if the error handling function is unlikely, you wouldn't care too much about how fast it is to call it? To me it seems like a structure of the form <read data> if (unlikely(malformed)) return error(); <prep more stuff> switch (data_type) { case x: return handle_x(); case y: return handle_y(); } generates a nice jump table quite reliably.

OskarS 2y ago
Obviously compilers have been doing tail call elimination for ever, but for this trick "generates [tail calls] quite reliably" is not enough: you have to GUARANTEE it (or fail compilation), otherwise this structure does not work (it will blow the stack immediately). That's the point of [[musttail]], tail call elimination is required, that's the only choice the compiler has.
- stkdump 2y ago
  That means that any such code is not portable across compilers anymore. It is effectively written in a non-standard C dialect, because it requires a language extension to work correctly.
  - ufo 2y ago
    Yes. But the alternative is assembly language, which is even less portable.
    - kachapopopow 2y ago
      assembly is the most portable of them all even across platforms! (x86 to arm compilation meme)
    - Karliss 2y ago
      The portable alternative is being explicit with your loops, possibly in combination with gigantic unwieldy switch statements or some regular goto (it is still part of standard). But that comes at the cost of readability and sometimes performance.Whether it's practical depends on the usecase. For something like recursive data structure algorithms which are relatively small and self contained, I would say it's perfectly doable. Simple interpreters - maybe. Complex interpreters - here it becomes messy.

PaulRobinson 2y ago

Perhaps I've just been looking more (because I've been going back to the books to pick up C again after a 20 year absence for a side project), but it feels like in recent years there has been a little uptick in people appreciating the level of control C provides, and "going back to basics". I think the work on C23 (which would have still been C2x when this article was written), means people are starting to want to see innovation in the language again. I don't think that would have happened without Go and Rust showing some great thinking, but it's interesting that it's happening at all. Tail calls are an interesting idea, and now I want to know more about both this extension, and also how to write my code in such a way as to help a compiler optimize for tail calls even when this extension isn't present. This somehow feels more fun to me than writing more Python or Ruby...

38 2y ago
[flagged]
- verandaguy 2y ago
  C is not a dead language to literally millions of other programmers and the billions of ongoing practical applications of it. If your threshold for a language's alive-ness is the presence or absence of a package manager, you should reevaluate.
- creata 2y ago
  1. I don't think the presence of centralized package management makes or breaks a language for most people. 2. Your platform's package manager should have plenty of C packages.
  - lwansbrough 2y ago
    I think the success of Javascript and Rust certainly tests your biases. I can say anecdotally that the lack of a standard package manager in C and C++ kept me from exploring those languages.
    - 2y ago

sp1rit 2y ago

I wonder how this behaves in combination with __attribute__((cleanup(...))). Especially if the to be cleaned variable is passed into the tail function as parameter.

Karliss 2y ago
You get an error that tail call can't be performed which is kind of the point of tailcall attribute. Same thing with regular c++ destructors or dozen other language features which interfere with tail calls, no need for extensions like __attribute__((cleanup()). https://godbolt.org/z/Yex74Wjz7 https://godbolt.org/z/Yex74Wjz7

fuhsnn 2y ago

A C standard proposal exists for tail call [0], in the form of "return goto (expression);". What I like about it, over standardizing [[musttail]], is that lifetimes of local objects are guaranteed to end. This makes it possible to implement without extensive escape analysis. [0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5-tail-call-elimination https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3266.htm#5...

nxobject 2y ago
As an aside, I’m excited - but also with lots of trepidation - about the new energy in adding new functionality to C. Excited because there are changes and additions that are crying to be made, even clarifying ideas… trepidation because C++’s gung ho update cadence has somehow ended up in wart patched over wart. Especially when feature reacts with feature in an unfelicitous way far earlier than anticipated. I hope the standards process finds a way to be very conservative, really thoroughly test features in large and diverse codebases, rather than just relying on rationales alone, when choosing to include feature.
- pjmlp 2y ago
  What new energy? We have had C89, C99, C11, C17, C23 And yet, no fix in sight for proper strings, arrays, or at very least bounds checked slices, like Dennis Ritchie originally proposed to ANSI/ISO.
haberman 2y ago
Thanks for the pointer, I'll have to check this out. Can you elaborate on how "return goto" is easier to implement? [[musttail]] also ends the lifetime of local objects AFAICS. One thing I'll mention from a quick scan: > [The] function called in tail position must have identical type to the callee. This ensures both that the return value does not require any conversion, and also that argument passing space is available and calling convention (if relevant) is maintained. One complaint I've seen repeatedly about [[musttail]] (which I implemented in Clang) is that this constraint is unnecessarily strict, since some architectures will allow tail calls even for functions that do not perfectly match: https://github.com/llvm/llvm-project/issues/54964 https://github.com/llvm/llvm-project/issues/54964 "But then the code would be nonportable." True, but tail call optimization is inherently nonportable, since some targets fundamentally do not support tail call optimization (eg. WASM without the tail call extension).

nu11ptr 2y ago

If added to Clang then I would assume this means it got support from LLVM. If so, does this mean that Rust can now rely on tail calls in LLVM to support something like the `become` keyword?

ori_b 2y ago
The problem with doing it in rust is that most calls aren't tail calls, even if they look like tail calls. You need to invoke the destructors for any code path that can drop.
- nu11ptr 2y ago
  Isn't that the purpose of `become`? I thought it was to say "this IS a tail call, error out if it is not". After that validation is done, then the compiler can drop as needed.
  - ori_b 2y ago
    The compiler can't drop as needed, because the drop prevents things from being tail calls. A single drop in a function prevents any calls from being tail calls, and therefore, they can't be eliminated. In idiomatic rust, this means very few functions can use become.

iTokio 2y ago

The remaining issue with tail calls used to switch context, is that you’re using functions that must use a calling convention. And unfortunately they waste registers to restore state on function exit. See the luajit remake blog for an exhaustive analysis and alternative using an intermediate compiler https://sillycross.github.io/2022/11/22/2022-11-22/ https://sillycross.github.io/2022/11/22/2022-11-22/

superdimwit 2y ago
Clang recently got a new calling convention that makes these tail calls much cheaper (avoids the need for the caller to preserve some registers). I can never remember the name - it’s either preserve_all or preserve_none (whose perspective is the preservation from?).
- haberman 2y ago
  preserve_none is the new one. It can be applied to the functions performing tail calls to allow them use of the full register space. I even saw an enhancement recently that will make preserve_none allocate arguments in the registers that are usually callee-saved: https://github.com/llvm/llvm-project/pull/88333 https://github.com/llvm/llvm-project/pull/88333 This will make [[musttail]] + preserve_none a winning combination when used together, particularly when making non-tail calls to fallback functions that use a regular calling convention, because all the arguments to [[musttail]] functions can stay pinned in the callee-save registers. I'm delighted, because this matches what I originally proposed back in 2021, except I called it "reverse_ccc" instead of "preserve_none": https://github.com/haberman/llvm-project/commit/e8d9c75bb35ce9c802f8eac522a2c6ce003f857f https://github.com/haberman/llvm-project/commit/e8d9c75bb35c... preserve_all also exists, and has existed for a while. You could use it on fallback functions to help the tail calling functions avoid spilling. But this always seemed like an unsatisfactory solution to me, because it's too intrusive (and requires too much diligence) to tag a bunch of regular functions as preserve_all. It's much more practical to tag all the core interpreter functions as preserve_none.
  - superdimwit 2y ago

beyondCritics 2y ago

With gcc [1] and clang [2] you always had the option "-foptimize-sibling-calls", to get away with tail calls even for debug builds. Of course having this standardized, guaranteed and at the function level is a huge improvement. [1] https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html [2] https://clang.llvm.org/docs/ClangCommandLineReference.html#target-independent-compilation-options https://clang.llvm.org/docs/ClangCommandLineReference.html#t...

chmaynard 2y ago

See also: https://news.ycombinator.com/item?id=26931581 https://news.ycombinator.com/item?id=26931581

crabbone 2y ago

I wrote C Protobuf decoder / encoder as well as IML parser and bindings for Python. Here's something I have to say about measuring parsing speed. * Since this library is only offered as a binding to some managed languages there are some extra caveats that, in term of performance overshadow everything else. I cannot speak to Ruby or PHP, but with Python I saw a dramatic speed increase when not using enumerators. I.e. if you translate Protobuf's enumerators into Python's enumerators any possible gains you may have in your C code will be trampled by creation times of different Python objects. The difference is many orders of magnitude. Similarly, you could go even further and implement all the supporting data-structures in C, and only expose minimal interface to them in Python. How fair would this sort of comparison be against code that uses Python's built-in structures is the question I cannot answer. * Google's Protobuf parser for Python would be still "faster" than 2+GB/s because... it doesn't parse anything beside the top-level message. The internal structure of the message is parsed on-demand. This will be probably slower than 2+GB/s if your code instantly reads everything that was parsed, but the obvious question would be: how can you possibly compare these two approaches in practical terms? And, again, there isn't a clear answer, because the practical results will depend on the nature of your application. * In general case, Protobuf parsing cannot be streamed (because of the handling of duplicates). This means, that, in practice, code that parses Protobuf content will be bottlenecked on I/O (it needs to wait for the end of the message before any parsing starts). Independently, depending on the typical Probobuf message in your application, it might be possible to parallelize parsing, which, again, will most likely outrun any single-threaded parser, but, just as examples above, cannot be said to be a winning strategy in general. * It's usually a lot more efficient to combine parsing with creation of domain objects, which is a step an application will almost always have to take anyways. How this functionality is accessible from the parser will in many cases determine which parser will win the race. ---- Bottom line: Protobuf (or maybe parser in general) is just a bad candidate to try to measure / compare speeds. It's too low-level and poorly designed to be a good measuring stick for performance benchmarks.

jeffbee 2y ago
> In general case, Protobuf parsing cannot be streamed (because of the handling of duplicates) I don't see how last field wins stops you from streaming parse. Please elaborate.

pizlonator 2y ago

The way interpreters usually achieve this kind of speedup in C++ is using computed goto. Then there’s no calling convention junk on the path from one opcode to the next. Also, the main reason why interpreters get faster using either the computed goto style or the tail style versus a classic switch loop is that it reduces pressure on the branch predictor since there’s statically one indirect branch per opcode rather than statically just one indirect branch.

tylerhou 2y ago
(As the article claims) even with computed goto register assignment of the most frequently used variables is fragile because the CFG of the function is so complicated. Register assignment is much less fragile when each function is small and takes the most important variables by argument.
- pizlonator 2y ago
  It's also fragile, in a different way, if you're threading state through tail calls. In my experience writing computed goto interpreters, this isn't a problem unless you have more state than what can be stored in registers. But then you'd also have that same problem with tail calls.
  - haberman 2y ago
    Fallback paths most definitely have more state than what can be stored in registers. Fallback paths will do things like allocate memory, initialize new objects, perform complicated fallback logic, etc. These fallback paths will inevitably spill the core interpreter state. The goal is for fast paths to avoid spilling core interpreter state. But the compiler empirically has a difficult time doing this when the CFG is too connected. If you give the compiler an op at a time, each in its own function, it generally does much better.
    - pizlonator 2y ago
      I get that and that’s also been my experience, just not for interpreters. In interpreters, my experience is that fallback paths are well behaved if you just make them noinline and then ensure that the amount of interpreter state is small enough to fit in callee save regs.

nly 2y ago

perhaps the always_inline attribute could be useful to encourage the compiler to do the right thing also.

highfrequency 2y ago

Could someone clarify the example where an unlikely fallback path is wrapped in a musttail? My understanding is that musttail is useful because it prevents stack frame construction and register spilling; the calling function basically says "you can re-use the existing stack and not worry about my local variables." But doesn't the stack frame construction overhead / register spilling only occur when the fallback path is actually invoked; therefore if it is unlikely and you care less about performance in this slow path it doesn't matter if you wrap the fallback path in musttail? (Is this purely a branch prediction effect, where the possibility of extra work needing to be done slows down the fast path even when the work does not need to be done?)

fweimer 2y ago
If the fallback path can be invoked repeatedly for one message (depending on message size), the tail call is a correctness issue because your stack is probably not going to be large enough to keep all the fallback path frames.

mbStavola 2y ago

For Rust enthusiasts, there is an old RFC[0] that would have added a "become" keyword which guaranteed tco. It was originally postponed in favor of focusing on the 2018 edition's goals (which was the right call) but the initiative has been revisited recently[1]. Maybe it'll make a comeback! [0]: https://github.com/rust-lang/rfcs/pull/1888 https://github.com/rust-lang/rfcs/pull/1888 [1]: https://github.com/rust-lang/rfcs/pull/3407 https://github.com/rust-lang/rfcs/pull/3407

MathMonkeyMan 2y ago

One of the compilation passes in a Scheme compiler (e.g. Guile or Racket) is conversion to continuation passing style. Here the author applies the pass manually as a code design decision, because later passes of the compiler (i.e. the actual C compiler) produce better code given that input. It's neat.

aidenn0 2y ago

It mentions C++ support; it would seem to me that C++ has very few tail-calls. Consider: foo() { auto a = SomeClassWithADestructor(); return bar(); // This is not a tail-call because the destruction of a happens *after* the call to bar(); }

mxz3000 2y ago
If the compiler can prove there isn't action-at-a-distance between those lines (this might be non-trivial), then can't the destructor be called before running bar ? Does the C++ spec necessarily say that destructors are called at the end of the block, compared to, let's say, as soon as the variable is no longer used?
- aidenn0 2y ago
  > If the compiler can prove there isn't action-at-a-distance between those lines (this might be non-trivial), then can't the destructor be called before running bar? Yes; there is an "as-if" rule in the C++ standard that says that the implementation must emulate only the "observable behavior" of the abstract machine defined by the standard. The observable behavior is: access through volatile lvalues, data written to files, and I/O to interactive devices. Does the C++ spec necessarily say that destructors are called at the end of the block, compared to, let's say, as soon as the variable is no longer used? Yes, as long as the destructor has any side effect: > If a variable with automatic storage duration has initialization or a destructor with side effects, an implementation shall not destroy it before the end of its block nor eliminate it as an optimization, even if it appears to be unused, except that a class object or its copy/move may be eliminated as specified in 11.10 [1]. Other wise things like std::lock_guard[2] would not work; that's an example of a type that is never explicitly used after definition, but used purely for the side-effects of its constructor/destructor. 1: https://isocpp.org/files/papers/N4860.pdf https://isocpp.org/files/papers/N4860.pdf 2: https://en.cppreference.com/w/cpp/thread/lock_guard https://en.cppreference.com/w/cpp/thread/lock_guard

ok123456 2y ago

What happens if you throw an exception in a C++ [[musttail]] function? Is the exception stack completely separate?

layer8 2y ago
The musttail return is not allowed to occur within a try block, or within the scope of variables with nontrivial destructors [0]. (In particular, this means that the function parameters cannot have nontrivial destructors.) Otherwise, within a musttail-called function, it's as if the original caller directly called that function, so exceptional stack unwinding is unaffected. [0] https://www.mail-archive.com/gcc@gcc.gnu.org/msg95265.html https://www.mail-archive.com/gcc@gcc.gnu.org/msg95265.html

kasajian 2y ago

They can do it in C, but Google still can't do it in JS in V8 :eyeroll:

turbolent 2y ago

GCC just got musttail too: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83324#c27 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83324#c27