13 ms·

A Tale of Java Hash Tables

128 points by nomemory 5y ago

RcouF1uZ4gsC 5y ago
> But, as described here, the decision to use Separate Chaining vs. Open Addressing is not unanimously accepted by programming languages designers. For example, in python, ruby, and rust, the standard hash tables are implemented using Open Addressing, while Java, go, C#, C++ are all more conservatory and use Separate Chaining. I think with regards to C++ using separate chaining is a legacy decision made in the late 1990's. I think back then, the CPU vs memory speed difference was not as big, so pointer chasing wasn't considered that big of a deal. In addition, this was the days of 32-bit systems with MB's or RAM so having separate, smaller allocations was seen as better than having one large one (see for example deque). Nowadays, with a much bigger relative performance penalty for accessing memory as well as 64-bit systems with GB's or RAM, I think people are moving to open addressing (for example Rust, as well as Google and Facebook's hash table implementations) unless you need pointer stability. The fact that std::unordered_map more or less mandated separate chaining is seen as something that holds the standard library back in terms of performance, hence the competing implementations from Google and Facebook.
- dpratt 5y ago
  Granted, it’s a micro benchmark without a lot of context, but wouldn’t the conclusion that the default HashMap implementation is, on average, faster than all the open addressing implementations contradict this conclusion?
  - nomemory 5y ago
    For me it was faster on average and with less variance. But the micro-benchmarks are flawed by default, so I believe it's room to improve them. Also maybe there are some tricks that can be done, to have a faster Open Addressing implementation in Java. PS: I've also tried Cuckoo Hashing and Hopscotch and they were also slower, but haven't managed to document my findings.
    - dpratt 5y ago
      FYI, if you're the author of the article, you deserve some recognition. It's extremely well written, concise and detailed. I've sent it out to my entire team as recommended reading.
- nomemory 5y ago
  Exactly. Looking at some discussions the open-jdk team had, they decided to continue with Separate Chaining. I don't have the link, but then I got interested to see how some Open Addressing (nothing fancy) will behave in Java, so this is the reason I've written this "article". Unfortunately I coudln't beat HashMap with the "classic" approach, but I got close. I am curious to see a better implementation that brings more engineering tricks on the table.
  - RcouF1uZ4gsC 5y ago
    > Unfortunately I coudln't beat HashMap with the "classic" approach, but I got close. I am curious to see a better implementation that brings more engineering tricks on the table. I think one of the big advantages of using open addressing is memory locality. Since it is harder to control memory layout in Java (and relies on the optimizer/JIT to optimize common patterns) I wonder if you are getting the full benefit of open addressing in Java. In addition HashMap is standard and the Java compiler/optimzer/JIT can make certain assumptions about how it is used which may enable certain optimizations. Also, a lot of the heuristics for optimization likely used a lot of profiling over the years, and because HashMap is so widely used, it is likely that common usages of HashMap are reflected in the profile data and thus the optimization heuristics.
    - nomemory 5y ago
      Exactly, in Java i couldn't even inline my functions, and had zero control over the underlying memory layout.
      - JanecekPetr 5y ago
        > i couldn't even inline my functions You could, manually :). Either way if they're hot, they're inlined. One common trick for open-addressing maps in Java I don't see in your implementations is to have an array of keys zipped with values (or two arrays, one for keys, one for values) instead of array of Entries. This improves locality and indirection a bit. Obviously more is needed for even more speed. (Mandatory "in the future it will be better": Valhalla is coming in a few years, that's when we'll have much more control over the memory layout.)
