kmarekspartz

I demonstrate parallelizing existing code in Haskell

---

I've been working through Parallel and Concurrent Programming in Haskell. In my last post, I demonstrated the facilities Haskell provides for lightweight concurrency. In this post, let's take a look at Haskell facilities for parallelism.

As a brief example, let's parallelize Quicksort[^1].

import Control.Parallel.Strategies

Strategies provide a means to tell the run-time system how to evaluate objects. We'll be using rseq is the sequential evaluation strategy, and parList takes a strategy for list items, and uses that strategy for each list element in parallel.

Here's our non-parallelized Quicksort implementation:

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
  let leftPartition = [y | y <- xs, y < x]
      rightPartition = [y | y <- xs, y >= x]
      left = quicksort leftPartition
      right = quicksort rightPartition
  in left ++ [x] ++ right

Quicksort partitions a list around a pivot, sorts each partition, and then combines the partitions and the pivot.

Our parallelized version is almost the same:

parallelsort :: Ord a => [a] -> [a]
parallelsort [] = []
parallelsort (x:xs) =
    let leftPartition = [y | y <- xs, y < x] `using` parList rseq
        rightPartition = [y | y <- xs, y >= x] `using` parList rseq
        left = parallelsort leftPartition
        right = parallelsort rightPartition
    in left ++ [x] ++ right

We simply tell the run-time system what strategy to use for the list comprehensions.

This doesn't really improve much in this case, but when used judiciously, extending your existing code with parallelism is straight-forward in Haskell.

This post is also available as a literate Haskell file.

[^1]: This isn't the best algorithm to parallelize, nor is this an efficient implementation, but it shows how to add parallelism to your code.