Re: Growable arrays?

[David Kastrup]

Mark H Weaver <address@hidden> writes:

> Hi David,
>
> David Kastrup <address@hidden> writes:
>> I don't think I need yet another data structure deficient in some
>> respects.  We have vectors that can't grow, hashtables that can grow but
>> only index through a hash function, vlists that can grow but have
>> immutable content...
> [...]
>> Why not just have a superset without arbitrary restriction and implement
>> the other structures based on that?  Then each one just needs to enforce
>> its personal restrictions in its accessor functions, and otherwise just
>> use what is there in the general mechanism.
>
> 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.  What kind of
performance gains are we talking about in a typical vector-heavy
application?  0.5%?  Scheme is, to some degree, a computer theoretic
language.  But in this case, this seems to me more like a "don't ask,
don't tell" scenario regarding the possibility of using one underlying
primitive type that dares to be a trifle more flexible than the
theoretically achievable minimum.  Scheme implementations have
considerable leeway concerning their memory and data layout.

-- 
David Kastrup