Découper une boucle pour occuper différents coeurs

Bonjour,

Je dispose d'une boucle de comparaison assez longue (5000 à 25000 éléments cela varie) entre des éléments qui sont des fonctions mathématiques. Pour comparer 2 fonctions je calcule leur distance à un histogramme par la méthode des moindres carrés (je ne rentre pas dans les détails mais cela fait pas mal de calcul) et donc ma boucle peut prendre jusque 2sec de temps à autre, ce n'est pas beaucoup mais quand il faut 50 itérations (50 boucles de comparaisons) cela commence à faire un peu beaucoup.

Code:

---

1 2 3 4 5 6 7

for( FctPoly functionLoop : pop) { // on itère sur toutes les fonctions de ma liste if ( this.moindreCarre(functionLoop) < val ) { // on calcul la valeur MoindreCarrée de la fonction et si elle est inférieur au minimum actuel on entre dans le 'if' f_parents = this.insert(f_parents, functionLoop) ; // on l'ajoute à la liste des bonnes fonctions val = this.moindreCarre( f_parents.get(f_parents.size()-1) ) ; // on met à jour notre minimum } } //des changements sont apportés au fonction ici

---

Et tout cela est dans un while(val>precision) on va donc répéter la boucle jusqu'à valider la condition et cela peut prendre du temps

Mon idée vient de ce que j'ai vu en cours avec OpenMP (et langage C) où on peut diviser une boucle en différents morceaux et dire à plusieurs Threads de s'occuper d'un bout de la boucle, après mon algo doit pouvoir tourner sur différentes machines, donc pas besoin de monter à plus de 4 Threads car si la machine à moins de coeurs cela sera inutile, mais au moins diviser par 2 si possible

Autre point : avant toute cette manip, je trie ma liste de fonction (taille 5000 à 25000) avec une implémentation du QuickSort adapté bien sur à mon cas et choisissant comme critère le calcul MoindreCarré, mais je me demande en même temps si implémenter un Comparator et faire un sort(liste,MyComparator) ne serait pas plus rapide ? Mais je n'en ai aucune idée

Avec java 8 et les stream ce serait assez simple.

Pour avoir tout ce qui match, avec un stream parallele:

Code:

---

liste = pop.stream().parallel().filter((i) -> moindreCarre(i) < val).collect(Collectors.asList());

---

Citation:

---

Envoyé par tchize_

Avec java 8 et les stream ce serait assez simple.
Pour avoir tout ce qui match, avec un stream parallele:

Code:

---

liste = pop.stream().parallel().filter((i) -> moindreCarre(i) < val).collect(Collectors.asList());

---

---

Ow je connaissais les streams mais que les trucs "de base" pas ce genre de fonctionnalités, il faudrait que je lise 2-3 trucs j'y découvrirait surement des outils pas mal !

Le principe est le bon, mais après pour mon cas et bien je n'ai pas réellement besoin de récupérer une liste des éléments qui sont moindreCarré inférieur à val

Mais comme je viens de lire sur la parallélisation (et ce qui me semble logique au final) c'est que c'est rentable sur des calculs indépendants, sinon s'il faut tenir compte de toute les valeurs ça ne sera pas plus performant voir pire
Et comme je cherche au final à trouver les minimums de ma liste, je remarque que paralléliser n'est peut-être pas le mieux

Citation:

---

Envoyé par azrop

Et comme je cherche au final à trouver les minimums de ma liste, je remarque que paralléliser n'est peut-être pas le mieux

---

C'est à voir évidement en fonction de tes algorithmes. Pour prendre un exemple de base, le max de N nombre, ça se paralléliste très bien en cherchant le max de chaque sous set, puis le max des max. Et l'api stream permet de faire ce genre de construction facilement en mettant à disposition du filtrage parallèle, de l'aggrégation supportant le parallélisme, etc.

C'est exactement le genre de choses que j'ai fait en cours mais dans un langage différent c'est donc assez dur de trouver les équivalents, enfin surtout là donc je veux bien quelques pistes ;) j'ai cherché un peu mais je ne trouve comment diviser, trouver les min et re-fusionner

Pour le moment cette ligne :

Code:

---

f4 = (ArrayList<FctPoly>) f4.stream().sorted((f1,f2)->Double.compare(histo.moindreCarre(f1), histo.moindreCarre(f2))).collect(Collectors.toList());

---

est plus performante que mon quickSort que j'avais fait ça me fera gagné des lignes de codes au moins (même sur des tailles de 10 c'est mieux)

