On Thu, 10 Mar 2005 04:28:26 +0000 (UTC), Ben Hinkle <Ben_member@pathlink.com> wrote:
> In article <opsnejj4bk23k2f5@nrage.netwin.co.nz>, Regan Heath says...
>>
>> On Wed, 9 Mar 2005 16:07:09 -0800, Walter <newshound@digitalmars.com>
>> wrote:
>>> "Stewart Gordon" <smjg_1998@yahoo.com> wrote in message
>>> news:d0kji1$2pt6$1@digitaldaemon.com...
>>>> This is one of two ways to insert in an array.  The other is
>>>>
>>>>      uint len = newElement.length;
>>>>      myArray.length = myArray.length + len;
>>>>      myArray[insertIndex+len..length]
>>>>        = myArray[insertIndex..length-len].dup;
>>>>      myArray[insertIndex..insertIndex+len] = newElement;
>>>>
>>>> Does DMD optimise the above to something like this?
>>>
>>> I'm not sure what's going on in that snippet <g>, but all the D runtime
>>> does
>>> is have an 'allocated' size for each array, which is >= the .length. The
>>> allocated size goes up by powers of 2. The array doesn't need to be
>>> reallocated if there is enough space in the allocated size to handle the
>>> increase.
>>
>> I know this has been mentioned before, but... Can we get a 'reserve'
>> method/property. eg.
>>
>>   array.reserve = 1,000,000;
>>
>> Which would essentially cause:
>>
>>   len = array.length;
>>   array.length = 1,000,000;
>>   array.length = len;
>>
>> Allowing us to reserve space before doing a large number of
>> concatentations (for example).
>> Obviating the need for 3 lines of code and a temp var.
>>
>> It can still, and should still allocate in powers of 2, it just allocates
>> to the power of 2 greater than the value specified.
>>
>> Another question, does the 'allocated' size ever decrease?
>> If so, when?
>> Is it possible for it to decrease while 1/2 way thru a large number of
>> concatentions.
>>
>> Regan
>
> It's funny you mention this. I was working on adding the attached "dynamic array
> with capacity" to mintl.array plus some other array helpers but since it came up
> I thought I'd post about it.
> Anyway, comments welcome,

At first glance the only difference between this and a built in dynamic array is the "capacity" functionality, correct?

Something I noticed, not a big deal really...

An implementation difference I notice is that you allocate exactly the requested length, not a power of 2, as Walter has mentioned the built-in array does.

I think it's safest to make no guarantee about this behaviour (which you haven't, yet) as that lets you optimise later on. I notice your unittest expects this behaviour, but your invariant doesn't.

Regan

"Walter" <newshound@digitalmars.com> wrote in message news:d0ojih$154h$1@digitaldaemon.com...
>
> "Regan Heath" <regan@netwin.co.nz> wrote in message news:opsnejj4bk23k2f5@nrage.netwin.co.nz...
>> I know this has been mentioned before, but... Can we get a 'reserve' method/property. eg.
>>
>>    array.reserve = 1,000,000;
>>
>> Which would essentially cause:
>>
>>    len = array.length;
>>    array.length = 1,000,000;
>>    array.length = len;
>>
>> Allowing us to reserve space before doing a large number of
>> concatentations (for example).
>> Obviating the need for 3 lines of code and a temp var.
>
> Why not just write a function to do it?

I agree. We should just have a standard library template to do it. In
the pre-DTL 0.3 pottering I'd got something
like:

    template arrayTemporaryReserve(T)
    {
        T[] arrayTemporaryReserve(T[] at, size_t len)
        {
            size_t oldLen = at.len;
            at.length = len;
            at.length = oldLen;

            return at;
        }
    }

We probably need to start thinking of all these kinds of utility functions, and deciding which ones need to be in Phobos proper. Perhaps we can have std/utility.d??

On Wed, 9 Mar 2005 20:39:19 -0800, Walter <newshound@digitalmars.com> wrote:
> "Regan Heath" <regan@netwin.co.nz> wrote in message
> news:opsnejj4bk23k2f5@nrage.netwin.co.nz...
>> I know this has been mentioned before, but... Can we get a 'reserve'
>> method/property. eg.
>>
>>    array.reserve = 1,000,000;
>>
>> Which would essentially cause:
>>
>>    len = array.length;
>>    array.length = 1,000,000;
>>    array.length = len;
>>
>> Allowing us to reserve space before doing a large number of
>> concatentations (for example).
>> Obviating the need for 3 lines of code and a temp var.
>
> Why not just write a function to do it?

True.

template(T) { void reserve(T[] array, size_t size) {
  int osize = array.length;
  array.length = size;
  array.length = osize;
}}

but it doesn't look as nice, eg.

char[] a;
reserve!(char)(a,10);

cos I can't write it as:

char[] a;
a.reserve(10);

but, that would be possible if:
 - We had implicit instantiation
 - I could use the array/method feature with templates eg.

