parsica-php / parsica

Parsica - PHP Parser Combinators - The easiest way to build robust parsers.
https://parsica-php.github.io/
MIT License
405 stars 18 forks source link

JSON string parsing speed improvements #25

Closed ToonGagor closed 3 years ago

ToonGagor commented 3 years ago

While testing some things in the JSON parser benchmarks when writing this, i found these:

⚡️ Write character parsers instead of string parsers

Since we're looking for a backslash, followed by a character from a list of special escaped characters, we can make this a simpler parse than looking for the explicit combinations as strings. This makes us backtrack less.

This results in a x3 speed improvement for parsing strings.

⚡️ Using takeWhile(f) is faster than zeroOrMore(satisfy(f)) combo

Because it doesn't have to run the parser completely, every time. It can just rely on the stream implementation. This results in a ± x1.25 speed improvement according to some benchmarks I did.

⚡️ Accept any character in JSON Strings instead of the special ones first

Instead of looking for special characters first, and backtracking if we don't find them, look for the accepted ones first, and parse the special ones only if that fails.

This results in a x1.35 speed improvement in the benchmarks I did.

ToonGagor commented 3 years ago
Screenshot 2021-01-02 at 16 44 22

screenshot of the benchmark, before changes, and after changes (with the "alotoftext" entry added to the benchmark for both runs)

ToonGagor commented 3 years ago

These are new benchmark results:

Screenshot 2021-01-03 at 11 34 41