[PING] Splay tree speedup

[Richard Guenther]

On 11/6/05, Mark Mitchell <mark@codesourcery.com> wrote:
> Richard Guenther wrote:
> > On Fri, 4 Nov 2005, Richard Guenther wrote:
> >
> >
> >>Considering we're open again for bugfixes, can someone look over the
> >>alternatives to speedup the libiberty splay_tree implementation?
> >>Thread starts at
> >>
> >>http://gcc.gnu.org/ml/gcc-patches/2005-10/msg00762.html
> >>
> >>it shaves off some 1% of tramp3d compile-time through improving
> >>ipa-type-escape analysis use of splay trees.
> >
> >
> > It was suggested to ping you, DJ and Mark directly about this patch,
> > as you, Mark, seem to be the original author of splay_tree.  We might
> > consider either of the two patches for 4.1 as a partial fix for the
> > compile-time regressions.
>
> First, what patch am I supposed to reviewing?  This one:
>
> http://gcc.gnu.org/ml/gcc-patches/2005-10/msg00832/p
>
> or the one by the original submitter?

I did my version because I believed the original submitter did not
have a copyright assignment and I like to have the improvement
for 4.1.  Otherwise I have no preference, but I didn't look into the
original submitters version too closely.

> Richard, your patch looks correct to me.  However, I'd like to
> understand why this is better than the current version.  Is it because
> we avoid recursion in splay_tree_splay_helper?  That seems like a good
> improvement, but I'd like to make sure we understand where the
> performance improvement is originating.

Yes, the increased performance should be basically due to the avoided
recursion and maybe better temporal cache locality due to the reversed
direction of the splay.

Richard.