TList

[Frits van Bommel]

Jesse Phillips wrote:
> On Wed, 19 Mar 2008 00:15:43 +0100, Frits van Bommel wrote:
> 
>> Sclytrack wrote:
>>> I was told that adding an array in D uses realloc (Haven't verified
>>> this),
>> It doesn't use C realloc(). In fact, it can't for several reasons: 1)
>> realloc only works on memory allocated by the normal C allocation
>> functions (malloc, calloc), which D doesn't use because they don't[*]
>> support GC.
>> 2) realloc is supposed[*] to free the original if reallocation succeeds
>> but the array was moved, which isn't what's supposed to happen when a D
>> array grows (the old one is left for anyone who still has references to
>> it; the GC cleans it up if that's not the case).
> 
> This is something I've wondered about, so D will grow the array in-place 
> on the ram?

(Imagine this post liberally sprinkeled with "IIRC"s :) )
The GC allocates memory in pools[1], with all blocks of memory in a pool 
having the same size[2]. If an array is appended to using ~=[3] it will 
be done in-place if these conditions hold:
1) The array is GC-allocated.
2) The array starts at the first byte of the block it's allocated in.
3) The resulting array will still fit into the block (i.e. there's still 
room)

If one of them doesn't hold, the append routine allocates a new block of 
memory to hold the result in an appropriate pool for its size, as if it 
had just been 'new'ed[4].


[1]: Large objects are allocate separately.
[2]: I don't know which sizes it uses, but powers of two are usual for 
this sort of thing.
[3]: Not with ~, which allocates unconditionally (even if one of the 
operands is empty).
[4]: Except perhaps uninitialized, since the append routine has access 
to internal GC functions and it can guarantee it'll always overwrite the 
whole block (the start with the result of concatenating the input 
arrays, and the rest with 0).