Batch insertion application
- Dominant language
- Python
- Stars
- 111
- Forks
- 54
- Avg merge
- 27m
- Merged PRs (30d)
- 1
Description
### What was wrong?
When a trie adds a single value, it must fix up all the nodes it touched along the way. This carries some performance cost, but is necessary for any single update. When applying a batch update, all the intermediate node fixups are wasted work. We could gain some (likely) significant performance benefits from a smarter batch-apply of a bunch of key/value pairs.
### How to fix it
Rough concept: walk through the trie with all scheduled insertions, applying them simultaneously.
For example, if two keys from the batch have the same first nibble, then follow the root node down into the extension/leaf/branch node with that nibble, keeping both of those insertions in memory. Then apply them both to the newly created node at the same time.
Contributor guide
Assessment
This issue has not been assessed yet.