Sinon pour trouver un groupe de minimum je pensais à trier la liste puis récupérer les 10 premiers par ex, mais côté parallélisation je sais pas trop ce qui est le mieux (j'ai aussi remplacé stream par parallelstream mais c'est moins performant, mais c'est normal car peu de données et le traitement n'est pas indépendant)

pour la parallélisation, faut tester. Le sorted je pense supporte la parallélisation. Tu va avoir N stream triés puis au moment du collect on comparera les têtes de chaque stream.

Donc 10 streams // pou 10 données ce nr sera pas performant,
10 streams pour 1 million de données, ça risque d'être mieux :)

Salut,

Citation:

---

Envoyé par azrop

Sinon pour trouver un groupe de minimum je pensais à trier la liste puis récupérer les 10 premiers par ex, mais côté parallélisation je sais pas trop ce qui est le mieux (j'ai aussi remplacé stream par parallelstream mais c'est moins performant, mais c'est normal car peu de données et le traitement n'est pas indépendant)

---

Attention car si les opérations ne sont pas indépendante cela peut même fausser le résultat du parallelStream...

Citation:

---

Envoyé par azrop

j'ai cherché un peu mais je ne trouve comment diviser, trouver les min et re-fusionner

---

C'est à dire ?
Que cherche-tu à récupérer exactement comme résultat ?
Que fait la méthode histo.moindreCarre() ?


a++

En fait j'ai besoin de récupérer les fonctions minimales de ma liste (taille entre 5000 et 25000)(minimale selon le sens minimale valeur au test du moindreCarré(cf plus bas))

