RFC: naming for FrontTransversal and Transversal ranges

[Robert Jacques]

On Fri, 01 May 2009 18:09:09 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> 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).

Ah, thank you. I would call this copy-on-mutate, rather than copy-on-write  
(though this is semantics). The COW that I normally think about has value  
semantics. In copy-on-mutate, the copying is done under the hood in order  
to provide lock-free properties. Do you have a link to your article? I'd  
like to know the relative performance. Though somehow changing O(1)  
algorithms that rarely touch the GC for O(n*t) that abuse the GC, provokes  
a certain gut reaction. This style of programming seems to need STM, so  
you can group a bunch of mutations into a single transaction, however, a  
lot of the queue/stack use cases are inherently single mutate  
transactions. What really worries me, is that lock-free queues and stacks  
are the building blocks of a lot of concurrency code, so making them fast  
is very important.

>> 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).