pugh@esprit.cs.umd.edu (Bill Pugh) (10/01/90)
Archive-name: skip-lists/29-Sep-90 Original-posting-by: pugh@esprit.cs.umd.edu (Bill Pugh) Original-subject: Re: data structures of Tarjan, et.al an Archive-site: mimsy.cs.umd.edu [128.8.128.8] Archive-directory: /pub/skipLists Reposted-by: emv@math.lsa.umich.edu (Edward Vielmetti) 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