Skip to content

[IMPROVEMENT] Hashmap implementation! Bigger builds are now faster!

I implemented a simple hashmap that resolves conflicts using open addressing linear probing. Using the first string hashing algorithm I found! I used & to bound the output using power of two sizes for the underlying array.

I didn't make any attempts to make the interface generic other than using typedefs here and there.

While it is a "naive" hashtable(If i ever was to optimize it I'd using something better than a plain & and probably a robinhood hashing instead) running the tests yields adequate results, in fact the complexity no longer scales with array size! With hashmap_insert(3)(the one and only function i needed to implement) taking up only 0.02% of the total runtime(previously it could be as high as 10% given a "big" build, for example, the linux kernel with all config options set to no).

Since I've made plenty of changes, I'd feel better if we were to instead use a testing branch for now. I am currently compiling wine, a project that previously took about four hours to compile on my machine while build_recorder wrapped it. I will post the two callgrind outputs(before and after the hashmap, aka main branch vs this PR hashtable branch) once it's complete!

Merge request reports

Loading