4 ms·

Keep in mind that - those hash maps are optimized for large sets - they work around several edge cases - they implement way more features than an in-house im

Keep in mind that - those hash maps are optimized for large sets - they work around several edge cases - they implement way more features than an in-house implementation - they need to support many types of hardware A decent engineer can beat the std collections in a day on performance. But to do that in production over a decade with shifting requirements is a different ball game.

veltas 4y ago
The one I cooked up was used to test some kind of game solver, so a 'large set' and it happily beat std::unordered_map, was a tiny bit slower than a Google hash map implementation. But I do believe in edge cases, I'm sure there are some pathological edge cases (that don't usually matter, but deserve consideration). I'm interested to know what 'way more features' are for hash maps/sets, because AFAIK C++ just supports the basic features you'd expect of the abstract data structure of a "map" with the algorithmic guarantees you'd expect from a hashmap. And nothing I did was aimed at 'specific hardware' other than it vaguely benefitted from memory locality / avoiding thrashing the cache.
- ahmedalsudani 4y ago
  "Features" was probably the wrong word for me to use. What I was referring to is interface + customizability. The STL map allows you to: - specify the key/value types - specify the equality predicate - specify which hash function to use - iterate over values along with a host of other things that most users don't initially need but they might need in the future. You could implement something that has feature parity in C++ or ideally find a battle-tested library that does. Using C, however, you'd have to sacrifice type safety and possibly readability. Yes it can be done, and yes it can be done correctly. But it's tricky and difficult to ramp up on for the new developer. This is the one that you should be careful about adopting. My philosophy is to use the STL containers because they're familiar and they're more than good enough for 99% of the use cases out there. Developer time has a premium, and this saves developer time. If you need performance because you're constrained by CPU cycles or if you're running at scale (Google for example), by all means reach for something better.

veltas 4y ago

The one I cooked up was used to test some kind of game solver, so a 'large set' and it happily beat std::unordered_map, was a tiny bit slower than a Google hash map implementation. But I do believe in edge cases, I'm sure there are some pathological edge cases (that don't usually matter, but deserve consideration). I'm interested to know what 'way more features' are for hash maps/sets, because AFAIK C++ just supports the basic features you'd expect of the abstract data structure of a "map" with the algorithmic guarantees you'd expect from a hashmap. And nothing I did was aimed at 'specific hardware' other than it vaguely benefitted from memory locality / avoiding thrashing the cache.

ahmedalsudani 4y ago
"Features" was probably the wrong word for me to use. What I was referring to is interface + customizability. The STL map allows you to: - specify the key/value types - specify the equality predicate - specify which hash function to use - iterate over values along with a host of other things that most users don't initially need but they might need in the future. You could implement something that has feature parity in C++ or ideally find a battle-tested library that does. Using C, however, you'd have to sacrifice type safety and possibly readability. Yes it can be done, and yes it can be done correctly. But it's tricky and difficult to ramp up on for the new developer. This is the one that you should be careful about adopting. My philosophy is to use the STL containers because they're familiar and they're more than good enough for 99% of the use cases out there. Developer time has a premium, and this saves developer time. If you need performance because you're constrained by CPU cycles or if you're running at scale (Google for example), by all means reach for something better.