eslint/eslint — pull request #1213 by btmills (2014-09-02 14:29:56+00:00)
Title: Fix: Speed up tokens API (refs #1212)

Rather than storing tokens in a sparse array, I was able to achieve a slight but measurable speedup by storing them in a doubly linked list with references into the linked list from the hash table. This allows token-related methods to traverse directly between tokens rather than looking for the next extant index in the hash table.

I also tried storing tokens in a non-sparse array so I could do something like `return currentTokens.slice(begin, end);`, but that actually ended up being slower than the linked list method. I still have the code in another branch if someone wants to look at it.

This did require one external change in the `space-infix-ops` rule. It was fabricating an artificial `ASTNode` to pass to `getTokens`, and in some circumstances the mock node had invalid range indices. With the change, it still creates a fake node, but it ensures that the range is valid.

I suspect there are further gains either within the tokens API or in the rules that use it, which is why the commit message `refs` rather than `fixes`. I'll keep looking and update #1212 with progress.

`npm run perf` before and after:

```
Performance Run #1: 1913.754539ms
Performance Run #2: 1905.181409ms
Performance Run #3: 1899.0104489999999ms
Performance Run #4: 1910.490959ms
Performance Run #5: 1919.422015ms
Performance budget ok: 1910.490959ms (limit: 3409.090909090909ms)
```

```
Performance Run #1: 1865.762569ms
Performance Run #2: 1850.884799ms
Performance Run #3: 1864.212372ms
Performance Run #4: 1866.0704289999999ms
Performance Run #5: 1875.189211ms
Performance budget ok: 1865.762569ms (limit: 3409.090909090909ms)
```