- Koffiepoeder 5y ago
  Could someone explain to me in a clear and high level fashion what exactly pointer stability (or pointer instability for that regards) entails? I've watched some of the cppcon talks on the google hashtable implementation [0] and in that talk Matt Kulukundis also mentioned it affecting the adoption rate, but I always failed to really grasp the concept and its implications. Google searches also ended up rather fruitless to be honest. [0]: https://youtube.com/watch?v=ncHmEUmJZf4 https://youtube.com/watch?v=ncHmEUmJZf4
  - gpderetta 5y ago
    If you allocate your objects inline in your internal table, rehashing will invalidate existing references to those objects as they will need to be copied into the new, larger, table. Allocating every object separately in its own node as used in chaining implementations guarantee that the object location is stable (i.e doesn't change), but in addition to making iteration slower it requires separate allocation for each object.
  - UncleMeat 5y ago
    An operation maintains Pointer Stability means if you take a pointer to an element in a data structure and then execute that operation, the pointer is still valid and pointing to the same data. Think about how vector would be implemented under the hood. What happens if you delete an element? Does it shift down all of the elements after it? If you do that, the objects have literally moved in memory. Any pointer that points into those memory locations is now invalid. That's a problem if you wanted to hold onto pointer to elements. But if you declare that your interface has certain pointer stability guarantees then suddenly your implementation is massively constrained. Now your vector implementation will have big gaps that you need to deal with and will waste a ton of memory if you add and remove many elements.
    - Koffiepoeder 5y ago
      So, am I correct if I then put it as following? Pointer instability means that it is undefined behaviour to: 1) store (both on stack and heap) the pointer address to a value element outside of its respective container 2) then modify the container's content 3) then thereafter use the stored pointer address This implies that: - containers without pointer stability require pass-by-value (or a pointer to a temp copy) to be used for its values after accessing them OR - containers without pointer stability require absolute immutibility of the container to guarantee runtime safety OR - containers without pointer stability require "relative" immutability during the existence of a pointer to a value element to guarantee runtime safety. Note that I think this last option is a bad idea, because it requires multithreaded blocking/synchronization of the container and is also easy to encapsulate wrongly, leading to UB.
mnw21cam 5y ago
> in practice, nobody will use a hash function that returns a constant integer How much do you want to bet on that?
- nomemory 5y ago
  I consider myself an optimist.
- michaelcampbell 5y ago
  Not quite that bad, but the hash algo for ... function lookup? (the exact usage escapes me) in PHP was "strlen". Yup, the length of the function name was the hash value.
  - nomemory 5y ago
    Maybe it was even more terrible, because it tried to be "smart".
  - bruce343434 5y ago
    yes, the early php stdlib functions sometimes had mangled names by replacing a "to" with 2, and maybe shortening some names but not others due to this reason. At least, that's what the creator of php says here: https://news-web.php.net/php.internals/70691 https://news-web.php.net/php.internals/70691 Also fun read: https://eev.ee/blog/2012/04/09/php-a-fractal-of-bad-design/ https://eev.ee/blog/2012/04/09/php-a-fractal-of-bad-design/
- jkaptur 5y ago
  I did this many years ago. It wasn't production code and I was prioritizing expediency. The class had rather complicated equals() semantics, I wanted "set" and "map" data structures, and I knew there would never be very many objects.
- omegalulw 5y ago
  > How much do you want to bet on that? Isn't it a rather safe bet since most people won't roll their own hash functions anyway.
zz865 5y ago
I like the link to Spotify profile, seems a much better way to get to know someone.
SloopJon 5y ago
The post quotes a comment from the Python source code for the dict object: This is done by initializing a (unsigned) vrbl "perturb" Is "vrbl" a term I should know, or just a prvrs abbrvtn for variable?
- raymondh 5y ago
  It's an acronym for "virtual retractable binary link", a concept well known to perturbation specialists.
- comex 5y ago
  It’s just an abbreviation.
habibur 5y ago
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.
willvarfar 5y ago
> I am yet to find an Open Addressing implementation that outperforms HashMap<K,V> by a significant margin I have a performance-critical framework that went from Java’s Map to Trove (http://trove4j.sourceforge.net/html/overview.html http://trove4j.sourceforge.net/html/overview.html) and now uses FastUtil (https://fastutil.di.unimi.it/ https://fastutil.di.unimi.it/). For my use cases, these massively outperform the built-in java Maps and Sets. It would be interesting to include these in the benchmark. A quick googling finds plenty of comparisons that are a few years old now but I can’t find a current up to date java map/set benchmark.
- JanecekPetr 5y ago
  That's because they used primitives, no? In that case also look at some other options: https://www.reddit.com/r/java/comments/r0b9o9/a_tale_of_java_hash_tables/hlrs01u/?utm_source=reddit&utm_medium=web2x&context=3 https://www.reddit.com/r/java/comments/r0b9o9/a_tale_of_java.... While I still think Koloboke in general is the fastest, I do agree that the difference between it and fastutil will not be very big. Or was this for Object/boxed primitives, too?
  - willvarfar 5y ago
    If you are working with primaries then the unboxed collections are a big boon. My code often uses objects though, so I use a lot of the fastutil Object2ObjectMap etc. There are two areas that are important in my use case: * the performance of normal get/computeIfAbsent/forEach etc. FastUtil has for example fast iterators avoid allocating Map.Entry etc. * the memory usage. The total footprint is important because I actually dimension VMs based on stuff. But garbage collection minimization is also really important.
    - JanecekPetr 5y ago
      Nice. Thanks. (For other viewers, all the non-standard maps I'm aware of are trying to avoid allocating those pesky Map.Entry objects, that's why they generally take up much less memory.)
- 5y ago
i3oi3 5y ago
Some areas that I explored more deeply in my Earlier Days w.r.t hash tables (Java hash tables, at that) that aren't covered by the analysis are: * Memory footprint and GC load * Write performance (especially characterizing fast-path vs. rebalance times) * Loading vs. performance tradeoffs (can the table perform well with 80% occupancy? 99%?) * Small-table utilization. If some of the implementations consume substantially less memory and/or GC churn while having largely indistinguishable lookup performance, then they're a win for value. This is one place that open addressing can win. For the libraries we were writing, we didn't know if consumers would be stuffing in one element (the most common case) or millions of elements (uncommon but important), so we ended up implementing a clever abstraction that would start with a pointer to the single object, then replace it with a hash table when the second element was added. Since we used hash tables like country doctors prescribe aspirin, it reduced the heap footprint of the server by ~30%. Of course, Hansen's Law states "Clever is the opposite of maintainable," and that definitely applied here.
- nomemory 5y ago
  Didn't have time to write about it, but I've used a GCProfiler as well. With a few exceptions, all the 5 implementations are comparable.
bjourne 5y ago
So the reason HashMap isn't as fast as it could be is because it converts buckets with linked lists to red-black trees when it reaches some threshold. The reason it does that is because in any hashing scheme, specifically crafted input can cause O(n) lookup times. It is reasonably trivial to take advantage of this to launch DOS attacks. Your web server parses HTTP headers with a hash table? Might very well be exploitable. Same thing with parsing JSON objects using hash tables. I posit that in practice there are very few scenarios in which the extra performance of an "optimized" hash table outweighs the benefits of having one that is not vulnerable to hash-flooding attacks.
- vlovich123 5y ago
  You can always use a cryptographic hash of the key instead of an untrusted key. Linked list buckets are terrible for cache locality anyway.
  - bjourne 5y ago
    Can you show me an implementation of a high-performance hash table with a cryptographic key that is not vulnerable to hash-flooding?
    - goldenkey 5y ago
      All you have to do is have the hashmap be HashMap<K,V,CryptographicKey> and never reveal the key, or seed it from randomness? One can use an HMAC or some other method to use the key to derive hashes.
      - bjourne 5y ago
        Is there as HashMap overload with three type parameters? Yes, you can use a cryptographic hash function like SipHash does but it wouldn't perform has well as HashMap.
        vlovich123 5y ago
kasperni 5y ago
As part of project Valhalla they did some performance tests with open addressing as well [1]. Result: java.util.HashMap was the best performing implementation most of the time. [1] https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/hash.html https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/has...
raymondh 5y ago
If the OP has time, it might be nice to experiment with the hash table technique used by sets in Python. It has a variant of open addressing the runs several linear probes before jumping to another location in hash table. The premise is that probing consecutive memory addresses is cheap because of cache locality and because the address computation is a simple increment. This should be cheaper than resolving hash collisions with additional random probes or by chasing linked list references to random memory locations for each link. https://github.com/python/cpython/blob/f840398a5fd8741653c26eb8641c48656c9800d4/Objects/setobject.c https://github.com/python/cpython/blob/f840398a5fd8741653c26...
slaymaker1907 5y ago
I've read that HashMap will use a tree if a single bucket gets too large so long as the keys are comparable.
mgaunard 5y ago
Java, the language where linear probing is considered high-tech. What's gonna happen once they discover robinhood hashing?
- nomemory 5y ago
  The point of the article was too prove that it's hard to do Open Adressing in Java and beat HashMap performance, that uses Separate Chaining. The article contains also a Robin Hood implementation that overall works worse than HashMap. If you can give something recommendation on how to improve it I would forever in debt.
  - mgaunard 5y ago
    use a programming language where you have control on memory layout.
    - iams 5y ago
      you mean like Java? https://docs.oracle.com/en/java/javase/16/docs/api/jdk.incubator.foreign/jdk/incubator/foreign/package-summary.html https://docs.oracle.com/en/java/javase/16/docs/api/jdk.incub...

128 points by nomemory 5y ago

> But, as described here, the decision to use Separate Chaining vs. Open Addressing is not unanimously accepted by programming languages designers. For example, in python, ruby, and rust, the standard hash tables are implemented using Open Addressing, while Java, go, C#, C++ are all more conservatory and use Separate Chaining. I think with regards to C++ using separate chaining is a legacy decision made in the late 1990's. I think back then, the CPU vs memory speed difference was not as big, so pointer chasing wasn't considered that big of a deal. In addition, this was the days of 32-bit systems with MB's or RAM so having separate, smaller allocations was seen as better than having one large one (see for example deque). Nowadays, with a much bigger relative performance penalty for accessing memory as well as 64-bit systems with GB's or RAM, I think people are moving to open addressing (for example Rust, as well as Google and Facebook's hash table implementations) unless you need pointer stability. The fact that std::unordered_map more or less mandated separate chaining is seen as something that holds the standard library back in terms of performance, hence the competing implementations from Google and Facebook.

dpratt 5y ago
Granted, it’s a micro benchmark without a lot of context, but wouldn’t the conclusion that the default HashMap implementation is, on average, faster than all the open addressing implementations contradict this conclusion?
- nomemory 5y ago
  For me it was faster on average and with less variance. But the micro-benchmarks are flawed by default, so I believe it's room to improve them. Also maybe there are some tricks that can be done, to have a faster Open Addressing implementation in Java. PS: I've also tried Cuckoo Hashing and Hopscotch and they were also slower, but haven't managed to document my findings.
  - dpratt 5y ago
    FYI, if you're the author of the article, you deserve some recognition. It's extremely well written, concise and detailed. I've sent it out to my entire team as recommended reading.
nomemory 5y ago
Exactly. Looking at some discussions the open-jdk team had, they decided to continue with Separate Chaining. I don't have the link, but then I got interested to see how some Open Addressing (nothing fancy) will behave in Java, so this is the reason I've written this "article". Unfortunately I coudln't beat HashMap with the "classic" approach, but I got close. I am curious to see a better implementation that brings more engineering tricks on the table.
- RcouF1uZ4gsC 5y ago
  > Unfortunately I coudln't beat HashMap with the "classic" approach, but I got close. I am curious to see a better implementation that brings more engineering tricks on the table. I think one of the big advantages of using open addressing is memory locality. Since it is harder to control memory layout in Java (and relies on the optimizer/JIT to optimize common patterns) I wonder if you are getting the full benefit of open addressing in Java. In addition HashMap is standard and the Java compiler/optimzer/JIT can make certain assumptions about how it is used which may enable certain optimizations. Also, a lot of the heuristics for optimization likely used a lot of profiling over the years, and because HashMap is so widely used, it is likely that common usages of HashMap are reflected in the profile data and thus the optimization heuristics.
  - nomemory 5y ago
    Exactly, in Java i couldn't even inline my functions, and had zero control over the underlying memory layout.
    - JanecekPetr 5y ago
      > i couldn't even inline my functions You could, manually :). Either way if they're hot, they're inlined. One common trick for open-addressing maps in Java I don't see in your implementations is to have an array of keys zipped with values (or two arrays, one for keys, one for values) instead of array of Entries. This improves locality and indirection a bit. Obviously more is needed for even more speed. (Mandatory "in the future it will be better": Valhalla is coming in a few years, that's when we'll have much more control over the memory layout.)
Koffiepoeder 5y ago
Could someone explain to me in a clear and high level fashion what exactly pointer stability (or pointer instability for that regards) entails? I've watched some of the cppcon talks on the google hashtable implementation [0] and in that talk Matt Kulukundis also mentioned it affecting the adoption rate, but I always failed to really grasp the concept and its implications. Google searches also ended up rather fruitless to be honest. [0]: https://youtube.com/watch?v=ncHmEUmJZf4 https://youtube.com/watch?v=ncHmEUmJZf4
- gpderetta 5y ago
  If you allocate your objects inline in your internal table, rehashing will invalidate existing references to those objects as they will need to be copied into the new, larger, table. Allocating every object separately in its own node as used in chaining implementations guarantee that the object location is stable (i.e doesn't change), but in addition to making iteration slower it requires separate allocation for each object.
- UncleMeat 5y ago
  An operation maintains Pointer Stability means if you take a pointer to an element in a data structure and then execute that operation, the pointer is still valid and pointing to the same data. Think about how vector would be implemented under the hood. What happens if you delete an element? Does it shift down all of the elements after it? If you do that, the objects have literally moved in memory. Any pointer that points into those memory locations is now invalid. That's a problem if you wanted to hold onto pointer to elements. But if you declare that your interface has certain pointer stability guarantees then suddenly your implementation is massively constrained. Now your vector implementation will have big gaps that you need to deal with and will waste a ton of memory if you add and remove many elements.
  - Koffiepoeder 5y ago
    So, am I correct if I then put it as following? Pointer instability means that it is undefined behaviour to: 1) store (both on stack and heap) the pointer address to a value element outside of its respective container 2) then modify the container's content 3) then thereafter use the stored pointer address This implies that: - containers without pointer stability require pass-by-value (or a pointer to a temp copy) to be used for its values after accessing them OR - containers without pointer stability require absolute immutibility of the container to guarantee runtime safety OR - containers without pointer stability require "relative" immutability during the existence of a pointer to a value element to guarantee runtime safety. Note that I think this last option is a bad idea, because it requires multithreaded blocking/synchronization of the container and is also easy to encapsulate wrongly, leading to UB.

