Hi, 2008/3/18, Sergey Kuksenko <[EMAIL PROTECTED]>: > 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. > > > > 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. > >
Yes, I believe so, it may be hard to test if the TreeMap is based on a typical R-B Tree. I just doubt it may break the spec if we use another mechanism instead former RB Tree. However current code is based on RB tree and small array, I have no idea if we can call it as an alternative-RB-tree algorithm? My main concern is performance, as it appear so good on SPECjbb, will it turn a bit slower in some other programs or benchmarks than the typical RB-tree? Typical RB-tree algorithm has proved its own benefits on some fields. And I believe java programmers may choose TreeMap instead of Arrays for their own propose of performance, in some fields that only typical RB-tree is best? I really have no idea or data about this, but as you say "small array is ALWAYS faster than tree on all operations", I think it is OK then (if we find some other problem, let's restart this thread) :) > > > 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. > -- Best Regards! Jimmy, Jing Lv China Software Development Lab, IBM
