This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Splay Tree
- From: Roger Sayle <roger at eyesopen dot com>
- To: Ian Blanes <ian at gentemsn dot com>
- Cc: gcc at gcc dot gnu dot org
- Date: Sun, 9 Jul 2006 09:09:59 -0600 (MDT)
- Subject: Re: Splay Tree
Hi Ian,
On Sun, 9 Jul 2006, Ian Blanes wrote:
> I've been recently looking at the splay tree implementation. I've noticed
> that this revision http://gcc.gnu.org/viewcvs?view=rev&revision=106584
> does a strange splaying. It does a bottom up splaying but starting at the
> root (not the same that top down). It works but performs worst.
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 appreciate that you've also benchmarked "typical" splay tree usage
during a GCC boostrap. Any chance, that you could repeat your experiment
but instead evaluate the behaviour of splay tree usage during a tramp3d
compilation: http://www.suse.de/~rguenther/tramp3d/
Whilst your analysis demonstrates that splay_tree_splay is behaving
curiously, I'm also interested in resolving the reported performance
benefits of the different implementations.
Thanks in advance,
Roger
--