RFC: naming for FrontTransversal and Transversal ranges

Robert Jacques sandford at jhu.edu
Fri May 1 16:18:51 PDT 2009

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

More information about the Digitalmars-d mailing list