View mode: basic / threaded / horizontal-split · Log in · Help
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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.
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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.
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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.
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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).
May 01, 2009
Re: RFC: naming for FrontTransversal and Transversal ranges
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
1 2 3 4 5 6 7 8 9
Top | Discussion index | About this forum | D home