Construction d'une image pixel par pixel en multi-threads

Bonjour à vous,

J'ai récemment créé un petit moteur de rendu de scène 3D. De base, il n'utilisait pas de threads supplémentaires.

Le traitement (la génération de l'image) prend ~2.5s. Je me suis donc dit que je pourrais essayer d'accélérer un peu tout ça en multi-threads (sur un core i7 920 d0 (4 cores physiques, 4 logiques)).

Le résultat: le programme met ~4.3s à l'exécution, mon implentation de threads l'a beaucoup ralentie. Je ne comprends pas bien pourquoi.

L'algorithme sans ajout de threads:

Code:

---

1 2 3 4 5 6 7 8 9 10

for (int i = 0; i < hauteurImage; i++) { for (int j = 0; j < largeurImage; j++) { //calcul de la couleur du pixel //traitement de la couleur du pixel (pour le out of gamma) //affichage du pixel fenetre.getGraphics.setColor(couleurCalculee); fenetre.getGraphics.fillRect(ligne, colonne, 1, 1); } }

---

Et en multi-threads:

Code:

---

1 2 3 4 5 6 7 8 9

//déclaration de x threads, où x = Runtime.getRuntime().availableProcessors(); for (int i = 0; i < hauteurImage; i++) { for (int j = 0; j < largeurImage; j++) { Thread truc = listeThreads.get(j%x); //thread correspondant au pixel en cours truc.join(); //attendre le traitement précédent du thread truc.start(); //calcul du pixel puis affichage de celui-ci, de la même méthode qu'en simple thread } }

---

J'ai aussi essayé en créant un thread temporaire par calcul de pixel, mais les résultats sont les mêmes.

Au final, les threads calculent un thread sur x, où x est le nombre de coeurs disponibles (ici 8, testé avec 4 aussi, mêmes résultats).

Salut,

ton join() fait que à chaque itération(), tu attends que ton thread soit terminé, donc en réalité tu n'est pas en multithread.

tu devrais essayer de gérer plutôt ça par un système de pool de thread : à chaque itération tu empile un ordre de calcul de point, ton pool étant chargé de paralléliser les traitement.

regarde l'api java.util.concurent

par exemple...

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

public class DessineImage {   public final Fenetre fenetre;   public DessineImage(int hauteurImage, int largeurImage, Fenetre fenetre) { this.fenetre=fenetre;   ExecutorService service = Executors.newFixedThreadPool(10/*nombre de threads*/);   for (int i = 0; i < hauteurImage; i++) { for (int j = 0; j < largeurImage; j++) { service.execute(new CalculPoint(j,i)); } }   service.shutdown(); }   public class CalculPoint implements Runnable {   private final int colonne; private final int ligne;   public CalculPoint(int colonne, int ligne) { this.colonne=colonne; this.ligne=ligne; }   @Override public void run() { //calcul de la couleur du pixel //traitement de la couleur du pixel (pour le out of gamma) //affichage du pixel fenetre.getGraphics().setColor(couleurCalculee); fenetre.getGraphics().fillRect(ligne, colonne, 1, 1);   } }   }

---

Bonsoir et merci de ta réponse.

eclesia m'a conseillé d'utiliser ceci aussi. Je l'ai donc implanté, l'exécution prend maintenant ~12 secondes. :/ Il m'a conseillé de regarder le temps d'exécution des méthodes, ce que je vais faire. :)

Concernant le join, en fait j'avais plusieurs threads, donc j'attendais seulement le thread qui était sensé calculer le pixel (je fais un .get sur une liste de threads précédemment déclarés).

Je viens aux nouvelles, j'avais laissé des centaines d'exécutions de System.out.println, d'où le temps d'exécution. Au final, le temps d'exécution passe à ~2.5s.

Soit environ le même temps qu'en simple thread. Les changements dans Graphics puis son affichage semble être le "souci" étant donné qu'une instruction seulement ne peut être faite en même temps. Bref, il va à priori falloir queje me débarasse de graphics.

il y a plusieurs choses à considérer :

- déjà les threads java ne sont pas des threads système mais des threads simulés dans la jvm : donc il y a un temps de partage.
tu peux éventuellement modifier la fabrique de thread pour modifier la priorité d'exécution de tes threads

- toute introduction de méthodes intermédiares introduit des temps de traitement en particulier pour la gestion de la pile

- l'instanciation des Runnable introduit un temps non négligable : on peut résoudre ça par un pool par exemple

- après il faut regarder comment est implémenté ton setColor et ton fillRect
tu peux éventuellement dessiner ton point par manipulation d'octet probablement plus rapide que les méthodes de dessin de la classe Graphics2D


- il faut mettre en opposition le temps de traitement unitaire de tes pixels et le temps introduit par l'introduction de thread : peut être que faire un thread par ligne serait plus efficace, ou découper ton image en bloc

pour les threads simulés, je me suis mal exprimé, les threads java sont mappés sur des threads natifs, mais ce sont pas des threads natifs, dans le sens ou il y a une surcouche de gestion interne qui introduit nécessairement un temps des gestion. maintenant il est peut probablement de gagner tant que ça en implémentant des threads complètement natif, sauf en introduisant la gestion de l'affinité de manière à optimiser la répartition sur les différents processeurs

Merci pour toutes ses informations, ça me sera très utile. :)

Je vais faire des tests, tenter des blocs de pixel par thread, l'instanciation doit prendre un certain temps en effet, pour une image de 400x400 ça me faisait 160 000 instanciations d'objet runnable.

Edit: par bloque de pixel ça reste au même temps d'exécution, je vais voir pour essayer de changer l'affichage, peut-être stocker l'image entière et l'afficher d'un coup au lieu d'appeler x fois fillRect & setColor, et si ça ne fonctionne pas mieux, voir pour trouver un autre moyen d'afficher l'image

Citation:

---

Envoyé par garheb

Merci pour toutes ses informations, ça me sera très utile. :)

Je vais faire des tests, tenter des blocs de pixel par thread, l'instanciation doit prendre un certain temps en effet, pour une image de 400x400 ça me faisait 160 000 instanciations d'objet runnable.

---

ça peut compter, mais bon 160000 instanciations,ça doit prendre peanuts (sur mon vieux pc pourri hyper lent (atom sous xp c'est pour dire), je viens de tester : 15ms) par rapport à 2,5s, mais bon, additionnées des ms, ça peut compter,

essayer de voir si tu peux pas optimiser tes calculs aussi (factoriser par exemple, précalculer, etc)

Ok, donc utiliser des * inverse au lieu de /, calculer des variables constantes au départ, et les réutiliser.

Je vais faire ça. (Ca va prendre du temps, y'a beaucoup de calculs :))

Citation:

---

Envoyé par garheb

Ok, donc utiliser des * inverse au lieu de /, calculer des variables constantes au départ, et les réutiliser.

Je vais faire ça. (Ca va prendre du temps, y'a beaucoup de calculs :))

---

oui ou faires des décalages au lieu de multiplications,

Code:

---

1 2 3 4

for(int i=0;i<10000000;i++) { int a=2; a=a+a; }

---

47ms

Code:

---

1 2 3 4

for(int i=0;i<10000000;i++) { int a=2; a*=2; }

---

47ms

Code:

---

1 2 3 4

for(int i=0;i<10000000;i++) { int a=2; a<<=1; }

---

32ms

pour les multiplications à la place des divisions ça dépend de tes opérandes à mon avis

Code:

---

1 2 3 4

for(int i=0;i<10000000;i++) { int a=2; a/=2; }

---

32ms

Code:

---

1 2 3 4

for(int i=0;i<10000000;i++) { int a=2; a*=0.5; }

---

125ms !

mais

Code:

---

1 2 3 4 5

int b=2; for(int i=0;i<10000000;i++) { int a=2; a/=b; }

---

454 ms !

alors que

Code:

---

1 2 3 4 5

final int b=2; for(int i=0;i<10000000;i++) { int a=2; a/=b; }

---

160ms !

En effet, je ne savais pas que ça changeait tant la donne de mettre en final ce qui doit l'être. Merci pour ces exemples, très instructif. :)

L'api graphique java2D (fillRect, fillPolygon &co) peut paraître capricieuse car elle est accéléré par le matériel.

De plus fillRect est une méthode complexe (il se passe plein de chose derrière), cela se vois très vite lors d'un profilling.

Si tu veu travailler sur ton image au niveau des pixel tu peu utiliser un tableau:

Code:

---

1 2 3 4 5 6 7

BufferedImage buffer = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB); int[] data = ((DataBufferInt) buffer .getRaster().getDataBuffer()).getData();   //ici tu peut modifier les pixels dans data, buffer sera mis a jour en fonction ... graphics.drawImage(buffer, 0, 0, null)

---

Déjà ca devrai booster tes perf. Tu peu avoir besoin de passer par un buffer intermédiaire (de mémoire le fait d’accéder directement aux pixels d'une Buffered Image peu désactiver certaines accélérations).
Note que je suis curieux de voir tes temps après ces modifs.

Pour la partie multithread, créé un thread par pixel, ca n'a pas de sens, a moins que ton pixel demande une méchante quantité de calcul, un thread c'est puissant mais "complex" pour le processeur. En gros l'idéal est de decouper ton image en 8 ou 16 sous images chacunes traitées dans un thread. Quant tout les threads ont fini leur travail tu dessine les N images aux bonnes positions sur ton ecran pour ainis reconstruire l'image final.
(ok c'est plus simple a dire qu'a faire ;))

Si tu a du post - traitement tu peu faire une file (pipeline) ou chaque thread fait un traitement sur l'image et le passe au thread suivant. Ca peu induire un peu de latence par contre.

En espérant avoir aidé, bonne chance !

Bonjour!

Je tombe à 1.4 secondes, en effet, une seconde de gagnée là-dessus! J'ai fait comme ceci:

Code:

---

1 2 3

BufferedImage _buffer = new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB); int[] _donnees = new int[h*w];

---

un setter pour remplir _donnees dans les threads puis:

Code:

---

1 2	_buffer.getRaster().setDataElements(0, 0, w, h, _donnees); _scene.getAffichage().drawImage(_buffer, 0, 0, null);

---

Je me posais une question concernant les différents calculs à optimiser: est-ce une bonne chose d'arrondir les double avant une division?

Par exemple, je manipule une valeur: 5.54165451517

puis je fais x/=valeur

Est-ce qu'arrondir la valeur à deux décimales (par exemple) près va accélérer tout ça? Ou au contraire, est-ce que le Math.round va ralentir le calcul?

Edit: La mise à jour de l'image (une fois générée une fois) avec un drag & drop d'objet dans la scène est quasimment instantanée (400ms), vraiment cool. :) Le résultat est quasimment du temps réel lors de mouvements successifs des objets)

salut

Citation:

---

Envoyé par garheb

Bonjour!

Je tombe à 1.4 secondes

---

cool :D

Citation:

---

Envoyé par garheb

, en effet, une seconde de gagnée là-dessus! J'ai fait comme ceci:

Code:

---

1 2 3

BufferedImage _buffer = new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB); int[] _donnees = new int[h*w];

---

un setter pour remplir _donnees dans les threads puis:

Code:

---

1 2	_buffer.getRaster().setDataElements(0, 0, w, h, _donnees); _scene.getAffichage().drawImage(_buffer, 0, 0, null);

---

Je me posais une question concernant les différents calculs à optimiser: est-ce une bonne chose d'arrondir les double avant une division?

Par exemple, je manipule une valeur: 5.54165451517

puis je fais x/=valeur

Est-ce qu'arrondir la valeur à deux décimales (par exemple) près va accélérer tout ça? Ou au contraire, est-ce que le Math.round va ralentir le calcul?

---

non je pense que çà fera rien : à priori les opérations en virgule flottante sont réalisées par le processeur, en un nombre de cycle qui ne dépend à priori pas de nombre de décimales

le round ralentira forcément le traitement et l'utilisation de l'arrondi au plus tôt dans tes calculs va introduire une dérive (une erreur) qui va forcément s'amplifier au long des calculs

Merci de ces renseignements, j'ai encore des calculs à optimiser puis il faudra que je cherche d'autres pistes d'améliorations. :)

Les Math.cos & sin, à utiliser tel quel ou faire sa propre fonction (ou une fonction optimisée trouvée) pour gagner encore en perfs?

Edit: Selon l'outil de mesure des temps de traitement cpu des différentes méthodes & threads, il s'agit bien du boulot des threads qui prend le plus de temps, donc c'est bien à ce niveau qu'il faut que j'optimise, l'affichage prend ~200ms, tandis que les threads prennent ~1.3s. Et plus précisément la méthode de détection des collisions des rayons (le moteur de rendu est en ray tracing) avec les objets de la scène.

Citation:

---

Envoyé par garheb

Merci de ces renseignements, j'ai encore des calculs à optimiser puis il faudra que je cherche d'autres pistes d'améliorations. :)

Les Math.cos & sin, à utiliser tel quel ou faire sa propre fonction (ou une fonction optimisée trouvée) pour gagner encore en perfs?

---

pour les cos et sin, tu peux précalculer des tables(échantillonage), mais tu perdras en précision, tout dépend de tes calculs : tu peux essayer par dichotomie de chercher la précision qui suffit pour ton calcul

je ne sais pas trop comment sont réalisées les cos et sin de java, mais j'imagine que même si elles ne sont pas traitées par le processeur directement (ce qui m'étonnerait aujourd'hui), elle doivent utiliser les algos les plus rapides. on ne peut pas exclure qu'un mathématicien ai pondu une formule de la mort qui tue de calcul de sinus ou cosinus depuis que les fonctions utilisées par java ont été implémentées, et qui écrasent les temps de calculs des algo précédents, mais bon, y'a peu de chances à mon avis, surtout que si tu refais l'implémentation d'un algo en java tu ne sera pas aussi performance qu'un proc

tiens j'ai trouvé ça rapidement : http://www.java-gaming.org/index.php?topic=24191.0

Merci je vais regarder ça. :)

C'est appliqué, le temps d'exécution ne change pas énormément, environ 50ms mais c'est très variable (sin & cos doivent être utilisés ~1000 fois pendant une exécution).

Au risque de redire la meme chose, profile ton sin et ton cos, si tu ne les appel que 1000 fois, j'imagine que ce n'est pas le point critique.

Pour ce qui est de la perf, tout dépend de ce que tu veu atteindre.

Historiquement tu peu faire rouler un jeu 3D dur un processeur a 100Mhz, le tout codé en C et ASMx86. Pour cela tu a 3 "secrets" :

-Connaitre les point faibles de ton langage (tu commence a en éliminer pas mal)
- Simplifier les calcules (lookuptable, comparer des ² plutôt que calculer une racine, ...)
- Diminuer le nombre de calcul nécessaire (c'est l’étape ou tu va gagner gros si tu trouve comment faire,tu a des piste dans la FAQ : http://jeux.developpez.com/faq/3d/?page=culling)

si tu veux pouvoir rendre n'importe quoi, le 3eme point est délicat et son application limité.

PS : on veux des screens !:D

Pour le rendu, une vidéo de quelques secondes de ce que ça donne: http://uptobox.com/kqgbq8gb59oo

Avec une lumière moins aggressive: http://uptobox.com/4ydq3eo5mj4s

Un sol réfléchissant (couleur 0, 51, 51), trois sphères réfléchissantes et une transparente.

Merci pour les pistes, je vous donnerais du neuf dans les prochains jours au fur et à mesure des améliorations. :)

J'ai changé le drag & drop, pour déplacer l'objet "en direct" et non plus au relâchement de la souris: http://uptobox.com/ejzlnuvdcm6b

On voit bien la latence que cela induit, mais le résultat n'est pas si mauvais. :)

Edit: une des fonction est appelée 2.6 millions de fois pour un rendu, c'est elle qui "bouffe" le plus de temps. A l'intérieur rien de très gourmand. Mais comme disait Coluche: "Un p'tit peu par un p'tit peu ça fait un gros peu". :D

Edit': Je pense que je vais devoir utiliser le gpu en parallèle pour avoir des temps plus décents, étant donné que le GPU est à priori très efficace pour ce qui est des traitements parrallèles. OpenCL a l'air d'être pas mal pour ça. Vous en pensez quoi? Ca pourrait à priori diviser le temps d'exécution par [1..10].

Hum ca doit surement aider, mais rendu la pourquoi ne pas utiliser opengl (qui utilise le gpu pour toi)?

En effet.

Mon objectif est d'essayer de faire du temps réel sans bibliothèque ou framework externe, ce serait violer cet objectif. :) Je vais chercher ce qu'il est possible de faire soi-même et comment il est possible de le faire.

Edit: Java 8 contiendra openCL en natif? ici et là Mhhh, dans ce cas, je peux l'utiliser sans violer mon objectif. :p

La fonction qui est appelée 2.6 millions de fois, elle contient quoi ?

Elle calcule, pour chaque objet, si le rayon en cours touche un des objets.

400*400 (nombres de pixels) * nombre de rayons envoyés par pixel (pour la précision) = ça monte très vite. :)

en gros pour ton rendu du fait un genre de raytracing soft et tu trouve étrange que ca soit long ? ^^

Je crois que c'est une méthode de rendu connue pour être longue (même optimisé sur un gros processeur) !

Du coup effectivement, openCL peu te sauver du temps, mais ça risque d’être difficile d'arriver a 60fps

Oui c'est du ray tracing (je l'ai marqué dans le premier post), je ne trouve rien bizarre, je cherche seulement à le rendre temps réel. :) Si possible ~15-20 fps, donc ~50 ms par image

hum bonne chance, du coup tu m'a donner envie de tester le raytracing, ca tombe bien c'est la fin de semaine :aie: de quoi passer un bon we!

La sans le code ca va être dur pour nous de te donner d'autre pistes ;) bonne chance !