Hi David,

David Kastrup <dak@gnu.org> writes:
> Mark H Weaver <mhw@netris.org> writes:
>> Simpler data structures can usually be implemented with less memory,
>> shorter code sequences with fewer conditional branches and less space in
>> the instruction cache, which in turn means they can be implemented more
>> efficiently.  Therefore, to allow efficient compilation, primitive data
>> structures should be very simple, with more complex structures built on
>> simpler ones instead of the other way around.
>>
>> For example, consider resizable vectors vs fixed-size vectors.  A
>> fixed-size vector can be represented as a single memory block that
>> contains both the length and the elements together.  A resizable vector
>> requires an additional level of pointer indirection, which inevitably
>> means slower accesses and greater code size.  Furthermore, fixed-size
>> vectors allow the possibility of compiling in an unsafe mode where
>> out-of-bounds checks can be skipped.
>
> I have a really hard time swallowing an efficiency argument for Scheme
> that is weak enough in comparison with the associated drawbacks not to
> find consideration in the C++ standard template library.

C++, like Scheme, already supports fixed-size vectors in the core
language, so it would be redundant to include them in a library.

> What kind of performance gains are we talking about in a typical
> vector-heavy application?

If C++ supported _only_ resizable vectors, such that there was no way to
avoid the additional level of pointer indirection, and all derived data
structures had to be built upon these doubly-indirected vectors, then
I'd expect that the efficiency impact would be quite significant in both
time and space.

I acknowledge that the added cost of resizable vectors would not be
noticable in the current implementation of Guile, that might very well
change in a few years when we have native compilation.  Therefore, I
continue to believe that our primitive vector type should be fixed-size.

On the other hand, I agree that Guile needs a more extensive library of
data structures (including resizable vectors) out of the box.

I've attached a preliminary implementation of resizable vectors.
Hopefully it works on Guile 1.8 as well, though I haven't tested that.
Comments and suggestions welcome.

    Best,
     Mark