Re: Growable arrays?

[David Kastrup <dak@gnu.org>]

Daniel Hartwig <mandyke@gmail.com> writes:

> On 15 June 2012 01:15, David Kastrup <dak@gnu.org> wrote:
>> Daniel Hartwig <mandyke@gmail.com> writes:
>>> 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).
>>
>> Huh?  Hashing computes a hash value, and the bucket is determined by
>> hash % vectorsize.  Double the vector size, and the new bucket locations
>> are at bucket and bucket+vectorsize, so you need to coalesce the bucket
>> at bucket into the buckets at bucket and bucket+vectorsize.
>>
>> Why would there be no correlation between old and new buckets when they
>> are calculated based on the same hash code?
> …
>
> I see.  So starting from the old tail there is little contention for
> the new buckets.  This seems obvious now in hindsight :-)
>
> Regarding the data type for your application, this is something which
> needs to be accessible from the c side also?

No.  And we have significant amount of C code of our own, so adding
stuff here is not a problem.  And we are talking about rather
performance-critical stuff.

For one thing, it feels ridiculous having to implement a rather basic
data type oneself.  For another, growing a memory area can sometimes be
done in-place when one talks nicely to the garbage management (allocate
from the free space following the resizable vector preferably backwards,
so that resizing may still be opportunistically possible.  Or allocate
the vector itself backwards and try growing it backwards in memory).
There are various strategies that might be more efficient than the
"naive relocator" but that can't be done without actually meddling with
Guile internals.

-- 
David Kastrup