www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Slices and array appending

reply "cal" <callumenator gmail.com> writes:
Just want to make sure I understand this properly:

I have a large dynamic array (whose elements are immutable) which 
only ever grows. I also have a whole lot of small slices into 
this array, the slices never change, and they don't span the 
entire contents of the array (they are just pieces).

Now if I append to the large array, and the runtime needs to 
re-allocate to accommodate the change in size, none of the pieces 
of the original array which are referred to by the slices can be 
freed, right? So I end up basically with two copies of the 
original large array, however the first version will now have 
little pieces missing from it (wherever the slices don't refer).

Is that correct?
Oct 21 2012
next sibling parent "Era Scarecrow" <rtcvb32 yahoo.com> writes:
On Sunday, 21 October 2012 at 23:35:30 UTC, cal wrote:

 Just want to make sure I understand this properly:

 I have a large dynamic array (whose elements are immutable) 
 which only ever grows. I also have a whole lot of small slices 
 into this array, the slices never change, and they don't span 
 the entire contents of the array (they are just pieces).

 Now if I append to the large array, and the runtime needs to 
 re-allocate to accommodate the change in size, none of the 
 pieces of the original array which are referred to by the 
 slices can be freed, right? So I end up basically with two 
 copies of the original large array, however the first version 
 will now have little pieces missing from it (wherever the 
 slices don't refer).

 Is that correct?


  Sounds right.. But it could be worse. The slices that are used 
by the original array are ignored in the new array, so unless you 
have a main array reference to access the whole thing, then you 
wasted space can only get worse.

  Now on the other hand, if you were to append to a slice, then 
that slice would duplicate and then add onto it making a new 
slice with minimal loss compared to the much larger reference.

  In this kind of case I can only think of a few ways I'd want to 
work around it so to help minimize loss.

  1) Lowlevel check/test to see if it can be appended, if not 
start with new array so we don't reallocate and duplicate. 
(malloc/realloc may be needed)
  2) Reserve memory enough for N elements where it's your 
estimated Max (or a little over)
  3) Save beginning/ending locations as ints instead of a slice 
(although the main/original array would need to be accessible); 
You then can create temporary slices for functions as needed, 
long as they don't leave the current scope.
  4) Work with small slices only, meaning you get 100 or so, then 
a new array with another 100 or so.
Oct 21 2012
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Monday, October 22, 2012 01:35:29 cal wrote:

 Just want to make sure I understand this properly:
 
 I have a large dynamic array (whose elements are immutable) which
 only ever grows. I also have a whole lot of small slices into
 this array, the slices never change, and they don't span the
 entire contents of the array (they are just pieces).
 
 Now if I append to the large array, and the runtime needs to
 re-allocate to accommodate the change in size, none of the pieces
 of the original array which are referred to by the slices can be
 freed, right? So I end up basically with two copies of the
 original large array, however the first version will now have
 little pieces missing from it (wherever the slices don't refer).
 
 Is that correct?


Blocks of memory are allocated and freed as a whole. When an array is forced 
to be reallocated, then a new block of memory is allocated for it, and any 
existing slices continue to refer to the original block of memory. The 
original block will not be freed until there are no more slices which refer to 
it. You really should read this article if you want to know how arrays work in 
D:

http://dlang.org/d-array-article.html

- Jonathan M Davis
Oct 21 2012
parent "cal" <callumenator gmail.com> writes:
On Monday, 22 October 2012 at 04:59:41 UTC, Jonathan M Davis 
wrote:

 Blocks of memory are allocated and freed as a whole. When an 
 array is forced
 to be reallocated, then a new block of memory is allocated for 
 it, and any
 existing slices continue to refer to the original block of 
 memory. The
 original block will not be freed until there are no more slices 
 which refer to
 it. You really should read this article if you want to know how 
 arrays work in
 D:

 http://dlang.org/d-array-article.html

 - Jonathan M Davis


Ah thanks, I didn't realize the _entire_ original array would 
hang around. That makes my current approach really dumb. Cheers
Oct 21 2012