Jimmy, Nathan, all, Do you know real applications which suffer from Sergey's implementation? Are there any broken use cases or failed tests?
Thanks. On Wed, Mar 19, 2008 at 3:17 AM, Nathan Beyer <[EMAIL PROTECTED]> wrote: > On Tue, Mar 18, 2008 at 4:18 AM, Sergey Kuksenko > <[EMAIL PROTECTED]> wrote: > > Hi Jimmy, > > > > I am really sorry for my long silence. > > > > > > > Does this cause a little confliction with spec, which annouced the > TreeMap > > is Red-Black tree based? > > How it can be checked? There are no way to check if three is RB tree > > outside. > > What we have it is TreeMap interface which completely satisfied to > > specification. > > RB-tree of not RB-tree can't be checked with public interface. > > True, but in this case, TreeMap isn't conceptually an interface, it's > an implementation and users are going to expect performance and > behavior that's consistent with the javadoc [1] and RI. If that's in > question in anyway, then we should avoid it. Optimizations on > implementation classes that declare their algorithms shouldn't change > the underlying algorithms; they should stick to things like reducing > memory overhead, reducing class complexity, reducing stack depth and > the like. > > In my opinion, a Map implementation that doesn't use an RB tree isn't > java.util.TreeMap and is the realm of projects like > commons-collections. > > -Nathan > > [1] http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html > > > > > > > > > > This algorithm works very well on small number of pairs (as we see, > 4%-10% > > improvement ), but will it pause huge regression if the number of pairs > > grows to a great number? > > > > I've based my implementation on the following steps: > > 1. small array is always faster then tree on all operations. > > 2. If we create Tree of small arrays we will get benifits on tree sizes. > > > > And the latest fact is proved by my measurements. > > I am really want to collect all my data and share it here. But, please, > > expect some delay in this. > > > > > > > > > I have a simple idea here, is it possible to just to apply only binary > > search array when total size of the tree is small (e.g, small than 64) and > > change it to RB-tree aglorithm(rebuild a RB-Tree) when the size exceed the > > bar? > > > > If you check history of TreeMap you can find that this first (initial) > idea > > was implemented (probably somewhere in August/September 2007 I don't > > remember exactly when). > > After that I was woking on expanding thiso idea to all tree sizes. > > > > -- > > Best regards, > > --- > > Sergey Kuksenko. > > > -- With best regards, Alexei
