AW: AW: Too much of a good thing? Michael Burschik 14 Apr 2003 08:31 UTC

Per Bothner wrote:
> Michael Burschik wrote:
> > Correct me if I'm wrong, but R5RS does not provide
> resizable vectors, and
> > functions generating vector element by element have no way
> of knowing the
> > length of the resulting vector beforehand.
> First, the SRFI process is about extending R5RS, so I don't see
> that as a restriction.

I am well aware of the fact that SRFIs are about extending R5RS, but I
wanted to point out that you cannot assume you have got resizable vectors at
your disposal *because* neither R5RS nor SRFI-43 mandate them.

> You have to use some data structure or programming convention that
> stores the "active length" - i.e. Common Lisp's "fill pointer".  If
> you're stuck with vanilla Scheme, then this would be a
> separate variable
> or a convention to use the the first variable of the vector.  (The
> former is awkward and the latter is worse, whihc is why an extension
> is needed.)

But this extension is not defined by SRFI-43, nor any other SRFI, as far as
I am aware.

> But assuming you have a separate fill pointer, then yes: It really is
> more efficient to allocate and re-allocate multiple vectors - as long
> as you each time double the allocated size.  E.g. start with a small
> vector of say 8 slots, then when that gets full use one with 16 lots,
> then one with 32 slots etc.  This uses less memory than cons cells
> (especially if you an object or malloc header), provides linear
> performance, and much better data locality.

Thanks for the explanation. Now, things begin to make sense. But again, the
SRFI does not define resizable vectors, and the reference implementation
does not use them either. Without resizable vectors, however, many of the
functions defined by the SRFI are just list manipulation functions followed
by list->vector.

Maybe a resizable vector library would be a worthwhile project. Or do many
scheme implementations offer resizable vectors?


Michael Burschik