perf: Store indent descriptors in a plain array

[fasttime]

Prerequisites checklist

• I have read the contributing guidelines.

What is the purpose of this pull request? (put an "X" next to an item)

[ ] Documentation update
[ ] Bug fix (template)
[ ] New rule (template)
[ ] Changes an existing rule (template)
[ ] Add autofix to a rule
[ ] Add a CLI option
[ ] Add something to the core
[x] Other, please explain:

Improves performance of the indent rule. Makes the build faster.

What changes did you make? (Give an overview)

This PR changes the underlying implementation of BinarySearchTree in the indent rule to a plain array. The name BinarySearchTree is changed to IndexMap to avoid confusion now that a tree-like structure is no longer used. I also renamed a few other identifiers for clarity.

How it works

The BinarySearchTree/IndexMap class is used by the indent rule to map runtime information (descriptors) to indices in the source code. You can think of it as a mapping of integers in a known interval to arbitrary objects.
The performance of this map is determined by the time consumed by the three methods that operate on it.

• Add a mapping (insert)
• Remove all mappings in a specified index range (deleteRange)
• Search backwards for the first mapping, starting at a specified index (findLe/findLastNotAfter)

In the previous implementation, a red-black tree (provided by this package) was used to store the mappings, whereas the new implementation uses a constant-size array. With this new implementation, adding a mapping only requires setting an element of the array. Deleting a range takes a single call to the built-in method fill. Obviously, both operations are much more efficient compared to their red-black tree counterparts.
As for the backward search, it now requires iterating indices one by one until a mapping is found. The exact number of iterations depends on the length and arrangement of tokens and spaces in the source file. While this value can grow up to the number of characters in the file + 1 in the worst case, it will typically not depend on the file size, but rather on the coding style. For reference, when linting the eslint repo, the average search takes about 47 iterations, and performs still much faster than the same search with the old implementation.

Measuring performance

I run npm run lint after setting the environment variable TIMING=1, and compared the results before and after the change.

Results

I tested these changes on MacOS and Windows with different versions of Node.js, with similar results. After the changes, the indent rule runs about 40% faster than before.

Example run:

Before

Rule                                          | Time (ms) | Relative
:---------------------------------------------|----------:|--------:
indent                                        |  3228.423 |    17.8%

After

Rule                             | Time (ms) | Relative
:--------------------------------|----------:|--------:
indent                           |  1656.434 |    10.0%

Is there anything you'd like reviewers to focus on?

[netlify]

✅ Deploy Preview for docs-eslint ready!

Name	Link
🔨 Latest commit	93c0bce
🔍 Latest deploy log	https://app.netlify.com/sites/docs-eslint/deploys/64592a9e9867620008f75e8d
😎 Deploy Preview	https://deploy-preview-17148--docs-eslint.netlify.app
📱 Preview on mobile	Toggle QR Code... Use your smartphone camera to open QR code link.

---

To edit notification comments on pull requests, go to your Netlify site settings.

[aladdin-add]

LGTM. Awesome job! 👍

waiting for a few more review before merging.

[nzakas]

Wow, that's a really impressive speed up. LGTM. We'll just need to wait until after Monday to merge.

[mdjermanovic]

Great work, thanks!