Hi, On Mon, 4 Jul 2011, Michael Matz wrote:
> > There were other people pointing out issues with the splay tree (but > > all w/o copyright assignment and much larger patches). > > > > I know I did the last re-write of this piece of code but it's been a > > long time ... in any case, previous reports were that the current > > implementation degenerates in some cases. > > And I also distinctly remember some actual measurements where our > current non-splay-tree is faster for a bootstrap (or similar testcases) > than a real splay tree. Couple years ago, on this list. Referenced from: http://gcc.gnu.org/ml/gcc/2006-10/msg00616.html Basically the reimplementation of richi (r106584) improved on the benchmarks (the former implementation was fairly bogus). The one from Brian Makin with some changes by Ian Barnes was only slightly better (and without copyright assignment). So it's very well possible that Richi doesn't rotate in optimal order. I think it's harmless for the average O(log n) invariants of a splay tree. Try some benchmarks :) Ciao, Michael.
