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

Peter Veentjer alarmnummer at gmail.com
Tue Mar 10 19:07:46 EDT 2009

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;
     Snapshot beforeCommitSnapshot = snapshotRef.get();
     Snapshot aferCommitSnapshot = beforeCommitSnapshot.update(stuffToCommit);
     success = snapshotRef.compareAndSwap(beforeCommitSnapshot,

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

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.

More information about the Concurrency-interest mailing list