4 ms·

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 ex

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.
  - mananaysiempre 2y ago
    See Mike Pall’s posts on the subject—the performance cost is considerable, for two reasons. First, you’re forcing the compiler to do register allocation for the whole interpreter at once, which it can virtually never do a good job of. (This is actually the more important part.) Second, given the existence of branch target buffers (and the ruinous cost of mispredicted branches), you really want the instruction dispatch to be a single indirect branch at the end of each instruction implementation, and for that standard tools are somewhere between unhelpful (you can write a macro containing switch (*insn++) { case INSN_FOO: goto impl_foo; /* ... */ } but it’s anybody’s guess whether you’re getting a single jump table for all copies of that) and actively obstructive (“tail merging” in older versions of Clang would actively destroy any attempts at copying dispatch code). Granted, sometimes things work out (new Clang versions can sometimes go “looks like you’re writing an interpreter” and turn a vanilla switch in a loop into duplicated dispatch code). Then again, sometimes they don’t, and you can’t actually know.
  - OskarS 2y ago
    Yeah, that's the way virtual machines have been written forever, some version of for instruction in instructions { switch (instruction) { case OPCODE_X: //.... case OPCODE_Y: //.... case OPCODE_Z: //.... } } This is how VMs have been written since the dawn of time (or using computed gotos, another non-standard addition to C). It has problems though, like the fact that the `switch` branch is extremely unpredictable, and that you get a massive function which is hard to optimize. This [[musttail]] trick is a huge improvement. But yeah, if you got to support compilers that don't have [[musttail]], you in essence have to have two implementations, the [[musttail]] one and the loop/switch one.
  - ufo 2y ago
    A switch-case is the default way to write an interpreter and I'd even argue it's the most readable. In the context of this article, it's all about the performance. Switch-case generates suboptimal code for the commonly used fast paths of the protobuf parser, because the mere existence of the slow paths is enough to interfere with the performance of the code around them.
OskarS 2y ago
Yes, that is correct. You cannot do this trick in standard C, C++ or Rust, it requires some version of [[musttail]]. Strong argument for adding it to the C standard, IMHO.
dist1ll 2y ago
Fwiw, many C projects are written in a non-standard C dialect, including the Linux kernel.
flohofwoe 2y ago
The typical way to deal with this is to put the __attribute__ into a C macro which expands to nothing on compilers which don't understand GCC/Clang's __attribute__ keyword. The code without the attribute will still compile and most likely also apply the tail call optimization, you just don't get an error if the compiler can't apply the optimization. Also TBF, hardly any real-world C code is strictly standard compliant. Many C compilers just agree on a common syntax that includes both the C standard and some popular non-standard extensions. PS: C++ compilers actually ignore unknown attributes since the `[[attribute]]` syntax has been standardized in C++11. In GCC and Clang you'll get a warning in the standard warning set, but not in MSVC. PPS: C23 also standardized the `[[attribute]]` syntax and also added a way to check for supported attributes: https://en.cppreference.com/w/c/language/attributes https://en.cppreference.com/w/c/language/attributes
- pjmlp 2y ago
  It will compile, and eventually blow up nicely with a stack overflow OS fault. Ah, the joys of writing "portable" C code with #ifdef spaghetti, across commercial UNIXes and their own C compilers, 20 years ago. It only got better because for many people just like they assume Web == Chrome, C gets C == GCC, blessifully ignoring everything else. Nowadays clang is also considered, mostly because a couple of companies wanted to replace GCC, and naturally clang needs to be able to match whatever GCC offers.
  - Filligree 2y ago
    > It will compile, and eventually blow up nicely with a stack overflow OS fault. Not at all guaranteed. Stack overflow is undefined behaviour, which means compilers can optimise your program on the assumption that it doesn’t happen.
    - pjmlp 2y ago
      Ah true, yet another case that one tends to forget about.
  - flohofwoe 2y ago
