Re: Growable arrays?

[David Kastrup <dak@gnu.org>]

Mark H Weaver <mhw@netris.org> writes:

> 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.

A vector with run-time determined size?  Which variant of C++ offers
that?

>> 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.

Reality check: C++ does not offer structs/classes containing vectors of
run-time determinable size.  You need to allocate a pointer for them.

You are apparently confusing fixed size with compile-time size.

-- 
David Kastrup