I've implemented a skip list that works in the STM monad. A skip list is a probabilistic data structure similar to a balanced tree. The main advantage of a skip list is that it doesn't require rebalancing, making it particularly suitable for concurrent programming. Here are the docs: http://darcs.monoid.at/tskiplist/dist/doc/html/tskiplist/Control-Concurrent-... It's not yet on hackage as the implementation is very incomplete and mostly untested. However, you can download a cabalized package from here: http://darcs.monoid.at/tskiplist/dist/tskiplist-0.0.0.tar.gz Darcs repository: http://darcs.monoid.at/tskiplist/ Peter
Hi Peter, Interesting. Your skip lists do not need re-balancing, but they do destructive updates. I wonder which factor outweighs the other in practise. Matthias.
Hi, Matthias.
Interesting. Your skip lists do not need re-balancing, but they do destructive updates. I wonder which factor outweighs the other in practise.
Hmm, I guess destructive updates cannot really be avoided no matter what data structure is used, since we're in the STM monad. Or do you see a specific problem that might occur? Peter
On 18/03/2010, at 9:49 AM, Matthias Görgens wrote:
Hi Peter,
Interesting. Your skip lists do not need re-balancing, but they do destructive updates. I wonder which factor outweighs the other in practise.
Isn't destructive update a feature in this case? i.e. these skip lists are designed for shared, mutable state. You could also have an immutable implementation, and in both cases not needing to rebalance helps -- less contention in the first instance and more sharing in the second.
participants (3)
-
Matthias Görgens -
Peter Robinson -
Tom Davies