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

Peter Veentjer alarmnummer at gmail.com
Wed Mar 11 10:18:32 EDT 2009


The book is under my pillow since it is one of the few resources about
Transactional Memory :) Although I take a completely different
approach, the book is full of useful information.

I'll reread the stuff about lock-free vs lock-based stuff..

Thanks for pointing it out.

On Wed, Mar 11, 2009 at 12:58 AM, Ben Manes <ben_manes at yahoo.com> wrote:
> 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;
> 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