Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!ucbvax!ulysses!kpv
From: kpv@ulysses.att.com (Phong Vo[drew])
Newsgroups: comp.theory
Subject: Re: data structures of Tarjan, et.al an
Summary: top-down splay is pretty good
Message-ID: <13811@ulysses.att.com>
Date: 28 Sep 90 15:26:53 GMT
References: <193541@<1990Sep23> <37800016@m.cs.uiuc.edu>
Organization: AT&T Bell Laboratories, Murray Hill
Lines: 41

In article <37800016@m.cs.uiuc.edu>, gillies@m.cs.uiuc.edu writes:
> Has anyone written a splay that is faster?  I suspect the splays just
> posted are not as fast.  However, my splay is just a benchmark and
> does not contain the all trivial amenities (like delete() or join()).
> The splay constant of proportionality is very large (there is an MIT
> Sloan School tech report just to complain about this fact).  In fact,
> the number above suggest the constant may be 5-10 times slower than
> search in a balanced tree.  It seems that in many applications, AVL
> trees would still be a bigger win, especially when insertions and
> deletions are relatively rare, and locality of reference is unlikely.
> Anyone care to comment?

I've used the top-down splay tree quite a bit. Its most significant use
so far is to maintain the free blocks (actually lists of free blocks of the
same size) in a malloc package based on the best-fit strategy.
This is a good application for splay trees
because malloc request sizes tend to be localized.
This malloc will be distributed in SysVr4.
I've also written a dictionary package based on top-down splay trees and hashing
(you can switch modes).  Comparing this with a similar package using balanced trees
(written by someone else who is at least as good a programmer as I am),
my package is anywhere between 10% to twice as fast.
The 10% is for doing uniformly random probes.
The 100% is for walking objects in their defined order.
An additional benefit of top-down splay tree is that you only need to spend
two pointers per object where in a balanced tree you need at least one more
balancing bit (a byte in a typical implementation) and probably another pointer
for the parent node.  Here's a small benchmark on a SPARC1+.
To insert 100000 integers in random order, walk them in order,
and probe each of them in random order, the splay tree package takes 15.01s
and uses up 2.8megs of memory. For the same work, the balanced tree package
takes 33.03s and uses up 3.6 megs of memory. Note that in this benchmark,
even though objects are integers, comparisons are done by function calls
since this is an interface restriction imposed by the packages.

On a slight tangent, I've also implemented skip list with somewhat disappointing
results. In its best days, skip lists is slightly worse than balanced trees.
This is not too hard to see in hindsight. Skip lists basically try to mimic
balanced trees in a probabilistic sense.

	Phong Vo, AT&T Bell Labs, Murray Hill, NJ07974, att!ulysses!kpv