Use RegExp sticky flag for lexer performance boost.

[bd82]

Modifying the RegExp's lastIndex instead of chopping off parts of the input string repeatedly.

• POC.
• Basic flows.
• Legacy mode (IE11 & friends).
• Fix existing tests.
• Tests for legacy mode.
• Validation that start of input anchor is not used.
• 100% code coverage.
• Modify Indentation example.
• Update Custom Token Docs.
• Document breaking changes.
• Update performance benchmark safari hack custom pattern.

[bd82]

A small POC showed 8-10% improvement in an E2E (lex + parse) JSON benchmark.
So that may be as much as 20% boost for the lexer itself.
Quite amazing that 1/5 of the lexer time may have been spent chopping up strings with substr...

getting this to productive quality requires handling some issues:

• Custom Token patterns API may have to be modified.
• How to avoid explosion of Lexer variants.
• How to support this capability optionally only on newer JS engine where the sticky option is available.

[leeoniya]

avoiding string allocation in hot code via substr, substring, slice is a good perf optimization. you're also better off checking string prefixes (if needed) via array access to individual chars and plain for loops or [1].

btw, native Array.forEach loops are slow.

[1] http://stackoverflow.com/a/4579228

[bd82]

Thanks for the feedback @leeoniya

also better off checking string prefixes (if needed) via array access to individual chars

The Chevrotain Lexer is based on Regular expressions, so there is no access to individual chars.
The lexer just tries matching against the provided patterns in a loop until it find a match.

avoiding string allocation in hot code via substr, substring, slice is a good perf optimization.

I'm already using substring, The optimization I'm talking about here is to completely avoid using substring. By using the RegExp new sticky flag combined with changing the regExp lastIndex property it is possible to match from any point in the string.

Currently Chevrotain is chopping off string prefixes using substring.
So if there are 10,000 tokens, substring would have been called 10,000 times during lexing...
That is quite expensive...

btw, native Array.forEach loops are slow.

Aye, I use the good old fashioned for loops in hot spot code.
For less important (performance wise) code I use a small set of utility functions
similar to lodash/underscore style.

[leeoniya]

I'm already using substring, The optimization I'm talking about here is to completely avoid using substring.

right, i agreed that avoiding it is the right way to go. i did a similar optimization in one of my libs recently and was also surprised by how big the boost was.

[bd82]

Breaking Changes

• Custom Token patterns used to be called with three arguments.

       function matchInteger(text, matchedTokens, groups) {}

  There are now four arguments.

       function matchInteger(text, offset, matchedTokens, groups) {}

The custom match is expected to be performed beginning from the offset argument in the text.
Previously the custom match always assumed the match must be performed from the start
of the input text.

[bd82]

re-opening as a reminder to update the safari custom pattern in the performance
benchmark.

[bd82]

Final performance results showed almost 30% for a simpler JSON Lexer.
More complex lexers should show lower gains as a smaller percentage of their runtime
is spent performing substrings on the input.

[bd82]

This is only applicable to modern JS engines.
On node.js version 4 the Lexer will run in the old legacy mode without any performance benefit.
Same on IE11.

But anyone using IE11 is doomed anyways 😄

[bd82]

Safari related performance workaround was no longer needed and was removed.