Common Lisp Parallel Programming

Question

I want to implement my particle filtering algorithm in parallel in Common Lisp. Particle Filtering and sampling can be parallelized and I want to do this for my 4-core machine. My question is whether programming in parallel is feasible in CL or not and if it is feasible are there any good readings, tutorials about getting started to parallel computing in CL.

Answer 1

Definitely feasible!

The Bordeaux Threads project provides thread primitives for a number of implementations; I would suggest using it instead of SBCL's implementation-specific primitives (especially if you aren't on SBCL!).

The thread primitives are provided by bt are, however, quite primitive. I've used and enjoyed Eager Future2 which builds on bt to provide concurrency features using futures. You can create futures that are computed lazily, eagerly (immediately), or speculatively. The speculative futures are computed by a thread pool whose size can be customized.

I started a little project to provide parallel versions of CL functions using EF2, but it's only about three functions so far, so it won't be of much use to anyone. I do of course welcome other coders to hack on it and submit pull requests, and I hope to do more work on it in the future.

There are many other libraries listed on Cliki that I haven't tried myself.

As far as tutorials, I don't know of any, but the concurrency features provided are found in other languages as well and good algorithms and practices are not generally language-specific.

If you're interested in reading a book, I recommend The Concurrent C Programming Language. The authors describe a new programming language, based on C, with concurrency as a language feature. Of course, due to the nature of CL, it would likely be possible to implement these features without resorting to creating a new compiler. In my opinion the book presents excellent concurrency concepts, and addresses many of the problems you may encounter or fail to consider in writing concurrent programs.

Answer 2

SBCL has some multithreading support. It is too low level and, to my knowledge, does not include any parallel algorithms. It has just the posibility of creating threads that execute some lambda function and test afterwards if the thread has finished (joining it). I used that support to generate my blog pages with great speedup (each page or set of pages in a different thread). You can see the code here:

https://github.com/dsevilla/functional-mind-blog/blob/master/blog/process.lisp

For eample, generating a thread for each page was something like:

#+sbcl (defun generate-post-pages ()   (map nil        #'(lambda (post)            (make-thread (lambda () (page-generation-function post))))        *posts*)) 

You can also join-thread, and have mutexes, etc. You can read the documentation here: SBCL Threading. It is too low-level, though. You'll end missing the fantastic features of Clojure for concurrency...

Answer 3

Check out bordeaux threads if you're looking for a single POSIX-threads-style interface to multi-threading primitives for different Lisps.

If I were looking for a reliable free Lisp implementation, I'd start with CCL and then try SBCL. I use CCL for almost all of my testing and SBCL and LispWorks for the remainder.

Sedach's futures library should provide a higher level interface. There are also some other contributions from various users in SBCL's contrib directory.

This coming from someone who has used neither bordeaux-threads nor Sedach's futures library and has written his own version of both of those. I could send you my implementation, but these two packages are also supposed to be good, and they're probably a better starting point.