Promises, futures -- implementation suggestions?

lisp

Promises, futures -- implementation suggestions?

Postby Mark H. » Wed, 11 Jul 2007 12:31:22 GMT

Greetings!

I was poking around with threads today and implemented a "promises"
mechanism.  (The discussion at

 http://www.**--****.com/ +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.


Re: Promises, futures -- implementation suggestions?

Postby Paul Khuong » Wed, 11 Jul 2007 14:28:03 GMT



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


Re: Promises, futures -- implementation suggestions?

Postby Mark H. » Wed, 11 Jul 2007 14:56:22 GMT



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).


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


Re: Promises, futures -- implementation suggestions?

Postby Alex Mizrahi » Wed, 11 Jul 2007 20:20:06 GMT

(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") 



Re: Promises, futures -- implementation suggestions?

Postby Paul Khuong » Wed, 11 Jul 2007 22:47:05 GMT





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.


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


Re: Promises, futures -- implementation suggestions?

Postby Mark H. » Thu, 12 Jul 2007 01:30:18 GMT





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.")


I think I just need to explore both implementations and see which one
performs better for a given application...


Ok, cool, actually the POSIX example in C that I saw also uses the
loop back "just in case."

Thanks so much!
mfh


Similar Threads:

1.little suggestion for xharbour future

2.On implementation limits and the future of CLC

Hello again.

I'm just dropping an idea here that will be incorporated into version 2.0
of my "topicality guidelines", along with the other stuff I've saved for
inclusion.

There's a widely known but often unspoken fact on this newsgroup that the
ISO Standard isn't exactly the pinnacle of assurance when it comes to
implementation limits. Many people are aware of the so-called One Program
Rule. There is also a non-normative footnote (#13) that says
"Implementations should avoid imposing fixed translation limits whenever
possible", but even if that were normative, it wouldn't really help at
all. None of this is really news to anyone who's been reading this
newsgroup long enough.

But I haven't seen the connection drawn between the above and the ideas of
the topicality/portability nuts on this newsgroup.

Assuming a hosted environment, then, what is wrong with the following
program, and why should it cease to be recommended on this newsgroup in
the interests of portability to systems outside of one's own system (which
may have a stack, a heap, a virtual memory subsystem, a threading library,
read()/write(), etc.)?

---------------------------------------------------------------------------
#include <stdio.h>

int main(void)
{
    printf("Hello, world!\n");
    return 0;
}
---------------------------------------------------------------------------


Yours,
Han from China

-- 
"Only entropy comes easy." -- Anton Chekhov

3.suggestion for scheme implementation

4.Implementation suggestions for creating a Hierarchical circuit database

5.Implementation suggestions for creating a Hierarchical circuit database

Hi,

I am writing a personal software that will read circuit design/
netlist. I will be using the MCNC benchmarks that contain different
types of designs in SPICE netlist format.

I need some pointers/papers/suggestions on creating a "hierarchical"
netlist database. The netlist database can, at times, be fully
flattened, partially flattened or fully hierarchical. I should be able
to answer queries like: are there any capacitors connected to node:
x1.x2.n1?

My program is currently only for analyzing designs for connectivity,
types of elements (resistors/capacitors) and figuring out some simple
electrical properties.

I am just starting, so please bear with me if I haven't thought about
corner cases.

Regards
Nick

6. Implementation of dictionary copying question/suggestion

7. Reference Implementation (Was: function implementation)

8. checking implementation defined and implementation dependent behaviour



Return to lisp

 

Who is online

Users browsing this forum: No registered users and 73 guest