rechercher un élément dans un tableau non trié en utilisant le multithreading

Version imprimable

j'ai écrit un programme mulithreadé en java pour rechercher un élément dans un vecteur non trié.
mon programme utilise le framework Executor.
voici mon essai:

Code:

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
 
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
 
public class SearchParallel {
 
    int[] array;
    Random r;
    int x, index = -1;
    ExecutorService pool;
 
    public SearchParallel(int length, int x) {
        this.x = x;
        pool = Executors.newCachedThreadPool();
        array = new int[length];
        r = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = r.nextInt(length);
        }
    }
 
    class Worker implements Runnable {
 
        int start, end;
 
        public Worker(int start, int end) {
            this.start = start;
            this.end = end;
        }
 
        @Override
        public void run() {
 
            while (index == -1 && start < end) {
                if (array[start] != x) {
                    start++;
                } else {
                    index = start;
                    System.out.println(Thread.currentThread().getName());
                }
            }
 
        }
    }
 
    void display() {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
 
    }
 
    void go(int n) {
        for (int k = 0; k < n; k++) {
            Worker w = new Worker(k * array.length / n, (k + 1) * array.length / n);
            pool.execute(w);
        }
        pool.shutdown();
        while (index == -1 && !pool.isTerminated()) {
        }
        if (index != -1) {
            System.out.println("item " + x + " is found at index " + index);
        } else {
            System.out.println("item " + x + "is not found");
        }
    }
 
    public static void main(String[] args) {
        int nbrTask = 10;
        SearchParallel sp = new SearchParallel(100, 4);
        sp.display();
        sp.go(nbrTask);
 
    }
 
}

normalement ce programme fonctionne mais j'aimerais profiter de votre expérience pour l’améliorer. si vous avez des remarques ou autres idées je suis très reconnaissant

09/05/2014, 18h25
adiGuba
Salut,

Perso ce qui me gêne le plus c'est la boucle d'attente active :
Code:

1 2 while (index == -1 && !pool.isTerminated()) { }
:arrow: Tu vas surcharger le CPU qui va constamment vérifier la condition de la boucle...
Une boucle passive serait plus adéquate :
Code:

1 2 3 while (!pool.isTerminated()) { pool.awaitTermination(1, TimeUnit.DAYS); }
Il y a aussi le fait que l'attribut "index" soit utilisé par plusieurs threads, et donc il devrait être déclaré volatile...

Sinon c'est un détail mais dans ta boucle tu répètes plusieurs fois le même calcul : array.length / n
Code:

1 2 3 4 for (int k = 0; k < n; k++) { Worker w = new Worker(k * array.length / n, (k + 1) * array.length / n); pool.execute(w); }
Il serait judicieux de déplacer cela avant la boucle :
Code:

1 2 3 4 5 final int size = array.length / n; for (int k = 0; k < n; k++) { Worker w = new Worker(k * size, (k + 1) * size); pool.execute(w); }
De plus il faudrait gérer le cas particulier où array.length est plus petit que n, sinon tu te retrouve avec un zéro...
Ta boucle est même fausse puisque tu peux ignorer certains éléments si la taille du tableau n'est pas divisible par "n".
Exemple avec un tableau de 50 éléments, et "n" qui vaut 3, on a array.length / n qui vaut 16.6666 soit 16 :
- 0 :arrow: new Worker(0, 16);
- 1 :arrow: new Worker(16, 32);
- 2 :arrow: new Worker(32, 48);
Il faudrait revoir cela...

