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

Peter Veentjer alarmnummer at gmail.com
Wed Mar 11 10:15:23 EDT 2009

Hi Gregg,

Something I forget to mention: some commits need to fail because a
write conflict has occurred. At the moment I use a very optimistic
approach in my stm,  so a write conflict is quite common. I'm working
on pessimistic locking but that isn't completed yet... and pessimistic
locking if going worsen the cas problem because every pessimistic lock
leads to a new snapshot (a snapshot containing the previous data + the
lock) that will interfere with the cas of longer running transactions.

Check out the stack example on this page:


Concurrent pushes and pops have a write conflict on the head of the stack.

If I have 2 threads that communicate through a stack in the stm, I
have 35% write conflicts on my dual core machine. So this means that
roughly 1 out of 4 transactions started with the commit, but could not
create a new snapshot to replace the older one and need to retry.

So queuing could be more complicated because one of the items that is
drained from the queue, could ruin it for the others.. but maybe you
are right and this is the way to go. Just letting each transaction do
its thing and let cas worry about the rest is not the silver bullet to

On Wed, Mar 11, 2009 at 2:39 PM, Gregg Wonderly <gregg at cytetech.com> wrote:
> 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