Re: Growable arrays?

[Daniel Hartwig <mandyke@gmail.com>]

On 14 June 2012 23:34, David Kastrup <dak@gnu.org> wrote:
> Daniel Hartwig <mandyke@gmail.com> writes:
>> The
>> guile core provides already a solid set of fundamental types which are
>> very easy to compose to produce *exactly* the type required for any
>> particular situation.
>
> Except when they don't.  Which is what started this thread.

You don't find that the guile primitives are easy to compose?

Please remind me what data structure you are precisely after?  You
initially were comparing with Lua tables, but then mentioned that you
only required the resizable vector function.

There has been at least two examples of that data types posted to this
thread which use the underlying vector primitive.  Both examples are
very simple.

Compared to a lot of the data types at the core of guile, resizable
vector has *lots* of variety in it's details, the particular subset
you optimize depends on your usage.

>>> Another complex type, this time with quite more serious memory and
>>> performance impact, that can't be implemented on top of a simple
>>> resizable common primitive and has an almost, but not quite, overlapping
>>> underlying feature set?
>>>
>>> It's almost as if you _like_ not being able to reuse code.
>>
>> I don't see how either hash table or multi-dimensional array type
>> could benefit from a shared, resizable primitive – they are quite
>> different algorithms, and both different again to the basic resizable
>> vector already discussed.
>>
>> It is moot that hash table internally manages a vector and allocates a
>> /new/ vector when needed.  This is not a simple resizing operation.
>
> Huh?  When resizing a hash table by doubling, you need to recoalesce
> each bucket to two buckets, one of which is the original.  Doubling the
> size of the underlying vector is a reasonable start to do this operation
> as a half-in-place rather than a three-address variant.

What is this half-in-place algorithm that makes this efficient?  If
the table is to remain balanced, all items should be rehashed and
reallocated to a new bucket and there is no correlation between an
items old and new buckets (hash).

Perhaps I miss an obvious trick, but I am thinking of …

… when the table controls it's own memory:

1. allocate new vector
2. assign each item to it's new bucket
3. destroy old vector

… when the table does not control it's own memory but uses an
underlying resizable type:

1. resize vector
1a. allocate new vector
1b. move data to head of new vector
1c. destroy old vector
2. assign each item to it's new bucket but this time watch out for
already populated buckets …

which to me /seems/ less efficient, and particularly bad if the
buckets are linked lists or open addressed.

But I am curious if this can be done efficiently, and indeed if it is
more efficient than the table managing it's own memory.

>
>> Are there any data types in the guile core which would benefit from
>> sharing a resizable vector primitive?
>
> Hash tables.  Apparently vlists.  I am not convinced that this does not
> make sense for normal and uniform vectors as an option as well.

A vlist is a very different, it does not resize the underlying vectors
but chains them together.  This avoids the memory copy implicit to
resizing vectors at the expense of some speed during other operations.
 The particulars also permit multiple vlists to share arbitrary tails,
and other nice properties.