The current splaying implementation does a bottom up splaying but starting at the root (should do a 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 in the mailing list). So the property of keeping recently used nodes up doesn't work.
Interestingly it doesn't hurt performance so much. Aactually it improves the performance compared to the previous version (previous bottom up implementation) because of the recursive nature of the former one. (patch and in depth explanation here) http://gcc.gnu.org/ml/gcc/2006-11/msg00074.html http://gcc.gnu.org/ml/gcc/2006-07/msg00210.html -- Summary: Incorrect splaying that not assures the caching property Product: gcc Version: 4.3.0 Status: UNCONFIRMED Severity: minor Priority: P3 Component: other AssignedTo: unassigned at gcc dot gnu dot org ReportedBy: ian dot blanes at campus dot uab dot es http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30920
