eslint/eslint — pull request #1514 by btmills (2014-11-27 08:40:42+00:00)
Title: Update: refactor tokens API (refs #1212)

This is a second attempt at the changes to the tokens API that had to be reverted a while back. It's a from-scratch rewrite, without looking at any of the old code.

It splits all of the token handling out of the core and into a new `TokenStore` class. This also greatly simplifies the token-handling tests.

Rather than searching linearly through ranges until hitting upon a matching token, `TokenStore` indexes based on the start and end of every token. This greatly simplifies logic inside of the API methods and improves performance because every token is accessible directly, no searching required. Furthermore, because tokens are still stored in the original array, there's no traversal required to reconstruct a contiguous array from the sparse array that was used before; all that's required is a call to `slice`.

Now for the performance data. All of this was obtained on a MacBook Pro with a 2nd-generation i7 running OS X Yosemite. Last time there was a performance regression on at least one machine, so help testing this on a variety of configurations is appreciated.

```sh
$ git co master && npm run perf

CPU Speed is 2200 with multiplier 7500000
Performance Run #1: 1499.543745ms
Performance Run #2: 1489.026796ms
Performance Run #3: 1489.335957ms
Performance Run #4: 1493.5138259999999ms
Performance Run #5: 1480.386587ms
Performance budget ok: 1489.335957ms (limit: 3409.090909090909ms)

$ git co token-store && npm run perf

CPU Speed is 2200 with multiplier 7500000
Performance Run #1: 1397.5820039999999ms
Performance Run #2: 1375.368813ms
Performance Run #3: 1379.974734ms
Performance Run #4: 1407.492416ms
Performance Run #5: 1368.602478ms
Performance budget ok: 1379.974734ms (limit: 3409.090909090909ms)
```

I created a custom config to enable only the rules that call the tokens API, and the performance difference in some of the rules between master (time 1) and this PR (time 2) is significant:

Rule | Time 1 (ms) | Time 2 (ms) | Difference |
:-----------------|------------:|------------:|-----------:|
no-extra-parens | 115.493 | 103.691 | -10% |
no-multi-spaces | 54.537 | 42.897 | -21% |
no-spaced-func | 53.051 | 24.711 | -53% |
space-in-brackets | 46.095 | 17.530 | -62% |
space-infix-ops | 27.661 | 25.098 | -9.3% |
no-empty-class | 26.492 | 14.316 | -46% |
no-div-regex | 19.175 | 17.577 | -8.3% |
brace-style | 18.792 | 19.086 | +1.5% |
semi | 17.413 | n/a | n/a |
no-regex-spaces | 15.793 | 15.156 | -4.0% |