Per Bothner <per@bothner.com> writes:

> On 08/19/2014 09:15 AM, Taylan Ulrich Bayirli/Kammer wrote:
>> Also if I remember correctly, resizable vectors incur a general
>> overhead on access, in addition to implementation complexity.  So
>> they should likely be a separate library, no?
>
> Simple re-sizable vectors require an indirection that might otherwise
> not be needed.  This overhead is much less than using linked lists.

For accessing elements, yes.

> Many programs needs to "build" a sequence, typically appending at the
> end each element as it is produced.  Using an array that gets
> reallocated (doubled) when full is usually the most efficient
> representation.  Having a standard re-sizable (growable) vector type
> would simplify the programming.

I think the typical way of doing this is to cons up a reverse list,
reverse! it, and use list->vector.  If the sequence is built at once
then this should be fine.

If the sequence needs to be accessed and expanded together efficiently
then that doesn't work and a different data structure is needed.  I
don't know how common of a situation that is, and how undesirable the
intrinsic overhead is for situations that don't need it.

One of the nice things about Scheme in my opinion is that it doesn't
overload much functionality into one API and instead offers specialized
APIs which allow for efficient code; that is in contrast to other "very
high level" or "scripting" languages which trade off much more
efficiency for programmer convenience.  I suspect that if we force the
vector API to use resizable vectors, some users will end up wishing for
a static-size vector API (like fixnums).  I don't know which use-case
should be marginalized.  Perhaps the best thing to do is to go by what
most implementations currently do.

We could also leave it up to an implementation for now whether the
normal vector API should work on vectors created by a hypothetical
resizable vector API.  Forcing their merge can be left to the future,
whereas breaking them apart later would be backwards incompatible.

Tell me if I'm bikeshedding. :-)

Taylan

_______________________________________________
Scheme-reports mailing list
Scheme-reports@scheme-reports.org
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports