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

Ben Manes ben_manes at yahoo.com
Tue Mar 10 19:58:59 EDT 2009

You may wish to read "Transactional Memory" by Larus and Rajwar.  They discuss a number of different implementations and found that lock-free implementations tended to perform worse than lock-based versions.  You could adopt an exponential back-off policy if the optimistic approach fails past a threshold.

From: Peter Veentjer <alarmnummer at gmail.com>
To: concurrency-interest at cs.oswego.edu
Sent: Tuesday, March 10, 2009 4:07:46 PM
Subject: [concurrency-interest] updating a pure functional tree and CAS problems

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.
Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20090310/198f275f/attachment.html>

More information about the Concurrency-interest mailing list