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

Possible batch update of values #40

Open
cheme opened this issue Nov 25, 2019 · 0 comments
Open

Possible batch update of values #40

cheme opened this issue Nov 25, 2019 · 0 comments
Assignees
Labels
enhancement New feature or request

Comments

@cheme
Copy link
Contributor

cheme commented Nov 25, 2019

When updating multiple value, calling 'insert' multiple time on a 'triedbmut' does not look as efficient as doing it in a single pass.
With a batch update, we can avoid putting the whole trie changes in memory.
This kind of batch update is only possible if values to change are sorted.
It does not require caching node values like current triedbmut does (just a stack of node).
It is basically just moving the sort done by unordered triemut insertion to a previous processing.

In substrate the trie is build by 'storage_root' call https://github.com/paritytech/substrate/blob/2ac4dd8a7e116c40a80bf443d942da7163cad8ca/primitives/state-machine/src/trie_backend.rs#L153 , relying on triedbmut multiple calls to 'insert':
https://github.com/paritytech/substrate/blob/2ac4dd8a7e116c40a80bf443d942da7163cad8ca/primitives/trie/src/lib.rs#L133 .
If keys in substrate change overlay were to be stored in a sorted manner at an additional cost (an hypothesis for paritytech/substrate#4185), this cost could probably be leveraged by having a batch insertion in trie afterward (it needs a bench to evaluate what kind of improvement we can get from a batch insertion implementation, it should not be much, but neither should be the loss from sorting key in substrate change overlay).

@cheme cheme added the enhancement New feature or request label Nov 25, 2019
@cheme cheme self-assigned this Nov 25, 2019
@cheme cheme mentioned this issue Jul 31, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant