A Tale of Java Hash Tables

https://www.andreinc.net/2021/11/08/a-tale-of-java-hash-tables

by nomemory • 5 years ago

128 87 5 years 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.

dpratt2• 5 years 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?

nomemory10• 5 years 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.

nomemory10• 5 years 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.

RcouF1uZ4gsC2• 5 years 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.

vips7L2• 5 years ago

https://cr.openjdk.java.net/~skuksenko/valhalla/hashmaps/has...

Might be what you're looking for?

Koffiepoeder2• 5 years 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

gpderetta• 5 years 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• 5 years 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.

mnw21cam• 5 years ago

in practice, nobody will use a hash function that returns a constant integer

How much do you want to bet on that?

nomemory10• 5 years ago

I consider myself an optimist.

michaelcampbell• 5 years 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.

nomemory10• 5 years ago

Maybe it was even more terrible, because it tried to be "smart".

bruce343434• 5 years 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

Also fun read: https://eev.ee/blog/2012/04/09/php-a-fractal-of-bad-design/

jkaptur• 5 years 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• 5 years 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• 5 years ago

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

SloopJon• 5 years 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?

raymondh2• 5 years ago

It's an acronym for "virtual retractable binary link", a concept well known to perturbation specialists.

comex• 5 years ago

It’s just an abbreviation.

habibur3• 5 years 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")
      }
  }

dragontamer6• 5 years 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.

habibur3• 5 years ago

unordered_map performs even worse than map. Tried it.

nikita22062• 5 years 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.

masklinn3• 5 years 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-impleme...

habibur3• 5 years 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.

masklinn3• 5 years 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• 5 years 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• 5 years 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.

willvarfar3• 5 years 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) and now uses FastUtil (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.

JanecekPetr6• 5 years 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.... 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?

willvarfar3• 5 years 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.

usefulcat2• 5 years ago

I can't really speak about Java, but for C++, std::unordered_map (which uses separate chaining) gets destroyed (performance-wise) by any number of alternate hash map implementations that use open addressing. There's just no question that open addressing is inherently faster for most use cases.

To be fair, unlike std::unordered_map, the open addressing implementations don't come with a guarantee that they won't move the items in the hash table. But in practice that doesn't really matter anyway, since you could always use unordered_map<unique_ptr<T>> instead of unordered_map<T>. But, I digress..

willvarfar3• 5 years ago

The moment you have value types and stack passed small structs you start beating Java pretty hard in precisely the collections area.

i3oi3• 5 years 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.

nomemory10• 5 years 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.

bjourne3• 5 years 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.

vlovich1232• 5 years 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.

bjourne3• 5 years ago

Can you show me an implementation of a high-performance hash table with a cryptographic key that is not vulnerable to hash-flooding?

rurban• 5 years ago

The tree conversion does not affect performance at all. It is only done on DOS attacks, which almost never occur. Counting the collisions is almost for free.

The optimizations are cache friendly open-addressing with linear probing, storing the hash, and power of 2 sizes. Another usual optimization would be a sorted array instead of the linked list.

q-big• 5 years ago

Your web server parses HTTP headers with a hash table? Might very well be exploitable.

That is why you shouldn't use hash tables in code that might (even potentially) become a target for DoS attacks.

nomemory10• 5 years ago

You can have hash tables that cannot be targeted by DoS attacks.

You can use a family of hash functions and seed the hash table instance with a key.

The attacker won't be able to do make assumptions regarding collisions because he doesn't have access to the initial key.

kasperni• 5 years 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/has...

raymondh2• 5 years 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/f840398a5fd8741653c26...

slaymaker1907• 5 years ago

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

mgaunard2• 5 years ago

Java, the language where linear probing is considered high-tech.

What's gonna happen once they discover robinhood hashing?

nomemory10• 5 years 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.

mgaunard2• 5 years ago

use a programming language where you have control on memory layout.

A Tale of Java Hash Tables

Related Stories