[erlang-questions] Why using pmap is not giving me the desired speedup ?

[Angel Alvarez]

El Martes, 17 de Noviembre de 2009 07:45:46 Tushar Deshpande escribió:
> Hi,
> 
> I'm a newcomer to the Erlang world. I'm trying
> to learn parallel programming with Erlang.

Welcome!! im newbie too! 

> 
> I tried to use Joe Armstrong's 'pmap' implementation
> to write a parallel quicksort.
> 
> I imagined that I would get some observable
> speedup with parallel quicksort.

Well many people at blogs , on the lists and other groups talk about this. Where
Joe talk about concurrency they ear "paralelism", those are not the same concepts.

The more concurrency, you put in your programs the more overall paralelism youll get
in the long term. But you can make a highly parallel program with almost no concurrency.

I see this problem as the Haskell vs Erlang or Clojure vs Erlang wars and that why many other 
languages took some erlang features like procceses and distributions but left others maybe more 
interesting like a strong exception support.

I saw on the list that erlang people change from "functional" to "concurrency oriented"
when refering to erlang to help others change minds.

> 
> I executed parallel quicksort on my dual-core
> notebook. I varied the erlang schedulers from
> 1 to 32.

More schedulers than cores is a bad idea, they end contending for the CPU's
Probably is best One scheduler per core ( maybe some core can be devoted to 
the async pool)

> I ran quicksort on several lists with lengths
> 1, 10, 100, 1000, 10000 and 100000.

There is alway a balance beetween cost of computations
and the overhead of distributing them. Also Amdahl's law 
marks the upper bound for speedups.

Make several runs with 1 scheduler and promediate results
then go for more cored up to the maximum you have (2) and promediate 
results.

That have to measure speedups , OTHO your code seems wrong.

where is the conditions that change using pqsort to plain qsort? 
It seems you keep spawning procceses also when you have pretty 
tiny lists down to one element.

Somewhere on the run its better to call plain qsort that keep spawning
because the cost for the plain function will be always better than
than pmap way.

Despite of ligth proccesses on Erlang that always applies, also on small data 
other algos as bubllesort sort can be as good as qsort or better...


/Angel

> 
> Contrary to my expectations, parallel version
> took more time to run. [The pmap gave
> significant speedup for example on page
> 371 (ptests.erl) in the Joe Armstrong's book]
> 
> What could be the reason ?
> 
> Notice, that the pqsort is non-tail-recursive
> function. Does this have anything to do
> with my observations ?
> 
> Wouls someone please help me ?
> 
> Here's my quicksort implementation for
> easy reference.
> 
> -module(qsort).
> -compile(export_all).
> -import(lib_parallel, [ pmap/2]).
> 
> pqsort([]) ->
>   [];
> pqsort([Pivot|T]) ->
>   L1 = [X || X <- T, X < Pivot],
>   L2 = [X || X <- T, X >= Pivot],
>   [Left,Right] = pmap(fun pqsort/1, [L1,L2]),
>   Left ++ [Pivot] ++ Right.
> 
> qsort([]) ->
>   [];
> qsort([Pivot|T]) ->
>   L1 = [X || X <- T, X < Pivot],
>   L2 = [X || X <- T, X >= Pivot],
>   Left = qsort(L1),
>   Right = qsort(L2),
>   Left ++ [Pivot] ++ Right.
> 
> --
> Warm Regards,
> 
> Tushar Deshpande
> 
> ________________________________________________________________
> erlang-questions mailing list. See http://www.erlang.org/faq.html
> erlang-questions (at) erlang.org
> 
> 


--

__________________________________________

Clist UAH a.k.a Angel
__________________________________________
Los dinosaurios murieron porque no tenían un programa espacial. Larry Niven.