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

[Tom Lord]

    > From: Denys Duchier <address@hidden>

    > Matthew Dempsky <address@hidden> writes:
    > > Pika's FFI will handle resizable vectors and threading fine because
    > > users never get pointers to the vector contents -- they can only do
    > > vector-ref and vector-set! operations on them.

    > That's true only if you can implement vector-ref and vector-set! as
    > atomic operations with respect to thread scheduling (simplest case),
    > or (more generally) if you remain consistent with an interleaving
    > semantics (not necessarily the one that actually occured) (can be hard
    > to prove).

The intention is that, in the FFI, they are atomic operations.


    > The problem is that vector-ref would typically be implemented using
    > two atomic steps:

    >   (1) fetch the pointer to the vector
    >   (2) fetch an entry in that vector

    > The crucial issue is: what happens if the thread executing the
    > sequence of two steps above is preempted by the scheduler between
    > steps 1 and 2?  Some other threads might then do arbitrary things to
    > the vector, such as resizing it.  [...] Also, what if the GC kicks in?

Good summary.

    > You probably wouldn't want to incur a mutex overhead for every
    > access.

    > Possibly, you have already addressed and resolved these issues, but
    > that was not apparent to me from the postings.


It's a little bit subtle.

The implementation of Pika is split into two parts, separated by an
abstraction barrier.  We can call these the "representations" part and
the "generic" part.

The default way to access or set vector elements,
scm_vector_{set,ref}, is part of the API between those two layers.

Consequently, those functions are _also_ part of the FFI of pika
(which is essentially a union of the representations API with the
generic API).

The internals of the representations part is where issues are resolved
such as: how are objects tagged?   what kind of GC is used?  are
threads supported?

Code using the FFI and code in the "generic" layer have to be
conservative -- portable to many kinds of GC; portable to
threads-or-no-threads.

So, now, about vector primitives:

scm_vector_{set,ref} are, indeed, semantically required to be atomic
operations.   Should the representations provide threads, they must,
indeed, be implemented with some form of locking.   

The chief virtue of that approach is that it is simple to use
correctly.  For uses from C: mostly, this is a non-issue.  It won't
matter much for performance.

But now the subtle parts:

In single-threaded instances -- which I regard as an important
special case -- locking is only an issue so far as asynchronous event
handling is concerned.  But Pika will use a polling-based approach to
asynchronous event handling -- so locking will not be needed at all in
single-threaded implementations.

For multi-threaded instances: Later, we'll add additional functions
that allow the locking to take place outside of the representations
level.  For example, FFI-using code can (briefly) lock one or two or N
vectors, reference and set their elements without additional locking,
then release the lock.  Something like a VECTOR-MOVE! or VECTOR-FILL!
implementation will likely want to use this interface instead.

The situation for the interpreter is not firmly decided, but I think a
reasonable approach in threaded environments will be to: (a) regard
FFI-using code in any thread as a single mutator; (b) make all
interpreter threads and the conglomeration of FFI-using threads behave
in what you describe as an "interleaving" manner.

Finally, what about compiled code?  Suppose that someone writes
VECTOR-FILL! in Scheme and compiles it.  Must the VECTOR-SET! calls in
their loop use the (possibly locking) scm_vector_set?  Well, yes --
absent esoteric optimizations specific to Pika and absent being
written using low-level dangerous procedures (also specific to Pika),
it must use the maybe-locking primitives.  But this is exactly an
example of why it's worth making a Scheme with a nice C interface in
the first place -- so that we don't have to solve impossible problems
in compilers just to make a practical system.  If you can't get a good
VECTOR-FILL! by coding it in Scheme -- and it's critical to the
performance of your application -- just write in either C or in
Scheme-but-using-low-level-Pika-specific-primitives.

-t