www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - dynamic array memory allocation

reply Greg Weber <webs.dev gmail.com> writes:
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.
May 15 2007
next sibling parent "Unknown W. Brackets" <unknown simplemachines.org> writes:
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.
May 16 2007
prev sibling next sibling parent davidl <davidl 126.com> writes:
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/
May 16 2007
prev sibling next sibling parent martin <m_dot_hinsch rug.nl> writes:
davidl Wrote:


 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/


I can immediately give an example for the usefulness of this from my field:
I'm doing individual-based simulations with many individuals (I'm a theoretical
biologist). Typically these individuals reproduce frequently which often
involves filling a new array with an unknown number of new objects (if you have
discrete generations) or alternatively adding (an unknown number of) objects to
an existing array. In C++ being able to do .reserve(large_enough_number) can
improve performance considerably.

Martin
May 16 2007
prev sibling next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
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];
May 16 2007
parent reply Traveler Hauptman <none none.com> writes:
Walter Bright wrote:

 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];


I can sympathize with greg, I often use arrays as an intermediate memory
allocator (when writing code that can't be garbage collected). But it
would require dynamic arrays have a different shape; you would have to
track the buffer size in addition to the number of elements... (or you
check mallocs boundary tags if you want to be non-portable)

It would be nice to be able to set minimum allocation chunk size on a
type-by-type basis; especially for small types. Or is that considered a
compiler optimization?
May 16 2007
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Traveler Hauptman wrote:

 It would be nice to be able to set minimum allocation chunk size on a
 type-by-type basis; especially for small types. Or is that considered a
 compiler optimization?


D allows for custom memory allocation schemes by overloading operators 
new and delete for a class/struct, or by using malloc/free (or one's own 
allocator) directly.
May 17 2007
parent Traveler Hauptman <none none.com> writes:
Walter Bright wrote:

 Traveler Hauptman wrote:

 It would be nice to be able to set minimum allocation chunk size on a
 type-by-type basis; especially for small types. Or is that considered a
 compiler optimization?


 
 D allows for custom memory allocation schemes by overloading operators
 new and delete for a class/struct, or by using malloc/free (or one's own
 allocator) directly.


I was suggesting a compromise for array allocation between what D has
now and what Greg was asking for. I'm assuming you can't overload
new/delete for arrays and the fundamental types.

I gotta say though, when I first looked at D a couple years ago and saw
that you gave access to the memory allocation layer with new/delete; I
think I jumped up and did a little dance. (I write hard-realtime code)

Cheers
May 17 2007
prev sibling next sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
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
May 16 2007
parent reply Greg Weber <webs.dev gmail.com> writes:
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?
May 16 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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).
May 16 2007
parent reply Greg Weber <webs.dev gmail.com> writes:
 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;
}
May 16 2007
next sibling parent Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
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
May 16 2007
prev sibling parent janderson <askme me.com> writes:
Greg Weber wrote:

 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;
 }
 


Nice!

I hate to ccomplain however this is not the most efficient way to resize 
an array, unless the compiler is smart enough to remove the copy.

-Joel
May 17 2007
prev sibling parent Derek Parnell <derek psych.ward> writes:
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
May 16 2007