Enfin, tu pourrais profiter du thread courant pour y exécuter un Worker au lieu de le passer au pool (plutôt que d'attendre, ca évitera de créer un thread).

Reste le problème du résultat, qui n'est pas déterminisme. C'est à dire que pour un même tableau qui contient plusieurs fois la même valeur, tu risques d'avoir un résultat différent selon l’exécution.
Mais c'est pas forcément un problème en soit...

A noter qu'avec Java 7 les ForkJoinTask serait peut-être plus pratique...
Et les Stream avec Java 8 !

a++
09/05/2014, 23h34
win_ubuntu
merci infiniment pour votre réponse.

Citation:

Envoyé par adiGuba

Salut,

Il y a aussi le fait que l'attribut "index" soit utilisé par plusieurs threads, et donc il devrait être déclaré volatile...

mais index est de type int (et non long ou double) et normalement c'est atomique.
Citation:
Sinon c'est un détail mais dans ta boucle tu répètes plusieurs fois le même calcul : array.length / n

Code:

1 2 3 4 for (int k = 0; k < n; k++) { Worker w = new Worker(k * array.length / n, (k + 1) * array.length / n); pool.execute(w); }

Il serait judicieux de déplacer cela avant la boucle :

Code:

1 2 3 4 5 final int size = array.length / n; for (int k = 0; k < n; k++) { Worker w = new Worker(k * size, (k + 1) * size); pool.execute(w); }
les deux codes ne donne pas le même résultat!
Citation:
De plus il faudrait gérer le cas particulier où array.length est plus petit que n, sinon tu te retrouve avec un zéro...
Ta boucle est même fausse puisque tu peux ignorer certains éléments si la taille du tableau n'est pas divisible par "n".
Exemple avec un tableau de 50 éléments, et "n" qui vaut 3, on a array.length / n qui vaut 16.6666 soit 16 :

0 :arrow: new Worker(0, 16);
1 :arrow: new Worker(16, 32);
2 :arrow: new Worker(32, 48);

Il faudrait revoir cela...
avec même boucle:
- 0 :arrow: new Worker(0, 16);
- 1 :arrow: new Worker(16, 33);
- 2 :arrow: new Worker(33, 50);
Citation:

Enfin, tu pourrais profiter du thread courant pour y exécuter un Worker au lieu de le passer au pool (plutôt que d'attendre, ca évitera de créer un thread).

comment, je n'ai pas bien compris

Citation:

Envoyé par win_ubuntu

mais index est de type int (et non long ou double) et normalement c'est atomique.

volatile ne sert pas à assurer l'atomicité, mais à indiquer à la JVM que la variable peut être accéder depuis différents threads.

Cela permet de forcer la JVM à vérifier réellement l'état de la variable, et de ne pas utiliser de cache.
Sinon, si la variable n'est pas modifié dans le code de la méthode, il est possible que la JVM ne la lise qu'une seule fois, et la remplace par la suite directement par la valeur lu en pensant qu'elle ne sera jamais modifié...

Citation:

Envoyé par win_ubuntu

les deux codes ne donne pas le même résultat!

En effet autant pour moi !!!
Le fait de sortir le calcul de la boucle fait ressortir le problème d'arrondi que j'indiquais... alors qu'il n'était pas présent dans ton code initial !!! :aie:

Citation:

Envoyé par win_ubuntu

comment, je n'ai pas bien compris

Il suffit de passer seulement "n-1" Worker au pool, et d'exécuter le dernier dans le thread courant avant d'attendre la fin du pool.
Exemple :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 // On passe les n-1 premiers Worker au pool : for (int k = 0; k < n-1; k++) { Worker w = new Worker(k * array.length / n, (k + 1) * array.length / n); pool.execute(w); } // On exécute directement le dernier Worker : new Worker(n-1 * array.length / n, array.length).run(); // Puis ont attend la fin des Worker du pool pool.shutdown(); while (index == -1 && !pool.isTerminated()) { }
Du coup avec "n=3" au lieu de créer 3 threads et d'avoir le thread courant en attente, tu vas seulement créer 2 threads et faire le dernier calcul dans le thread courant...

a++

10/05/2014, 22h45
Gugelhupf

Bonsoir,

Citation:

Envoyé par adiGuba

volatile ne sert pas à assurer l'atomicité, mais à indiquer à la JVM que la variable peut être accéder depuis différents threads.

Lorsqu'un attribut (variable primitive ou objet) est "volatile", les opérations d'affectations deviennent bien atomiques n'est-ce pas ?

Cordialement,
10/05/2014, 23h09
adiGuba

Citation:

Envoyé par Gugelhupf

Lorsqu'un attribut (variable primitive ou objet) est "volatile", les opérations d'affectations deviennent bien atomiques n'est-ce pas ?

Oui les affectations sont atomiques dans tous les cas, que l'on utilise volatile ou pas !
(sauf sur les long et double, où cela n'est pas garantie)
Cela garantie que tu n'auras jamais une valeur invalide car "à moitié" modifié par un autre thread.

Toutefois ce n'est pas suffisant pour un code multi-threadé, car il peut y avoir des effets indésirables lié aux différents caches (surtout dans un environnement multi-processeur).
Si tu n'utilises pas volatile, il est possible qu'un thread ne voie pas la modification de la valeur effectuée dans un autre thread, car il utiliserait une copie dans un cache qui lui est propre.
Le mot-clef volatile empêche cela, en obligeant le CPU à vérifier à chaque fois la vrai valeur de l'attribut.

a++
11/05/2014, 10h29
Gugelhupf

Ah d'accord, merci :)

En fait, suite à mon précédent sujet, j'avais cru que le mot-clé volatile servait à rendre les opérations d'affectation atomiques pour tous (long, double, et les autres objets).

Les 3 exemples que j'ai cités dans mon sujet n'étaient donc pas si équivalents que cela. Pour qu'ils le soient, j'aurais du, tout comme mon 3eme exemple (avec volatile boolean), mettre le mot-clé volatile à mon 1er exemple (avec boolean), et à mon 2nd exemple (avec AtomicBoolean), afin que la JVM ne cherche pas à mettre dans un cache d'optimisation ces attributs.

Merci (et désolé de squatter le topic :? ).