Common Lisp Package: LPARALLEL

This is a convenience package which exports the external symbols of: lparallel.kernel lparallel.promise lparallel.defpun lparallel.cognate lparallel.ptree

README:

lparallel

lparallel is a library for parallel programming in Common Lisp, featuring

  • a simple model of task submission with receiving queue
  • constructs for expressing fine-grained parallelism
  • asynchronous condition handling across thread boundaries
  • parallel versions of map, reduce, sort, remove, and many others
  • promises, futures, and delayed evaluation constructs
  • computation trees for parallelizing interconnected tasks
  • bounded and unbounded FIFO queues
  • high and low priority tasks
  • task killing by category
  • integrated timeouts

See http://lparallel.org for documentation and examples.

Running

lparallel should run on any Common Lisp implementation supported by bordeaux-threads. The following implementations successfully pass the test suite:

  • ABCL
  • Allegro
  • Clozure
  • LispWorks
  • SBCL

To run tests, load lparallel-test.asd and call (lparallel-test:execute).

To run benchmarks, load lparallel-bench.asd and call (lparallel-bench:execute N) where N is the number of worker threads.

Author

James M. Lawrence <llmjjmll@gmail.com>

FUNCTION

Public

CALL-PTREE (ID PTREE)

Return the computation result of the node with identifier `id' in `ptree'. If the node is uncomputed, compute the result. If the node is already computed, return the computed result.

CANCEL-TIMEOUT (TIMEOUT TIMEOUT-RESULT)

Attempt to cancel a timeout. If successful, the channel passed to `submit-timeout' will receive `timeout-result'. At most one call to `cancel-timeout' will succeed; others will be ignored. If the timeout has expired on its own then `cancel-timeout' will have no effect. `cancel-timeout' is not available in ABCL.

CHAIN (OBJECT)

Create a chain. A chain links objects together by relaying `force' and `fulfilledp' calls.

CHECK-KERNEL

Ensures the value of `*kernel*' is a kernel instance. Provides the MAKE-KERNEL and STORE-VALUE restarts. Returns `*kernel*'.

CHECK-PTREE (PTREE)

Verify that all nodes have been defined with an associated function. If not, `ptree-undefined-function-error' is signaled.

CLEAR-PTREE (PTREE)

Clear all node results in `ptree', restoring the tree to its uncomputed state.

CLEAR-PTREE-ERRORS (PTREE)

Clear all error results in `ptree', allowing the computation to resume from its latest pre-error state.

END-KERNEL (&KEY WAIT)

Sets `*kernel*' to nil and ends all workers gracefully. `end-kernel' should not be used as a substitute for properly waiting on tasks with `receive-result' or otherwise. If `wait' is nil (the default) then `end-kernel' returns immediately. Workers are waited upon by a separate shutdown manager thread. If `wait' is non-nil then `end-kernel' blocks until all workers are finished. No shutdown manager thread is created. A list of the implementation-defined worker thread objects is returned. If `wait' is nil then the shutdown manager thread is also returned as the first element in the list. Note that creating and destroying kernels is relatively expensive. A kernel typically exists for lifetime of the Lisp process. Having more than one kernel is fine -- simply use `let' to bind a kernel instance to `*kernel*' when you need it. Use `kill-tasks' to terminate deadlocked or infinite looping tasks.

FORCE (OBJECT)

If `object' is a promise and the promise is fulfilled, return the fulfilled value (possibly multiple values). If the promise is unfulfilled then the call blocks until the promise is fulfilled. If `object' is a chain, call `force' on the chained object. If `object' is not a promise and not a chain, return the identical object passed. Note if `force' is called on an unfulfilled future then the future is fulfilled by the caller of `force'.

FULFILLEDP (OBJECT)

If `object' is a promise, return a boolean indicating whether the promise is fulfilled. If `object' is a chain, call `fulfilledp' on the chained object. If `object' is not a promise and not a chain, return true.

INVOKE-TRANSFER-ERROR (ERROR)

Equivalent to (invoke-restart 'transfer-error error). This is a convenience function for use in `task-handler-bind'.

KERNEL-BINDINGS

Return the bindings passed to `make-kernel'.

KERNEL-CONTEXT

Return the context passed to `make-kernel'.

KERNEL-NAME

