[Bug other/30920] New: Incorrect splaying that not assures the caching property

[ian dot blanes at campus dot uab dot es]

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