Optimize hot code paths

[jviide]

This pull request aims to optimize some hot code paths of esquery. These changes include the things we encountered with @marvinhagemeister, who outlined them in the excellent article Speeding up the JavaScript ecosystem - eslint, plus some additional ones added after the post was published.

The specific changes are as follows:

• Create matcher functions for each selector on-the-fly. Cache them in selector._match. In and of itself this doesn't have any performance impact, but helps in the next step.
• Hoist constants. For example getPath often ends up used a lot, and each invocation of getPath(node, selector.name) split selector.name. As each selector's name stays constant we could split each name once and reuse the result.
• Use basic for loops to iterate arrays instead of for-of loops. The transpiled for-of loops can be costly as they generate some intermediate objects (please refer to the blog article for further information).
• Modify nthChild to check a node is its parent's nth child directly instead of looking it up with .indexOf. This way the check's time complexity becomes constant (O(1)) instead of linear (O(number of siblings)).
• Avoid an intermediate array in :has selectors, traverse the AST tree only once as traversal has some overhead, and lastly bail out early with this.break() if a match is encountered.
• Avoid creation of intermediate array slices in inPath.

We microbenchmarked the effect of each of these changes, but to get a better of their real life impact I tested the eslint-plugin-unicorn ESLint plugin on the codebase at my workplace. The plugin relies heavily on selectors. Linting times were as follows:

• Before enabling eslint-plugin-unicorn: 14s (TypeScript codebase with type-aware linting rules enabled, and esquery optimizations didn't have any real impact here)
• After enabling eslint-plugin-unicorn's recommended config without these optimizations: 23s
• After enabling eslint-plugin-unicorn's recommended config with these optimizations: 18s

Cumulatively these optimizations cut down the overhead added by eslint-plugin-unicorn by more than 50%, at least in our setup. The biggest bang for the buck came from hoisting constants (2s reduction) and avoiding for-of transpilation (2s reduction).

The changes pass the tests and should be fully backwards compatible.

[floroz]

This pull request aims to optimize some hot code paths of esquery. These changes include the things we encountered with @marvinhagemeister, who outlined them in the excellent article Speeding up the JavaScript ecosystem - eslint, plus some additional ones added after the post was published.

really impressive investigation and great article 👏

[gajus]

@michaelficarra Is it possible to merge and release these changes?

[michaelficarra]

@gajus Thanks for the ping.

[gajus]

Thank you all ❤️

[michaelficarra]

@jviide I pushed some additional tweaks. Can you review and confirm that the performance has not regressed for you? After that, this should be good to go.

[jviide]

@michaelficarra Looks good, there were no performance regressions in my environment.

[jviide]

@michaelficarra A side note about the tests: On Node 18 the tests also failed for me (like they seem to be failing in the CI), until I changed the mocha --require chai/register-assert part in package.json to mocha --require chai/register-assert.js. Don't really know why.

[michaelficarra]

@jviide It seems to work when I remove the ^ from the dependency's semver spec, so we'll just do that. I guess they made a breaking change. Thanks for the pointer though.

[jviide]

Awesome, thank you for the review and the merge 🙂

[michaelficarra]

Published 1.4.1.