Return the name passed to `make-kernel'.

KERNEL-WORKER-COUNT

Return the number of workers in the current kernel.

KILL-TASKS (TASK-CATEGORY &KEY DRY-RUN)

This is an expensive function which should only be used in exceptional circumstances. Every task has an associated task category. When a task is submitted, it is assigned the category of `*task-category*' which has a default value of `:default'. `kill-tasks' interrupts running tasks whose category is `eql' to `task-category'. The corresponding worker threads are killed and replaced. Pending tasks are not affected. If you don't know what to pass for `task-category' then you should probably pass `:default', though this may kill more tasks than you wish. Binding `*task-category*' around `submit-task' enables targeted task killing. If `dry-run' is nil, the function returns the number of tasks killed. If `dry-run' is non-nil then no tasks are killed. In this case the return value is the number of tasks that would have been killed if `dry-run' were nil. `kill-tasks' is not available in ABCL.

MAKE-CHANNEL (&REST ARGS)

Create a channel for submitting and receiving tasks. The current value of `*kernel*' is stored for use in `submit-task'. By default there is no limit on the channel capacity. Passing a `fixed-capacity' keyword argument limits the capacity to the value passed. Note that a fixed capacity channel may cause a deadlocked kernel if `receive-result' is not called a sufficient number of times.