Et comme je veux les 5-6 "meilleurs" et bien avec la boucle cela marchait pas mal, mais avec les stream je en trouve pas du tout mieux, car "il faut" (car je n'ai pas trouvé autre chose) trier puis récupérer les 5-6 premiers mais c'est 5 à 10 fois plus long car avec la boucle pas question de tri mas seulement un parcours de la liste et hop

Performances actuelles :
tps<2sec pour le tour de boucle
tps>25sec pour le tri du stream puise récup des 5 premiers (list =list.stream().limit(5).sorted(...);)
Le test moindreCarré c'est ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

public static double moindreCarre1(Fonctionf){ double y=0; double f_x=0; double resultat=0; for(Entry<Double, Double> set : histo.getMap().entrySet()){ y = set.getValue(); f_x = f.f_de_x(set.getKey()); resultat += Math.pow((y-f_x), 2); } return resultat; }

---

Pour faire simple c'est la distance entre une courbe et un histogramme
On a une tache plutôt indépendante, on pourrait paralléliser le travail : plusieurs flux font la somme de certains éléments et on fusionne les sommes partielles, mais je ne sais pas le faire car on ne peut utiliser que des variables 'final' dans les stream

Code:

---

1 2 3

histo.getMap().entrySet().parallelStream().forEach(entry -> { Math.pow((entry.getValue()-f.f_de_x(entry.getKey())), 2); });

---

actuellement ce que j'ai fait, mais cela ne fait rien j'en suis conscient

Donc :
- je ne sais pas diviser un calcul qui a pour but de calculer une valeur pour chaque élément et sommer dans une unique variable
- je cherche à récupérer les 5-6 minimums d'une liste selon un critère plus performant que par un tour de boucle même si je commence à douter de son existence

Je suis super motivé et prêt à faire toutes les recherches et tests qu'il faudra, mais je ne juste pas où aller malgré mes recherches

Citation:

---

Envoyé par azrop

- je ne sais pas diviser un calcul qui a pour but de calculer une valeur pour chaque élément et sommer dans une unique variable

---

Tu somme dans N variables correspondant aux N threads parallèles
Un fois tout finis tu somme les N variables dans ta variable finale.

autrement dit

Code:

---

X = f(a) + f(b) + f(c) + f(d) + f(e) + f(f)

---

c'est le même que

Code:

---

1 2 3

X = f(a) + f(b) + f(c) + f(d) + f(e) + f(f)

---

Le problème c'est que tu pense avoir besoin de trier pour ça. Probablement parce que tu te concentre sur ce qu'offre par défaut l'api Stream avec les collecteurs. Finalement tu as déjà une boucle qui marche, il te faut juste:

l'appliquer sur N sous sets => parallelStream
Stocker ça dans une structure dédiée puisque chaque thread aura besoin de son set de variables => classe dédiée plus accumulateur
Trouver le moyen de recombiner les résultats de chaque set. => Combiner

Le tout avec reduce dont le boulot est de sortir un objet calculé à partir d'un stream.

Exemple de structure avec ce que j'ai compris de ton code

Code:

---

1 2 3 4

public class Resultat { Double total; TonType[] cinqPlusPetits = new TonType[5]; }

---

L'accumulation que faisait déjà ta boucle, juste qu'elle stockait pas dans un objet dédié.

Code:

---

1 2 3 4 5 6 7 8

Resultat accumulateur(Resultat actuel,TonType nouveau){ if (actuel==null){ actuel = new Resultat(); } actuel.total += tonCalcul(nouveau); // si nouveau plus petit qu'un des 5 plus petits dans actuel, mettre à jour tableau. return actuel; }

---

La combinaison du résultat de plusieurs boucles indépendantes, à créer.

Code:

---

1 2 3 4 5 6

Resultat combineur(Resultat gauche, Resultat droite) { Resultat resultat = new Resultat(); resultat.total = gauche.total + droite.total; resultat.cingPlusPetits = // calculer les plus petits entre gauche et droite. return resultat; }

---

Code:

---

1 2 3 4 5 6

Collection<TonType> taCollection = ....; Resultat resultat = taCollection.parallelStream().reduce( null, this::accumulateur this::combineur );

---

Je rajoute que le stream n'est qu'une aide pour faciliter les opérations de mise en parallèle, mais ce qu'il te faut d'abord, c'est d'avoir sur papier un algo déjà parallèle. Tu dois donc penser, j'ai N élément, je le divise en 2 sets, comment je peux calculer un résultat sur chaque set, indépendament de l'autre set et comment en comparant deux résultat indépendants sur deux set indépendant, je peux en conclure le résultat si j'avais calculé sur le set complet.

Dans l'exemple simple du max, ce serait dire max (set) = max(max(sousset1),max(sousset2));
dans l'exemple du sum, ce serait un sum(set) =sum(sousset1)+ sum(sousset2);
dans le cas d'une moyenne ce serait moyenne(set) =( moyenne(sousset1)*taille(sousset1) + moyenne(sousset2)*taille(sousset2) ) / taille(set);


etc...

Je ne suis pas sur d'avoir compris toutes tes explications mais ayant cherché et discuté ailleurs en même temps, j'ai trouvé une solution pour mon calcul des éléments sur la boucle :

Code:

---

double val = histo.getMap().entrySet().parallelStream().map(entry->Math.pow((entry.getValue()-f.f_de_x(entry.getKey())), 2)).reduce(0.0,Double::sum);

---

Mais pas de gain de perf ni en parallelStream ni stream simple
la boucle de base prend : 480µs (micro-sec)
avec stream : 48 000µs
Donc bon pas top

Sinon pour le point de calculer les minimums, et bien je pense qu'il n'est pas possible d'aller plus vite tout simplement, car avec une boucle on passe une fois et on met en même temps à jour notre minimum alors qu'avec un stream on ne peut pas changer son état pendant l'éxecution donc on ne gagne rien, on est même très perdant si on cherche à trier avant

Merci pour vos aides

Citation:

---

Envoyé par azrop

la boucle de base prend : 480µs (micro-sec)

---

Pourquoi tu veux optimiser au delà de ça, c'est des cacahuète ça. Tu nous paralais au début de plusieurs secondes :weird:

J'avoue que moi-même ne trouve pas ça très clair, car en commençant je me souviens bien que ça prenait jusque 1sec, mais là je le refait tourner avec les qqaméliorations et j'affiche le temps de chaque tour et je tourne autour de 100-300ms ce qui est très très bien, donc j'avoue que je ne sais pas trop d'où tout sort si c'est grâce à chaque trucs par ci par là, en touts cas je peux clore le post, merci à vous