4 ms·

This is an exceptionally great article, which indeed discusses strong Rust limitations. I have one question: the parser in the article uses computed goto, whic

This is an exceptionally great article, which indeed discusses strong Rust limitations. I have one question: the parser in the article uses computed goto, which, as far as I know, is not standard C. Are there many cases where even the standard goto yields significantly better performance?

ncmncm 6y ago
This is an exceptionally bad article, packed to the brim with unambiguous falsehoods. It is very unlikely that the computed gotos make the parser faster than using standard features of a more powerful language.
- alok-g 6y ago
  >> It is very unlikely that the computed gotos make the parser faster than using standard features of a more powerful language. Can you explain more on how? Use case I have in mind is bytecode interpretation where computed goto should be a big help.
  - ncmncm 6y ago
    Optimized tail calls are effectively the same as computed goto, but are a Standard feature. Or, rather, don't require non-standard syntax. A program that relies on the optimization built by a compiler that failed to implement it--which is allowed--would not be expected to run well. https://github.com/ncm/computed-goto https://github.com/ncm/computed-goto The "more powerful language" part is to get language-level tools to compose parser combinators, ultimately resolving down to tail calls.
    - krizhanovsky 6y ago
      The benchmarks https://github.com/ncm/computed-goto/blob/master/benchmarks/trivial.cpp https://github.com/ncm/computed-goto/blob/master/benchmarks/... benchmark is not applicable to this discussion because it compares _too_ small state machines. I reference my talk and presentation once more: http://www.tempesta-tech.com/research/http_str.pdf http://www.tempesta-tech.com/research/http_str.pdf - slide 23 discusses that the goto FSM makes sense for _hundreds_ of states.
      - ncmncm 6y ago
        The number of states is irrelevant. An optimized tail call is achieved with, exactly, a single branch instruction.
krizhanovsky 6y ago
Thank you, I'm glad that you enjoyed the article! Regarding computed and simple goto I'd like to reference our early article discussing the parser in standard goto https://natsys-lab.blogspot.com/2014/11/the-fast-finite-state-machine-for-http.html https://natsys-lab.blogspot.com/2014/11/the-fast-finite-stat... . My recent talk at scale https://www.socallinuxexpo.org/scale/17x/presentations/fast-http-string-processing-algorithms https://www.socallinuxexpo.org/scale/17x/presentations/fast-... (watch videohttps://www.youtube.com/watch?v=LQc4er8ng64&feature=youtu.be&t=25501 https://www.youtube.com/watch?v=LQc4er8ng64&feature=youtu.be... and slides at http://www.tempesta-tech.com/research/http_str.pdf http://www.tempesta-tech.com/research/http_str.pdf ) discusses the parser with the compiler extensions. We also found hat Ragel parser generator (using the goto state machine) generated somewhat faster large state machines than Bison (switch-drived state machine). However, as pointed out in the SCALE talk goto works better only on big enough state machines.

ncmncm 6y ago

This is an exceptionally bad article, packed to the brim with unambiguous falsehoods. It is very unlikely that the computed gotos make the parser faster than using standard features of a more powerful language.

alok-g 6y ago
>> It is very unlikely that the computed gotos make the parser faster than using standard features of a more powerful language. Can you explain more on how? Use case I have in mind is bytecode interpretation where computed goto should be a big help.
- ncmncm 6y ago
  Optimized tail calls are effectively the same as computed goto, but are a Standard feature. Or, rather, don't require non-standard syntax. A program that relies on the optimization built by a compiler that failed to implement it--which is allowed--would not be expected to run well. https://github.com/ncm/computed-goto https://github.com/ncm/computed-goto The "more powerful language" part is to get language-level tools to compose parser combinators, ultimately resolving down to tail calls.
  - krizhanovsky 6y ago
    The benchmarks https://github.com/ncm/computed-goto/blob/master/benchmarks/trivial.cpp https://github.com/ncm/computed-goto/blob/master/benchmarks/... benchmark is not applicable to this discussion because it compares _too_ small state machines. I reference my talk and presentation once more: http://www.tempesta-tech.com/research/http_str.pdf http://www.tempesta-tech.com/research/http_str.pdf - slide 23 discusses that the goto FSM makes sense for _hundreds_ of states.
    - ncmncm 6y ago
      The number of states is irrelevant. An optimized tail call is achieved with, exactly, a single branch instruction.

krizhanovsky 6y ago

Thank you, I'm glad that you enjoyed the article! Regarding computed and simple goto I'd like to reference our early article discussing the parser in standard goto https://natsys-lab.blogspot.com/2014/11/the-fast-finite-state-machine-for-http.html https://natsys-lab.blogspot.com/2014/11/the-fast-finite-stat... . My recent talk at scale https://www.socallinuxexpo.org/scale/17x/presentations/fast-http-string-processing-algorithms https://www.socallinuxexpo.org/scale/17x/presentations/fast-... (watch videohttps://www.youtube.com/watch?v=LQc4er8ng64&feature=youtu.be&t=25501 https://www.youtube.com/watch?v=LQc4er8ng64&feature=youtu.be... and slides at http://www.tempesta-tech.com/research/http_str.pdf http://www.tempesta-tech.com/research/http_str.pdf ) discusses the parser with the compiler extensions. We also found hat Ragel parser generator (using the goto state machine) generated somewhat faster large state machines than Bison (switch-drived state machine). However, as pointed out in the SCALE talk goto works better only on big enough state machines.