Discussion :

[GnuVince]

Comme promis, je vais poster un programme concurrent en Erlang. Je vais également poster la version séquentielle à titre de comparaison.

Tout d'abord, la tâche: j'ai décidé d'utiliser un exercice du Projet Euler, le problème #14. Pour ceux qui ne lisent pas l'anglais, voici une traduction:

La séquence itérative suivante est définie pour l'ensemble des entiers positifs:

n -> n / 2 (si n est pair)
n -> 3n + 1 (si n est impair)

En utilisant cette règle, et en commençant avec 13, on génère la suite suivante:

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

On peut observer que cette suite (démarrant à 13 et terminant à 1) contient 10 items. Malgré que cela n'ait pas été encore prouvé (problème Collatz), on croit que tous les nombres de départs finissent à 1.

Quel nombre de départ, plus petit qu'un million, produit la plus longue suite?

Le problème est assez simple. Voici la solution séquentielle en Erlang:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
-module(prob14s).
-compile(export_all).

even(N) -> N rem 2 == 0.

do_chain(N) ->
    do_chain(N, []).

do_chain(1, Acc) -> length(Acc);
do_chain(N, Acc) ->
    case even(N) of
        true  -> do_chain(N div 2, [N | Acc]);
        false -> do_chain(3 * N + 1, [N | Acc])
    end.

main() ->
    L = [{X, do_chain(X)} || X <- lists:seq(1, 999999)],
    hd(lists:sort(fun({_, A}, {_, B}) -> A > B end, L)).

Voici une explication rapide comment ça fonctionne. Pour chaque nombre de 1 à 999,999 on ajoute le tuple {Nombre, Longueur de la suite} à une liste. Une fois que la liste est pleine, on la met en ordre décroissant selon la longueur de la suite et on retourne le premier élément. Voici ce que ça donne quand on exécute le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
1> c(prob14s).
{ok,prob14s}
2> prob14s:main().
{837799,524}
3>

Maintenant, passons aux choses sérieuses! L'ordre dans lequel on obtient la longueur des suites n'est pas importante, ça semble donc un projet idéal pour utiliser les deux cores de mon processeur! Voyons le code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
-module(prob14p).
-compile(export_all).

even(N) -> N rem 2 == 0.

do_chain(N) ->
    do_chain(N, []).

do_chain(1, Acc) -> length(Acc);
do_chain(N, Acc) ->
    case even(N) of
        true  -> do_chain(N div 2, [N | Acc]);
        false -> do_chain(3 * N + 1, [N | Acc])
    end.


range_seq(Start, Stop, Step)
    when Start + Step >= Stop ->
        [{Start, Stop}];
range_seq(Start, Stop, Step) ->
    [{Start, Start + Step - 1} | range_seq(Start + Step, Stop, Step)].


spawn_processes(Ranges) ->
    Pid = self(),
    lists:foreach(
        fun(L) ->
            spawn(
                fun() ->
                    lists:foreach(
                        fun(X) ->
                            Pid ! {sequence, {X, do_chain(X)}}
                        end, L)
                end)
        end, Ranges).


main() ->
    Ranges = [lists:seq(Start, Stop) ||
             {Start, Stop} <- range_seq(1, 999999, 20000)],
    spawn_processes(Ranges),
    L = lists:map(
        fun(_) ->
            receive
                {sequence, {X, Length}} -> {X, Length}
            end
        end, lists:seq(1, 999999)),
    hd(lists:sort(
        fun({_, A}, {_, B}) -> A > B end, L)).

Hummm, le code est plus long, est-ce que ça en vaut la peine? Nous verrons plus tard, pour l'instant, quelques explications.

L'idée de ce nouveau programme est d'utiliser plusieurs processus, où chacun calculera la longueur d'une parti des nombres de 1 à 999,999. Combien de suites à calculer par processus? Comme nous avons un million de nombres à calculer, il serait irréaliste d'utiliser un processus par nombre, le "overhead" de la création d'un million de processus va certainement tuer la performance de notre programme. J'ai choisi de calculer la longueur de 20,000 suites par processus, ce qui donne un total de 5,000 processus. Est-ce le meilleur choix? Franchement, je sais pas, il faudrait faire des benchmarks.

Donc, la première chose qu'on fait, on crée une liste de listes. La fonction range_seq/3 permet de créer cette liste. Ensuite, on démarre les processus. Dans la fonction spawn_processes/1, on crée un processus, et à l'intérieur on appelle do_chain/1 sur chaque élément de la sous-liste. Il est à noter que spawn/1 ne bloque pas, donc les 5,000 processus sont démarrés très rapidement. À l'intérieur du processus, on envoie à notre processus principal le message {sequence, {X, Longueur}}. On envoie le message afin de pouvoir récupérer le résultat plus tard.

De retour dans notre fonction main/0, nous allons utiliser la fonction map/2 pour récupérer les résultats. Nous avons envoyé 999,999 message, il faut donc récupérer 999,999 résultats. On utilise donc lists:seq(1, 999999) afin de faire 999,999 receive, mais la valeur courant de seq/2 ne nous intéresse pas du tout, c'est pourquoi on utilise la variable _. Dans le corps de receive, on extrait X et la longueur. Ils seront accumulés dans une liste. Finalement, on fait la même chose que dans le programme séquentiel, on trouve la plus longue suite.

Est-ce que le programme parallèle est plus rapide? Voyons!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
% erl -smp
Erlang (BEAM) emulator version 5.5.2 [source] [smp:2] [async-threads:0] [kernel-poll:false]

