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.
