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 ;
