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-threadis 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 ;
do-somethingis called while
ahappens 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
ais 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.
Threads are now a first-class data type and runnable threads are registered in a global hashtable which can be printed by the
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
in-threadword 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
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:
49 x set-global
63 x [
[ x get . ] "Test" spawn drop
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
:: 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.
tsetwords get and set thread-local variable values, just like
setfor dynamic variables.
There are essentially no changes to this other than the fact that the concurrency vocabulary is now named
concurrency.messaging, and the
spawnword has been moved into the core
Promises and futures
These have been split out and moved into
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:
<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
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-write-lock. Read/read, Write/read and write/write reentrancy is supported.
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-downand can be waited on with
Count-down latches are used to implement a
parallel-eachcombinator. 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 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 are in the
concurrency.semaphoresvocabulary. 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-semaphorecombinator is provided which decrements the semaphore, runs a quotation, then increments it again.
Here is an example which uses
parallel-eachto 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-expensive-stuff ] curry with-semaphore
: do-jobs ( values -- )
10 <semaphore> [ do-job ] curry parallel-each ;