[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: Thu, 14 Jun 2012 17:34:55 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.1.50 (gnu/linux)

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

reply via email to

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