Hacker News Reader

Comment by willvarfar | Hacker News Reader

> 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.

View on HN

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?

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.

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.)

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..

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

Reply on news.ycombinator.com