mnw21cam 5y ago

> in practice, nobody will use a hash function that returns a constant integer How much do you want to bet on that?

nomemory 5y ago
I consider myself an optimist.
michaelcampbell 5y ago
Not quite that bad, but the hash algo for ... function lookup? (the exact usage escapes me) in PHP was "strlen". Yup, the length of the function name was the hash value.
- nomemory 5y ago
  Maybe it was even more terrible, because it tried to be "smart".
- bruce343434 5y ago
  yes, the early php stdlib functions sometimes had mangled names by replacing a "to" with 2, and maybe shortening some names but not others due to this reason. At least, that's what the creator of php says here: https://news-web.php.net/php.internals/70691 https://news-web.php.net/php.internals/70691 Also fun read: https://eev.ee/blog/2012/04/09/php-a-fractal-of-bad-design/ https://eev.ee/blog/2012/04/09/php-a-fractal-of-bad-design/
jkaptur 5y ago
I did this many years ago. It wasn't production code and I was prioritizing expediency. The class had rather complicated equals() semantics, I wanted "set" and "map" data structures, and I knew there would never be very many objects.
omegalulw 5y ago
> How much do you want to bet on that? Isn't it a rather safe bet since most people won't roll their own hash functions anyway.

zz865 5y ago

I like the link to Spotify profile, seems a much better way to get to know someone.