MAKE-KERNEL (WORKER-COUNT &KEY (NAME lparallel) (BINDINGS `((*STANDARD-OUTPUT* ,@*STANDARD-OUTPUT*) (*ERROR-OUTPUT* ,@*ERROR-OUTPUT*))) (CONTEXT #'FUNCALL) (SPIN-COUNT *KERNEL-SPIN-COUNT*))

Create a kernel with `worker-count' number of worker threads. `name' is a string identifier for this kernel which is reported by `print-object'. Worker threads will also be given this name, shown in `bordeaux-threads:all-threads'. `bindings' is an alist for establishing thread-local variables inside worker threads. By default workers will have *standard-output* and *error-output* bindings. Dynamic context for each worker may be established with the function `context'. The argument passed to `context' is a function which must be funcalled. It begins the worker loop and will not return until the worker exits. The default value of `context' is #'funcall. The special variables in `bindings' are available inside the `context' function. When a worker discovers that no tasks are available, `spin-count' is the number of task-searching iterations done by the worker before sleeping. A kernel will not be garbage collected until `end-kernel' is called.

MAKE-PTREE

Create a ptree instance.

PCOUNT (ITEM SEQUENCE &KEY FROM-END (START 0) END KEY TEST TEST-NOT PARTS)

Parallel version of `count'. The `parts' option divides `sequence' into `parts' number of parts. Default is (kernel-worker-count).

PCOUNT-IF (PREDICATE SEQUENCE &KEY FROM-END (START 0) END KEY PARTS)

Parallel version of `count-if'. The `parts' option divides `sequence' into `parts' number of parts. Default is (kernel-worker-count).

PCOUNT-IF-NOT (PREDICATE SEQUENCE &REST ARGS &KEY FROM-END START END KEY PARTS)

Parallel version of `count-if-not'. The `parts' option divides `sequence' into `parts' number of parts. Default is (kernel-worker-count).

PEVERY (PREDICATE &REST SEQUENCES)

Parallel version of `every'. Calls to `predicate' are done in parallel, though not necessarily at the same time. Behavior is otherwise indistinguishable from `every'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PFIND (ITEM SEQUENCE &REST ARGS &KEY FROM-END TEST TEST-NOT START END KEY PARTS)

Parallel version of `pfind'. The `parts' option divides `sequence' into `parts' number of parts. Default is (kernel-worker-count).

PFIND-IF (PREDICATE SEQUENCE &REST ARGS &KEY FROM-END START END KEY PARTS)

Parallel version of `pfind-if'. The `parts' option divides `sequence' into `parts' number of parts. Default is (kernel-worker-count).

PFIND-IF-NOT (PREDICATE SEQUENCE &REST ARGS &KEY FROM-END START END KEY PARTS)

Parallel version of `pfind-if-not'. The `parts' option divides `sequence' into `parts' number of parts. Default is (kernel-worker-count).

PMAP (RESULT-TYPE FUNCTION &REST SEQUENCES)

Parallel version of `map'. Keyword arguments `parts' and `size' are also accepted. The `parts' option divides each sequence into `parts' number of parts. Default is (kernel-worker-count). The `size' option limits the number of elements mapped to `size'. When given, no `length' calls are made on the sequence(s) passed. Warning: `size' must be less than or equal to the length of the smallest sequence passed. It is unspecified what happens when that condition is not met.

PMAP-INTO (RESULT-SEQUENCE FUNCTION &REST SEQUENCES)

Parallel version of `map-into'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PMAP-REDUCE (MAP-FUNCTION REDUCE-FUNCTION SEQUENCE &REST ARGS &KEY START END INITIAL-VALUE PARTS RECURSE)

Equivalent to (preduce reduce-function sequence :key map-function ...).

PMAPC (FUNCTION &REST LISTS)

Parallel version of `mapc'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PMAPCAN (FUNCTION &REST LISTS)

Parallel version of `mapcan'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PMAPCAR (FUNCTION &REST SEQUENCES)

Parallel version of `mapcar'. Keyword arguments `parts' and `size' are also accepted (see `pmap'). Unlike `mapcar', `pmapcar' also accepts vectors.

PMAPCON (FUNCTION &REST LISTS)

Parallel version of `mapcon'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PMAPL (FUNCTION &REST LISTS)

Parallel version of `mapl'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PMAPLIST (FUNCTION &REST LISTS)

Parallel version of `maplist'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PMAPLIST-INTO (RESULT-LIST FUNCTION &REST LISTS)

Like `pmaplist' but results are stored in `result-list'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PNOTANY (PREDICATE &REST SEQUENCES)

Parallel version of `notany'. Calls to `predicate' are done in parallel, though not necessarily at the same time. Behavior is otherwise indistinguishable from `notany'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PNOTEVERY (PREDICATE &REST SEQUENCES)

Parallel version of `notevery'. Calls to `predicate' are done in parallel, though not necessarily at the same time. Behavior is otherwise indistinguishable from `notevery'. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PREDUCE (FUNCTION SEQUENCE &REST ARGS &KEY KEY FROM-END (START 0) END INITIAL-VALUE PARTS RECURSE)

Parallel version of `reduce'. `preduce' subdivides the input sequence into `parts' number of parts and, in parallel, calls `reduce' on each part. The partial results are then reduced again, either by `reduce' (the default) or, if `recurse' is non-nil, by `preduce'. `parts' defaults to (kernel-worker-count). `key' is thrown out while reducing the partial results. It applies to the first pass only. `start' and `end' have the same meaning as in `reduce'. `from-end' means "from the end of each part". `initial-value' means "initial value of each part".

PREDUCE-PARTIAL (FUNCTION SEQUENCE &REST ARGS &KEY KEY FROM-END (START 0) END INITIAL-VALUE PARTS)

Like `preduce' but only does a single reducing pass. The length of `sequence' must not be zero. Returns the partial results as a vector.

PREMOVE (ITEM SEQUENCE &REST ARGS &KEY TEST TEST-NOT FROM-END (START 0) END KEY PARTS)

Parallel version of `remove'. Note the `count' option is not supported. The `parts' option divides `sequence' into `parts' number of parts. Default is (kernel-worker-count).

PREMOVE-IF (TEST SEQUENCE &REST ARGS &KEY FROM-END (START 0) END KEY PARTS)

Parallel version of `remove-if'. Note the `count' option is not supported. The `parts' option divides `sequence' into `parts' number of parts. Default is (kernel-worker-count).

PREMOVE-IF-NOT (TEST SEQUENCE &REST ARGS &KEY FROM-END (START 0) END KEY PARTS)

Parallel version of `remove-if-not'. Note the `count' option is not supported. The `parts' option divides `sequence' into `parts' number of parts. Default is (kernel-worker-count).

PROMISE

Create a promise. A promise is a receptacle for a result which is unknown at the time it is created.

PSOME (PREDICATE &REST SEQUENCES)

Parallel version of `some'. Calls to `predicate' are done in parallel, though not necessarily at the same time. Behavior is otherwise indistinguishable from `some' except that any non-nil predicate comparison result may be returned. Keyword arguments `parts' and `size' are also accepted (see `pmap').

PSORT (SEQUENCE PREDICATE &KEY KEY GRANULARITY &ALLOW-OTHER-KEYS)

Parallel version of `sort'. If `granularity' is provided then parallel tasks are created only for segments larger than `granularity'. This may or may not result in better performance. At present `psort' is only parallelized for vectors; other types are given to `cl:sort'.

PSORT* (SEQUENCE PREDICATE &KEY KEY GRANULARITY &ALLOW-OTHER-KEYS)

Like `psort' but optimized for N-1 worker threads where N is the number of cores. The caller of `psort*' always participates in the computation. In contrast, the caller of `psort' participates only when the caller is in a worker thread.

PTREE-COMPUTED-P (ID PTREE)

Return true if the node with identifier `id' in `ptree' has finished computing, otherwise return false.

PTREE-FN (ID ARGS FUNCTION PTREE)

Define a ptree node with identifier `id', which is some unique object suitable for `eql' comparison such as symbol. The ids of its child nodes are elements of the list `args'. `function' is the function associated with this node. The arguments passed to `function' are the respective results of the child node computations. `ptree' is the ptree instance in which the node is being defined.

RECEIVE-RESULT (CHANNEL)

Remove a result from `channel'. If nothing is available the call will block until a result is received.

SUBMIT-TASK (CHANNEL FUNCTION &REST ARGS)

Submit a task through `channel' to the kernel stored in `channel'.

SUBMIT-TIMEOUT (CHANNEL TIMEOUT-SECONDS TIMEOUT-RESULT)

Effectively equivalent to (submit-task channel (lambda () (sleep timeout-seconds) timeout-result)) The difference is that `submit-timeout' does not occupy a worker thread. A timeout object is returned, which may be passed to `cancel-timeout'.

TASK-CATEGORIES-RUNNING

Return a vector containing the task category currently running for each worker.

TRY-RECEIVE-RESULT (CHANNEL)

Non-blocking version of `receive-result'. If a result is available then it is returned as the primary value in (values result t). Otherwise (values nil nil) is returned.

MACRO

Public

DECLAIM-DEFPUN (&REST NAMES)

See `defpun'.

DEFPUN (NAME PARAMS &BODY BODY)

`defpun' defines a function which is specially geared for fine-grained parallelism. If you have many small tasks which bog down the system, `defpun' may help. The syntax of `defpun' matches that of `defun'. The difference is that `plet' and `plet-if' take on new meaning inside `defpun'. The symbols in the binding positions of `plet' and `plet-if' should be viewed as lazily evaluated immutable references. Inside a `defpun' form the name of the function being defined is a macrolet, as are the names of other functions which were defined by `defpun'. Thus using #' on them is an error. Calls to functions defined by `defpun' entail more overhead when the caller lies outside a `defpun' form. A `defpun' function must exist before it is referenced inside another `defpun' function. If this is not possible--for example if func1 and func2 reference each other--then use `declaim-defpun' to specify intent: (declaim-defpun func1 func2)

DEFPUN* (NAME PARAMS &BODY BODY)

Like `defpun' except that it defines a function which is optimized for N-1 worker threads where N is the number of cores. A function defined with `defpun*' differs from its unstarred counterpart in two ways: it has less overhead, and the thread which calls it always participates in the computation. In contrast, the caller of a function defined by `defpun' participates in the computation only when the caller is in a worker thread.

DEFPUN/TYPE (NAME PARAMS ARG-TYPES RETURN-TYPE &BODY BODY)

Typed version of `defpun'. `arg-types' is an unevaluated list of argument types. `return-type' is an unevaluated form of the return type, possibly indicating multiple values as in (values fixnum float). (As a technical point, if `return-type' contains no lambda list keywords then the return type given to ftype will be additionally constrained to match the number of return values specified.)

DEFPUN/TYPE* (NAME PARAMS ARG-TYPES RETURN-TYPE &BODY BODY)

Typed version of `defpun*'. Also see `defpun/type'.

DELAY (&BODY BODY)

Create a delay. A delay is a promise which is fulfilled when `force' is called upon it.

DO-FAST-RECEIVES ((RESULT CHANNEL COUNT) &BODY BODY)

Receive `count' number of results from `channel', executing `body' each time with the result bound to `result'. `body' should be a trivial operation such as an aref call.

FULFILL (OBJECT &BODY BODY)

Attempt to give `object' a value. If `object' is a promise which is not fulfilled and not currently being fulfilled, then the implicit progn `body' will be executed and the promise will store the result. In this case `fulfill' returns true. If `object' is a promise that is either already fulfilled or actively being fulfilled, then `body' will not be executed and `fulfill' returns false. If `object' is a chain, call `fullfill' on the chained object. If `object' is not a promise and not a chain then false is returned immediately, with `body' being ignored.

FUTURE (&BODY BODY)

Create a future. A future is a promise which is fulfilled in parallel by the implicit progn `body'.

PAND (&REST FORMS)

Parallel version of `and'. Forms in `forms' may be executed in parallel, though not necessarily at the same time. If all forms evaluate to true, then the result of any form may be returned.

PDOTIMES ((VAR COUNT &OPTIONAL RESULT PARTS) &BODY BODY)

Parallel version of `dotimes'. The `parts' option divides the integer range into `parts' number of parts. Default is (kernel-worker-count). Unlike `dotimes', `pdotimes' does not define an implicit block named nil.

PFUNCALL (FUNCTION &REST ARGS)

Parallel version of `funcall'. Arguments in `args' may be executed in parallel, though not necessarily at the same time.

PLET (BINDINGS &BODY BODY)

The syntax of `plet' matches that of `let'. plet ({var-no-init | (var [init-form])}*) form* For each (var init-form) pair, a future is created which executes `init-form'. Inside `body', `var' is a symbol macro which expands to a `force' form for the corresponding future. Each `var-no-init' is bound to nil and each `var' without `init-form' is bound to nil (no future is created). `plet' is subject to optimization inside `defpun'.

PLET-IF (PREDICATE BINDINGS &BODY BODY)

The syntax of `plet-if' matches that of `let' except for the addition of the `predicate' form. If `predicate' evaluates to true, the behavior is the same as `plet'. If `predicate' evaluates to false, the behavior is the same as `let'. `plet-if' is subject to optimization inside `defpun'.

POR (&REST FORMS)

Parallel version of `or'. Forms in `forms' may be executed in parallel, though not necessarily at the same time. Any form which evaluates to non-nil may be returned.

PTREE (DEFS &BODY BODY)

Create a ptree using `flet' syntax. ptree ((node-name child-names function-body)*) form* Each `node-name' form corresponds to the definition of a ptree node. `node-name' is the name of the node being defined (a symbol). `child-names' is a list of the names of child nodes (symbols). The function associated with the node being defined is `(lambda ,child-names ,@function-body) `child-names' cannot contain lambda list keywords. For each `node-name', a symbol macro is defined which expands to a `call-ptree' form for that node.

SPECULATE (&BODY BODY)

Create a speculation. A speculation is a low-priority future.

TASK-HANDLER-BIND (CLAUSES &BODY BODY)

Like `handler-bind' but handles conditions signaled inside tasks that were created in `body'.

VARIABLE

Public

*DEBUG-TASKS-P*

If true (the default), the debugger is invoked when an error goes unhandled inside a task, i.e. when the handlers established by `task-handler-bind' (if any) do not handle it. If false, unhandled errors from tasks are automatically transferred to their parent thread (and/or any dependent threads) via the `transfer-error' restart. This is for convenience -- sometimes you wish to avoid N debugger popups arising from N errors in N worker threads. For local control over debugger invocation, bind a task handler: (task-handler-bind ((error #'invoke-debugger)) ...) (task-handler-bind ((error #'invoke-transfer-error)) ...)

*KERNEL*

The current kernel, or nil.

*KERNEL-SPIN-COUNT*

Default value of the `spin-count' argument to `make-kernel'.

*PTREE-NODE-KERNEL*

When non-nil, `*kernel*' is bound to this value during the call of a node function.

*TASK-CATEGORY*

See `kill-tasks'. Default value is `:default'.

*TASK-PRIORITY*

When bound to `:low', the kernel schedules submitted tasks at low priority. Default value is `:default'.

CLASS

Public

CHANNEL

A task is submitted to the kernel using a channel. A channel always points to the same kernel, which is the value of `*kernel*' when the channel is created.

KERNEL

The kernel encompasses the scheduling and execution of parallel tasks using a pool of worker threads. All parallelism in lparallel is done on top of the kernel.

PTREE (DEFS &BODY BODY)

A ptree is a computation represented by a tree together with functionality to execute the tree in parallel.

CONDITION

Public

KERNEL-CREATION-ERROR

Error signaled when `make-kernel' fails.

NO-KERNEL-ERROR

Error signaled when `*kernel*' is nil.

PTREE-LAMBDA-LIST-KEYWORD-ERROR

Lambda list keywords found in function definition.

PTREE-REDEFINITION-ERROR

Attempted to redefine a node's function.

PTREE-UNDEFINED-FUNCTION-ERROR

Attempted to execute a node which had no function.

TASK-KILLED-ERROR

Error signaled when attempting to obtain the result of a killed task.