On Mon, 1 Oct 2001 danielv at netvision.net.il wrote:

> Well, I really cannot say who said what, or who I'm answering to, but -
> In Celeste, this could make recovery after image crashes faster. With
> SortedCollections re-adding the n logged actions done before the crash
> takes n^2 time, with SkipLists, presumably, n*log(n).
>
> Or we could tweak Celeste to not update this list during recovery, and
> resort it once later.
> Still nicer to just have nice behaving data structures...
>
> Anyone know what this thing eats in memory usage?
>

*hint* Just CC me this sort of request. I'm a CS theory weenie. :)


Skip lists use variable sized nodes (1-32 references), in most
implementations, the expected number of references per node is two. Making
them the same expected overhead as splay trees or doubly-linked lists.
Given squeak header overhead, this means an expected 5 longwords/node (2
header, 2 for navigation, one for the data).

Given their extra size and complexity, they're probably not worth it
unless you've got at least 20 nodes and a pretty high update rate.

Though, may I suggest refactoring skiplists so that they subclass
OrderedCollection, and implement the same interface as SortedCollection so
that they are a drop-in replacement.

SortedCollection is the right choice for what you're doing. Its not your
fault that the implementation is not perfect. IE, don't fix your code, fix
SortedCollection by making an alternate O(log n) implementation.

Scott