char[] a;
void foo(char[] a){}
a.foo();

>> It can still, and should still allocate in powers of 2, it just allocates
>> to the power of 2 greater than the value specified.
>>
>> Another question, does the 'allocated' size ever decrease?
>> If so, when?
>> Is it possible for it to decrease while 1/2 way thru a large number of
>> concatentions.
>
> That's at the discretion of the implementation of the gc.

So, no guarantess then. The current GC only does a pass when you allocate memory, so presuming you don't allocate it during the concatenation, it should be safe, right?

Regan

In article <d0ok99$15st$1@digitaldaemon.com>, Matthew says...
>
>
>"Walter" <newshound@digitalmars.com> wrote in message news:d0ojih$154h$1@digitaldaemon.com...
>>
>> "Regan Heath" <regan@netwin.co.nz> wrote in message news:opsnejj4bk23k2f5@nrage.netwin.co.nz...
>>> I know this has been mentioned before, but... Can we get a 'reserve' method/property. eg.
>>>
>>>    array.reserve = 1,000,000;
>>>
>>> Which would essentially cause:
>>>
>>>    len = array.length;
>>>    array.length = 1,000,000;
>>>    array.length = len;
>>>
>>> Allowing us to reserve space before doing a large number of
>>> concatentations (for example).
>>> Obviating the need for 3 lines of code and a temp var.
>>
>> Why not just write a function to do it?
>
>I agree. We should just have a standard library template to do it. In
>the pre-DTL 0.3 pottering I'd got something
>like:
>
>    template arrayTemporaryReserve(T)
>    {
>        T[] arrayTemporaryReserve(T[] at, size_t len)
>        {
>            size_t oldLen = at.len;
>            at.length = len;
>            at.length = oldLen;
>
>            return at;
>        }
>    }
>
>We probably need to start thinking of all these kinds of utility functions, and deciding which ones need to be in Phobos proper. Perhaps we can have std/utility.d??

The version from MinTL also treat 0 length specially since setting the length of an array to 0 throws away the ptr part. Hence any reserve is useless if you start from 0.

/** Reserve a capacity for a dynamic array. If the array already has
* more elements or if the original length is zero it does nothing.
* Compiler-dependent.
* \param x the array to modify
* \param n the requested capacity
*/
template reserve(Value : Value[]) {
void reserve(inout Value[] x, uint n) {
uint oldlen = x.length;
if ((oldlen < n) && (oldlen > 0)) {
x.length = n;
x.length = oldlen;
}
}
}

>> It's funny you mention this. I was working on adding the attached
>> "dynamic array
>> with capacity" to mintl.array plus some other array helpers but since it
>> came up
>> I thought I'd post about it.
>> Anyway, comments welcome,
>
>At first glance the only difference between this and a built in dynamic array is the "capacity" functionality, correct?

yes - I was thinking of a couple extra tricks like backwards iteration etc but basically it's just a compiler-independent capacity-aware array.

>Something I noticed, not a big deal really...
>
>An implementation difference I notice is that you allocate exactly the requested length, not a power of 2, as Walter has mentioned the built-in array does.

Since my posted code uses arrays they grow by powers of 2 if the compiler does that under the hood.

>I think it's safest to make no guarantee about this behaviour (which you haven't, yet) as that lets you optimise later on. I notice your unittest expects this behaviour, but your invariant doesn't.

I should change the unittest to not look like that, though, since that wasn't my intention. I was going to always obey the capacity and let the user worry about increasing capacity at whatever rate they want or let the compiler decide under the hood.

>Regan

"Ben Hinkle" <Ben_member@pathlink.com> wrote in message news:d0om9f$1931$1@digitaldaemon.com...
> In article <d0ok99$15st$1@digitaldaemon.com>, Matthew says...
>>
>>
>>"Walter" <newshound@digitalmars.com> wrote in message news:d0ojih$154h$1@digitaldaemon.com...
>>>
>>> "Regan Heath" <regan@netwin.co.nz> wrote in message news:opsnejj4bk23k2f5@nrage.netwin.co.nz...
>>>> I know this has been mentioned before, but... Can we get a
>>>> 'reserve'
>>>> method/property. eg.
>>>>
>>>>    array.reserve = 1,000,000;
>>>>
>>>> Which would essentially cause:
>>>>
>>>>    len = array.length;
>>>>    array.length = 1,000,000;
>>>>    array.length = len;
>>>>
>>>> Allowing us to reserve space before doing a large number of
>>>> concatentations (for example).
>>>> Obviating the need for 3 lines of code and a temp var.
>>>
>>> Why not just write a function to do it?
>>
>>I agree. We should just have a standard library template to do it. In
>>the pre-DTL 0.3 pottering I'd got something
>>like:
>>
>>    template arrayTemporaryReserve(T)
>>    {
>>        T[] arrayTemporaryReserve(T[] at, size_t len)
>>        {
>>            size_t oldLen = at.len;
>>            at.length = len;
>>            at.length = oldLen;
>>
>>            return at;
>>        }
>>    }
>>
>>We probably need to start thinking of all these kinds of utility
>>functions, and deciding which ones need to be in Phobos proper.
>>Perhaps
>>we can have std/utility.d??
>
> The version from MinTL also treat 0 length specially since setting the
> length of
> an array to 0 throws away the ptr part. Hence any reserve is useless
> if you
> start from 0.
>
> /** Reserve a capacity for a dynamic array. If the array already has
> * more elements or if the original length is zero it does nothing.
> * Compiler-dependent.
> * \param x the array to modify
> * \param n the requested capacity
> */
> template reserve(Value : Value[]) {
> void reserve(inout Value[] x, uint n) {
> uint oldlen = x.length;
> if ((oldlen < n) && (oldlen > 0)) {
> x.length = n;
> x.length = oldlen;
> }
> }
> }

