6 ms·

Check also PHP-7 or 8's "open addressing" hash map. Beats the hell out of everyone else. Like C++ red-black tree default hashmap implementation taking 1.0 secon

Check also PHP-7 or 8's "open addressing" hash map. Beats the hell out of everyone else. Like C++ red-black tree default hashmap implementation taking 1.0 second -- vs PHP taking 0.5 second for the same dataset. Here's the code I tested with. php: #!/usr/bin/env php <? $ret=[]; for($i=0; $i<5000000; $i++){ $ret["id.".($i%500000)]="val.".$i; } print(count($ret))."\n"; print $ret["id.10000"]."\n"; cpp: #include <iostream> #include <map> using namespace std; int main(){ map<string, string> ret; for(int i=0; i<5000000; i++){ ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); } cout << ret.size() << endl; cout << ret["id.10000"] << endl; return 0; } Rust : use std::collections::HashMap; fn main(){ let mut ret = HashMap::new(); for i in 0..5000000 { ret.insert(format!("id.{}", i%500000), format!("val.{}",i)); } println!("{}", ret.len()); match ret.get("id.10000") { Some(val) => println!("{}", val), None => println!("ERROR") } }

dragontamer 5y ago
> C++ red-black tree default hashmap unordered_map is the hashmap. map is a red-black tree, which keeps the data sorted. You should use map<> if you need to visit the data in-order with a for-each loop. Hashmaps can't visit the data in order.
- deleted 5y ago
  [deleted]
- habibur 5y ago
  unordered_map performs even worse than map. Tried it.
  - dragontamer 5y ago
    Looking at the code more carefully, I'd actually bet its string that's slow, and not actually map. unordered_map is actually known to have relatively bad performance on GCC and some other open-source implementations. I don't know if there's a spec-problem that favors a slower-hash table (rather than the modern open-addressing scheme, which is faster on modern computers), but I can believe unordered_map has an issue on common standard libraries today. ------------ > ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); Lets count the mallocs. > string("id.") One > to_string(i%500000) Two > string("id.")+to_string(i%500000) Three, then two frees() as the previous two strings are deallocated. > ret[string("id.")+to_string(i%500000)] Four. 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. std::move() might solve that issue and cut this one out easily? > string("val.") Five > to_string(i) Six > string("val.")+to_string(i) Seven + 2x frees. > ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); Eight, to place the value in there. Again, probably solved with std::move. +1 more free. So eight mallocs and 6 frees? --------- Yeah, C++ strings shoot yourself in the foot performance-wise. But they're easy to use and free of stupid malloc/free bugs, but it means that they will malloc/free a LOT more than you might guess with the untrained eye. I know that Perl / PHP / etc. etc. were explicitly designed to be more favorable towards string manipulation. And I'd bet that there's some old C++98 stuff that might lock in the performance of string to this older, less performant model. EDIT: I see you managed to avoid the problem of excessive mallocs/frees in the Rust code with "format". The C++ equivalent might be snprintf, though that dips down into C-style strings.
    - maleldil 5y ago
      > The C++ equivalent might be snprintf There's std::format from C++20 too[1]. One can use std::ostringstream instead, I suppose, but at that point I'd probably use snprintf too. [1] https://en.cppreference.com/w/cpp/utility/format/format https://en.cppreference.com/w/cpp/utility/format/format
      - spacechild1 5y ago
        std::ostringstream will certainly allocate its buffer on the heap. When you call the str() method to retrieve the final result, it will have to make another copy. So you will always have an extra allocation. Note that std::format still returns a std::string (which might allocate memory, depending on the size of the string), but that doesn't matter if it is going to be moved anyways. If you want to write into an existing buffer, you can use std::format_to_n as a modern replacement for snprintf.
    - spacechild1 5y ago
      > 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!
  - jcelerier 5y ago
    that's absolutely untrue in a lot of cases: https://stackoverflow.com/questions/36392583/is-an-unordered-map-really-faster-than-a-map-in-practice https://stackoverflow.com/questions/36392583/is-an-unordered... of course one can always find faster, drop-in replacement libraries: https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/ https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o... e.g. replacing std::unordered_map with robin_hood::hash_map makes the above C++ code go from 1.2 seconds to 0.5 seconds on my machine (std::map is around 1.3/1.4 seconds for libstdc++). (though as others said, this test is in big part a test of std::string performance... replacing strings by int make times go down to ~0.1s here)
nikita2206 5y ago
Last time I checked, that was around PHP 7.0, it was using chaining for its hash table implementation. One notable thing was that its hash table was also using a more optimal array impl (no hashing) if you were only using numerical consecutive keys starting from zero.
- masklinn 5y ago
  > that was around PHP 7.0 7.0 is when php switched to open addressing: https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html https://www.npopov.com/2014/12/22/PHPs-new-hashtable-impleme...
  - nikita2206 5y ago
    Interesting, I definitely missed some of that, didn’t know about replacement of doubly linked list with arData array for maintaining insertion order. It does still use chaining though, just not with the classical pointers and instead with indexes into an array but indirection is still there for collision cases.
    - deleted 5y ago
      [deleted]
