This is the mail archive of the
mailing list for the GCC project.
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.
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 :)