8000 Optimize performance of setCategoryIndex by hy9be · Pull Request #1544 · plotly/plotly.js · GitHub
[go: up one dir, main page]
Skip to content

Optimize performance of setCategoryIndex #1544

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.

Sign up for GitHub

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

Merged
merged 13 commits into from
Apr 10, 2017
Merged

Optimize performance of setCategoryIndex #1544

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
13 commits
Select commit Hold shift + click to select a range
40e69d3
Optimize performance of setCategoryIndex
hy9be Mar 31, 2017
b47c7af
Update unit test
hy9be Mar 31, 2017
e8941d6
Refactor the changes
hy9be Apr 3, 2017
b3fb03d
Build the lookup map for initialized categories
hy9be Apr 3, 2017
2992126
Reset the lookup map when the categories are reset
hy9be Apr 3, 2017
989f07a
Optimize the scatter trace sorting comparator with map
hy9be Apr 5, 2017
91cfaa4
Merge remote-tracking branch 'origin/master' into perf-setcategoryindex
hy9be Apr 8, 2017
abcd729
Clean ESLint errors in CI
hy9be Apr 8, 2017
153f547
getCategoryIndex falls back to the former implementation to fix the f…
hy9be Apr 8, 2017
ff043b4
Fix another problem in getCategoryIndex
hy9be Apr 8, 2017
c32163e
Add comments
hy9be Apr 8, 2017
d2be6c9
Remove the fallback to indexOf search in getCategoryIndex, update the…
hy9be Apr 10, 2017
14d6649
Remove out of date comments
hy9be Apr 10, 2017
File filter

Filter by extension

Filter by extension
8000
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Remove the fallback to indexOf search in getCategoryIndex, update the… 
… mock object in unit test instead
  • Loading branch information
@hy9be
hy9be committed Apr 10, 2017
commit d2be6c94f3291c42666bf5c3f086968f42010ba2
4 changes: 1 addition & 3 deletions src/plots/cartesian/set_convert.js
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -152,10 +152,8 @@ module.exports = function setConvert(ax, fullLayout) {
if(ax._categoriesMap) {
index = ax._categoriesMap[v];
if(index !== undefined) return index;
} else {
index = ax._categories.indexOf(v);
if(index !== -1) return index;
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Awesome, I'm glad it was as easy as that :)

Apologies for the iterations, but one more related request since this is a perf PR of a couple of very hot code paths: I don't think that either getCategoryIndex or setCategoryIndex needs the fallbacks for missing _categoriesMap - the previous version, using only _categories, didn't have these fallbacks, and every path that creates _categories also creates _categoriesMap, right?

(also 📚 your comment above this is out of date now)

Copy link
Contributor Author
@hy9be hy9be Apr 10, 2017 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Right now no functions will fallback to use indexOf on _categories anymore.

Currently I made sure _categoriesMap is always populated accordingly when _categories is created or initialized with some items for the current code. But this is not a robust way. Someone could change _categories without updating _categoriesMap in their code, and it will not be trivial for them to realize they need to update _categoriesMap.

I have code with fallbacks in stash. If you think that's a better way I can quickly change it back.

Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh sorry, I just meant we can remove the fallbacks for if _categoriesMap doesn't even exist, ie in getCategoryIndex changing:

if(ax._categoriesMap) {
    var index = ax._categoriesMap[v];
    if(index !== undefined) return index;
}

to just:

var index = ax._categoriesMap[v];
if(index !== undefined) return index;

and removing from setCategoryIndex:

if(ax._categoriesMap === undefined) {
    ax._categoriesMap = {};
}

As far as I can tell, that much should be robust. Not a huge deal but should be a small performance boost.

But you raise a good point about future changes, I guess that's an argument for converting these two to a single bidirectional map object even if it doesn't yield any additional perf benefits.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh I get it. Sorry I misunderstood your point.

Well, I feel a liiiittle bit uncomfortable of doing that, because if there is any case that the map is not created, it will result in an uncaught exception, which to me, seems more severe than a messed up chart.

And I tried on jsperf, the overhead of checking null is less than 10% on Chrome:
image
And considering the performance of reading a map itself, 10% differences here will not be a big cost for the whole workflow.

For Safari the differences are even less.
image

Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

That's fine, I'm pretty confident that it's OK since that's how it worked previously, but I can take responsibility for removing it (in another PR) and ensuring we have sufficient test coverage. You're right that the penalty is much smaller than the improvement you've made here (though I'd be wary of that jsperf result, I suspect in Safari the compiler has optimized away almost everything you see there).

So I think this is ready to go! Nice job @hy9be !

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good to know! I used to trust the results I got from jsperf a lot...
Thanks a lot for reviewing my code! @alexcjohnson

}
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If this block is only here to fix that test, and never gets hit in real code (which looks to be the case to me, since ax._categories and ax._categoriesMap always get populated simultaneously) then we should leave out the else block here, and just make the test more realistic by creating the corresponding _categoriesMap in the mock ax object.

For the record, this made me curious "do we still need ax._categories at all?" But you were right to not remove it, as getCategoryName (ax.c2d etc, ie hover info) still needs the reverse mapping to be fast.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Totally agree. I will make the change on the mock object instead.

Yeah I tried to completely replacing the _categories array with the map, but there will be some cases we need a reverse mapping.

Actually, comparing to maintaining a pair of synced-up array and map, I feel there must be some better data structure for a performant categories collection. But I was sort of lazy and did not give it another think anymore.

Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I feel there must be some better data structure for a performant categories collection.

Good point, I'm sure there is, though it won't be built in so is unlikely to improve performance, it would just clean up the API... lets not worry about it for now, this two-part solution is light and easy enough to use here but we can look into it further if this comes up in enough other places.


if(typeof v === 'number') { return v; }
}

Expand Down
1 change: 1 addition & 0 deletions test/jasmine/tests/axes_test.js
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -1685,6 +1685,7 @@ describe('Test axes', function() {
var ax = {
type: 'category',
_categories: ['a', 'b', 'c', 'd'],
_categoriesMap: {'a': 0, 'b': 1, 'c': 2, 'd': 3},
tickmode: 'array',
tickvals: ['a', 1, 1.5, 'c', 2.7, 3, 'e', 4, 5, -2],
ticktext: ['A!', 'B?', 'B->C'],
Expand Down
0