Some changes to threads

For the last two days I've been working on Factor's threading system. First the bad news: it is still a co-operative threading system that doesn't use multiple cores. However the changes were pretty extensive.

I noticed a memory leak in the UI: sometimes opening and closing lots of windows didn't release memory. I tracked it down to a "feature" of Factor's threads: when in-thread is called, the new thread starts with a copy of the current thread's data stack and name stack. This is wrong; consider the following code:

: do-something ( x -- )
    [ ... ] in-thread process-x ;

: another-word ( a x -- b )
    do-something blah ;

Here, do-something is called while a happens to be on the stack, and the new thread starts with this value on the stack too. However, do-something's stack effect does not include a; it doesn't care about a, and if a is large and the thread outlives the dynamic extent of the call to another-word, then we've potentially leaked memory.

Another limitation of Factor's threads I've been annoyed with in the past is that there's no way to get a list of running threads: threads were just continuations, and threads waiting on some condition were just some random continuation stashed away somewhere.

A final issue was that Chris Double''s message-passing concurrency library needed to associate a mailbox with every thread, and he was doing this in an ad-hoc way, storing the mailbox in a dynamically-scoped variable when spawning the thread. However the problem with this approach is that dynamic scope is not exactly thread local scope: if a continuation is reified in one thread and resumed in another, it inherits all dynamic bindings, whereas in this case you would not want it to inherit the mailbox.

So with these three problems in mind, I set out to make some changes to Factor's thread system.

Spawning threads

Threads are now a first-class data type and runnable threads are registered in a global hashtable which can be printed by the threads. word.

To spawn a thread, it is now recommended that you use the following word:

: spawn ( quot name -- thread )

It now takes a name for debug purposes, and outputs the thread on the stack. The new thread starts with an empty data stack and a name stack containing the global namespace only; if you want to pass data to the thread, you must arrange for this by partially applying the data to the quotation using curry or compose.

The in-thread word is still there and has the old behavior: the new thread gets a copy of the data and name stacks, and nothing remains on the stack. It is useful for quick tests and such, but new code should use spawn instead.

Dynamic, lexical and thread-local variables

As I've mentioned, new threads no longer inherit the name stack when started with spawn (to get the old behavior, use in-thread). That is, the following will print 49:

SYMBOL: x

49 x set-global
63 x [
    [ x get . ] "Test" spawn drop
] with-variable

This behavior is in line with a number of Common Lisp implementations that decided not to have threads inherit dynamic bindings for similar reasons (potential hard to find memory leaks) as well as issues unique to Common Lisp (dynamic variables can be stack-allocated if dynamic extent optimizations are used).

Note that threads still respect lexical scope just as one would expect. Here is a word which makes a closure that closes over the parameter to the word (n) as well as a binding established by [let:

:: make-thread | n |
    [let | x 49 |
        [ [ n x + . ] "Test" spawn ]
    ] ;

We can make a closure and call it; it will print 69:

20 make-thread call

This required no extra work to implement correctly; the locals vocabulary already implements correct closure semantics for all combinators.

Thread-local variables are new. I haven't found a use for them yet, but they were trivial to implement now that threads are first-class.

The tget, tset words get and set thread-local variable values, just like get and set for dynamic variables.

Message-passing concurrency

There are essentially no changes to this other than the fact that the concurrency vocabulary is now named concurrency.messaging, and the spawn word has been moved into the core threads vocabulary.

Chris Double's channels work unchanged.

Promises and futures

These have been split out and moved into concurrency.promises and concurrency.futures, respectively.

Locks

Message-passing concurrency and channels are great but sometimes you just need something simpler. I implemented some new abstractions, mostly by taking ideas from Java's java.util.concurrent package.

First up are locks, found in concurrency.locks. These come in two forms, non-reentrant and reentrant. A combinator is used to acquire and release the lock, ensuring that lock operations are paired:

SYMBOL: my-lock

<lock> my-lock set

...

my-lock get [ ... ] with-lock

Reentrant locks can be acquired recursively by a thread already holding the lock; otherwise they are the same. They are created by <reentrant-lock>.

Read/write locks

Read/write locks implement the pattern where you want multiple reader threads to have access to a shared resource, but only one writer thread to have access at a time, and only if no threads are reading.

Read/write locks are created with <rw-lock>, and acquired/released with with-read-lock and with-write-lock. Read/read, Write/read and write/write reentrancy is supported.

Count-down latches

A count-down latches, found in concurrency.count-downs, begin with some initial value; threads can either wait for its value to reach zero, or decrement its value (never past zero). They are craeted with <count-down>, decremented with count-down and can be waited on with await.

Count-down latches are used to implement a parallel-each combinator. This combinator takes a sequence and a quotation, spawns a thread for each element, and waits for them all to finish. It does this by creating a count-down latch that each thread decrements as it finishes; after spawning all threads, the caller waits for the latch to reach zero.

Exchangers

Exchangers are implemented in concurrency.exchangers. An exchanger is a synchronization point between two threads: a thread comes to the exchange point with an object, and waits for another thread to do the same. Then the first thread receives the second thread's object, and vice versa.

Exchangers are created by calling <exchanger> and objects are exchanged with exchange. Their implementation is delightfully simple thanks to boxes:

TUPLE: exchanger thread object ;

: <exchanger> ( -- exchanger )
    <box> <box> exchanger construct-boa ;

: exchange ( obj exchanger -- newobj )
    dup exchanger-thread box-full? [
        dup exchanger-object box>
        >r exchanger-thread box> resume-with r>
    ] [
        [ exchanger-object >box ] keep
        [ exchanger-thread >box ] curry "exchange" suspend
    ] if ;

Counting semaphores

Counting semaphores are in the concurrency.semaphores vocabulary. Semaphores are created by passing an initial non-zero value to <semaphore>. A thread can either decrement a semaphore with acquire, or increment one with release: if it is already zero when being decremented, it waits for another thread to increment it first.

Unlike locks, acquire/release does not need to be paired and can even be done in different threads: however for pairing, a with-semaphore combinator is provided which decrements the semaphore, runs a quotation, then increments it again.

Here is an example which uses parallel-each to spawn a series of jobs, the jobs proceed mostly in parallel however a semaphore is used to ensure that one particular section is not run by more than 10 threads at a time, perhaps because it spawns an external process which uses a lot of memory and we do not wish to hit the swap:

: do-stuff ( value -- ) ... ;

: do-expensive-task ( value -- ) ... ;

: do-more-stuff ( value -- ) ... ;

: do-job ( value semaphore -- )
    over do-stuff
    over [ do-expensive-stuff ] curry with-semaphore
    do-more-stuff ;

: do-jobs ( values -- )
    10 <semaphore> [ do-job ] curry parallel-each ;