Robert Jacques wrote:
> Lastly, what you're trying to fix is a bug in the implementation of arrays (see my posts in this thread) and not a bug in the design.

I think your fix to the array-slice conflation is simply to make slices arrays by adding extra information. This approach is reasonable, but (1) will make slices bigger and slower, and (2) will port very poorly to most other containers.

Code using ad-hoc arrays in C often had to pass two words around (usually pointers+length). Similarly, code using iterators in C++ must pass two pointers/iterators around (begin+end). With D, we have a 1-1 correspondence of that situation with slices, which makes for a great argument on why a slice that contains two boundaries is an awesome way to encapsulate a concept at no efficiency cost. Adding a third word to the slice would mark a step backwards in terms of data being trafficked around, and a questionable increase in expressiveness. An obese three-words slice would avoid stomping over other slices upon append, but would still exhibit a rather unpredictable append behavior: a function taking a slice and appending to it may or may not publish its changes to its caller.

A good design is to have containers and ranges, not container_ranges.


Andrei

Robert Jacques wrote:
> On Thu, 30 Apr 2009 23:18:13 -0400, Rainer Deyke <rainerd@eldwood.com> wrote:
>>   - It uses an extra heap allocation per instance.
> 
> And during a deep copy, you're often making a lot of heap copies. (N vs
> N+1 when N>>1)

In the case of dynamic arrays, N = 1 (or possibly 0 if the small array optimization is used).  In the case of static arrays, N = 0.  Either way, the extra level of indirection is significant.

>>   - It allocates an extra reference to a virtual function table per
>> instance.
> 
> Huh? Isn't that part of the extra heap allocation?

Extra allocations: 1.

Extra memory usage: 2 words (virtual function table pointer, local pointer) plus heap overhead for one allocation.

> Also, a really important question is: is it possible to implement are shared, lock-free containers as value types?


Is it possible to implement them as reference types?  Why would the issues different between reference types and value types?  A reference type is just a reference wrapper around a value type.


-- 
Rainer Deyke - rainerd@eldwood.com

On Fri, 01 May 2009 14:00:35 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Robert Jacques wrote:
>> Lastly, what you're trying to fix is a bug in the implementation of arrays (see my posts in this thread) and not a bug in the design.
>
> I think your fix to the array-slice conflation is simply to make slices arrays by adding extra information. This approach is reasonable, but (1) will make slices bigger and slower, and

The extra information is on the heap, not on the stack, so slices are no bigger or slower than normal (for GC or reference counted memory; fully manual memory management could have a 3 word array type and a 2 word slice type)

> (2) will port very poorly to most other containers.

Well, these bugs don't affect other containers.

> Code using ad-hoc arrays in C often had to pass two words around (usually pointers+length). Similarly, code using iterators in C++ must pass two pointers/iterators around (begin+end). With D, we have a 1-1 correspondence of that situation with slices, which makes for a great argument on why a slice that contains two boundaries is an awesome way to encapsulate a concept at no efficiency cost. Adding a third word to the slice would mark a step backwards in terms of data being trafficked around, and a questionable increase in expressiveness. An obese three-words slice would avoid stomping over other slices upon append, but would still exhibit a rather unpredictable append behavior: a function taking a slice and appending to it may or may not publish its changes to its caller.

I have not suggested obese 3-slices (in general). Let's look at actual costs of your previous array + slice proposal and my array/slice proposal:

GC:
Array       2 words (begin*, end*)
Slice       2 words (begin*, end*)
Array/Slice 2 words (ptr*, length)

Reference counting:
Array       4 words (begin*, end*, end-of-store*, refcount*)
Slice       3 words (begin*, end*, owner*)
Array/Slice 3 words (begin*, end*, memInfo*)

Manual memory managment:
Array       3 words (begin*, end*, end-of-store*)
Slice       2 words (begin*, end*)
Array/Slice 3 words (ptr*, length, memInfo*)

And you known something interesting: a 4-word alice is actually faster that a 2 word slice, _if_ you use MMX or SSE instructions (even unaligned, though aligned is even faster).

> A good design is to have containers and ranges, not container_ranges.

I agree in general. But, containers don't talk the same language, ranges do. So array slices having a few extra features (i.e ~=), doesn't bother my abstractions: it's still a range.

On Fri, 01 May 2009 14:03:44 -0400, Rainer Deyke <rainerd@eldwood.com> wrote:

> Robert Jacques wrote:
>> On Thu, 30 Apr 2009 23:18:13 -0400, Rainer Deyke <rainerd@eldwood.com>
>> wrote:
>>>   - It uses an extra heap allocation per instance.
>>
>> And during a deep copy, you're often making a lot of heap copies. (N vs
>> N+1 when N>>1)
>
> In the case of dynamic arrays, N = 1 (or possibly 0 if the small array
> optimization is used).  In the case of static arrays, N = 0.  Either
> way, the extra level of indirection is significant.
>

In the case of dynamic arrays, it's a struct. So no extra heap allocation is done. Same goes with heaps. Your argument only applies to object based containers, like trees, which generally contain lots of child objects., i.e. N heap allocations.

>>>   - It allocates an extra reference to a virtual function table per
>>> instance.
>>
>> Huh? Isn't that part of the extra heap allocation?
>
> Extra allocations: 1.
>
> Extra memory usage: 2 words (virtual function table pointer, local
> pointer) plus heap overhead for one allocation.

Nope. Most of the time, the extra memory usage is 0. Remember, the GC uses large blocks with power of 2 sizes. Unless you happen to push across a boundry, the extra 2 words don't matter.

>> Also, a really important question is: is it possible to implement are
>> shared, lock-free containers as value types?
>
>
> Is it possible to implement them as reference types?

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.

> A reference
> type is just a reference wrapper around a value type.

Precisely, so it's always passed by reference and doesn't need to support copying.

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

Robert Jacques wrote:
> Precisely, so it's always passed by reference and doesn't need to support copying.

All containers need to support copying.


-- 
Rainer Deyke - rainerd@eldwood.com

On Fri, 01 May 2009 15:07:17 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@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.

Robert Jacques wrote:
> On Fri, 01 May 2009 15:07:17 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@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

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

> Robert Jacques wrote:
>> On Fri, 01 May 2009 15:07:17 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@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).

Rainer Deyke wrote:
> Robert Jacques wrote:
>> Precisely, so it's always passed by reference and doesn't need to
>> support copying.
> 
> All containers need to support copying.

Speaking of which, I'm thinking of a field like scientific computing (even of the simplest, most basic kind that we all dabble into) or applied math. People who use for example matrices would NOT expect them to have reference semantics. They'd find it very confusing if a = b would not make matrix "a" a copy of matrix "b" and so on. (That + no operator overloading = R.I.P. my excitement for doing numeric work in Java.)

It would work to ask people who actually use Matrix!double to wrap it in a Value!(Matrix!double). But say someone asks, whatever, but if Value!(Matrix!double) is a matrix, then what is Matrix? Well, I'd reply, Matrix is actually a reference to a matrix. Then, they'll ask, why don't you call what you call today "Matrix", RefMatrix or Ref!Matrix or whatever, and call a Matrix a matrix? Um, I don't know. That's what the buzz was on the newsgroup when we were thinking of it. Some said that's what people coming from Java expect.

I guess at that point the would-be D user would be entitled to make me a lavaliere out of my Matrix library and move on.


Andrei