[Gardeners] SSC-Spec & Bordeaux-Threads, was Re: Shared State Concurrency specification.

[Marco Monteiro]

I'll give you an example: thread A spawns thread B. Should thread B 
'see'the special variables bindings of thread A, or should it 'see' the 
global values? In Bordeaux-Threads it depends of the implementation: it 
depends on the behavior of the implementation because it is on top of 
it. I want this to be specified in SSC: SSC is to be made part of the
implementation. This is why the objectives differ. If SSC (or something
like it) succeeds, Bordeaux-Threads will be irrelevant; there will be no
need for a library to hide some of the differences between
implementations (knowing it could never hide them all). If it does not,
Bordeaux-Threads is very useful.

Note that the difference between a reader-biased rwlock and a
writer-biased is performance (and maybe possible starvation of some 
threads). They are both rwlocks (only readers or a writer can use the
shared resource at a time). It is specified that they work as rwlocks;
it is not forced on the implementation that it must be as fast as it can
be, given the hints of the programmer of how they are used.

Matthew Astley wrote:
> Questions herein: how do we make useful specs? how can CL power be
> added to threads? speed of implementation (improving and displaying).
> 
> On Tue, Jul 18, 2006 at 11:20:29AM +0100, Marco Monteiro wrote:
> 
>> I do know Bordeaux-Threads. The purpose of the SSC project is to
>> build a thread model specification, programming interface
>> documentation and a test suite.
> 
> B-T appears to have these, for a set of the features which partly
> overlaps SSC and differs in some details.  Both differ again from
> sb-thread.  I don't understand what SSC is doing that B-T isn't.
> 
> How should the "specification" part differ from the interface docs?
> 
> I see that SSC has &allow-other-keys on spawn-thread where B-T doesn't
> on make-thread; SSC has some a fairness control on rwlocks and then
> says this is only a hint and can be ignored; B-T says "Local bindings
> in the the caller of MAKE-THREAD may or may not be shared with the new
> thread [...]".
> 
> Are these the sorts of difference that make the text a spec instead of
> API docs?
> 
> 
>> In addition, I'm working on an implementation of the SSC
>> Specification in SBCL.
> 
> My understanding of specification vs. implementation is that it's most
> useful to have one specification per problem area, then perhaps
> multiple implementations to provide some richness and competition.
> 
> Was the process of standardising ANSI CL basically a diffing of the
> existing implementations and a pondering of what should be Common?
> Can this be done for B-T and SSC, and any others out there?
> 
> If such diffing is to be done, can you include in each spec part some
> mention of alternatives that were discussed and why they weren't
> included?  B-T has some of this.  I imagine it would make it easier
> for people to see why the spec is the way it is, without discussing
> the points again if another similar-but-different spec comes along for
> comparison.
> 
> 
>> Although it will probably be done, the main purpose is not to build
>> a wrapping library for CL implementations. There are too many
>> differences between the implementations for an approach like that to
>> work well.
> 
> Can you list some differences?  They will be important for anyone
> trying to write portable code.  For a spec to say implementation-
> defined of an important feature is honest but not very helpful.
> 
> Too many undefined things will tend to send the programmer down
> single-implementation alleys - this is my small experience[1].
> 
> 
> If a wrapper library is provided, it should be easier to translate or
> cushion the differences between native thread implementations.  This
> may come with a speed penalty, but that can be removed by pushing the
> feature back up into the compiler at some later time - without
> changing the API.  This gives programmers all the benefits.
> 
> Have I missed something?
> 
> 
> 
>> [...] not very innovative [...] almost POSIX threads for CL.
> 
> So much for bringing POSIX threads to CL.  Is anyone interested in
> talking about what CL can bring to threads?
> 
> I started wondering about restarts (in the context of deadlock) and
> how a macro should know which lock to acquire when modifying a
> variable.
> 
> There must be more things possible, that other threaded languages
> simply can't support or imagine.  I don't have enough experience with
> CL or threads to know what else has been done, but I'm happy doodling.
> 
> 
> [...]
>> I'm open to all suggestion regarding the API to approximate it to what 
>> exists in Bordeaux-Threads; maybe change LOCK-MUTEX and UNLOCK-MUTEX to 
>> ACQUIRE-LOCK and RELEASE-LOCK, for instance.
> 
> There are other differences.  Why does B-T need all of
>   make-lock           acquire-lock            release-lock
>   make-recursive-lock acquire-recursive-lock  release-recursive-lock
> when SSC can make do with
>                       lock-mutex              unlock-mutex
>  (make-mutex :kind :no-errorcheck)
>  (make-mutex :kind :recursive)		?
> 
> Also, why do
>   '(condition-wait condition-notify thread-yield thread-name threadp)
> have subject-verb or subject-property, while
>   '(interrupt-thread acquire-lock make-thread) etc.
> have a verb-subject pattern?
> 
> I'm not trying to take sides, I only wish to work upwards on the
> usefulness gradient.
> 
>> Maybe we can work together to merge our efforts, although we are not
>> working with the same objective.
> 
> As a potential user, merging sounds good to me.  I don't understand
> how the objectives differ, can you explain please Marco?
> 
> 
> 
> [...]
>> Semaphores and cyclic barriers can be implemented more efficiently
>> if they are in the implementation. In my SBCL implementation, for
>> instance, semaphores are several time faster than if they were built
>> on mutexes and condition variables. Synchronization primitives
>> should be very efficient.
> 
> This was the comment that sparked my comment about moving features
> from wrapper library up into implementation.
> 
> It also suggests that in addition to the test suit showing green (i.e.
> safe to use) across platforms, it may be useful to give relative
> speeds for the supported constructs on each.
> 
> 
>> Thread mailboxes will not be in SSC; I'm still thinking how to allow
>> extensions to build them; [...]
> 
> Suppose I wish to lock the tail of a list for writing (cons onto or
> remove from the slow end).  Under my naive view of how lists are made,
> it appears to be safe to do this even while another thread push'es or
> pop's the head of the list.  Provided the list has two (one?) cons.
> 
> This is relevant for making fast thread mailboxes.  Also I hold it up
> as an example of where POSIX locking semantics may be limiting.  Does
> this make any sense?
> 
> 
> Matthew  #8-)