Faster HashMap implementation (original) (raw)

Alex Yakovlev alex14n at gmail.com
Tue Jun 9 14:43:26 UTC 2009

Doug,

On Tue, Jun 9, 2009 at 4:09 PM, Doug Lea <dl at cs.oswego.edu> wrote:

Alex Yakovlev wrote:

entrySet() iterator which is very expensive.

Very big speedup would be to reuse Entry object, We had originally done this in a few classes. The Iterator spec even allows it. However, most usages ignore that part of the spec, and it led to a bunch of bug reports, so now all Entry iterators for classes using non-Entry-based representations create new ones. When running on the -server compiler this is not a huge loss, but it hurts noticeably using -client. BTW, when checking performance, do always run both, and also run across multiple machines. Especially for hash tables, there are usually interactions with processor-level properties.

FYI: I've run MapCheck with -XX:+DoEscapeAnalysis "Iter Entry" got very significant boost, almost 10x but "Iter EntrySet contains" did not (in source code entry object is passed into contains method thus cannot be stack-allocated).

I'll note testing ClientVM too, thanx mentioning it.

Still, there probably needs to be a better effort to

approximately match current space consumption in these cases.

I currently have no idea how to do that, anyway this is not a major issue.

BTW, on your last message on memory consumption, object header is not one word, I don't remember exaclty but in memory analyzer I saw ~12 bytes header on 32-bit JVM and ~20 bytes on 64-bit.

Google search says about 8 bytes on 32bit and 16 on 64: http://kohlerm.blogspot.com/2008/12/how-much-memory-is-used-by-my-java.html maybe my data was greater because of alignment.

Currently I've changed default capacity from 16 to 4, with 0.75 load factor it's exactly 3 elements you wrote about and total memory is about ~60 bytes, approx. same as current HashMap.

It strikes me that there might be a bigger win available

here by using some hybrid strategy based on IdentityHashMap-like single-indirect (i.e., usually at most a single cache miss) for collision-free accesses but using a variant of your clever packed-indices under collisions. I might try this out someday.

Interesting, I'm looking forward to see it. On a little bit of preliminary exploration, it might be better yet to use something like ternary tries for collision/overflow. It might be a while before I get to this though.

Well. I was curious enough myself to write some proof-of-concept code to test this approach: http://github.com/alex14n/CompactHashMap/blob/8f935e1b5fc7c673e04c93eca2402aada5137b39/java/HybridHashMap.java

There are a lot of to do: Map interface is not implemented, no iterators, no key removal, resize is very slow, management of overflow data can be done several ways, etc.

But current version shows ~10% performance improvement in reading existing mappings over both HashMap and my map. Misses are slower but is approximately the same as HashMap.

or you mean iterateFirst/iterateNext methods?

Their only purpose is to simplify LinkedMap and reuse code, but maybe having different iterators will give some speedup, but it's just one virtual call - you think it's really that bad? But hence it could not be inlined by HotSpot...

Right. Overridden virtual calls inside iterators usually hurt enough to avoid, but it is worth empirically checking.

I did a bit of testing and there were no significant speedup, but I was testing ServerVM. But I might do it someday anyway.

I was thinking if it would be possible to make concurrent

implementation based on AtomicIntegerArray with CAS/retries, but there are some problems I cannot solve.

Cliff Click's hash table (http://sourceforge.net/projects/high-scale-lib/) does something along these lines. The tradeoffs involved here only sometimes seem to win out over current ConcurentHashMap.

Honestly I don't think that array-based approach can be bettter than current concurrent implementation since there'll be more retries because of more competition over the same array index compared to current possibility just to call new to create new object, so I see no reason even to try. Maybe I'll change my mind over time.

Alex -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20090609/6a79721c/attachment.html>

More information about the core-libs-dev mailing list