[Haskell-cafe] Looking for an efficient tree in STM
john at repetae.net
Mon Mar 20 15:50:12 EST 2006
On Sat, Mar 18, 2006 at 05:46:30PM -0500, ajb at spamcop.net wrote:
> B-trees are popular for a similar reason. A node is an obvious unit of
> granularity, since different threads can work in different nodes without
> interfering. Not only is the page size tunable, there is also an obvious
> way to "group" nodes together such that locks can cover more than one
> physical node if you need that.
I believe the current best choice in concurrent environments is
'skip-lists' since they require no global invarients (or locks) to be
maintained as they are probabalistic. They parallelize very well.
John Meacham - ⑆repetae.net⑆john⑈
More information about the Haskell-Cafe