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