Problem with parallel quicksort in erlang?

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.

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.

– pranjal Sep 4 '10 at 19:38 3 Because if it is not exported, then it can only be called from functions that are native to your module. Think of it as a private function. Then when you call erlang:spawn_link/3 it is a different modules effectively trying to call main:quick/2.

But it can't because main:quick/2 is a private function and no other module knows about it. – Olives Sep 4 '10 at 19:45.

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 = X ) ++ Headnew ++ quicksort( Y || Y Any explanation for spawned quicksort to perform poorer than unspawned one?

1 Well, if you only have a single core then you don't have any ability to do work in parallel, so I wouldn't expect any benefit. On the other hand, while processes may be cheap in Erlang they aren't free and message sends and spawns require a complete copy of the list. Also think about what happens near the base case, you spawn lots of processes to send back the empty list.It might be interesting to write a version that spawns processes for the first couple of steps and then falls back to the unspawned version.

(If you have a multicore machine to try it on. ) – cthulahoops Sep 5 '10 at 9:01 On my dual core laptop it's still slightly slower even when I spawn two processes only. – cthulahoops Sep 5 '10 at 9:16 I tested on dual core, in fact I limited the spawning when array size reaches below 100.

(total list size being 1 million), I get around 2.4 sec with spawned version and around 3.2 sec with unspawned version. – pranjal Sep 5 '10 at 13:42 2 Don't forget that for each spawned process Erlang copies the list to that processes own heap. With a rough calculation log2Len * Len list elements are copied in total, which is quite a lot for a list of a million integers.

– Zed Sep 6 '10 at 6:53 lists:sort/1 for 1 million takes about 800ms. Lists:sort/1 is merge sort written in smart way. If you consider that this list can be sorted by algorithm with worst case O(N*log2N) (i.e.

Merge sort) than even one copying of all list members between processes can matter and it does. You have to have a lot of cores to make parallel version faster and tune it carefully. – Hynek -Pichi- Vychodil Sep 6 '10 at 12:20.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.