Greetings!
I was poking around with threads today and implemented a "promises"
mechanism. (The discussion at
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/f24770a85b8fcecc/6eba41ffd39b7d9f?lnk=gst&q=promise+future+parallel&rnum=1#6eba41ffd39b7d9f
explains the difference between promises (must be forced explicitly)
and futures (implicitly return the value).) It works (passes
correctness tests) but I don't know if it's efficient. Here's the
code -- I'm using OpenMCL but I imagine it would look similar in any
CL with a POSIX-like threads interface. Below the code, I've got some
questions about efficiency.
(defstruct promise
(value nil) ; the value that the promise returns
(finished nil) ; T iff the promise has finished computing the value
(lock (make-lock))) ; Synchronizes access to the promise's value
(defun force (promise)
"Wait until the promise has completed its computation, and then
return its resulting value."
(progn
;; Hopefully PROCESS-WAIT doesn't spin on the condition.
(process-wait "Waiting on promise"
#'(lambda ()
(with-lock-grabbed ((promise-lock promise))
(promise-finished promise))))
(promise-value promise)))
(defun spawn (fn &rest args)
"Spawn off a promise that computes the function FN (with optional
arguments ARGS) and returns its value. Only one value is allowed."
(let ((x (gensym "thread-")) ; unique process name
(promise (make-promise)))
(progn
;; Create the thread and run it.
(process-run-function (symbol-name x)
#'(lambda ()
(with-lock-grabbed ((promise-lock promise))
(setf (promise-value promise) (apply fn args))
(setf (promise-finished promise) t))))
promise)))
Question: Is there a more efficient way of communicating "this thread
has finished its computations" than using a lock? Say that thread A
calls SPAWN (and later FORCE) and thread B computes the promise's
function. Is there a more efficient way for B to "signal" A than to
use a lock? Should I trust that PROCESS-WAIT is implemented
efficiently, or should I implement my own back-off policy to make sure
that A doesn't spin on the lock too much?
This is certainly somewhat system- and OS-dependent but I was
wondering if there was a general idea on this --
Many thanks,
mfh
P.S. I'm not necessarily advocating using promises or futures -- they
have their own problems (e.g., forget about unboxed values in arrays
and any kind of binary compatibility of arrays with C) -- but I'm just
curious how one would implement promises efficiently.
On Jul 9, 11:31 pm, "Mark H." <············@gmail.com> wrote:
> Question: Is there a more efficient way of communicating "this thread
> has finished its computations" than using a lock? Say that thread A
> calls SPAWN (and later FORCE) and thread B computes the promise's
> function. Is there a more efficient way for B to "signal" A than to
> use a lock? Should I trust that PROCESS-WAIT is implemented
> efficiently, or should I implement my own back-off policy to make sure
> that A doesn't spin on the lock too much?
>
> This is certainly somewhat system- and OS-dependent but I was
> wondering if there was a general idea on this --
It sounds like you want a condition variable (POSIX name, nothing to
do with CL conditions). Getting a value would look like:
Return value if it's available (no need to get a lock if nobody
writes anymore)
Get mutex
a. If a value is available, release mutex & return value (the value
could have become available between the first check and the actual
acquisition of the mutex).
b. wait on the condition variable. Loop back to (a)
Writing a value would just have to make sure to mark the value as
available (and broadcast on the condition variable) *after* writing
it.
SBCL exposes condition variables. I don't know for other
implementations, but they are part of bordeaux-threads's API, and bx-
threads supports ACL, ABCL, ECL, LW, OpenMCL and SBCL. Unfortunately,
there is no support for waking up *all* waiting threads, so you'd have
to iteratively wake other threads up in the value reading code...
which might be better for performance.
Paul Khuong
On Jul 9, 10:28 pm, Paul Khuong <·······@gmail.com> wrote:
> SBCL exposes condition variables. I don't know for other
> implementations, but they are part of bordeaux-threads's API, and bx-
> threads supports ACL, ABCL, ECL, LW, OpenMCL and SBCL. Unfortunately,
> there is no support for waking up *all* waiting threads, so you'd have
> to iteratively wake other threads up in the value reading code...
> which might be better for performance.
I'm a bit confused -- why would I want to wake up _all_ the waiting
threads? The "promise" construct only relates two threads to one
another; the other threads (in the POSIX model) will continue on their
own merry ways (preemptive multitasking on an SMP).
> It sounds like you want a condition variable (POSIX name, nothing to
> do with CL conditions). Getting a value would look like:
>
> Return value if it's available (no need to get a lock if nobody
> writes anymore)
> Get mutex
> a. If a value is available, release mutex & return value (the value
> could have become available between the first check and the actual
> acquisition of the mutex).
> b. wait on the condition variable. Loop back to (a)
May I ask how this is different than the original proposal? There's
still waiting ("Loop back to (a)") going on, no? I'm probably just
confused about the terminology since I come from a distributed-memory
parallelism background.
mfh
On Jul 10, 1:56 am, "Mark H." <············@gmail.com> wrote:
> On Jul 9, 10:28 pm, Paul Khuong <·······@gmail.com> wrote:
>
> > SBCL exposes condition variables. I don't know for other
> > implementations, but they are part of bordeaux-threads's API, and bx-
> > threads supports ACL, ABCL, ECL, LW, OpenMCL and SBCL. Unfortunately,
> > there is no support for waking up *all* waiting threads, so you'd have
> > to iteratively wake other threads up in the value reading code...
> > which might be better for performance.
>
> I'm a bit confused -- why would I want to wake up _all_ the waiting
> threads? The "promise" construct only relates two threads to one
> another; the other threads (in the POSIX model) will continue on their
> own merry ways (preemptive multitasking on an SMP).
I'm assuming you want a call-by-need like memoising architecture, to
avoid evaluating a given thunk twice (which would probably gives more
FLOPs, but certainly less performance ;). In that case, if thread A
forces the promise, and then thread B does so too (while the promise
is still under evaluation), then two threads, A and B, will be waiting
for the promise's result. Broadcasting or signalling a condition wakes
all all/some threads that are waiting *on the condition*.
If you don't want memoisation, and will just spawn threads dyamically
instead of using a thread pool, then pthread_join is a bit less work.
> > It sounds like you want a condition variable (POSIX name, nothing to
> > do with CL conditions). Getting a value would look like:
>
> > Return value if it's available (no need to get a lock if nobody
> > writes anymore)
> > Get mutex
> > a. If a value is available, release mutex & return value (the value
> > could have become available between the first check and the actual
> > acquisition of the mutex).
> > b. wait on the condition variable. Loop back to (a)
>
> May I ask how this is different than the original proposal? There's
> still waiting ("Loop back to (a)") going on, no? I'm probably just
> confused about the terminology since I come from a distributed-memory
> parallelism background.
Waiting on a condition variable doesn't poll and is (ideally) taken
into account by the scheduler. The thread actually sleeps until the
condition is signalled (although SBCL's manual says there might be
spurious activations, hence the loop back).
Paul Khuong
On Jul 10, 6:47 am, Paul Khuong <·······@gmail.com> wrote:
> On Jul 10, 1:56 am, "Mark H." <············@gmail.com> wrote:
> > I'm a bit confused -- why would I want to wake up _all_ the waiting
> > threads? The "promise" construct only relates two threads to one
> > another; the other threads (in the POSIX model) will continue on their
> > own merry ways (preemptive multitasking on an SMP).
>
> I'm assuming you want a call-by-need like memoising architecture, to
> avoid evaluating a given thunk twice (which would probably gives more
> FLOPs, but certainly less performance ;). In that case, if thread A
> forces the promise, and then thread B does so too (while the promise
> is still under evaluation), then two threads, A and B, will be waiting
> for the promise's result. Broadcasting or signalling a condition wakes
> all all/some threads that are waiting *on the condition*.
Oh, hm, that's interesting, I wasn't thinking about memoization. Do
you think that would be useful in a game tree search context? I
hadn't thought of a promise as being owned by more than one thread but
that could certainly be a useful thing.
I read up on conditions at some inhumanly early hour this morning and
realized that they fit the application much, much better ;-) (It's
counterintuitive, though, that the POSIX condition construct requires
a mutex _and_ a "condition variable.")
> If you don't want memoisation, and will just spawn threads dyamically
> instead of using a thread pool, then pthread_join is a bit less work.
I think I just need to explore both implementations and see which one
performs better for a given application...
> > May I ask how this is different than the original proposal? There's
> > still waiting ("Loop back to (a)") going on, no? I'm probably just
> > confused about the terminology since I come from a distributed-memory
> > parallelism background.
>
> Waiting on a condition variable doesn't poll and is (ideally) taken
> into account by the scheduler. The thread actually sleeps until the
> condition is signalled (although SBCL's manual says there might be
> spurious activations, hence the loop back).
Ok, cool, actually the POSIX example in C that I saw also uses the
loop back "just in case."
Thanks so much!
mfh
(message (Hello 'Mark)
(you :wrote :on '(Mon, 09 Jul 2007 20:31:22 -0700))
(
MH> Question: Is there a more efficient way of communicating "this thread
MH> has finished its computations" than using a lock?
possibly something like pthread_join()
The pthread_join() subroutine blocks the calling thread until the specified
threadid thread terminates.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"scorn")