Parallel For

(parallel-for pool start end function &key chunk-size)

parallel-for splits the integers from start below end into chunks, calls function with each chunk's bounds on the pool's workers, as (function chunk-start chunk-end), and returns when every chunk is done.

(defun scale (vector factor pool)
  "Multiply every element of VECTOR by FACTOR, in parallel."
  (th:parallel-for pool 0 (length vector)
                   (lambda (start end)
                     (loop for i from start below end
                           do (setf (aref vector i) (* factor (aref vector i)))))))

The function receives a range, not one index, so the per-element work is a plain loop with no call overhead per element.

• An empty range, start not below end, calls nothing.
• start and end are fixnums.
• It returns no values. Write results into shared structures that chunks do not overlap in, or into worker storage.
• If a chunk signals an error, the other chunks still run, then parallel-for signals a job-error. See Errors in Jobs.

Chunk sizes

By default, the range is split into four chunks per worker:

;; 4 workers, 1000 integers: 16 chunks of 63 (the last one shorter)
(th:parallel-for pool 0 1000 #'work)

Four per worker balances the load when chunks take different times, while keeping the cost of queueing small. :chunk-size sets the number of integers per chunk instead:

(th:parallel-for pool 10 20 #'work :chunk-size 3)
;; chunks: (10 13) (13 16) (16 19) (19 20)

Choose a smaller chunk size when items differ a lot in cost, such as entities with very different update work, and a larger one when each item is tiny, so each chunk does enough work to cover its overhead. :chunk-size 1 gives one chunk per integer, for ranges that index a few large jobs.

Sharing data between chunks

Chunks run at the same time on different threads. They may freely:

• read data that nothing writes during the parallel-for;
• write to parts of a structure that no other chunk touches, such as their own elements of an array.

For anything else, such as adding to a total, either give each worker its own accumulator with worker storage, which needs no lock, or guard the shared value with a lock, which serialises the workers on it. Per-worker accumulators are much faster when the update is frequent.

Running every frame without allocating

Once a pool has warmed up, parallel-for allocates nothing, so it can run in code that runs every frame. It recycles its internal job groups and queue entries.

Your function counts too. A lambda that closes over variables is a new closure each time it is evaluated, typically 32 bytes on SBCL. To allocate nothing per frame, make the function once:

;; Allocates a closure every call:
(defun update (pool entities dt)
  (th:parallel-for pool 0 (length entities)
                   (lambda (start end) (update-range entities dt start end))))

;; Allocates nothing: the function is made once, with an object that holds
;; what each frame gives it.
(defstruct (updater (:constructor make-updater-without-function ()))
  "What a frame's update works on, and the function that updates a chunk of it."
  (entities nil)
  (dt 0.0 :type single-float)
  (function nil :type (or null function)))

(defun make-updater ()
  "Return an UPDATER, whose function updates a chunk of its entities."
  (let ((updater (make-updater-without-function)))
    (setf (updater-function updater)
          (lambda (start end)
            (update-range (updater-entities updater) (updater-dt updater) start end)))
    updater))

(defun update (pool updater entities dt)
  "Update ENTITIES for DT seconds on POOL's workers, with UPDATER."
  (setf (updater-entities updater) entities
        (updater-dt updater) dt)
  (th:parallel-for pool 0 (length entities) (updater-function updater)))

Make the updater once, with whatever owns the entities, such as a scene, and pass it to every frame's update. The workers read its slots, which the frame sets before parallel-for hands out the chunks. Keep such data in an object rather than in global variables, which everything in the image shares: two updates running at once, such as two scenes', would overwrite each other's.

Calling it from anywhere

parallel-for may be called from any thread.

• From a thread that is not one of the pool's workers, such as the main thread, the caller blocks until the chunks are done.
• From one of the pool's workers, inside a job, the worker runs this call's queued chunks itself while it waits, and nothing else. So jobs can use parallel-for too, nested as deep as you like, even on a pool of one worker:

(th:with-job-pool (pool :workers 1)
  (let ((total 0) (lock (th:make-lock "total")))
    (th:parallel-for pool 0 4
                     (lambda (start end)
                       (declare (ignore start end))
                       (th:parallel-for pool 0 10
                                        (lambda (start end)
                                          (th:with-lock (lock) (incf total (- end start))))
                                        :chunk-size 1))
                     :chunk-size 1)
    total))
;; => 40

A worker of a different pool blocks, as any other thread does.

Why only this call's chunks: the worker runs them on top of the waiting job, on the same stack, and the waiting job cannot continue until they return. Its own chunks never wait for it, so that is safe. An unrelated job might wait for the job beneath it, which could then never return. See Job Groups.