[Top][All Lists]

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

Re: Growable arrays?

From: Krister Svanlund
Subject: Re: Growable arrays?
Date: Sat, 9 Jun 2012 16:43:27 +0200

On Sat, Jun 9, 2012 at 2:32 PM, David Kastrup <address@hidden> wrote:


the main data structure of Lua is a "table", an associative array, and a
table t has a continguous numerically addressed part from 1..#t, with
all other indices going through a hashing mechanism.  One principal
distinguishing feature, like with a Scheme hashtable, is the ability to
grow on-demand.

Scheme/Guile vectors are fixed size.  Now I have a situation where I
have a basic type lattice with records stored in vectors, and this type
lattice may be extended dynamically (which typically happens at the
start of a whole file, for potentially multi-file runs).  Scheme does
not offer a suitable data structure for that.  It is a bit of a nuisance
that one can grow a hashtable efficiently and on-demand, but not so an

Now it would be possible when the type lattice gets extended to store
the new entries in a hashtable and go from there.  Or put them into a
list, and reallocate on first access beyond the existing element.  That
seems rather contorted.  And since there is, if I remember, a project to
run Lua on top of Guile, having a fundamental and reasonably efficient
data structure corresponding to a Lua table, or at least the contiguous
part of a Lua table, would seem like a reasonably useful idea.  After
all, there already _is_ such a mechanism underlying hash tables so it
seems somewhat peculiar not to have it available for vectors as well.


David Kastrup

I don't know how much you know about data structures, and I must confess I'm not very educated on Guile or Luas implementations. Based on what you are writing I would assume that the scheme hashtables aren't growable in the same way as a vector has to be growable. The number of elements in a hashtable isn't limited by it's "size". They are often implemented as each position (where the hashtables size is the number of positions) being a linked list giving the hashtable (in theory) limitless actual size. Growing a vector/array involves having to allocate new continuous memory and copying all the elements there, so for example in C++ (i think) the std:vector is increased by half it's current size each time meaning that the more expensive the copying gets the more elements you can insert into the vector before it has to resize.

I would assume it wouldn't be that difficult to implement a pretty efficient growable vector for scheme.

// Krister Svanlund

reply via email to

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