Array append performance 2

[Fawzi Mohamed]

On 2008-08-31 17:37:13 +0200, bearophile <bearophileHUGS at lycos.com> said:

> 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

I had not thought about an important thing: the content of the array 
can change... so copying is safer.
Probably using (as you said) a linked list of fixed arrays is the best 
approach for many small appends, maybe append might have a bool 
argument "fixed=false" to know if copying can be avoided.

Fawzi