This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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:

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 :)


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]