[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Growable arrays?

From: David Kastrup
Subject: Re: Growable arrays?
Date: Tue, 12 Jun 2012 22:47:56 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1.50 (gnu/linux)

Mark H Weaver <address@hidden> writes:

> Hi David,
> David Kastrup <address@hidden> writes:
>> Mark H Weaver <address@hidden> 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

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]