PCall, or parallel call, is a Common Lisp library intended to + simplify some kinds of parallelisation. It uses a thread pool to + schedule small computations without allocating a thread for them. + This makes it possible to make use of multiple cores without too + much fuss.
+ +18-05-2008: Version + 0.1: The first release. Should be considered beta. Any testing + and feedback is appreciated.
+ +PCall is released under a BSD-like license, which + approximately means you can use the code in whatever way you like, + except for passing it off as your own or releasing a modified + version without indication that it is not the original. See the + LICENSE file in the distribution.
+ +PCall depends on bordeaux-threads, + and on fiveam + for the test suite.
+ +The latest release of PCall can be downloaded from http://marijn.haverbeke.nl/pcall/pcall.tgz, + or installed with asdf-install.
+ +A darcs repository with the + most recent changes can be checked out with:
+ +> darcs get http://marijn.haverbeke.nl/pcall/pcall+ +
Or you can look at the repository + through darcsweb.
+ +I hope to have a common-lisp.net mailing list for + the project soon. For now, feel free to drop me an e-mail + directly: Marijn + Haverbeke.
+ +PCall is a rather simple library. There are three basic + concepts that you have to come to grips with:
+ +pcall and pexec. This creates a computation
+ that may be parallelised.join), which
+ extracts the value from a computation.Imagine that we have this wonderful algorithm for computing + (why not) Fibonnaci numbers:
+ ++(defun fib (n) + (if (> n 2) + (+ (fib (- n 1)) (fib (- n 2))) + 1)) + +(time (fib 40))+ +
Depending on your machine, this might take some 2 to 10 + seconds. We don't have that kind of patience, and you can see that + this algorithm is entirely optimal. Our only option, it seems, is + to use more hardware -- or make better use of the hardware we + have:
+ ++(time (let ((f39 (pexec (fib 39))) + (f38 (pexec (fib 38)))) + (+ (join f39) (join f38))))+ +
On my 2-core machine, that speeds things up by about a third -- + which makes sense, since computing fib(39) is about twice as much + work as computing fib(38). A nicer way to write the same would + be:
+ ++(time (plet ((f39 (fib 39)) + (f38 (fib 38))) + (+ f39 f38)))+ +
plet takes care of the
+ wrapping and joining in cases like this. Why do we need the let
+ anyway? You could try this:
+(time (+ (join (pexec (fib 39))) (join (pexec (fib 38)))))+ +
... but that won't buy you anything. The tasks have to both be + created before you join the first one, or the second task will not + exist when the first one runs, and thus won't be able to run + concurrently.
+ +You might be tempted to write something like this:
+ ++(defun pfib (n) + (if (> n 2) + (plet ((a (pfib (- n 1))) + (b (pfib (- n 2)))) + (+ a b)) + 1))+ +
... but don't. There is some overhead associated with creating
+ and executing tasks, and for a function like naive-fibonacci,
+ which recurses a zillion times even for small inputs, this will
+ radically slow your algorithm down. A parallel mapping function,
+ as shown below, works great for mapping a relatively heavy
+ function over a list of limited length, but is no use for mapping
+ 1+ over a million elements.
+(defun pmapcar (f list) + (let ((result (mapcar (lambda (n) (pexec (funcall f n))) list))) + (map-into result #'join result))) + +(defvar *numbers* (loop :for i :from 0 :below 30 :collect i)) +(time (mapcar #'fib i)) +(time (pmapcar #'fib i))+ +
Note that joining tasks is not required. When you do not care + about the result of a computation, you can just spawn the task and + leave it at that.
+ +
+ function
+ pcall (thunk)
+
→ task
+
Create a task that will call the given + argumentless function.
+ +
+ macro
+ pexec (&body body)
+
→ task
+
A shorthand for (pcall
+ (lambda () ...)).
+ macro + plet ((bindings) &body body) +
+ +Follows the behaviour of let, but
+ wraps every bound value into a pexec form, and automatically adds
+ join calls around uses of the
+ bound variables.
+ function
+ join (task)
+
→ result
+
Waits for the given task to finish, and then
+ returns any values the task produced. When executing the task
+ raised an uncaught error, this error will be raised when joining
+ the task. When, at the moment join is called, the
+ task has not been assigned to any thread, the joining thread will
+ execute the task itself. (Note that this makes the dynamic
+ environment in which the task runs unpredictable.) A task may be
+ joined multiple times. Subsequent joins will again return the
+ values, without re-executing the task.
+ function
+ done-p (task)
+
→ boolean
+
Tests whether a task has been executed.
+ ++ function + thread-pool-size () +
+ +Returns the current size of the thread pool. Also
+ supports setf to change this size. The default value
+ is 3.
+ function + finish-tasks () +
+ +Takes the current threads out of the pool, waits + for the task queue to empty, and then for the threads to finish + executing any tasks they might be busy with. This is intended to + be called when shutting down -- killing the threads might cause + some tasks to be aborted, which could result in data loss. If you + join every task you create, this should not be necessary. Note + that if you call this function while other threads are still + creating tasks, it might never return.
+ + + + addfile ./doc/style.css hunk ./doc/style.css 1 +body { + margin: 0; + font-family: tahoma, arial, sans-serif; + margin: 60px 120px; + color: black; + max-width: 50em; +} + +h1 { + font-size: 250%; + border-bottom: 3px solid #C42; +} + +h2 { + font-size: 140%; + border-bottom: 1px solid #C42; +} + +h3 { + font-size: 110%; +} + +code { + font-size: 1.2em; +} + +p.news { + text-indent: -3em; + padding-left: 3em; +} + +pre.code { + margin: 0 16px; + padding: 7px; + border: 1px solid #DA8; +} + +p.def { + margin-top: 1.5em; + font-family: courier; +} + +p.def span { + color: #555555; + font-weight: bold; + font-family: tahoma, arial, sans-serif; + font-size: .8em; +} + +.desc { + margin-left: 1em; +} + +thead { + font-weight: bold; +} + +table { + border-collapse: collapse; +} + +tr + tr { + border-top: 1px solid #88BB99; +} + +thead tr { + border-bottom: 2px solid #88BB99; +} + +td + td, th + th { + border-left: 2px solid #88BB99; +} + +th { + text-align: left; + padding: 2px 5px; +} + +td { + padding: 2px 5px; + vertical-align: top; +} + +a:link { + color: #3333AA; + text-decoration: none; +} + +a:visited { + color: #773377; + text-decoration: none; +} + +a:hover { + text-decoration: underline; +} + +ul.symbol-index { + font-family: monospace; + font-size: 1.2em; +} }