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?
Daniel
Karl Ramberg karl.ramberg@chello.se wrote:
On Tue, 25 Sep 2001, Andreas Raab wrote:
Folks,
I noticed them coming into Squeak a while ago and always since I wanted to ask this question: What the heck are they good for?! ;-) I don't see them
Basically, Skiplists (and/or balanced tree implementations of SortedCollection) should be used anywhere where you have a lot of inserts/removals from a sorted collection, and profiling shows that that is a problem.
Scott
On Mon, 1 Oct 2001 danielv@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
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
Or, perhaps, change sorted collection so it uses Skip Lists, etc, as backing stores when certain conditions are met ( Usually size of data stored ). With a little code profiling, one could tune it to change it's backing data rep at the appropiate times as the data stored grows.
This is done in some Smalltalks.
I've been reading too much on Smalltalk best practices, and refactoring...
Daniel Joyce
On Tue, 2 Oct 2001, Daniel Joyce wrote:
Or, perhaps, change sorted collection so it uses Skip Lists, etc, as backing stores when certain conditions are met ( Usually size of data stored ). With a little code profiling, one could tune it to change it's backing data rep at the appropiate times as the data stored grows.
This is done in some Smalltalks.
Make it a drop-in replacement. It is quite a bit more expensive; let the programmer figure out that it is needed through profiling, and make the drop-in replacement.
Any automatic conversion is probably a bad idea. Sometimes, memory is more important than speed, sometimes the reverse; a lot of things will affect the relative differences between them.
Scott
squeak-dev@lists.squeakfoundation.org
-
Daniel Joyce -
danielv＠netvision.net.il -
Scott A Crosby