Builtin array and AA efficiency questions

[Random D user via Digitalmars-d-learn]

Thanks for thorough answer.

On Thursday, 15 October 2015 at 18:46:22 UTC, H. S. Teoh wrote:
>
> It adjusts the size of the allocated block in the GC so that 
> subsequent appends will not reallocate.
>

So how does capacity affect this? I mean what is exactly a GC 
block here.

Shrink to fit bit was confusing, but after thinking about this 
few mins I guess there's like at least three concepts:

slice          0 .. length
allocation     0 .. max used/init size (end of 'gc block', also 
shared between slices)
raw mem block  0 .. capacity (or whatever gc set aside (like 
pages))

slice is managed by slice instance (ptr, length pair)
allocation is managed by array runtime (max used by some array)
raw mem block is managed by gc (knows the actual mem block)

So if slice.length != allocation.length then slice is not an mem 
"owning" array (it's a reference).
And assumeSafeAppend sets allocation.length to slice.length i.e. 
shrinks to fit. (slice.length > allocation.length not possible, 
because allocation.length = max(slice.length), so it always just 
shrinks)
Now that slice is a mem "owning" array it owns length growing 
length happens without reallocation until it hits raw mem 
block.length (aka capacity).

So basically the largest slice owns the memory allocation and 
it's length.

This is my understanding now. Although, I'll probably forget all 
this in 5..4..3..2...

> The thought that occurs to me is that you could still use the 
> built-in arrays as a base for your Buffer type, but with 
> various operators overridden so that it doesn't reallocate 
> unnecessarily.

Right, so custom array/buffer type it is. Seems the simplest 
solution.
I already started implementing this. Reusable arrays are 
everywhere.

> If you want to manually delete data, you probably want to 
> implement your own AA based on malloc/free instead of the GC. 
> The nature of GC doesn't lend it well to manual management.

I'll have to do this as well. Although, this one isn't that 
critical for me.

> The only thing I can think of is to implement this manually, 
> e.g., by wrapping your AA in a type that keeps a size_t 
> "generation counter", where if any value in the AA is found to 
> belong to a generation that's already past, it pretends that 
> the value doesn't exist yet.  Something like this:

Right. Like a handle system or AA of ValueHandles in this case. 
But I'll probably just hack up some custom map and reuse it's 
mem. Although, I'm mostly doing this for perf (realloc) and not 
mem size, so it might be too much effort if D AA is highly 
optimized.