Comment by program_whiz
8 years ago
Props, this is an amazing contribution. So much respect for someone who can really dig in, figure this stuff out, and make a better data-structure for nothing more than the love of doing so. Everyone making their living as a programmer/tech person owes it to people like this who make the basic tools.
His ska-sort (a really fast in-place radix sort generalisable to almost all data) is also very interesting, I'm surprised there aren't more people working on the data structures he builds to make little improvements.
I may actually have figured out a way to (theoretically) make it faster, but I don't grok C++ templates so can't write a pull-request (the general idea is: instead of a standard full swap, use two temporaries and ping-pong between them while swapping elements to do half-swaps. This reduces required assignments to move an element to its final position from three to two).
To be fair, the max load factor for this hash map is set to 0.5, which is quite wasteful in terms of memory. If you allow for 50% load in dense_hash_map (and most hash maps for that matter,) they become much faster themselves.
The hashmap the author wrote is .95, it's the google ones with a 0.5 load factor.
Is this true? From the article: ''ska::flat_hash_map has a max_load_factor of 0.5''. ska::flat_hash_map is the author's implementation (but maybe not the most recent iteration ?)
1 reply →