I find myself wondering what actually happens when I create a dynamic array and concatenate items onto it.  I think I read in a post that memory will be over-allocated at times to avoid re-allocating.

I think it would help out a lot to have an ability to specify over-allocation.  Something like
uint a = [];
a.length = 3:10

Where the array length is 3, but you are guaranteed to have memory allocation for 10, so you can be guaranteed that concatenation up to ten will not need to allocate memory.  This could help in the situation where there is concatenation in a loop, and the programmer over-sizes the array before the loop and re-sizes after the loop.

If that happened, it would most likely look more like:

a.allocated = 10;

But, generally, in my experience I've found very little need to set such a value - as much as it seems very useful, from a logical standpoint.

Instead, I've found myself setting length to a higher-than-necessary value, and setting it down once I'm finished.  I use slicing a lot more than concatenating this way.

I suspect, performance and footprint wise, it's not much different.

-[Unknown]


Greg Weber wrote:
> I find myself wondering what actually happens when I create a dynamic array and concatenate items onto it.  I think I read in a post that memory will be over-allocated at times to avoid re-allocating.
> 
> I think it would help out a lot to have an ability to specify over-allocation.  Something like
> uint a = [];
> a.length = 3:10
> 
> Where the array length is 3, but you are guaranteed to have memory allocation for 10, so you can be guaranteed that concatenation up to ten will not need to allocate memory.  This could help in the situation where there is concatenation in a loop, and the programmer over-sizes the array before the loop and re-sizes after the loop.

It's useful. Seperating the concept of capacity and length should be considered carefully

> I find myself wondering what actually happens when I create a dynamic array and concatenate items onto it.  I think I read in a post that memory will be over-allocated at times to avoid re-allocating.
>
> I think it would help out a lot to have an ability to specify over-allocation.  Something like
> uint a = [];
> a.length = 3:10
>
> Where the array length is 3, but you are guaranteed to have memory allocation for 10, so you can be guaranteed that concatenation up to ten will not need to allocate memory.  This could help in the situation where there is concatenation in a loop, and the programmer over-sizes the array before the loop and re-sizes after the loop.



-- 
使用 Opera 革命性的电子邮件客户程序: http://www.opera.com/mail/

Greg Weber wrote:
> I find myself wondering what actually happens when I create a dynamic array and concatenate items onto it.  I think I read in a post that memory will be over-allocated at times to avoid re-allocating.
> 
> I think it would help out a lot to have an ability to specify over-allocation.  Something like
> uint a = [];
> a.length = 3:10
> 
> Where the array length is 3, but you are guaranteed to have memory allocation for 10, so you can be guaranteed that concatenation up to ten will not need to allocate memory.  This could help in the situation where there is concatenation in a loop, and the programmer over-sizes the array before the loop and re-sizes after the loop.

a.length = 10;
a = a[0 .. 3];

Greg Weber skrev:
> I find myself wondering what actually happens when I create a dynamic array and concatenate items onto it.  I think I read in a post that memory will be over-allocated at times to avoid re-allocating.
> 
> I think it would help out a lot to have an ability to specify over-allocation.  Something like
> uint a = [];
> a.length = 3:10
> 
> Where the array length is 3, but you are guaranteed to have memory allocation for 10, so you can be guaranteed that concatenation up to ten will not need to allocate memory.  This could help in the situation where there is concatenation in a loop, and the programmer over-sizes the array before the loop and re-sizes after the loop.

D no longer clears an array when the size is set to zero, so a reserve method should be as simple as:


void reserve(T,I)(inout T[] arr, I reservedSize) {
    static assert(is(I:size_t),"reserve needs an integer size parameter");
    size_t l = arr.length;
    if (reservedSize > l) {
        arr.length = reservedSize;
        arr.length = l;
    }
}

...

int[] a;
a.reserve(1000);
for (int i = 0; i < 1000; i++)
	a ~= i; // no reallocation


Care should be taken as always when appending to slices.

/Oskar

On Wed, 16 May 2007 02:30:35 -0400, Greg Weber wrote:

> I find myself wondering what actually happens when I create a dynamic array and concatenate items onto it.  I think I read in a post that memory will be over-allocated at times to avoid re-allocating.
> 
> I think it would help out a lot to have an ability to specify over-allocation.  Something like
> uint a = [];
> a.length = 3:10
> 
> Where the array length is 3, but you are guaranteed to have memory allocation for 10, so you can be guaranteed that concatenation up to ten will not need to allocate memory.  This could help in the situation where there is concatenation in a loop, and the programmer over-sizes the array before the loop and re-sizes after the loop.

In those situations I do this ...

  uint[] a;
  a.length = 10;
  a.length = 3;

This keeps the 10 (actually 16 I think) allocated while setting the length
to 3.

-- 
Derek Parnell
Melbourne, Australia
"Justice for David Hicks!"
skype: derek.j.parnell

Oskar Linde Wrote:

> Greg Weber skrev:
> > I find myself wondering what actually happens when I create a dynamic array and concatenate items onto it.  I think I read in a post that memory will be over-allocated at times to avoid re-allocating.
> > 
> > I think it would help out a lot to have an ability to specify over-allocation.  Something like
> > uint a = [];
> > a.length = 3:10
> > 
> > Where the array length is 3, but you are guaranteed to have memory allocation for 10, so you can be guaranteed that concatenation up to ten will not need to allocate memory.  This could help in the situation where there is concatenation in a loop, and the programmer over-sizes the array before the loop and re-sizes after the loop.
> 
> D no longer clears an array when the size is set to zero, so a reserve method should be as simple as:
> 
> 
> void reserve(T,I)(inout T[] arr, I reservedSize) {
>      static assert(is(I:size_t),"reserve needs an integer size parameter");
>      size_t l = arr.length;
>      if (reservedSize > l) {
>          arr.length = reservedSize;
>          arr.length = l;
>      }
> }
> 
> ...
> 
> int[] a;
> a.reserve(1000);
> for (int i = 0; i < 1000; i++)
> 	a ~= i; // no reallocation
> 
> 
> Care should be taken as always when appending to slices.
> 
> /Oskar

Thanks, that is very useful.  So the next question becomes how can I re-size a dynamic array down to a smaller length and guarantee that (most of) the memory has been freed?

Greg Weber wrote:
> Thanks, that is very useful.  So the next question becomes how can I re-size a dynamic array down to a smaller length and guarantee that (most of) the memory has been freed?

AFAIK there's no way to shrink the memory allocated to an array, and the closest you can get is to call .dup on a slice. This will get you a copy of part of the array, allowing the original to be garbage collected (assuming no more references to it exist).

> AFAIK there's no way to shrink the memory allocated to an array, and the closest you can get is to call .dup on a slice. This will get you a copy of part of the array, allowing the original to be garbage collected (assuming no more references to it exist).

So here is my attempt.

bool downsize(T,I)(inout T[] arr, I downSize) {
    static assert(is(I:size_t),"downsize needs an integer size parameter");

    if (downSize < arr.length) {
        auto downsized = arr[0 .. downsize].dup;
        arr = downsized;
        return true;
    }
    return false;
}


bool allocate(T,I)(inout T[] arr, I reservedSize) {
    static assert(is(I:size_t),"reserve needs an integer size parameter");
    size_t l = arr.length;
    if (reservedSize > l) {
        arr.length = reservedSize;
        arr.length = l;
        return true;
    }
    return false;
}

Greg Weber skrev:
>> AFAIK there's no way to shrink the memory allocated to an array, and the closest you can get is to call .dup on a slice. This will get you a copy of part of the array, allowing the original to be garbage collected (assuming no more references to it exist).
> 
> So here is my attempt.
> 
> bool downsize(T,I)(inout T[] arr, I downSize) {
>     static assert(is(I:size_t),"downsize needs an integer size parameter");
> 
>     if (downSize < arr.length) {
>         auto downsized = arr[0 .. downsize].dup;
>         arr = downsized;
>         return true;
>     }
>     return false;
> }
> 
> 
> bool allocate(T,I)(inout T[] arr, I reservedSize) {
>     static assert(is(I:size_t),"reserve needs an integer size parameter");
>     size_t l = arr.length;
>     if (reservedSize > l) {
>         arr.length = reservedSize;
>         arr.length = l;
>         return true;
>     }
>     return false;
> }
> 

Looks good, except possibly the bool return value of allocate, as there is no guarantee a reallocation really happened even though it returns true. A better way would perhaps be to compare the .ptr and return true if it changed.

/Oskar