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

fix(lib/runtime/storage): improve NextKeys time complexity #3958

Closed
EclesioMeloJunior opened this issue May 16, 2024 · 1 comment · Fixed by #3961
Closed

fix(lib/runtime/storage): improve NextKeys time complexity #3958

EclesioMeloJunior opened this issue May 16, 2024 · 1 comment · Fixed by #3961
Assignees
@EclesioMeloJunior
Labels
C-complex Complex changes across multiple modules. Possibly will require additional research. P-critical this must be fixed immediately or contributors or users will be severely impacted. S-sync-westend related to particular network syncing. T-refactor this issue/pr covers refactoring of existing code.

Comments

@EclesioMeloJunior
Copy link
Member

EclesioMeloJunior commented May 16, 2024 •
edited

Description

  • When the runtime requests the next key under an ongoing transaction we should not use t.state.Entries(), this method will go through the entire in-memory trie inserting each key and value in a map to be used to search the next key in lexicographic order. This is not optimal because the trie tends to grow so t.state.Entries() is O(n).

  • Outside of ongoing transaction the same method searches in the in-memory trie directly which is more efficient since you don't need to search the entire trie but just the path for the next key in lex order

The motivation is explained here: #3950 (comment).
@EclesioMeloJunior EclesioMeloJunior added C-complex Complex changes across multiple modules. Possibly will require additional research. P-critical this must be fixed immediately or contributors or users will be severely impacted. S-sync-westend related to particular network syncing. T-refactor this issue/pr covers refactoring of existing code. labels May 16, 2024
@EclesioMeloJunior EclesioMeloJunior self-assigned this May 16, 2024
@EclesioMeloJunior
Copy link
Member Author

The following algo might fix the bottleneck!

  • search on the trie get a next key there
  • then search on the map and get the next key there
  • compare both and return the next one in lex order

@dimartiro dimartiro mentioned this issue May 16, 2024
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@EclesioMeloJunior EclesioMeloJunior

Labels
C-complex Complex changes across multiple modules. Possibly will require additional research. P-critical this must be fixed immediately or contributors or users will be severely impacted. S-sync-westend related to particular network syncing. T-refactor this issue/pr covers refactoring of existing code.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

fix(storage): Improve get nextkey performance when we have txs ChainSafe/gossamer
1 participant
@EclesioMeloJunior