This is an attempt to create a faster and more memory efficient map for V by using a B-tree instead of a BST. Early benchmarks show a speed increase of ~50% (in what I consider a general case) for lookups and inserts while keeping memory reduced by 50%. These benchmarks are extremely primitive, so take them with a grain of salt. This implementation currently only accepts strings for keys and ints for values. I expect that this implementation will be at least twice as fast, compared to the current map in V - for integral-types keys. B-trees are faster due to their cache-friendliness, however, they are not faster when keys become incredibly big 128+ characters, but I would argue that the average string in a map would be 20-30 characters (where btree-v is 50% faster). Integral-types are also common keys in maps (where btree-v is going to be at least 100% faster - I expect 500% faster). Remember this is work in progress! Lower is better in the graph.
-
Notifications
You must be signed in to change notification settings - Fork 0
ka-weihe/btree-v
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
About
Fast B-tree implementation for V
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published