Array append performance 2

bearophile bearophileHUGS at lycos.com
Sun Aug 31 08:37:13 PDT 2008


Fawzi Mohamed:
> I would have done it quite differently: keep a linked list (if you want 
> to improve of batches of 10 arrays), with a pointer to the end, append 
> in O(1), and keep the total length.
> only upon a call to toArray allocate an array of the requested length 
> and fill it.
> An array (even with tricks) is not a good structure to append to, so it 
> seems a bad idea to me to use it.

Yes, my code was experimental, my main purpose was to ask if it's correct, in its GC management, etc. Algorithmic and code tuning is something I think about later.

I'm now implementing ArrayBuilder with a deque-like, to see how it performs in comparison.
There are 3 possible things you may want to join to such ArrayBuilder:
- Fixed size arrays
- Single items
- Dynamic arrays

For the dynamic arrays can be copied just a reference, for the other is better to copy the data. The single items can be added to short (64 KB) structs with fixed size arrays inside, organized into a linked list. The static arrays can equally be copied in pieces into such blocks. The dynamic arrays instead require short arrays filled with the struct of the dynamic arrays. This makes things messy. If the user keeps alternating single items to dynamic arrays the data structure has to avoid wasting too much memory. So I don't see an easy solution yet, beside my original one or a similar one (that consists in copying all items of dynamic arrays too).

Bye and thank you,
bearophile



More information about the Digitalmars-d mailing list