SloopJon 5y ago

The post quotes a comment from the Python source code for the dict object: This is done by initializing a (unsigned) vrbl "perturb" Is "vrbl" a term I should know, or just a prvrs abbrvtn for variable?

raymondh 5y ago
It's an acronym for "virtual retractable binary link", a concept well known to perturbation specialists.
comex 5y ago
It’s just an abbreviation.

habibur 5y ago

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.

willvarfar 5y ago

> I am yet to find an Open Addressing implementation that outperforms HashMap<K,V> by a significant margin I have a performance-critical framework that went from Java’s Map to Trove (http://trove4j.sourceforge.net/html/overview.html http://trove4j.sourceforge.net/html/overview.html) and now uses FastUtil (https://fastutil.di.unimi.it/ https://fastutil.di.unimi.it/). For my use cases, these massively outperform the built-in java Maps and Sets. It would be interesting to include these in the benchmark. A quick googling finds plenty of comparisons that are a few years old now but I can’t find a current up to date java map/set benchmark.

JanecekPetr 5y ago
That's because they used primitives, no? In that case also look at some other options: https://www.reddit.com/r/java/comments/r0b9o9/a_tale_of_java_hash_tables/hlrs01u/?utm_source=reddit&utm_medium=web2x&context=3 https://www.reddit.com/r/java/comments/r0b9o9/a_tale_of_java.... While I still think Koloboke in general is the fastest, I do agree that the difference between it and fastutil will not be very big. Or was this for Object/boxed primitives, too?
- willvarfar 5y ago
  If you are working with primaries then the unboxed collections are a big boon. My code often uses objects though, so I use a lot of the fastutil Object2ObjectMap etc. There are two areas that are important in my use case: * the performance of normal get/computeIfAbsent/forEach etc. FastUtil has for example fast iterators avoid allocating Map.Entry etc. * the memory usage. The total footprint is important because I actually dimension VMs based on stuff. But garbage collection minimization is also really important.
  - JanecekPetr 5y ago
    Nice. Thanks. (For other viewers, all the non-standard maps I'm aware of are trying to avoid allocating those pesky Map.Entry objects, that's why they generally take up much less memory.)
5y ago

i3oi3 5y ago

Some areas that I explored more deeply in my Earlier Days w.r.t hash tables (Java hash tables, at that) that aren't covered by the analysis are: * Memory footprint and GC load * Write performance (especially characterizing fast-path vs. rebalance times) * Loading vs. performance tradeoffs (can the table perform well with 80% occupancy? 99%?) * Small-table utilization. If some of the implementations consume substantially less memory and/or GC churn while having largely indistinguishable lookup performance, then they're a win for value. This is one place that open addressing can win. For the libraries we were writing, we didn't know if consumers would be stuffing in one element (the most common case) or millions of elements (uncommon but important), so we ended up implementing a clever abstraction that would start with a pointer to the single object, then replace it with a hash table when the second element was added. Since we used hash tables like country doctors prescribe aspirin, it reduced the heap footprint of the server by ~30%. Of course, Hansen's Law states "Clever is the opposite of maintainable," and that definitely applied here.

nomemory 5y ago
Didn't have time to write about it, but I've used a GCProfiler as well. With a few exceptions, all the 5 implementations are comparable.

bjourne 5y ago

So the reason HashMap isn't as fast as it could be is because it converts buckets with linked lists to red-black trees when it reaches some threshold. The reason it does that is because in any hashing scheme, specifically crafted input can cause O(n) lookup times. It is reasonably trivial to take advantage of this to launch DOS attacks. Your web server parses HTTP headers with a hash table? Might very well be exploitable. Same thing with parsing JSON objects using hash tables. I posit that in practice there are very few scenarios in which the extra performance of an "optimized" hash table outweighs the benefits of having one that is not vulnerable to hash-flooding attacks.

vlovich123 5y ago
You can always use a cryptographic hash of the key instead of an untrusted key. Linked list buckets are terrible for cache locality anyway.
- bjourne 5y ago
  Can you show me an implementation of a high-performance hash table with a cryptographic key that is not vulnerable to hash-flooding?
  - goldenkey 5y ago
    All you have to do is have the hashmap be HashMap<K,V,CryptographicKey> and never reveal the key, or seed it from randomness? One can use an HMAC or some other method to use the key to derive hashes.
    - bjourne 5y ago
      Is there as HashMap overload with three type parameters? Yes, you can use a cryptographic hash function like SipHash does but it wouldn't perform has well as HashMap.
      - vlovich123 5y ago

kasperni 5y ago

As part of project Valhalla they did some performance tests with open addressing as well [1]. Result: java.util.HashMap was the best performing implementation most of the time. [1] https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/hash.html https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/has...

raymondh 5y ago

If the OP has time, it might be nice to experiment with the hash table technique used by sets in Python. It has a variant of open addressing the runs several linear probes before jumping to another location in hash table. The premise is that probing consecutive memory addresses is cheap because of cache locality and because the address computation is a simple increment. This should be cheaper than resolving hash collisions with additional random probes or by chasing linked list references to random memory locations for each link. https://github.com/python/cpython/blob/f840398a5fd8741653c26eb8641c48656c9800d4/Objects/setobject.c https://github.com/python/cpython/blob/f840398a5fd8741653c26...

slaymaker1907 5y ago

I've read that HashMap will use a tree if a single bucket gets too large so long as the keys are comparable.

mgaunard 5y ago

Java, the language where linear probing is considered high-tech. What's gonna happen once they discover robinhood hashing?

nomemory 5y ago
The point of the article was too prove that it's hard to do Open Adressing in Java and beat HashMap performance, that uses Separate Chaining. The article contains also a Robin Hood implementation that overall works worse than HashMap. If you can give something recommendation on how to improve it I would forever in debt.
- mgaunard 5y ago
  use a programming language where you have control on memory layout.
  - iams 5y ago
    you mean like Java? https://docs.oracle.com/en/java/javase/16/docs/api/jdk.incubator.foreign/jdk/incubator/foreign/package-summary.html https://docs.oracle.com/en/java/javase/16/docs/api/jdk.incub...