Parallel Quicksort in Erlang - Part II

21st Century Code WorksBest of Erlang - noreply@blogger.com (Benjamin Nortier) - May 07, 2008

In my previous post, Jaksa pointed out that there’s a problem, in that although there may be multiple processes, they will be blocked and waiting (sequencially) for the first peval to complete, then the second peval, etc. Which will result in a pseudo-parallel depth-first quicksort, instead of a breadth-first quicksort. This is the offending line:

peval(fun pqsort/1, Left) ++ [Pivot] ++ peval(fun pqsort/1, Right).

I was hoping Erlang would be clever enough to execute the two functions in parallel, but that’s a fairly unreasonable (and completely incorrect) assumption!

But how to fix it? There is a parallel implementation of the map function in Joe’s book, and Montsamu has a variation of it on his blog:

-module(plists).
-export([pmap/2]).

pmap(F, L) ->
    S = self(),
    Pids = lists:map(fun(I) -> spawn(fun() -> pmap_f(S, F, I) end) end, L),
    pmap_gather(Pids).

pmap_gather([H|T]) ->
    receive
        {H, Ret} -> [Ret|pmap_gather(T)]
    end;
pmap_gather([]) ->
    [].

pmap_f(Parent, F, I) ->
    Parent ! {self(), (catch F(I))}.

The pmap_gather function is the interesting one. It will traverse the list of Pids, and wait for each to send back its result. Using pmap, we update pqsort as follows:

pqsort([]) -> [];
pqsort([Pivot]) -> [Pivot];
pqsort([Pivot|Rest]) ->
    io:format("+", []),
    Left = [X || X <- Rest, X < Pivot],
    Right = [Y || Y <- Rest, Y > Pivot],
    [SortedLeft, SortedRight] = plists:pmap(fun pqsort/1, [Left, Right]),
    io:format("-", []),
    SortedLeft ++ [Pivot] ++ SortedRight.

And with a perfectly unbalanced (for quicksort) list to sort, we expect 1 process, then 3 as the first spawns 2 new ones, then down again to zero:

(emacs@21ccw.blogspot.com)47> pqsort:pqsort([4,2,1,3,6,5,7]).
+++---[1,2,3,4,5,6,7]

For the same example we had last time, sorting 100 random numbers, the number of concurrent process graph during execution looks like this:



Much better!

Categories: Blogs  21st Century Code Works  Best of Erlang  

Comments

No comments so far, you could be the first.

Add comment

Name:

Email:

URL:

Smileys

Remember my personal information

Notify me of follow-up comments?