[concurrency-interest] NavigableMap implementation bugs

[Osvaldo Pinali Doederlein]

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