how to efficiently apply a medium-weight function

Question

I'm looking to map a modestly-expensive function onto a large lazy seq in parallel. pmap is great but i'm loosing to much to context switching. I think I need to increase the size of the chunk of work thats passed to each thread.

I wrote on a function to break the seq into chunks and pmap the function onto each chunk and recombine them. this 'works' but the results have not been spectacular. The origional code essentially looks like this:

(pmap eval-polynomial (range x) coificients)

How can I really squeez this while keeping it lazy?

Answer 1

I'd look at the ppmap function from: http://www.braveclojure.com/zombie-metaphysics/. It lets you pmap while specifying the chunk size.

The solution to this problem is to increase the grain size, or the amount of work done by each parallelized task. In this case, the task is to apply the mapping function to one element of the collection. Grain size isn’t measured in any standard unit, but you’d say that the grain size of pmap is one by default. Increasing the grain size to two would mean that you’re applying the mapping function to two elements instead of one, so the thread that the task is on is doing more work. [...] Just for fun, we can generalize this technique into a function called ppmap, for partitioned pmap. It can receive more than one collection, just like map:

(defn ppmap
  "Partitioned pmap, for grouping map ops together to make parallel
  overhead worthwhile"
  [grain-size f & colls]
  (apply concat
   (apply pmap
          (fn [& pgroups] (doall (apply map f pgroups)))
          (map (partial partition-all grain-size) colls))))
(time (dorun (ppmap 1000 clojure.string/lower-case orc-name-abbrevs)))
; => "Elapsed time: 44.902 msecs"

Answer 2

I would look at the Fork/Join library, set to be integrated into JDK 7. It's a lightweight threading model optimized for nonblocking, divide-and-conquer computations over a dataset, using a thread pool, a work-stealing scheduler and green threads.

Some work has been done to wrap the Fork/Join API in the par branch, but it hasn't been merged into main (yet).

Answer 3

If you don't mind something slightly exotic (in exchange for some really noticeable speedup), you might also want to look into the work done by the author of the Penumbra-library, which provides easy access to the GPU.

Answer 4

How about using the partition function to break up your range sequence? There was an interesting post on a similar problem at http://www.fatvat.co.uk/2009/05/jvisualvm-and-clojure.html