Soory, I did typo "Generally it was lacky coincidence" Should be read as "Generally it was lucky coincidence"
On 3/19/08, Sergey Kuksenko <[EMAIL PROTECTED]> wrote: > > Hi Jimmy, > > > 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? > > Generally it was lacky coincidence that it gave some small benefit on > SPECjbb. > In general, I've realized in set of experiments that small array is better > then small tree. > After that I've created a RB-tree of small arrays and realized that such > representation is faster then simple tree on operations not only like get, > but including such operations like put and delete. > I have a set of practical measurements which show that such is faster even > for really big trees. > The question is that I am going to write article about that, that is why I > didn't put my results here yet. > > > 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 > > > > > -- > Best regards, > --- > Sergey Kuksenko. > Intel Enterprise Solutions Software Division. > -- Best regards, --- Sergey Kuksenko. Intel Enterprise Solutions Software Division.
