4 ms·

> I don't know if there's a spec-problem that favors a slower-hash table Yes. std::unordered_map requires that pointers to stored values will always be valid

> I don't know if there's a spec-problem that favors a slower-hash table Yes. std::unordered_map requires that pointers to stored values will always be valid (except if the value is erased). This makes open adressing effectively impossible. If you need max. performance, std::unordered_map is indeed not a good choice. > The ret[] operator searches for the string. Since it doesn't exist, it now has to malloc the key and insert the value in there. The optimal method would be https://en.cppreference.com/w/cpp/container/unordered_map/emplace https://en.cppreference.com/w/cpp/container/unordered_map/em... > So eight mallocs and 6 frees? > Yeah, C++ strings shoot yourself in the foot performance-wise. Most implementations of std::string use short string optimization. Typically, you can save up to 12 chars (32-bit) or 24 chars (64-bit) inside the actual string container without any memory allocation. Looking at the code example, I would say that there won't be any mallocs at all for std::string. I think the performance difference just comes from the suboptimal design of std::unordered_map, where each node has to be allocated on the heap. In open addressing hash tables, as used by PHP (and I guess also by Rust), the nodes live in a single large array. The only memory allocation you see is when the array has to be resized due to a rehash - which happens very rarely!

dragontamer 5y ago
Thanks for the SSO pointer. I'll keep that in mind in the future. > Yes. std::unordered_map requires that pointers to stored values will always be valid (except if the value is erased). Hmm, that requirement also prevents Cuckoo-hashing. The general pattern here (and this is problematic in a lot of languages), is the idea of having a "shortcut" into an object in a data-structure. For example, C++ and Java's "iterator-invalidation" rules are absolutely arcane, even if we removed the pointer-requirements. Many data-structures want to move things around (cuckoo-hashing, open-addressing, robin-hood hashing... look 3 different, high-performance strategies and we're still just talking about hash tables!!). But those moves "invalidate" the shortcuts (be it a pointer or an iterator). Some data-structures can have those pointers just fine (Red-and-black trees), others cannot. Representing all these possibilities with a fixed, easily understood interface that generalizes among all of these data-structures / decisions seems impossible. ------ Well, I guess that's why I keep rolling my own data-structures when I need performance guarantees... standard-library just has to make decisions that may or may not match my cases.
- spacechild1 5y ago
  > Well, I guess that's why I keep rolling my own data-structures when I need performance guarantees... Yes, this is what many companies do. std containers are good enough for the general case, but are certainly situations where you need something more fancy. However, before you roll your own, first check if there's a good library you can use. The world's best hashtable has already been written by other people :-)
- usefulcat 5y ago
  For std::unordered_map, I don't know why they decided to add the no-iterator-invalidation requirement. If you really need that property, you could get most of the benefits by using unordered_map<unique_ptr<T>> instead of unordered_map<T>. So maybe not the best example of "don't pay for what you don't use".
  - spacechild1 5y ago
    > the no-iterator-invalidation requirement Iterators can be invalidated (e.g. after a rehash). The requirement is rather that the address of the value itself must not change (so that pointers will remain valid). > If you really need that property, you could get most of the benefits by using unordered_map<unique_ptr<T>> instead of unordered_map<T>. I agree. I don't know why they have decided for the current design. They even expose the bucket interface (https://en.cppreference.com/w/cpp/container/unordered_map/bucket https://en.cppreference.com/w/cpp/container/unordered_map/bu...) which should really be an implementation detail...
  - dragontamer 5y ago
    I mean, its a hashmap we're talking about. I'm not sure if iterators even make sense in any regard. Things inside of a hashmap have no order at all. And determining if a cell is full or empty in a hash-map isn't exactly efficient either (You pretty much have to visit those locations and see if a tombstone or empty symbol is there). ------- I recognize that people want to foreach() over a HashMap, but I'm just not convinced its an efficient operation, nor a good fit for the iterator interface (especially with all this discussion of invalidations and movement...)

dragontamer 5y ago

Thanks for the SSO pointer. I'll keep that in mind in the future. > Yes. std::unordered_map requires that pointers to stored values will always be valid (except if the value is erased). Hmm, that requirement also prevents Cuckoo-hashing. The general pattern here (and this is problematic in a lot of languages), is the idea of having a "shortcut" into an object in a data-structure. For example, C++ and Java's "iterator-invalidation" rules are absolutely arcane, even if we removed the pointer-requirements. Many data-structures want to move things around (cuckoo-hashing, open-addressing, robin-hood hashing... look 3 different, high-performance strategies and we're still just talking about hash tables!!). But those moves "invalidate" the shortcuts (be it a pointer or an iterator). Some data-structures can have those pointers just fine (Red-and-black trees), others cannot. Representing all these possibilities with a fixed, easily understood interface that generalizes among all of these data-structures / decisions seems impossible. ------ Well, I guess that's why I keep rolling my own data-structures when I need performance guarantees... standard-library just has to make decisions that may or may not match my cases.

spacechild1 5y ago
> Well, I guess that's why I keep rolling my own data-structures when I need performance guarantees... Yes, this is what many companies do. std containers are good enough for the general case, but are certainly situations where you need something more fancy. However, before you roll your own, first check if there's a good library you can use. The world's best hashtable has already been written by other people :-)
usefulcat 5y ago
For std::unordered_map, I don't know why they decided to add the no-iterator-invalidation requirement. If you really need that property, you could get most of the benefits by using unordered_map<unique_ptr<T>> instead of unordered_map<T>. So maybe not the best example of "don't pay for what you don't use".
- spacechild1 5y ago
  > the no-iterator-invalidation requirement Iterators can be invalidated (e.g. after a rehash). The requirement is rather that the address of the value itself must not change (so that pointers will remain valid). > If you really need that property, you could get most of the benefits by using unordered_map<unique_ptr<T>> instead of unordered_map<T>. I agree. I don't know why they have decided for the current design. They even expose the bucket interface (https://en.cppreference.com/w/cpp/container/unordered_map/bucket https://en.cppreference.com/w/cpp/container/unordered_map/bu...) which should really be an implementation detail...
- dragontamer 5y ago
  I mean, its a hashmap we're talking about. I'm not sure if iterators even make sense in any regard. Things inside of a hashmap have no order at all. And determining if a cell is full or empty in a hash-map isn't exactly efficient either (You pretty much have to visit those locations and see if a tombstone or empty symbol is there). ------- I recognize that people want to foreach() over a HashMap, but I'm just not convinced its an efficient operation, nor a good fit for the iterator interface (especially with all this discussion of invalidations and movement...)