Re: Growable arrays?

[David Kastrup]

Daniel Hartwig <address@hidden> writes:

> On 14 June 2012 22:47, David Kastrup <address@hidden> wrote:
>> Mark H Weaver <address@hidden> writes:
>>
>>> David Kastrup <address@hidden> writes:
>>>> Scheme/Guile vectors are fixed size.  [...]  It is a bit of a nuisance
>>>> that one can grow a hashtable efficiently and on-demand, but not so an
>>>> array.
>>>
>>> Although Scheme vectors should remain fixed-size for reasons I have
>>> given elsewhere in this thread, Guile also includes a more complex
>>> 'array' type that includes features such as arbitrary rank (i.e. number
>>> of dimensions), arbitrary lower bounds (not just 0), and shared views on
>>> the same underlying array with arbitrary affine mappings of indices.
>>>
>>> Guile 'arrays' cannot currently be resized, but I see no good reason for
>>> this limitation.  They are already quite complex, and already require a
>>> second level of pointer indirection.
>>>
>>> What do other people think?
>
> Perhaps drop a basic resizable type in the guile-lib?  Any
> implementation is going to be less-than-ideal in some situations. 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.

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

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

-- 
David Kastrup