Eshell V5.5.2  (abort with ^G)
1> c(prob14s).
{ok,prob14s}
2> timer:tc(prob14s, main, []).
{30539552,{837799,524}}
3> c(prob14p).
{ok,prob14p}
4> timer:tc(prob14p, main, []).
{20054550,{837799,524}}
5>

La version séquentielle prend 30.5 secondes et la version parallèle prend 20 secondes. Cool, hein?

Et voilà, j'espère que mes explications ont été claires (et exactes, je suis encore nouveau à Erlang.) N'hésitez pas à demander des explications supplémentaires et les experts d'Erlang, corrigez-moi s'il y a lieu.

[Jedai]

De mon côté, avec un simple Core, j'ai testé ces deux programmes avec Erlang5.5.5, prob14s prend 30s et prob14p prend 27s (?? je rappelle que j'ai une machine à simple Core, il semblerait donc que l'usage de threads m'ait permis d'exploiter plus à fond ma machine... ).

Néanmoins, si ton algorithme se prête bien à cette parallélisation, c'est parce qu'il est un peu naïf (c'est souvent le cas avec les algorithmes parallélisables, pour éviter les interdépendances qui nuisent à la parallélisation, avec suffisamment de Core ils peuvent prendre l'avantage sur des algorithmes séquentiels), un algorithme moins naïf mais difficilement parallélisable serait :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
import Data.Array
import Data.List
 
syrs n = let a = listArray (1,n) $ 0:[1 + syr a n x | x <- [2..n]] in a
    where
      syr a n x = let x' = if even x then x `div` 2 else 3 * x + 1
                  in if x' <= n then a ! x' else 1 + syr a n x'
 
main = print $ foldl' maxBySnd (0,0) $ assocs $ syrs 1000000
    where maxBySnd x@(_,a) y@(_,b) = if a > b then x else y

Ce programme tourne en 2s sur ma machine...

--
Jedaï

[igwan]

Bien bien ! Je vois une petite optimisation possible : au lieu d'attendre d'avoir reçu les résultats des calculs pour toutes les séquences et de constituer une liste et de la trier, on peut calculer le Max à chaque résultat reçu, au fil de l'eau. Ca économise la mémoire, et ca va plus vite :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
main2() ->
    Ranges =[lists:seq(Start, Stop) ||
        {Start, Stop} <- range_seq(1, 999999, 20000)],
    spawn_processes(Ranges),
    main2_loop(999999).

main2_loop(N) ->
    main2_loop(N, {0,0}).

main2_loop(0, {Max_X, Max_length}) ->
    {Max_X, Max_length};
main2_loop(N, {Max_X, Max_length}) ->
    receive
        {sequence, {X, Length}} when Length > Max_length ->
            main2_loop(N - 1, {X, Length});
        {sequence, {_X, _Length}} ->
            main2_loop(N - 1, {Max_X, Max_length})
    end.

Sur ma machine (non-smp) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
7> timer:tc(prob14p, main, []).
{22437000,{837799,524}}
8> timer:tc(prob14p, main2, []).
{18344000,{837799,524}}

On peut aussi faire que chaque process calcule son propre maximum et ne transmette ainsi qu'un seul message ... 5000 messages au lieu de 999 999. Ca devrait aussi accelerer le programme, vu que les valeurs sont copiées lorsqu'on transmet un message. (a l'exception des binaires à partir d'une certaine taille qui sont passés par référence)


Tu peux aussi essayer la compilation native (ne fonctionne pas encore sous Win) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

c(prob14p, [{native, o3}]).

[GnuVince]

De mon côté, avec un simple Core, j'ai testé ces deux programmes avec Erlang5.5.5, prob14s prend 30s et prob14p prend 27s (?? je rappelle que j'ai une machine à simple Core, il semblerait donc que l'usage de threads m'ait permis d'exploiter plus à fond ma machine... ).

Néanmoins, si ton algorithme se prête bien à cette parallélisation, c'est parce qu'il est un peu naïf (c'est souvent le cas avec les algorithmes parallélisables, pour éviter les interdépendances qui nuisent à la parallélisation, avec suffisamment de Core ils peuvent prendre l'avantage sur des algorithmes séquentiels), un algorithme moins naïf mais difficilement parallélisable serait :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
import Data.Array
import Data.List
 
syrs n = let a = listArray (1,n) $ 0:[1 + syr a n x | x <- [2..n]] in a
    where
      syr a n x = let x' = if even x then x `div` 2 else 3 * x + 1
                  in if x' <= n then a ! x' else 1 + syr a n x'
 
main = print $ foldl' maxBySnd (0,0) $ assocs $ syrs 1000000
    where maxBySnd x@(_,a) y@(_,b) = if a > b then x else y

Ce programme tourne en 2s sur ma machine...

--
Jedaï

Je dois avouer que les problèmes du Projet Euler ne sont pas les meilleurs pour la parallèlisation, car ils peuvent *tous* être écrit pour exécuter en moins d'une minute même sur une machine très modeste.

Le but ici n'est pas de montrer un algorithme très "clever", mais de discuter comment utiliser la concurrence de Erlang.

[GnuVince]

Suite à la suggestion de igwan, j'ai réduit le nombre de messages de 999,999 à 5,000. Le nouveau temps en dual-core:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
2> timer:tc(prob14p, main2, []).
{15985109,{837799,525}}
3>

Pas mal!