- habibur 5y ago
  > Last time I checked, that was around PHP 7.0, it was using chaining for its hash table implementatio Chaining was from php 5.
masklinn 5y ago
> Rust : You’re using the default hash function, which is SipHash 1-3, which is known to be quite slow. Not horrendously so but it was picked for attack resistance. If you need high hashmap performances and control input (or have a rather safe type) it’s pretty common knowledge that you should replace the hash function with something like fnv or fx. You’re also allocating a ton in a hot loop, also a known mispattern. I’d expect C++ to also be greatly affected there.
- fl0ki 5y ago
  My experience with fx has been very mixed and I don't think it's a safe default recommendation. It can often outperform fnv and wyhash because it does so little, but it can also greatly underperform once it's used in a hash table because it can cause a lot of conflicts for some types of keys, especially after modulo. This can be much slower than just having a slightly slower hash function, because the equality function will be called against many more candidates, potentially with each requiring one or more uncached fetches from main memory. I now recommend wyhash more often than not, and sometimes fnv can beat that. wyhash has the substantial advantage that it can also be made attack-resistant with a seed given to the builder, with much less overhead than sip. My most recent problematic use cases for fx were all to do with hashing just one or two scalar integers per key. Its few per-word instructions weren't nearly enough to get a good distribution when there were only 1-2 words (on a usize=u64 target). Even hacking in fmix64 from Murmur3 helped a ton, but made it no faster than wyhash in the end, and harder to reason about. I ended up using wyhash for some keys and fnv for others. In any case, nobody should switch hash functions without evaluating performance on full-sized realistic production data. You can easily end up with bad overall hash table performance because of poor distribution with your real keys. Microbenchmarks tend to miss this, especially if they do not create real-sized and real-shaped key sets. Then all you see is the hash function performance, which is misleading if it results in poor overall table performance, which is what happened to me with fx in particular. I think a lot of people choose fx based on such microbenchmarks and assume its distribution is good enough to scale out, but this should not be assumed, only tested. You might also see surprising effects from cache locality when testing tables big enough that they don't fit in cache, and if this matters for your workload then you definitely want to account for that in your choice of hash table data structure.
singron 5y ago
Wow. That php program is fast! I was skeptical for much the same reasons as the other commentators. But I took the rust version, packed the strings into u128, eliminated the allocations in the loop, --release, lto, codegen-units=1, target-cpu=native (basically all the tricks to make it fast). I tried FxHashMap, AHashMap, and hashbrown, but they didn't make much difference with the other optimizations (and FxHashMap was significantly slower). Even with all that, the php version was still 2x faster. And it truly is due to the hashtable implementation itself.

dragontamer 5y ago

> C++ red-black tree default hashmap unordered_map is the hashmap. map is a red-black tree, which keeps the data sorted. You should use map<> if you need to visit the data in-order with a for-each loop. Hashmaps can't visit the data in order.

deleted 5y ago
[deleted]
habibur 5y ago
unordered_map performs even worse than map. Tried it.
- dragontamer 5y ago
  Looking at the code more carefully, I'd actually bet its string that's slow, and not actually map. unordered_map is actually known to have relatively bad performance on GCC and some other open-source implementations. I don't know if there's a spec-problem that favors a slower-hash table (rather than the modern open-addressing scheme, which is faster on modern computers), but I can believe unordered_map has an issue on common standard libraries today. ------------ > ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); Lets count the mallocs. > string("id.") One > to_string(i%500000) Two > string("id.")+to_string(i%500000) Three, then two frees() as the previous two strings are deallocated. > ret[string("id.")+to_string(i%500000)] Four. 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. std::move() might solve that issue and cut this one out easily? > string("val.") Five > to_string(i) Six > string("val.")+to_string(i) Seven + 2x frees. > ret[string("id.")+to_string(i%500000)] = string("val.")+to_string(i); Eight, to place the value in there. Again, probably solved with std::move. +1 more free. So eight mallocs and 6 frees? --------- Yeah, C++ strings shoot yourself in the foot performance-wise. But they're easy to use and free of stupid malloc/free bugs, but it means that they will malloc/free a LOT more than you might guess with the untrained eye. I know that Perl / PHP / etc. etc. were explicitly designed to be more favorable towards string manipulation. And I'd bet that there's some old C++98 stuff that might lock in the performance of string to this older, less performant model. EDIT: I see you managed to avoid the problem of excessive mallocs/frees in the Rust code with "format". The C++ equivalent might be snprintf, though that dips down into C-style strings.
  - maleldil 5y ago
    > The C++ equivalent might be snprintf There's std::format from C++20 too[1]. One can use std::ostringstream instead, I suppose, but at that point I'd probably use snprintf too. [1] https://en.cppreference.com/w/cpp/utility/format/format https://en.cppreference.com/w/cpp/utility/format/format
    - spacechild1 5y ago
      std::ostringstream will certainly allocate its buffer on the heap. When you call the str() method to retrieve the final result, it will have to make another copy. So you will always have an extra allocation. Note that std::format still returns a std::string (which might allocate memory, depending on the size of the string), but that doesn't matter if it is going to be moved anyways. If you want to write into an existing buffer, you can use std::format_to_n as a modern replacement for snprintf.
  - spacechild1 5y ago
    > 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!
