Re: Splay Tree

[Ian Blanes <ian at gentemsn dot com>]

On Sun, 9 Jul 2006, Roger Sayle wrote:
> Interesting.  Richard Guenther's post for the above change, which was
> based upon a previous proposal by Brian Makin, suggested that this
> patch reduced the compile-time of his tramp3d benchmark by 1%.
> http://gcc.gnu.org/ml/gcc-patches/2005-11/msg00294.html

I realized that 3 orders of magnitude of diference wasn't a very realistic 
benchmark. So I reviewed it. I found that I forgot some profiling code 
that was biasing the result of the revision 106584, and that the pice 
of splay tree usage used to perform the benchmark wasn't so representative 
of the whole bootstrap. So the previous benchmark wasn't accurate at all.

That said, I rebuild a benchmark this time with full traces of splay tree 
usage during tramp3d (380mb) compilation and gcc bootstraping(1gb).
And I did the benchmarking again. This time with the original code, with 
the revision 106584 code and with the proposed by Brian Makin (with a 
few changes). Thus I have been able to reproduce the speed improvement 
with the Richard Guenther's patch.

I also noticed that the code sent by Brian Makin is slightly better than 
Revision 106584 and that not pushes down the root node more than 2 levels,
which can prevent that some rare cases perform bad.

bootstrap

Original
real 61.630s
user 61.010s
sys   0.620s

Revision 106584
real 59.660s
user 59.000s
sys   0.660s

New
real 58.910s
user 58.240s
sys   0.670s

tramp3d

Original
real 26.680s
user 26.350s
sys   0.340s

Revision 106584
real 26.010s
user 25.660s
sys   0.340s

New
real 25.700s
user 25.340s
sys   0.360s

ian

Attachment: splay-tree.patch
Description: Text document