Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Core API can be more efficient #1212

Closed
btmills opened this issue Sep 2, 2014 · 26 comments
Closed

Core API can be more efficient #1212

btmills opened this issue Sep 2, 2014 · 26 comments
Labels
accepted There is consensus among the team that this change meets the criteria for inclusion archived due to age This issue has been archived; please open a new issue for any further discussion core Relates to ESLint's core APIs and features enhancement This change enhances an existing feature of ESLint

Comments

@btmills
Copy link
Member

btmills commented Sep 2, 2014

There are slight but measurable performance gains to be had from refactoring how tokens are handled internally by the tokens API. Right now, tokens are indexed in a sparse array, and traversal is done (nearly) linearly based on the range index, with some intelligent skips where possible. PR to follow.

btmills added a commit to btmills/eslint that referenced this issue Sep 2, 2014
nzakas added a commit that referenced this issue Sep 2, 2014
@gyandeeps
Copy link
Member

@nzakas I think this issue can be closed.

@nzakas
Copy link
Member

nzakas commented Sep 3, 2014

@btmills said in the PR that he was still digging into this (note the commit says "refs" instead of "fixes"). So I'm leaving it open to give him a chance to continue investigating.

@gyandeeps
Copy link
Member

But its already merged.

@nzakas
Copy link
Member

nzakas commented Sep 3, 2014

Yes, and there can be other PRs that add onto those changes. Again, the "refs" in the commit message indicates that this is not intended to close the ticket.

emilbayes pushed a commit to emilbayes/eslint that referenced this issue Sep 3, 2014
@btmills btmills changed the title Tokens API can be more efficient Core API can be more efficient Sep 4, 2014
@btmills
Copy link
Member Author

btmills commented Sep 4, 2014

After speeding up tokens, the new most time-consuming method was getScope(), and I've made some pretty good gains there. PR coming shortly. I've updated the rule title to reflect that I'm looking at more of lib/eslint.js than just the tokens API.

btmills added a commit to btmills/eslint that referenced this issue Sep 4, 2014
Instead of reverse()ing, iterates parents backwards.
Indexes scopes for direct random lookup rather than linear search.
@btmills
Copy link
Member Author

btmills commented Sep 4, 2014

As I mentioned at the end of #1216, I added some timing code in a local branch to track relative processing time consumed by each rule. Here are the ten worst offenders on tests/performance/jshint.js:

rank rule time
1 no-unused-vars 22.70%
2 no-spaced-func 7.12%
3 camelcase 5.82%
4 space-infix-ops 3.43%
5 no-shadow 3.34%
6 no-empty-class 3.33%
7 brace-style 2.04%
8 quotes 1.90%
9 semi 1.85%
10 no-undefined 1.85%

