This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Splay Tree
- From: Ian Blanes <ian at gentemsn dot com>
- To: gcc at gcc dot gnu dot org
- Cc: Roger Sayle <roger at eyesopen dot com>, Richard Guenther <rguenther at suse dot de>
- Date: Sun, 29 Oct 2006 18:27:55 +0100 (CET)
- Subject: Splay Tree
Could this patch be applied now?
http://gcc.gnu.org/ml/gcc/2006-07/msg00210.html
Discussion starts here:
http://gcc.gnu.org/ml/gcc/2006-07/msg00147.html (benchmarks are wrong)
Original patch posted by Brian Makin here:
http://gcc.gnu.org/ml/gcc-patches/2005-10/msg00762.html
Quote:
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. One
example of this is that while in the implementation described in
http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf the root node
ends at most two levels down, in the current implementation it can end at
an arbiratry depth (example attached). So the property of keeping recently
used nodes up doesn't work.
ian