On Parallelism

Recently, I read an article describing someone’s experiments in parallel genetic programming, and so I decided to run my own. As has been mentioned, I am quite fond of functional languages; for me, easy parallelism is simply a pleasant bonus. I do think its worth noting, however, that while functional programming may be generally awesome, throwing in massive amounts of parallelism is often overkill (certainly when one runs his programs on a lowly Macbook).

Take Gajure, my unfeature-full framework for creating genetic algorithms. On a whim, I changed out most map functions with pmap, its parallel counterpart, and ran the example code included on github. This took literally two seconds — for instance, something like roulette-select was changed by two characters:

(defn roulette-select
  "Select num individuals from pop, with an individual's
   fitness porportional to selection likelihood."
  [pop fit-fn num]
  (let [pop-fits (pmap fit-fn pop)
        inc-fits (iterate (fn [[pfit idx]]
                          [(+ (nth pop-fits
                           (+ idx 1)) pfit) (+ idx 1)])
                          [(first pop-fits) 0])
        max-fitness (apply + pop-fits)
        pick-one (fn [num] (second (first (drop-while
                                         #(< (first %) num)
                                         inc-fits))))]
    (pmap (fn [x] (nth pop (pick-one (rand-int max-fitness))))
               (range num))))

On the face of things, a genetic algorithm would seem to be a perfect target for parallelism. Within a single generation, fitness computations and mutation operations can be run for each population member completely independent of its compatriots. Alas, such performance gains were not realized — not, at least, on my humble dual-core machine.

The bottom line: running time more than doubled for evolving “hello world.” What previously took 1450 ms takes 3162 ms with the new implementation. I will be gathering more representative statistics later on, but probably, the overhead involved in creating parallel mappings outweighs any benefits, given that I only have two processors (on that note, I’d be curious to know how much nicer things would run in Erlang, where the threads are more lightweight). Another contributing factor is simply the inane simplicity of the problem space; in an ideal case, each fitness evaluation would be doing a bit more work.

So in some sense, my dimwitted “hello world” example represents a worse case for the parallel implementation, particularly when run on my relatively underpowered machine. With that, I’m committing the pmap changes to github under a separate branch, here.