3 ms·

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

• utopcell 8y ago
  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.
  • SolarNet 8y ago
    The hashmap the author wrote is .95, it's the google ones with a 0.5 load factor.
    • utopcell 8y ago
      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 ?)
      • jpetso 8y ago
        Right, ska::bytell_hash_map is the most recent iteration and ska::flat_hash_map was the previous one.
• vanderZwan 8y ago
  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).