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: Splay Tree

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%.

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.


real 61.630s
user 61.010s
sys   0.620s

Revision 106584
real 59.660s
user 59.000s
sys   0.660s

real 58.910s
user 58.240s
sys   0.670s


real 26.680s
user 26.350s
sys   0.340s

Revision 106584
real 26.010s
user 25.660s
sys   0.340s

real 25.700s
user 25.340s
sys   0.360s


Attachment: splay-tree.patch
Description: Text document

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