Possible batch update of values
@cheme is already working on this.
Since Nov 25, 2019.
- Dominant language
- Rust
- Stars
- 274
- Forks
- 72
- PR merge metrics
- No merged PRs in 30d
Description
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 https://github.com/paritytech/substrate/pull/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).
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.