Good point! I'll borrow that. :-)

> The version from MinTL also treat 0 length specially since setting the length of
> an array to 0 throws away the ptr part. Hence any reserve is useless if you
> start from 0.

I don't think it is special when using slice syntax; and slice syntax is probably faster since it doesn't have to look up the pointer in the GC table (or whatever) to see if the new length is smaller or bigger.


char[] reserve(inout char[] buf, size_t len)
{
   if(buf.length < len)
   {
      size_t prevLen;
      prevLen = buf.length;
      buf.length = len;
      buf = buf[0 .. prevLen];
   }
   return buf;
}

Walter wrote:
> "Stewart Gordon" <smjg_1998@yahoo.com> wrote in message
> news:d0kji1$2pt6$1@digitaldaemon.com...
> 
>>This is one of two ways to insert in an array.  The other is
>>
>>     uint len = newElement.length;
>>     myArray.length = myArray.length + len;
>>     myArray[insertIndex+len..length]
>>       = myArray[insertIndex..length-len].dup;
>>     myArray[insertIndex..insertIndex+len] = newElement;
>>
>>Does DMD optimise the above to something like this?
> 
> 
> I'm not sure what's going on in that snippet <g>,

Seems obvious to me.  It extends the array to accommodate the data to be added, then shifts data forward to make room for the insertion in the right place, and then inserts it.

> but all the D runtime does
> is have an 'allocated' size for each array, which is >= the .length. The
> allocated size goes up by powers of 2. The array doesn't need to be
> reallocated if there is enough space in the allocated size to handle the
> increase.

I'd got that far.  But that doesn't tell me anything about how exactly it goes about optimising Nick's snippet, considering the specification that concatenation always creates a new array.

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on the 'group where everyone may benefit.

In article <opsnep5qlhkcck4r@esi>, Vathix says...
>
>> The version from MinTL also treat 0 length specially since setting the
>> length of
>> an array to 0 throws away the ptr part. Hence any reserve is useless if
>> you
>> start from 0.
>
>I don't think it is special when using slice syntax; and slice syntax is probably faster since it doesn't have to look up the pointer in the GC table (or whatever) to see if the new length is smaller or bigger.
>
>
>char[] reserve(inout char[] buf, size_t len)
>{
>    if(buf.length < len)
>    {
>       size_t prevLen;
>       prevLen = buf.length;
>       buf.length = len;
>       buf = buf[0 .. prevLen];
>    }
>    return buf;
>}

The ptr is also thrown away when resizing from 0 as well. I think the only way to resize an array from 0 without throwing away the ptr is to cast the array to a pointer and then slice an arbitrary amount - though this isn't very safe since there are no checks for capacity.

Walter wrote:
> "Stewart Gordon" <smjg_1998@yahoo.com> wrote in message
> news:d0kji1$2pt6$1@digitaldaemon.com...
> 
>>This is one of two ways to insert in an array.  The other is
>>
>>     uint len = newElement.length;
>>     myArray.length = myArray.length + len;
>>     myArray[insertIndex+len..length]
>>       = myArray[insertIndex..length-len].dup;
>>     myArray[insertIndex..insertIndex+len] = newElement;
>>
>>Does DMD optimise the above to something like this?
> 
> 
> I'm not sure what's going on in that snippet <g>, but all the D runtime does
> is have an 'allocated' size for each array, which is >= the .length. The
> allocated size goes up by powers of 2. The array doesn't need to be
> reallocated if there is enough space in the allocated size to handle the
> increase.
> 
> 
Sorry if I am being completely stupid here, but are you saying that dynamic arrays in D have an underlying length that is not equal to their actual length?  And that this underlying allocated size increases with powers of two?  If so, I think that there is a serious lack of documentation about a fundamental D data structure.  The online docs specifically mention that increasing the size of an array by one at a time will be expensive - in my mind this implies that the .length is the actual size.  If there is an underlying allocation size, it should be exposed as a properly and be allowed to be changed.

I'm confused! :)
Brad