[concurrency-interest] NavigableMap implementation bugs

[Martin Buchholz]

Osvaldo, I fundamentally agree with you that
optimizing HashSet in the manner you describe
is worthwhile, but because the implementation
needs to "parallel" HashMap, it would be good
to do this after the current hacking activity on
HashMap quiesces.

Unfortunately, this kind of programming
is pure tedium - who will volunteer?

Martin

On Mon, Jun 9, 2008 at 2:09 PM, Osvaldo Pinali Doederlein
<osvaldo at visionnaire.com.br> wrote:
> Doug Lea wrote:
>>
>> I don't think so. Relaying the subset methods to the *Set classes
>> was just an implementation expediency under the mis-thought that they
>> would take care of recursive subsets etc rather than needing
>> special implementations for KeySets. But the byproduct for remove()
>> is clearly wrong so they do need separate implementations.
>>
>
> This remembers me from an old pet peeve, the fact that java.util.HashSet is
> implemented as a wrapper over java.util.HashMap. This sucks
> performance-wise, due to the additional indirections everywhere, and even
> more important, because every entry single object is larger than necessary -
> it contains a key and a value fields, but a single field would be necessary
> for HashSet. If you have a Set with millions of entries, the overhead of one
> useless pointer per entry is significant. Plus, the wrapping implementation
> uses a dummy, fixed Object instance as the value for all entries - and this
> may create another subtle performance problem: large numbers of
> "cross-space" references in the heap. I know that in most GCs only
> old-to-young refs are evil, but it seems that in some GCs any cross-space
> reference is bad (requires remset tracking), like Detlef et al's new
> "Garbage-First" collector (if I understood it).
>
> Back in J2SE1.2 time, the runtime savings from the wrapping implementation
> could be significant... but, today? The HashMap* classes inside the latest
> rt.jar are 18,5Kb total (uncompressed), versus 3Kb from HashSet. That's a
> 12Kb of space saving, plus some small saving in JIT time too. I'd say that
> this is an irrelevant advantage, even in JavaME. The performance bonus of a
> tuned HashSet, however modest, would certainly be much more significant. I
> know it's ugly from a maintenance POV to have two large classes that will be
> 90% identical, but to paraphrase the movie Some Like It Hot, nothing is
> perfect...
>
> A+
> Osvaldo
>
> --
> -----------------------------------------------------------------------
> Osvaldo Pinali Doederlein                   Visionnaire Informática S/A
> osvaldo at visionnaire.com.br                http://www.visionnaire.com.br
> Arquiteto de Tecnologia                          +55 (41) 337-1000 #223
>
>