[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Storage Efficiency of Vectors



Alan Watson wrote:
I'm also not sure that "stretchy" vectors will help much in the common
case that a vector of an initially unknown size is constructed and then
its size is not changed.  ... So, to some degree which is better
comes down to the distribution of vector lengths. However, we're talking
about factors of less than two.

The tradeoff here depends a lot on your memory allocation and gc
overheads.  If you have a memory allocator that is tuned for handling
allocating and reclaiming cons cells really fast, then I suspect the
best strategy is to use a temporary list.  On the other hand if
object allocation or collection are relatively slow or don't
special-case cons cells, then re-allocating will probably be faster.

It is of course more elegant (and more portable) to have the final
result be a vector whose allocated size matches the active size.
For best general-purpose efficiency it might be best to allocate
temporary medium-sized chunks of say 32-64 elements and chain them
together, and then make a final pass copying them to the result vector.
--
	--Per Bothner
per@xxxxxxxxxxx   http://per.bothner.com/