Problem with parallel quicksort in erlang

Question

I am facing problem with writing quicksort in erlang. What I am doing is I am spawning two processes and then blocking the current process till I get the response from both the left and right sub-arrays. Getting both these responses I send a message to its parent giving it the computed list. Parent ! {self(), Lone ++ [H] ++ Ltwo}

But I am getting error of gettting undef in both the sub-processes. Here is the code.

 22 quick(Parent, []) -> Parent ! {self(), []};
 23 quick(Parent, [H | T]) ->
 24     Pone = spawn_link(main, quick, [ self(), [ X || X <- T, H >= X ] ]) ,
 25     Ptwo = spawn_link(main, quick, [ self(), [ Y || Y <- T, H < Y ] ]) ,
 26     receive
 27         {Pone, Lone} ->
 28             receive
 29                 {Ptwo, Ltwo} -> Parent ! {self(), Lone ++ [H] ++ Ltwo}
 30             end;
 31         {Ptwo, Ltwo} ->
 32             receive
 33                 {Pone, Lone} -> Parent ! {self(), Lone ++ [H] ++ Ltwo}
 34             end
 35     end.
 36 
 37 sortquick(List) ->
 38     quick(self(), List).

called as:

main:sortquick([12,4,7,22,25]).

Answer 1

The code itself is not the problem. The quick sort works fine. The reason, probably, why you are getting an undef in the subprocesses is due to the fact that the function quick/2 is not exported at all. When you call spawn_link with the module and function, the function needs to be exported.

You can fix this by either added

-export([quick/2]).

Or by changing the spawn_links to something like

spawn_link(fun() -> quick(Self, [Y || Y <- T, H < Y]) end

Though if you do it the latter way, you'll need to create a variable

Self = self()

Before you make the calls or else it wont return to the proper process.

Answer 2

The code above works fine by exporting quick/2 function.

Later on I compared the run time of the spawned quicksort vs the unspawned quicksort. The spawned quicksort is taking anywhere between 15sec to 32 sec to sort a list of 1 million random numbers in range (1,1000000).

The unspawned quicksort is(code below):

 55 quicksort([]) -> [];
 56 quicksort([H]) -> [H];
 57 quicksort([H | T]) ->
 58     [Headnew | Tailnew] = [H | T],
 59     quicksort([ X || X <- Tailnew, Headnew >= X ]) ++ [Headnew] ++ quicksort([ Y || Y <- Tailnew, Headnew < Y ]).

takes anywhere between 5sec and 8sec to sort same list of a million random numbers.

I am testing code on my old Thinkpad, 1.7 Ghz processor (single core) and 512 Mb RAM.

Any explanation for spawned quicksort to perform poorer than unspawned one ?