Faster HashMap implementation

[Alex Yakovlev]

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>