gillies@m.cs.uiuc.edu (09/27/90)
I implemented a recursive Tarjan Splay and my own splay on a 16Mhz Mac
II (2-3 MIPS, about as fast as a SUN III). I was disappointed because
after substantial tuning, I could only achieve about 40,000-50,000
integer comparisons / second. In other words, to insert 1000 integers
and then look them up repeatedly, you would get about 5,000 lookups
per second. I used straightforward recursive algorithms in C.
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?
Don W. Gillies, Dept. of Computer Science, University of Illinois
1304 W. Springfield, Urbana, Ill 61801
ARPA: gillies@cs.uiuc.edu UUCP: {uunet,harvard}!uiucdcs!gilliesjones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) (09/28/90)
From article <37800016@m.cs.uiuc.edu>, by gillies@m.cs.uiuc.edu: > > 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()). It is easy to delete the delete() and join() operations from my Pascal code or Brower's C code. Just delete the uplink field from each node in the data structure, and delete every statement in the code containing a reference to this field. This breaks the bottom-up splay procedure, and all procedures depending on bottom-up splaying, but it leaves the basic top-down splay procedures fully operational (and faster!), allowing a fair comparison with your code. On a side issue, splay trees are particularly well suited to use as priority queues because of the way they unbalance when half of the operations are delete-min (or get-next in discrete-event simulation). Each delete-min operation shortens the leftmost branch of the tree by roughly a factor of two, with the result that, on average, this path is of constant length independent of the tree size. Thus, you get O(1) time for delete-min and O(log n) time for insert (all bounds are amortized). Doug Jones jones@herky.cs.uiowa.edu
kpv@ulysses.att.com (Phong Vo[drew]) (09/28/90)
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
jgk@osc.COM (Joe Keane) (09/29/90)
What we really need is an algorithm that lets you get away with little or no modification when everything is going well, but keeps the amortized upper bound of the original splaying algorithm. Sleator and Tarjan talk about this in their paper, for example you could do a full splay only when the path length is greater than some threshold. However, to my knowledge no one has come up with a really good way of doing this.
pugh@esprit.cs.umd.edu (Bill Pugh) (09/29/90)
In article <13811@ulysses.att.com> kpv@ulysses.att.com (Phong Vo[drew]) writes: > >..., 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 As the original author of skip lists, I thought I'd throw in a few words. A while back, I ran some benchmarks on on SPARC machine, and found that skip lists did not do very well on them; their relative performance, compared with balanced trees, was significantly worse on SPARC machines than on other computers I tested. I looked into it a little and found that the SPARC machine, since it is a RISC design, makes some operations slow. Unfortunately, some of the slow operations include the multiplication and indexing operations used in skip list algorithms. With regards to the relative speed of skip lists and balanced trees, I never claimed that skip lists were significantly faster than a highly optimized balanced tree implementation. But I do believe that a casual implementation of skip lists will often be significantly faster than a casual implementation of balanced trees. It takes skill and effort to write a fast implementation of balanced trees, items that are often in short supply. A while back, I solicited fast implementations of balanced trees from the net and from a number of researchers. While some of the implementations I received were roughly as fast as skip lists, others (such as one by Chris Van Wyk) were 5-6 times slower. In summary, the only way to be sure which of two implementations is faster for your purposes is to runs trials yourself on your machine using your compiler. Bill Pugh P.S. C and Pascal implementations of skip lists are still available for anonymous ftp from mimsy.cs.umd.edu for anybody who wishes to obtain them. Bill Pugh Dept. of Comp. Sci., Univ. of Maryland pugh@cs.umd.edu