taneq 2y ago
There's no such thing as "standard C" that you can actually write, due to UB and implementation defined behaviour. There's just (C, compiler version, platform) that defines (if only through the compiler's source code) what will actually happen in any given situation.
- perching_aix 2y ago
  so because there are implementation defined behaviors in the standard, language extensions become okay?
  - flohofwoe 2y ago
    Language extensions are a feature, not a bug. They allow C to evolve and C compilers to compete without requiring committee consensus. Good extensions will eventually be picked up by other compilers, and maybe even find their way into the standard.
    - perching_aix 2y ago
      sure, i get the joke, i just don't like it. it's the same story as browsers. proprietary extensions in the name of progress because technically it's allowed, but also unimplemented standardized features galore, necessitating polyfill libraries and frequent checking of support matrices. it's just sprawl with popular support.
      - gpderetta 2y ago
        It is very different. A web browser is a (almost) fully self contained environment. Same with something like JAVA. On the other hand a standard C or C++ compiler+runtime has (by design) very little features. Anything beyond trivial programs has to reach to platform specific features. Even POSIX is often not enough.
        perching_aix 2y ago
        not sure i'm following? i was referring exactly to those "few" language features, e.g.: https://en.cppreference.com/w/cpp/compiler_support https://en.cppreference.com/w/cpp/compiler_support
jonstewart 2y ago
The article is pretty clear about this. When it comes to fast lexing and parsing, it is typical for projects to make portability tradeoffs in favor of performance. For example, simdjson is full of assembly.
- stkdump 2y ago
  Portability isn't just about use of non-standard features. It is in general about the reliance on such features. In simdjson there is a fallback implementation without any assembly, making the project as a whole portable. You could do the same in a protobuf parser, but I honestly doubt that someone would implement a tail recursion optimization relying parser for a language like protobuf and then have a separate FSA implementation inside the same library as a fallback. Unless maybe both parsers are not hand-written, but generated with a parser generator maybe. Instead you would probably just say "fuck it, this parser library is not portable, period".
eru 2y ago
You say it like it's a bad thing.

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.
- mananaysiempre 2y ago
  See Mike Pall’s posts on the subject—the performance cost is considerable, for two reasons. First, you’re forcing the compiler to do register allocation for the whole interpreter at once, which it can virtually never do a good job of. (This is actually the more important part.) Second, given the existence of branch target buffers (and the ruinous cost of mispredicted branches), you really want the instruction dispatch to be a single indirect branch at the end of each instruction implementation, and for that standard tools are somewhere between unhelpful (you can write a macro containing switch (*insn++) { case INSN_FOO: goto impl_foo; /* ... */ } but it’s anybody’s guess whether you’re getting a single jump table for all copies of that) and actively obstructive (“tail merging” in older versions of Clang would actively destroy any attempts at copying dispatch code). Granted, sometimes things work out (new Clang versions can sometimes go “looks like you’re writing an interpreter” and turn a vanilla switch in a loop into duplicated dispatch code). Then again, sometimes they don’t, and you can’t actually know.
- OskarS 2y ago
  Yeah, that's the way virtual machines have been written forever, some version of for instruction in instructions { switch (instruction) { case OPCODE_X: //.... case OPCODE_Y: //.... case OPCODE_Z: //.... } } This is how VMs have been written since the dawn of time (or using computed gotos, another non-standard addition to C). It has problems though, like the fact that the `switch` branch is extremely unpredictable, and that you get a massive function which is hard to optimize. This [[musttail]] trick is a huge improvement. But yeah, if you got to support compilers that don't have [[musttail]], you in essence have to have two implementations, the [[musttail]] one and the loop/switch one.
- ufo 2y ago
  A switch-case is the default way to write an interpreter and I'd even argue it's the most readable. In the context of this article, it's all about the performance. Switch-case generates suboptimal code for the commonly used fast paths of the protobuf parser, because the mere existence of the slow paths is enough to interfere with the performance of the code around them.

OskarS 2y ago

Yes, that is correct. You cannot do this trick in standard C, C++ or Rust, it requires some version of [[musttail]]. Strong argument for adding it to the C standard, IMHO.

dist1ll 2y ago

Fwiw, many C projects are written in a non-standard C dialect, including the Linux kernel.

flohofwoe 2y ago

The typical way to deal with this is to put the __attribute__ into a C macro which expands to nothing on compilers which don't understand GCC/Clang's __attribute__ keyword. The code without the attribute will still compile and most likely also apply the tail call optimization, you just don't get an error if the compiler can't apply the optimization. Also TBF, hardly any real-world C code is strictly standard compliant. Many C compilers just agree on a common syntax that includes both the C standard and some popular non-standard extensions. PS: C++ compilers actually ignore unknown attributes since the `[[attribute]]` syntax has been standardized in C++11. In GCC and Clang you'll get a warning in the standard warning set, but not in MSVC. PPS: C23 also standardized the `[[attribute]]` syntax and also added a way to check for supported attributes: https://en.cppreference.com/w/c/language/attributes https://en.cppreference.com/w/c/language/attributes

pjmlp 2y ago
It will compile, and eventually blow up nicely with a stack overflow OS fault. Ah, the joys of writing "portable" C code with #ifdef spaghetti, across commercial UNIXes and their own C compilers, 20 years ago. It only got better because for many people just like they assume Web == Chrome, C gets C == GCC, blessifully ignoring everything else. Nowadays clang is also considered, mostly because a couple of companies wanted to replace GCC, and naturally clang needs to be able to match whatever GCC offers.
- Filligree 2y ago
  > It will compile, and eventually blow up nicely with a stack overflow OS fault. Not at all guaranteed. Stack overflow is undefined behaviour, which means compilers can optimise your program on the assumption that it doesn’t happen.
  - pjmlp 2y ago
    Ah true, yet another case that one tends to forget about.
- flohofwoe 2y ago

taneq 2y ago

There's no such thing as "standard C" that you can actually write, due to UB and implementation defined behaviour. There's just (C, compiler version, platform) that defines (if only through the compiler's source code) what will actually happen in any given situation.

perching_aix 2y ago
so because there are implementation defined behaviors in the standard, language extensions become okay?
- flohofwoe 2y ago
  Language extensions are a feature, not a bug. They allow C to evolve and C compilers to compete without requiring committee consensus. Good extensions will eventually be picked up by other compilers, and maybe even find their way into the standard.
  - perching_aix 2y ago
    sure, i get the joke, i just don't like it. it's the same story as browsers. proprietary extensions in the name of progress because technically it's allowed, but also unimplemented standardized features galore, necessitating polyfill libraries and frequent checking of support matrices. it's just sprawl with popular support.
    - gpderetta 2y ago
      It is very different. A web browser is a (almost) fully self contained environment. Same with something like JAVA. On the other hand a standard C or C++ compiler+runtime has (by design) very little features. Anything beyond trivial programs has to reach to platform specific features. Even POSIX is often not enough.
      - perching_aix 2y ago
        not sure i'm following? i was referring exactly to those "few" language features, e.g.: https://en.cppreference.com/w/cpp/compiler_support https://en.cppreference.com/w/cpp/compiler_support

jonstewart 2y ago

The article is pretty clear about this. When it comes to fast lexing and parsing, it is typical for projects to make portability tradeoffs in favor of performance. For example, simdjson is full of assembly.

stkdump 2y ago
Portability isn't just about use of non-standard features. It is in general about the reliance on such features. In simdjson there is a fallback implementation without any assembly, making the project as a whole portable. You could do the same in a protobuf parser, but I honestly doubt that someone would implement a tail recursion optimization relying parser for a language like protobuf and then have a separate FSA implementation inside the same library as a fallback. Unless maybe both parsers are not hand-written, but generated with a parser generator maybe. Instead you would probably just say "fuck it, this parser library is not portable, period".

eru 2y ago

You say it like it's a bad thing.