4 ms·

It's worth noting that Python 3 uses a PEG-based parser and its performance (when it was introduced at least) was within 10% of the old parser: https://peps.pyt

It's worth noting that Python 3 uses a PEG-based parser and its performance (when it was introduced at least) was within 10% of the old parser: https://peps.python.org/pep-0617/ https://peps.python.org/pep-0617/

kragen 2y ago
In absolute terms, the numbers given in the PEP work out to about a thousand machine instructions per byte of input, for both the old and new parsers. From my point of view, that's pretty slow. Note that this includes the time for tokenization, which is generally the bulk of the time spent in parsing, and which I believe did not change between the old recursive-descent parser and the new PEG parser. Typically the tokenizer must iterate over some 32 characters per line of input code, which it reduces to some 8 tokens for the benefit of the parser proper, so usually the tokenizer is the bottleneck. However, the performance in this case seems too poor to attribute to the tokenizer. That PEP also discusses some avoidable inefficiencies in the old parser that accounted for a substantial fraction of its runtime. One of the biggest advantages of PEGs is that you don't need a separate tokenization pass. But that means you are incurring Packrat's inefficiency per character instead of per token. As I said above, I believe the CPython implementation does not do this. I've written and worked on PEG parser generators, and I think PEG parsing is the best option in a wide variety of circumstances. But it is rarely the fastest option and usually far from it.
- pdubroy 2y ago
  Yes, you're right that PEG parsing is usually not the fastest option. As with many things, the operative question is: is it fast _enough_? > Note that this includes the time for tokenization, which is generally the bulk of the time spent in parsing Hmmm, I've never heard this before and I'm curious if you can point me to any benchmarks or other sources that demonstrate this. If it's true it's surprising to me!
  - kragen 2y ago
    I can't! But if you have a conventional lex/yacc parser handy, it should be easy to test by measuring the time for just lexing a large input file and discarding the tokens. If you do the experiment, I'm interested to hear your results! I don't believe that software is ever fast enough, but trading off speed is often worthwhile, for example to get composability or readability.
    - pdubroy 2y ago
      I found some benchmarks in the ANTLR project: https://github.com/antlr/grammars-v4/blob/master/java/java/Benchmarks.md https://github.com/antlr/grammars-v4/blob/master/java/java/B... Project Parsing/Lexing Ratio ---------------------------------------- jdk8 5.34x Spring Framework 3.81x Elasticsearch 5.76x RxJava 5.69x JUnit4 4.51x Guava 5.37x Log4j 2.92x Obviously this is just one toolkit, one language, and one set of examples. But in these benchmarks, the tokenization (lexing) time is a small fraction of the total parse time.
      - kragen 2y ago
        Thank you!
      - vanderZwan 2y ago
        Well, "small" is relative. It's certainly not a bottleneck, but it's still between 17.4% to 34.2% of the total time. That's definitely still in range where optimizing could have a measurable impact on performance difference (depending on how much room there's left for optimization). 100/2.92 = 34.2% 100/5.76 = 17.4%
        kragen 2y ago
        Right, but it's clearly not the situation I was describing where cutting the parse time to zero for the stages after the tokenization stage would only slightly decrease total time.
  - jitl 2y ago
    In my line of work (writing JavaScript that will run on Android devices) there is no such thing as fast enough. If you’re not going as fast as possible the experience is bad. After all this is a platform where getting data from the local disk is frequently slower than the network because there’s so little CPU & disk bandwidth…
    - kragen 2y ago
      Also, if you're computing for 3 milliseconds for every touchmove event instead of 0.3 milliseconds, you'll run the battery down a lot faster. Though not actually ten times faster, because the screen keeps sucking power even when the CPU is asleep.

kragen 2y ago

In absolute terms, the numbers given in the PEP work out to about a thousand machine instructions per byte of input, for both the old and new parsers. From my point of view, that's pretty slow. Note that this includes the time for tokenization, which is generally the bulk of the time spent in parsing, and which I believe did not change between the old recursive-descent parser and the new PEG parser. Typically the tokenizer must iterate over some 32 characters per line of input code, which it reduces to some 8 tokens for the benefit of the parser proper, so usually the tokenizer is the bottleneck. However, the performance in this case seems too poor to attribute to the tokenizer. That PEP also discusses some avoidable inefficiencies in the old parser that accounted for a substantial fraction of its runtime. One of the biggest advantages of PEGs is that you don't need a separate tokenization pass. But that means you are incurring Packrat's inefficiency per character instead of per token. As I said above, I believe the CPython implementation does not do this. I've written and worked on PEG parser generators, and I think PEG parsing is the best option in a wide variety of circumstances. But it is rarely the fastest option and usually far from it.

pdubroy 2y ago
Yes, you're right that PEG parsing is usually not the fastest option. As with many things, the operative question is: is it fast _enough_? > Note that this includes the time for tokenization, which is generally the bulk of the time spent in parsing Hmmm, I've never heard this before and I'm curious if you can point me to any benchmarks or other sources that demonstrate this. If it's true it's surprising to me!
- kragen 2y ago
  I can't! But if you have a conventional lex/yacc parser handy, it should be easy to test by measuring the time for just lexing a large input file and discarding the tokens. If you do the experiment, I'm interested to hear your results! I don't believe that software is ever fast enough, but trading off speed is often worthwhile, for example to get composability or readability.
  - pdubroy 2y ago
    I found some benchmarks in the ANTLR project: https://github.com/antlr/grammars-v4/blob/master/java/java/Benchmarks.md https://github.com/antlr/grammars-v4/blob/master/java/java/B... Project Parsing/Lexing Ratio ---------------------------------------- jdk8 5.34x Spring Framework 3.81x Elasticsearch 5.76x RxJava 5.69x JUnit4 4.51x Guava 5.37x Log4j 2.92x Obviously this is just one toolkit, one language, and one set of examples. But in these benchmarks, the tokenization (lexing) time is a small fraction of the total parse time.
    - kragen 2y ago
      Thank you!
    - vanderZwan 2y ago
      Well, "small" is relative. It's certainly not a bottleneck, but it's still between 17.4% to 34.2% of the total time. That's definitely still in range where optimizing could have a measurable impact on performance difference (depending on how much room there's left for optimization). 100/2.92 = 34.2% 100/5.76 = 17.4%
      - kragen 2y ago
        Right, but it's clearly not the situation I was describing where cutting the parse time to zero for the stages after the tokenization stage would only slightly decrease total time.
- jitl 2y ago
  In my line of work (writing JavaScript that will run on Android devices) there is no such thing as fast enough. If you’re not going as fast as possible the experience is bad. After all this is a platform where getting data from the local disk is frequently slower than the network because there’s so little CPU & disk bandwidth…
  - kragen 2y ago
    Also, if you're computing for 3 milliseconds for every touchmove event instead of 0.3 milliseconds, you'll run the battery down a lot faster. Though not actually ten times faster, because the screen keeps sucking power even when the CPU is asleep.