[Haskell-cafe] Looking for an efficient tree in STM

John Meacham 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

-- 
John Meacham - ⑆repetae.net⑆john⑈


More information about the Haskell-Cafe mailing list