(Note that this is with the change in #1216.)

Looks like no-unused-vars might be the next place I look for optimizations.

@nzakas
Copy link
Member

nzakas commented Sep 4, 2014

Nice analysis!

michaelficarra added a commit to michaelficarra/eslint that referenced this issue Sep 4, 2014
btmills added a commit to btmills/eslint that referenced this issue Sep 4, 2014
Instead of reverse()ing, iterates parents backwards.
Indexes scopes for direct random lookup rather than linear search.
michaelficarra added a commit to michaelficarra/eslint that referenced this issue Sep 4, 2014
nzakas added a commit that referenced this issue Sep 4, 2014
nzakas added a commit that referenced this issue Sep 4, 2014
@nzakas
Copy link
Member

nzakas commented Sep 4, 2014

This is interesting. Here's my run of npm perf before pulling in the changes from the last couple of days:

CPU Speed is 3093 with multiplier 7500000
Performance Run #1:  1982.4735879999998ms
Performance Run #2:  1944.014737ms
Performance Run #3:  1956.617173ms
Performance Run #4:  1942.606373ms
Performance Run #5:  1956.5277839999999ms
Performance budget ok:  1956.5277839999999ms (limit: 2424.8302618816683ms)

Here's when I run it with master:

CPU Speed is 3093 with multiplier 7500000
Performance Run #1:  2237.275482ms
Performance Run #2:  2211.988173ms
Performance Run #3:  2194.714366ms
Performance Run #4:  2203.978643ms
Performance Run #5:  2234.894772ms
Performance budget ok:  2211.988173ms (limit: 2424.8302618816683ms)

If I go back to the tagged 0.7.4 version, I get:

CPU Speed is 3093 with multiplier 7500000
Performance Run #1:  1830.3789379999998ms
Performance Run #2:  1842.5665450000001ms
Performance Run #3:  1832.773222ms
Performance Run #4:  1820.4028640000001ms
Performance Run #5:  1852.86839ms
Performance budget ok:  1832.773222ms (limit: 2424.8302618816683ms)

So for some reason, at least on my machine, it seems like we're going backwards in terms of performance. Any ideas?

@btmills
Copy link
Member Author

btmills commented Sep 4, 2014

Just a guess: new rules or features added since 0.7.4 carried performance penalties that weren't fully offset by the recent optimizations. If that theory is correct, in doing more, it got slower, but not nearly as much as it could have.

@nzakas
Copy link
Member

nzakas commented Sep 4, 2014

Good point. I'm going to review any new on-by-default rules and see what's up.

@nzakas
Copy link
Member

nzakas commented Sep 4, 2014

The only two new rules added into the default config as enabled are no-extra-bind and no-trailing-spaces. I turned both of those off and it made no difference, so it must be a change to an existing rule.

@nzakas
Copy link
Member

nzakas commented Sep 4, 2014

Okay, something weird is going on. I just tried locally reverting commit 137b4dd and then the performance is even better than 0.7.4:

CPU Speed is 3093 with multiplier 7500000
Performance Run #1:  1758.506711ms
Performance Run #2:  1762.022322ms
Performance Run #3:  1751.08582ms
Performance Run #4:  1751.8078799999998ms
Performance Run #5:  1749.078555ms
Performance budget ok:  1751.8078799999998ms (limit: 2424.8302618816683ms)

I'm running Node v0.10.31 on Windows.

When I try running it on Linux, master is faster than 0.7.4, so it seems like a platform-specific difference. :( That puts me in a bit of a tough spot because even though the performance is slightly better on Linux, it's quite a bit worse on Windows.

@ilyavolodin
Copy link
Member

There's a possibility that V8 handles memory allocation on Linux differently then on Windows. For example, if linked list is done as a sparse array on Windows, memory seek time might be offsetting performance gains from the change (although doubtful). It's also possible that while you have faster CPU, you have slower memory. In that case, linked list is going to be quite a bit more costly then array.

Edit: Also, looking at the changes in the initial commit, I'm really not sure why there was any increase in performance at all. Changing to doubly linked list should've made no difference, since BigO of the code didn't change at all (except doubly linked list will be using more memory and can suffer from seek time latency). What would've probably make a difference is to change output array in each of those functions into linked list or stack. Unless unshift reallocates additional memory in the begging of memory block every time it's called, it should be a very costly operation. Doing insert at the root of the linked list should be quite a bit faster. Even considering that you would need to copy linked list to an array at the end.

@nzakas
Copy link
Member

nzakas commented Sep 4, 2014

All quite possible. However, my larger concern is making a divergent performance change across platforms. It makes it really hard to judge if other changes are making things faster or slower.

At the moment, in the interest of getting v0.8.0 out the door, I'm strongly considering rolling back the getTokens() change. That at least gets us an even perf profile across platform and we can consider how to proceed after the release stabilizes.

Thoughts?

@michaelficarra
Copy link
Member

I'm on Mac OS. master:

$ npm run perf

> eslint@0.7.4 perf /Users/u443/projects/eslint
> node Makefile.js perf

CPU Speed is 2300 with multiplier 7500000
Performance Run #1:  1255.083537ms
Performance Run #2:  1181.058817ms
Performance Run #3:  1224.097727ms
Performance Run #4:  1227.289147ms
Performance Run #5:  1201.452253ms
Performance budget ok:  1224.097727ms (limit: 3260.8695652173915ms)

0.7.4:

$ npm run perf

> eslint@0.7.4 perf /Users/u443/projects/eslint
> node Makefile.js perf

CPU Speed is 2300 with multiplier 7500000
Performance Run #1:  1485.552517ms
Performance Run #2:  1514.867645ms
Performance Run #3:  1499.276985ms
Performance Run #4:  1513.224784ms
Performance Run #5:  1457.4515529999999ms
Performance budget ok:  1499.276985ms (limit: 3260.8695652173915ms)

Is anyone else able to reproduce @nzakas's claim? If not, it's not a divergent perf change, it's a single outlier.

@ilyavolodin
Copy link
Member

I'm trying to reproduce it right now on my machine (Windows). Will get back with results in a few. Also, can @btmills explain why he thinks though changes should improve performance. Maybe I'm missing something, but as I mentioned in the edit of my comments, I'm not seeing anything that should improve performance in getTokens changes.

@nzakas
Copy link
Member

nzakas commented Sep 4, 2014

I'm using Windows 7, FWIW. Anyone else have a Windows 7 machine to test on?

I'll hold off on pushing out 0.8.0 at least until tomorrow to see if we can get some more data and maybe a possible solution. If not, I'll revert the change and push out 0.8.0, and we can revisit in a future release.

@ilyavolodin
Copy link
Member

I found my really old laptop that is still running Windows 7. Not sure how useful this data is, but here's what I'm seeing:

Master

CPU Speed is 1662 with multiplier 7500000
Performance Run #1:  7774.087588ms
Performance Run #2:  6528.679058ms
Performance Run #3:  6258.322175ms
Performance Run #4:  5840.615711ms
Performance Run #5:  5822.06197ms
Performance budget exceeded: 6258.322175ms (limit: 4512.635379061372ms)

v0.7.4

CPU Speed is 1662 with multiplier 7500000
Performance Run #1:  6415.795225ms
Performance Run #2:  6314.637517ms
Performance Run #3:  6496.323498ms
Performance Run #4:  6458.743596ms
Performance Run #5:  6456.497289ms
Performance budget exceeded: 6456.497289ms (limit: 4512.635379061372ms)

So still doesn't line up with what @nzakas is seeing.

@btmills
Copy link
Member Author

btmills commented Sep 5, 2014

Mine, on Windows 8.1:

master:

CPU Speed is 3374 with multiplier 7500000
Performance Run #1:  1602.964774ms
Performance Run #2:  1600.1042240000002ms
Performance Run #3:  1599.575515ms
Performance Run #4:  1610.915737ms
Performance Run #5:  1634.2933349999998ms
Performance budget ok:  1602.964774ms (limit: 2222.8808535862477ms)

v0.7.4:

CPU Speed is 3374 with multiplier 7500000
Performance Run #1:  2007.371266ms
Performance Run #2:  1963.407723ms
Performance Run #3:  1961.348431ms
Performance Run #4:  1956.311739ms
Performance Run #5:  1964.268773ms
Performance budget ok:  1963.407723ms (limit: 2222.8808535862477ms)

@ilyavolodin
Copy link
Member

Just for reference: http://jsperf.com/unshift-vs-stack This is an improvement that I was talking about in the comment above. I have changes locally, but I will hold off until after v8 release. I also still don't really think that changes that @btmills introduced are as good as it can get. I can see performance improvement, I just really don't understand why I'm seeing it. Linked lists should be slower to traverse then arrays, they are better at insertion and deletion, which we are not doing at all. Array + hashtable should actually perform better. Doubly linked skip list should be even better then that. I'm going to see if I can do a partial skip list implementation for getTokens and check it's performance.

@michaelficarra
Copy link
Member

I'm working on no-unused-vars. The performance increase should be... extreme.

michaelficarra added a commit to michaelficarra/eslint that referenced this issue Sep 5, 2014
nzakas added a commit that referenced this issue Sep 5, 2014
@nzakas
Copy link
Member

nzakas commented Sep 5, 2014

Okay, I'm reverting 137b4dd and going ahead with the 0.8.0 release. We can continue investigating, but in the meantime, the other changes by @btmills and @michaelficarra have resulted in about a 100-200ms speed improvement, which is pretty sweet.

nzakas added a commit that referenced this issue Sep 5, 2014
@ilyavolodin
Copy link
Member

I modified the code for tokens to use hashtable + array. Changed all skip functions (getTokenAfter, getTokenBefore, etc.) to have static bigO and all of the rest of the function only do as many iterations as the number of items returned and I'm not seeing any performance improvement (at least on my machine). I think that at this point, the code is IO bound, not CPU. Here's the link to the branch with code changes: https://github.com/ilyavolodin/eslint/tree/performance

@nzakas nzakas added the accepted There is consensus among the team that this change meets the criteria for inclusion label Sep 20, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
btmills added a commit to btmills/eslint that referenced this issue Nov 27, 2014
nzakas added a commit that referenced this issue Nov 27, 2014
Update: refactor tokens API (refs #1212)
@nzakas
Copy link
Member

nzakas commented Jan 18, 2015

I think we finished this work, so closing.

@nzakas nzakas closed this as completed Jan 18, 2015
Holixus pushed a commit to Holixus/eslint that referenced this issue Feb 12, 2015
@eslint-deprecated eslint-deprecated bot locked and limited conversation to collaborators Feb 7, 2018
@eslint-deprecated eslint-deprecated bot added the archived due to age This issue has been archived; please open a new issue for any further discussion label Feb 7, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
accepted There is consensus among the team that this change meets the criteria for inclusion archived due to age This issue has been archived; please open a new issue for any further discussion core Relates to ESLint's core APIs and features enhancement This change enhances an existing feature of ESLint
Projects
None yet
Development

No branches or pull requests

5 participants