Splay Tree

[Ian Blanes <ian at gentemsn dot com>]

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.

original tree (tree rotated 90º left)

 71
70
  61
 60
   51
  50
    41
   40
     31
    30
      21
     20
       11
      10
        1
       0
        -10

splaying at 0 with revision=106584

     71
    70
      61
     60
      51
   50
     41
    40
     31
  30
    21
   20
    11
 10
  1
0
 -10

splaying at 0 with previous version

  71
 70
    61
   60
    51
  50
     41
    40
     31
   30
      21
     20
      11
    10
     1
0
 -10


I also did a testcase for this using tipical splay tree usage during gcc 
bootstraping (attached). Timings (four runs, average of the last three):

http://gcc.gnu.org/viewcvs?view=rev&revision=106584
real    0m1.174s
user    0m0.336s
sys     0m0.837s

http://gcc.gnu.org/ml/gcc-patches/2005-10/msg00775.html (other top down 
patch)
real    0m0.005s (to low to be acurate)
user    0m0.004s
sys     0m0.003s

previous version
real    0m0.005s
user    0m0.003s
sys     0m0.003s

ian

Attachment: splay_tree_test.c.bz2
Description: Binary data

Attachment: example.c
Description: Text document