Re: [Pika-dev] Guile FFI: resizable vector problem

[duchier]

Tom Lord <address@hidden> writes:

> So an operation like vector_set is:
>
>       1: ar = array(vector);
>         2: ar[x] = value;
>
> And vector_resize is something like:
>
>       1: array(vector) = realloc (array(vector),newsize)

realloc cannot be used because, as I mentioned previously, to support
the interleaving semantics, you may need both the vector before and
the vector after simultaneously.  I would suggest to model it slightly
differently:

        1. ar1 = array(vector)
        2. ar2 = allocate(newsize)
        3. copy(ar1,ar2)
        4. array(vector) = ar2

and this make clear that you are right and there is a problem, for
example because copy(ar1,ar2) is normally not an atomic operation.  I
think the interleaving argument works fine with non atomic
vector-ref/vector-set! in the absence of resizing, but that's not
exactly what we wanted :-(

Unless someone has a brilliant idea, it indeed looks like some form of
locking may be necessary to protect against unresolvable
inconsistencies that could be introduced by a non-atomic resize.

I'll then refine the vague idea I previously outlined into what could
be more properly regarded as an optimization that minimizes the actual
locking overhead.

I would suggest a spin-lock technique on architectures that support
atomic test-and-set, using the array(vector) pointer itself as the
lock.  As per the interleaving semantics argument, the lock need only
be taken for resizing (still needs a formal proof). Each operation
spins as long as array(vector) is 0.  Locking is setting array(vector)
to 0.

With this idea, if a resizing lock is taken at time T, all other
operations that were _initiated_ before T, will be ordered in the
interleaving semantics as _completing_ before any operation initiated
after T.

The advantage of this idea is that typical executions require no
locking:

        vector-ref(V,I)
            do { ar=vector(V); } while (ar==0);
            return ar[I]

for improved branch prediction, when compiling with gcc, we could
write the condition __builtin_expect((ar==0),0) because typically the
lock won't be taken.

Again, an important assumption in the above is that vector memory
collection is not explicitly managed (e.g. by calling realloc as in
your suggestion), but is subject to ordinary GC.  The reason is that
there may be operations that are _initiated_ before a resize, and I
don't want to force them to also complete before the resize (which is
what you suggest when you say that all operations must use locking).

> Second: from the point of view of _Scheme_ semantics -- all concurrent
> executions of vector_set and vector_resize have the same result: the
> assignment takes place and is apparent in the final result.  Locking
> is necessary for that reason, too.  This objection is, I think,
> unsurmountable.

I didn't understand that paragraph.

Cheers,

-- 
Denys Duchier - Équipe Calligramme - LORIA, Nancy, France