- jcelerier 5y ago
  that's absolutely untrue in a lot of cases: https://stackoverflow.com/questions/36392583/is-an-unordered-map-really-faster-than-a-map-in-practice https://stackoverflow.com/questions/36392583/is-an-unordered... of course one can always find faster, drop-in replacement libraries: https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/ https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-o... e.g. replacing std::unordered_map with robin_hood::hash_map makes the above C++ code go from 1.2 seconds to 0.5 seconds on my machine (std::map is around 1.3/1.4 seconds for libstdc++). (though as others said, this test is in big part a test of std::string performance... replacing strings by int make times go down to ~0.1s here)

nikita2206 5y ago

Last time I checked, that was around PHP 7.0, it was using chaining for its hash table implementation. One notable thing was that its hash table was also using a more optimal array impl (no hashing) if you were only using numerical consecutive keys starting from zero.

masklinn 5y ago
> that was around PHP 7.0 7.0 is when php switched to open addressing: https://www.npopov.com/2014/12/22/PHPs-new-hashtable-implementation.html https://www.npopov.com/2014/12/22/PHPs-new-hashtable-impleme...
- nikita2206 5y ago
  Interesting, I definitely missed some of that, didn’t know about replacement of doubly linked list with arData array for maintaining insertion order. It does still use chaining though, just not with the classical pointers and instead with indexes into an array but indirection is still there for collision cases.
  - deleted 5y ago
    [deleted]
habibur 5y ago
> Last time I checked, that was around PHP 7.0, it was using chaining for its hash table implementatio Chaining was from php 5.

masklinn 5y ago

> Rust : You’re using the default hash function, which is SipHash 1-3, which is known to be quite slow. Not horrendously so but it was picked for attack resistance. If you need high hashmap performances and control input (or have a rather safe type) it’s pretty common knowledge that you should replace the hash function with something like fnv or fx. You’re also allocating a ton in a hot loop, also a known mispattern. I’d expect C++ to also be greatly affected there.

fl0ki 5y ago
My experience with fx has been very mixed and I don't think it's a safe default recommendation. It can often outperform fnv and wyhash because it does so little, but it can also greatly underperform once it's used in a hash table because it can cause a lot of conflicts for some types of keys, especially after modulo. This can be much slower than just having a slightly slower hash function, because the equality function will be called against many more candidates, potentially with each requiring one or more uncached fetches from main memory. I now recommend wyhash more often than not, and sometimes fnv can beat that. wyhash has the substantial advantage that it can also be made attack-resistant with a seed given to the builder, with much less overhead than sip. My most recent problematic use cases for fx were all to do with hashing just one or two scalar integers per key. Its few per-word instructions weren't nearly enough to get a good distribution when there were only 1-2 words (on a usize=u64 target). Even hacking in fmix64 from Murmur3 helped a ton, but made it no faster than wyhash in the end, and harder to reason about. I ended up using wyhash for some keys and fnv for others. In any case, nobody should switch hash functions without evaluating performance on full-sized realistic production data. You can easily end up with bad overall hash table performance because of poor distribution with your real keys. Microbenchmarks tend to miss this, especially if they do not create real-sized and real-shaped key sets. Then all you see is the hash function performance, which is misleading if it results in poor overall table performance, which is what happened to me with fx in particular. I think a lot of people choose fx based on such microbenchmarks and assume its distribution is good enough to scale out, but this should not be assumed, only tested. You might also see surprising effects from cache locality when testing tables big enough that they don't fit in cache, and if this matters for your workload then you definitely want to account for that in your choice of hash table data structure.

singron 5y ago

Wow. That php program is fast! I was skeptical for much the same reasons as the other commentators. But I took the rust version, packed the strings into u128, eliminated the allocations in the loop, --release, lto, codegen-units=1, target-cpu=native (basically all the tricks to make it fast). I tried FxHashMap, AHashMap, and hashbrown, but they didn't make much difference with the other optimizations (and FxHashMap was significantly slower). Even with all that, the php version was still 2x faster. And it truly is due to the hashtable implementation itself.