Wednesday, 7 May 2008

Parallel Quicksort in Erlang - Part II

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!

1 comment:

Jucimar said...

Which tool you create this graph? Percept?