It looks we can't make it with only T[]. We need a genuine container type, and T[new] was suggested. It would probably have value semantics.

T[U] seems to have the same problem. If T[U] is the range, then how do you call the container?

If we follow through with a no-garbage-collected option for the core types, then we also need to distinguish between a slice and its container. The fact that we (almost) got away with T[] being at the same time the container and the slice was that the garbage collector would collect all unused slices.


Andrei

Andrei Alexandrescu wrote:
> It looks we can't make it with only T[]. We need a genuine container type, and T[new] was suggested.
<snip>

What do you mean by a "genuine container type"?

Stewart.

Stewart Gordon wrote:
> Andrei Alexandrescu wrote:
>> It looks we can't make it with only T[]. We need a genuine container type, and T[new] was suggested.
> <snip>
> 
> What do you mean by a "genuine container type"?

One with capacity and probably value semantics.

Andrei

On 2009-04-25 09:07:52 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> It looks we can't make it with only T[]. We need a genuine container type, and T[new] was suggested. It would probably have value semantics.
> 
> T[U] seems to have the same problem. If T[U] is the range, then how do you call the container?
> 
> If we follow through with a no-garbage-collected option for the core types, then we also need to distinguish between a slice and its container. The fact that we (almost) got away with T[] being at the same time the container and the slice was that the garbage collector would collect all unused slices.

I always disliked T[new]. Here's a better candidate:

     | range  | container
----- | ------ | ---------
array | T[]    | T.[]
assoc | T[U]   | T.[U]

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On Sat, 25 Apr 2009 09:07:52 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> It looks we can't make it with only T[]. We need a genuine container type, and T[new] was suggested. It would probably have value semantics.
>
> T[U] seems to have the same problem. If T[U] is the range, then how do you call the container?
>
> If we follow through with a no-garbage-collected option for the core types, then we also need to distinguish between a slice and its container. The fact that we (almost) got away with T[] being at the same time the container and the slice was that the garbage collector would collect all unused slices.
>
>
> Andrei

No, it's perfectly possible to have T[] be the same type for the container and the slice with reference counting instead of a full GC. All you need to do is store a pointer to the memory block's node. Then it's trivial to 1) get the capacity and 2) increase / decrease the reference count. You could even add an 'allocated length' parameter to the node, so you'd avoid some of the slicing bugs in the current implementation.

struct T[] {
    T*     ptr;
    size_t length;
    void*  memory_block;
}

On Sat, 25 Apr 2009 09:16:39 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> Stewart Gordon wrote:
>> Andrei Alexandrescu wrote:
>>> It looks we can't make it with only T[]. We need a genuine container type, and T[new] was suggested.
>> <snip>
>>  What do you mean by a "genuine container type"?
>
> One with capacity and probably value semantics.
>
> Andrei

First, capacity is only static (i.e. can be included in the array as you suggest) for free-list based allocation. Which is _only_ used by malloc and mark-sweep GCs. And I'm really hoping Leandro gives us something better than mark-sweep.

Second, if people want value semantics, they can already use .dup or a[] = ... when needed. Adding value semantics to arrays seems to me like a recipe for unintended poor performance by new to D programmers (who don't know) and experienced ones (who make a hard to find typo) a like. (I can see that value semantics for static arrays might be useful i.e. foo(real[4] vec), but I don't see a major need for dynamic vectors to have value semantics and every reason they shouldn't, i.e. foo(real[] big_image). Counter examples are desired and welcome.)

== Quote from Robert Jacques (sandford@jhu.edu)'s article
> On Sat, 25 Apr 2009 09:16:39 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> > Stewart Gordon wrote:
> >> Andrei Alexandrescu wrote:
> >>> It looks we can't make it with only T[]. We need a genuine container type, and T[new] was suggested.
> >> <snip>
> >>  What do you mean by a "genuine container type"?
> >
> > One with capacity and probably value semantics.
> >
> > Andrei
> First, capacity is only static (i.e. can be included in the array as you suggest) for free-list based allocation. Which is _only_ used by malloc and mark-sweep GCs. And I'm really hoping Leandro gives us something better than mark-sweep.

But in a pointer bumping GC, the right way to do dynamic arrays would be to allocate some extra space for the array beyond the length requested, to allow it to be appended to without being reallocated.  In this case, the extra space is being allocated under the hood by the array functions, not the garbage collector, but it's still there and you still need a capacity field to track it without expensive GC queries.

On Sat, 25 Apr 2009 08:07:52 -0500, Andrei Alexandrescu wrote:

> It looks we can't make it with only T[]. We need a genuine container type, and T[new] was suggested. It would probably have value semantics.
> 
> T[U] seems to have the same problem. If T[U] is the range, then how do you call the container?
> 
> If we follow through with a no-garbage-collected option for the core types, then we also need to distinguish between a slice and its container. The fact that we (almost) got away with T[] being at the same time the container and the slice was that the garbage collector would collect all unused slices.
> 
> 
> Andrei

You are confusing the difference between T[] and T[U].  T[U] is a strange beast because it does not need to be new'd, but it acts completely like a reference type.  But T[U] *is* the container type.  What you should be asking is what is the *slice* type for T[U].  My answer would be that a slice type for a hashtable doesn't make sense.  We don't need AAs to be completely on par with normal arrays, so just leave them alone ;)

-Steve

On Sat, 25 Apr 2009 11:57:25 -0400, dsimcha <dsimcha@yahoo.com> wrote:
> == Quote from Robert Jacques (sandford@jhu.edu)'s article
>> On Sat, 25 Apr 2009 09:16:39 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail@erdani.org> wrote:
>> > Stewart Gordon wrote:
>> >> Andrei Alexandrescu wrote:
>> >>> It looks we can't make it with only T[]. We need a genuine container
>> >>> type, and T[new] was suggested.
>> >> <snip>
>> >>  What do you mean by a "genuine container type"?
>> >
>> > One with capacity and probably value semantics.
>> >
>> > Andrei
>> First, capacity is only static (i.e. can be included in the array as you
>> suggest) for free-list based allocation. Which is _only_ used by malloc
>> and mark-sweep GCs. And I'm really hoping Leandro gives us something
>> better than mark-sweep.
>
> But in a pointer bumping GC, the right way to do dynamic arrays would be to
> allocate some extra space for the array beyond the length requested, to allow it
> to be appended to without being reallocated.  In this case, the extra space is
> being allocated under the hood by the array functions, not the garbage collector,
> but it's still there and you still need a capacity field to track it without
> expensive GC queries.

1) There are multiple types of pointer bumping GCs and checking/exending an array can be pretty darn cheap. (You only have to find the memory page)
2) Pointer bumping is only half a GC, generally the other half is going to move/compact the array, at which point the capacity *should* be changed.
3) Over-allocating all arrays is a wonderful waste of memory and performance (re chache lines, etc). A cleaner answer is an array builder class, which only pays for this overhead when it's actually needed.

On Sat, 25 Apr 2009 09:16:39 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> Stewart Gordon wrote:
>> Andrei Alexandrescu wrote:
>>> It looks we can't make it with only T[]. We need a genuine container type, and T[new] was suggested.
>> <snip>
>>  What do you mean by a "genuine container type"?
>
> One with capacity and probably value semantics.
>
> Andrei

If you add capacity to arrays, why do need seperate slice and container types?
i.e.
.capacity  > 0 -> container
.capacity == 0 -> slice

Note: this use of a capacity field has been mentioned before.