RFC: naming for FrontTransversal and Transversal ranges

[Andrei Alexandrescu]

Robert Jacques wrote:
> On Fri, 01 May 2009 15:07:17 -0400, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> wrote:
>> Robert Jacques wrote:
>>> Yes. See java.util.concurrent for examples. In fact, all of the 
>>> algorithms I've read explicitly don't support copying, which is why 
>>> I'm asking.
>>>
>>>> Why would the
>>>> issues different between reference types and value types?
>>>  A value type has to support copying. Reference types don't. Perhaps 
>>> I should have said value semantics / reference semantics instead.
>>
>> I thought lock-free data structures are the quintessential COW type. 
>> You might as well just have provided the perfect argument against your 
>> case.
>>
>> Andrei
> 
> Andrei, I've never seen a COW lock-free algorithm.

Maybe we have some terms confused. Yes, lock-free singly-linked lists 
and stacks (and some dictionaries) that are defined in the literature 
are meant to be shared and use minimal and coherent CAS-based updates. 
This is quite a feat because copying is the easy way to go and doesn't 
quite deserve a peer-reviewed conference paper. However, Maged Michael 
and I co-wrote a few magazine articles on the topic.

The general structure of a COW lock-free object is:

struct Something { ... }

struct LockFree
{
     Something * s;

     void makeSomeChange()
     {
         do {
             Something * copy = s.deepDup;
             copy.makeSomeChange;
         } while (!cas(copy, s));
     }
}

For example if Something is some array and you want to insert elements 
in it atomically, you make a copy of the array, insert stuff, and then 
substitute the copy for the original array with care such that the array 
stayed in place (otherwise your insertions aren't doing what you 
initially thought).

> Andrei, you might be thinking about STM, which follows a transactional 
> model: lazy copy, mutate copy, publish-retry changes.

My understanding is that STM is a generalized, multi-object, 
transparent, and systematic way of doing CAS-based work (please correct 
me if I'm wrong, I'm not an expert in STM).


Andrei