Is libiberty's splay-tree.c really a splay tree?

[Michael Matz]

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.