Email list hosting service & mailing list manager

Storage Efficiency of Vectors Alan Watson (16 Apr 2003 16:56 UTC)
Re: Storage Efficiency of Vectors Per Bothner (16 Apr 2003 18:40 UTC)
Re: Storage Efficiency of Vectors bear (16 Apr 2003 22:58 UTC)
Re: Storage Efficiency of Vectors Per Bothner (16 Apr 2003 23:08 UTC)
Re: Storage Efficiency of Vectors Taylor Campbell (17 Apr 2003 02:04 UTC)

Re: Storage Efficiency of Vectors Per Bothner 16 Apr 2003 18:41 UTC

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
xxxxxx@bothner.com   http://per.bothner.com/