[concurrency-interest] updating a pure functional tree and CAS problems

Gregg Wonderly gregg at cytetech.com
Wed Mar 11 09:39:57 EDT 2009

Peter can you make each contending add result in a single rebuild with "all the 
stuff"?  I'm thinking that this loop should actually be in a monitor which gets 
a queue of things to rebuild with, always emptying the queue for all items with 
a drainTo() or something similar.

Gregg Wonderly

Peter Veentjer wrote:
> Hi Guys,
> I foresee a scalability/performance problem in a CAS-loop in a
> Software Transaction Memory implementation I'm working on, and I'm
> looking for some ideas.
> The situation:
> I use multiversioning as concurrency mechanism, so when changes are
> committed to the heap, a new heapsnapshot is created and within a cas
> loop it replaces the current one:
> so something like this:
> boolean success;
> do{
>      Snapshot beforeCommitSnapshot = snapshotRef.get();
>      Snapshot aferCommitSnapshot = beforeCommitSnapshot.update(stuffToCommit);
>      success = snapshotRef.compareAndSwap(beforeCommitSnapshot,
> afterCommitSnapshot);
> }while(!success)
> The problem is that this solution suffers from lifelocking if there is
> contention. The problems worsens if the number of things that need to
> be committed increase because it takes more time to build the new
> snapshot. It could even mean that long running transaction never can
> commit because some shorter running transaction take less time and let
> the long transaction try forever.
> I already have done a lot of optimizations in building the heap: the
> heapsnapshot is just a balanced tree. The tree is completely
> immutable, so an update creates a new tree based on the old one + the
> changes (the same way a tree is build in a pure functional programming
> language).
> My question is:
> this cas loop is just an optimistic version of the classic lock and
> something different than a wait free version. Does anyone have some
> pointers to literature for creating wait-free versions of pure
> functional trees?
> Other idea's are very much appreciated.
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

More information about the Concurrency-interest mailing list