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.

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

Jump to bottom

Replace Map<number,T> with (sparse) Array<T> #467

Open
BurtHarris opened this issue Apr 29, 2020 · 1 comment · May be fixed by #468
Open

Replace Map<number,T> with (sparse) Array<T> #467

BurtHarris opened this issue Apr 29, 2020 · 1 comment · May be fixed by #468
Assignees
@BurtHarris
Labels
enhancement in progress performance

Comments

@BurtHarris
Copy link
Collaborator

BurtHarris commented Apr 29, 2020 •
edited
Loading

Arrays in JavaScript are by definition sparse, so using a Map with number key seems like a potential performance improvement. For example, DFAState.edges is high-traffic, particularly in getTarget().

A quick trial experiment of this showed around 17% speed improvement in TestLexerSeed. Before the change:

       lex_legacy_java_utf8 average time 2951us over 2000 runs of 29600 symbols
       lex_legacy_java_utf8 average time 7137us over 2000 runs of 29600 symbols DFA cleared
          lex_new_java_utf8 average time 2937us over 2000 runs of 29600 symbols
          lex_new_java_utf8 average time 7180us over 2000 runs of 29600 symbols DFA cleared

With Array replacing Map<number, DFAState> the results were:

       lex_legacy_java_utf8 average time 2436us over 2000 runs of 29600 symbols
       lex_legacy_java_utf8 average time 6733us over 2000 runs of 29600 symbols DFA cleared
          lex_new_java_utf8 average time 2481us over 2000 runs of 29600 symbols
          lex_new_java_utf8 average time 6761us over 2000 runs of 29600 symbols DFA cleared
@BurtHarris
Copy link
Collaborator Author

One challenge to this is that Array<T>.keys returns number keys with undefined elements. This required a little filtering in a toString() method, but Array.forEach() works out well.

Other potential applications of this include ATN.LL1Table, which might be significant in parsing speed.

TokenStreamRewriter.ts indexToOp, ATNDeserialization rulePrecedenceDecisions, and ParserATNSimulator.ts statesFromAlt1 also seem to fit the pattern, but seem not to be on critical paths.

@BurtHarris BurtHarris self-assigned this Apr 29, 2020
@BurtHarris BurtHarris linked a pull request Apr 29, 2020 that will close this issue
Open
@BurtHarris BurtHarris linked a pull request Apr 30, 2020 that will close this issue
Replace Map<number, T> with sparse array in DFAState #468
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@BurtHarris BurtHarris

Labels
enhancement in progress performance
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Replace Map<number, T> with sparse array in DFAState
1 participant
@BurtHarris