Skip to content

ka-weihe/btree-v

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

29 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

btree-v (merged)

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.

Benchmark

About

Fast B-tree implementation for V

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages