RFC: naming for FrontTransversal and Transversal ranges

[Robert Jacques]

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. In fact, to the best of  
my knowledge, you can only copy lock-free hash tables and arrays.  
Everything else, even stacks or queues implemented on an array, don't  
work. For instance, the issues with walkers on singly linked lists is a  
well known problem. I've read several paper on lock-free queues and  
lock-free stacks, and none have mentioned copying. They simply ignore it.  
(The hash table talk implied it, but didn't mention it explicitly) So if  
you have a paper on how to do a lock free stack, queue, etc that supports  
copying I'd love to read it. (which is one reason why I'm asking)

Andrei, you might be thinking about STM, which follows a transactional  
model: lazy copy, mutate copy, publish-retry changes. (Technically, under  
the hood the publish takes a lock. It's just that by taking all the  
required locks at once in a known manner, deadlocks are avoided. And the  
locks are taken for a much shorter time period.(Caveat: there are other  
ways of doing STM, and I don't know what D's specific plans are)) This is  
generally considered to be different from specific lock-free containers.  
(I'm pretty sure that simple STM containers would have worse performance  
than a lock version, let alone a lock-free version, but I've haven't seen  
data for STM used with simple containers, like a stack, queue or tree, so  
I don't know for sure. Usually, you see it with unstructured objects )

I should probably have used the term Concurrent Collections as opposed to  
lock-free collections.