Re: Growable arrays?

[Mark H Weaver]

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.

Even if one is willing to pay the price of a relatively heavyweight
primitive data structure, Lua's tables are not always a good fit.  What
if you need a table keyed on large, sparsely distributed integer keys?
What if you need a linked list with O(1) insertions?  What if you need a
doubly-linked list with O(1) deletions?

Data structure design involves many tradeoffs, and unfortunately there
is no complex "one-size-fits-all" data structure that is a good
universal primitive upon which to build all others.

    Regards,
      Mark