[concurrency-interest] NavigableMap implementation bugs

[Joshua Bloch]

Osvaldo,

Yes, I must say that I'm surprised that my original implementation of
HashSet still stands.  It would be interesting to see what sort of
performance improvement (time and space) we could get with a freestanding
HashSet implementation.

     Josh

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
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20080609/ca58ae9a/attachment.html>