Optimiser un programme java

Bonjour,

Pour mon travail je dois réaliser un outil de simulation multi-agent, en physique.
Imaginez un grand nombre de particules dans un espace en 2D. Chaque particule à ses coordonnés (x,y) et se déplace au hasard sur le plan.
Chaque fois qu'une particule se rapproche d'une autre elle est repoussé suivant une fonction mathematique assez lourde (avec des exponentielles).

Comment j'ai procédé :
En gros j'ai un Thread principal qui contient une boucle. Cette boucle calcul la prochaine position de chaque particule en fonction de toute les autre (il faut les comparer une à une). Lorsque toutes les particules sont mise à jour, j'incremente le temps de simulation et je recommence.

Apres quelques semaines de boulot mon programme JAVA est pret. Mais malheurs, dès que le nombre de particule dépasse une soixantaine, le programme rame comme pas possible (avec ou sans affichage graphique). L'utilisation normal c'est au moins avec 500 voir 1000 agents en meme temps.
Je peux pas rendre ce prog, il faut que je l'optimise un peu, mais je ne sais pas du tout comment faire. Est ce que vous pourriez me donner quelques conseils ?
Quel genre d'operations est le plus lourd ?
y a t il des 'trucs' pour aller plus vite?
Est ce que j'ai bien fait de choisir Java?
Est ce que c'est plutot lié au pc moyennement performant ou au programme mal codé ?
Existe t il des outils qui permette d'optimiser automatiquemnt un code?
Existe t il des outils qui permette de mesurer la "lourdeur du code" ?

MErci pour votre aide.
a+

Bonjour,

Citation:

---

Cette boucle calcul la prochaine position de chaque particule en fonction de toute les autre (il faut les comparer une à une).

---

Peux-tu nous donner plus d'informations sur la façon dont tu fais cela ? Tu compares vraiment toutes les particules avec toutes les autres, soit n² opérations ?

N'est-il pas possible de "négliger" l'influence des particules loin de celle qu'on étudie ?

Nicolas

PS - voir aussi le forum algorithmique de ce site.

Tu pourrais également passer ton programme dans un Profiler afin de voir quelles sont les parties de ton code qui font office de golet d'étranglement, et pouvoir réagir en conséquence...


Tu as par exemple le profiler de netbeans qui est parfait pour ce genre d'opérations:

http://profiler.netbeans.org/

Merci pour vos réponses, peux tu m'en dire plus sur les Profilers? c'est un soft? ça se telecharge ?

C'est un module de l'environnement de programmation (IDE) Netbeans. Dans quoi codes-tu ?

Si tu pouvais nous montrer quelques bouts de codes susceptibles d'être longs (le calcul en lui-même, et la méthode paintComponent(Graphics) de ton composant d'affichage des particules).

Je code avec JCreator.

Je vais essayer de vous passer quelques bouts de code. Mais ça ne sera pas facile, parceque j'ai un découpage en sous-classes très important, va falloir que je réécrive certaine partie pour vous montrer.

Je reviens vous voir bientot.
En attendant, tout nouveau conseil est le bienvenue ! ;)
Merci

Avec des boucles et des calculs complexe le processeur est constamment sollicité essaye de voir si tu peux changer tes formules de calculs puis de tester leur temps d'exécution. Autre remarque si tu as plusieurs processeurs sur ta machine tu peux créer plusieurs threads afin qu'ils soient tous utilisés.

Citation:

---

si tu peux changer tes formules de calculs

---

et aussi stocker des résultats intermédiaires intervenant souvant dans les calculs

Bonjour,

par "Agent" je crois qu'on imagine plus ou moins un Thread. Or 6000 Thread en même temps, c'est trop gourmand en ressoruce, 60 ça devrais passer.

Si tu crée un Thread par agent, il faut aussi pense à ne pas en créer trop... ni trop peu: en créer quelques-uns pour paralléliser un minimum le traitement, mais tu traiter tes agents linéairement par paquet dans un pool de Thread, pour distinguer en quelques sortes tes tâhces alogrithmique, et le sThread systèmes. (un peu à la manière de la classe TimerTask)

si toutfois le problème viens des Thread: ça tu le vois facilement dans Eclipse ou avec un profiler.

Je suis d'accord. Si tu veux simuler plusieurs milliers de particules, un Thread par particule, pas étonnant que ton programme n'arrive pas à gérer.

Dans ce genre de cas, le mieux est de créer une liste de tes objets particules, et de les faire se déplacer une par une en bouclant sur ta liste.

Ensuite, à toi de gérer intelligemment les répulsions pour ne pas allourdir les calculs (chaque objet "particule" pourrait connaître les 10 particules les plus proches et négliger les autres... cette liste étant évidemment mise à jour après déplacement)

Bonjour et merci pour vos nombreuses réponses.

Concernant les Threads, je pense que la discussion est interessante.
En fait je n'ai PAS un thread par particule , mais un seul thead en tout dans mon programme.
Ce thread contient une boucle 'while' dans laquelle se trouve une routine de mise à jour de chaque particule une par une , grosso modo :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

Tant que (simulationEnCours)   Pour i de 1 à taille(listeParticule)   Particule p = listeParticule(i) ; p.miseAJour(listeParticule) ;   Fin   Fin

---

Sachant que la fonction Particule.miseAJour(liste) parcours à nouveau la liste pour calculer les differentes répulsions.
Un calcul de replusion entre deux particules consiste à résoudre 3 fonctions qui contiennent chacune des exponentielles. (eh ouai ,ça explose vite le nombre d'operations tout ça!)
Peut etre devrais-je utiliser mon thread differement ?


Sinon petite remarque. Je veux bien considerer uniquement les 10 plus proches particules. Mais pour savoir quelles sont les 10 plus proches , il faut bien que je parcours la liste au complet et que je rajoute un calcul de distance en plus. Je ne suis pas certain que ça aille réellement plus vite.

Qu'en pensez-vous ?

Ton problème à mon avis n'est pas lié au thread.

Peux-tu exécuter ton calcul sans l'interface graphique (juste faire des println) pour voir si c'est bien le calcul qui te ralentit ou si ça n'est pas une mauvaise gestion de l'affichage?

Citation:

---

Sinon petite remarque. Je veux bien considerer uniquement les 10 plus proches particules. Mais pour savoir quelles sont les 10 plus proches , il faut bien que je parcours la liste au complet et que je rajoute un calcul de distance en plus. Je ne suis pas certain que ça aille réellement plus vite.

---

En première approximation, tu peux dire : pour calculer le déplacement de la particule x, je ne considère que les particules situées à moins d'une distance d (où d est fixe). Mais il ne faut pas que cela détruise ton modèle physique...

Nicolas

Rom :

Citation:

---

Peux-tu exécuter ton calcul sans l'interface graphique (juste faire des println) pour voir si c'est bien le calcul qui te ralentit ou si ça n'est pas une mauvaise gestion de l'affichage?

---

C'est fait et ça ne change rien. L'affichage n'est pas en cause, ça va toujours aussi lentement (ou presque).

Nicolas:

Citation:

---

En première approximation, tu peux dire : pour calculer le déplacement de la particule x, je ne considère que les particules situées à moins d'une distance d (où d est fixe). Mais il ne faut pas que cela détruise ton modèle physique...

---

Mais pour trouver "les particules situées à moins d'une distance d" il faut que je parcours toutes ma liste de particule, en calculant la distance à chaque fois, pour décider si je vais la garder ou non... ça n'accelere pas mon programme tant que ça... (un peu quand meme , mais je ne peux pas trop réduire la distance d'iteraction.)

euhh...
Ben je ne sais plus trop quoi tenter ... :(
Est ce que je gagnerais du temps si je mets à jour les positions des differentes particules en parrallele , plutot que sequentiellement comme je le fait dans ma boucle?

Bon alors là c'est la complexité de l'algorithme qui est en cause, pas l'implantation...

Dans ce sens: séquentiel vers parallèle, cela oblige à revoir un peu l'algorithme de calcul: quels sont les calcul interdépendant et qu'il faut faire l'un après l'autre... un peu complexe à définir sans connaitre les détails du calcul.

Si tu le fais: fais un découpage paramétrable en plusieurs groupe de particules, et exécute le avec 2, 4 ou 8 .. découpages pour éventuellement utiliser plusieurs core. (un nombre assez limité de Thread quoi)
Et définit les points de synchronisation entre les Thread (le moins souvent possible pour optimiser, mais quand cela est nécessaire pour garantir un résultat juste)


bref, je ne suis pas sûr que le parallélisme te feras gagner beaucoup de temps (il faut au moins que tu aie un dual-core),
ça veut peut-être aussi dire qu'il faut revoir l'algo: privilégier comme on disait les particules proches, (i.e. estimer quelles seront les valeur négligeables dans le calcul) et donc organiser les données pour qu'à chaque particule on puisse facilement associer une liste des particules proches, sans trop de calculs: un simple calcul de distance ne devrait pas être trop couteux ??

important pour optimiser les boucles
essaie de resuivre les calculs aussi: de sortir des boucles les calculs les plus couteux: racines carrée, exponentielles (le fonctions ) et les divisions, pour te restreindres aux additions et multiplications.
Par exemple pour le calcul de distance: ne calcule que la somme des carrés, mais pas la racine: tu travaille directement sur les carrés de distance.

Autre idée: si l'exponentielle est trop couteuse, il y a peut-être moyen de simplifier les calcul par développements limités en négligeant la partie "epsilon" du DL.

@om> tout à fait, mais l'implémentation est un terme plus adapté que l'implantation, qui peut porter à confusion dans certains contexte ;)

Re,

Pour information, le Profiler JPROBE a analysé mon code et associe la grande majorité du temp de calcul à la fonction particule.miseAJour() et en particulier à la methode qui implemente le calcul de répulsion entre particule.
Cette methode à un temp de calcul elevé et est appellé plusieurs millions de fois pendant 10 secondes de simulation.
Donc c'est bien cette fonction mathematique que je dois optimiser.

Je vais essayer les conseils d'optimisation mathematiques de Deltree , que je remercie chaleureusement!

Il faut donc tout faire pour limiter la complexité de la methode miseajour.

La piste que tu dois explorer est, à mon avis, de limiter le nombre de particule qui peuvent "repulser" la particule à mettre à jour.

Pour cela il t'a été proposé de prendre les particules se trouvant à une distance donnée de ta particule mais cela nécessite toujours de parcourir toutes tes particules même si le calcul de l distance et assez simple.

Une autre solution pourrait être le découpage de l'espace en zone et de te limiter uniquement à la zone dans laquelle se trouve la particule ainsi que les zones adjacentes. Tu peux associer à chaque zone les particules s'y trouvant en la mettant à jour à chaque fin de mise à jour de particule.

A toi de voir laquelle des deux solutions te fait gagner le plus mais fait attention à l'implementation que tu vas faire car cela peut ne rien amélioré si tu ne fait pas attention.

Citation:

---

Envoyé par benratti

Il faut donc tout faire pour limiter la complexité de la methode miseajour.

La piste que tu dois explorer est, à mon avis, de limiter le nombre de particule qui peuvent "repulser" la particule à mettre à jour.

Pour cela il t'a été proposé de prendre les particules se trouvant à une distance donnée de ta particule mais cela nécessite toujours de parcourir toutes tes particules même si le calcul de l distance et assez simple.

Une autre solution pourrait être le découpage de l'espace en zone et de te limiter uniquement à la zone dans laquelle se trouve la particule ainsi que les zones adjacentes. Tu peux associer à chaque zone les particules s'y trouvant en la mettant à jour à chaque fin de mise à jour de particule.

A toi de voir laquelle des deux solutions te fait gagner le plus mais fait attention à l'implementation que tu vas faire car cela peut ne rien amélioré si tu ne fait pas attention.

---

De même tu peux regarder si tu as des constantes qui sont recalculées à chaque boucle ou pas.
Attention par constante, j'entends des constantes ou des constantes par particules. ( genre pas la peine de calculer à chaque fois des éléments qui varie pas pour une particule donnée)

Et regarde la parallélisation ou un pool de thread pour faire le calcul.

(genre j'ai 60 particules mais j'ai 6 threads de calcul par exemple)

Un petit truc aussi pour aller 2 fois plus vite: il y a des chances que l'interaction d'une particule a sur une particule b soit la même au signe près de b sur a. Donc pas la peine de la calculer dans les 2 sens.

Autre idée: vérifie que tu ne crée pas de variable temporaire dans ta fonction de mise à jour. Les allocations mémoire + Garbage Collector peuvent faire mal.

Merci pour tous vos commentaires.
Tous ont l'air interessants , il va me falloir un moment pour implementer tout ça mais je reviendrais bientot vous dire quelles solutions ont le mieux marchées.
Merci encore à bientot

nicoV > Des variables temporaires, j'en crée des disaines dans la fonction de mise à jour. Mais c'est indispensable , non ? Il vaut mieux que je les passe en attribut de ma classe plutot ? Ca changera vraiment quelque chose ?

Citation:

---

Envoyé par piteon

nicoV > Des variables temporaires, j'en crée des disaines dans la fonction de mise à jour. Mais c'est indispensable , non ? Il vaut mieux que je les passe en attribut de ma classe plutot ? Ca changera vraiment quelque chose ?

---

Non, il vaut mieux les laisser en locales...

Ce qu'il voulait dire, je pense, c'est d'instancier des objets à chaque tour de boucle si tu n'es pas obligé...

Bonjour Piteon,

tu pourrais peut-être aussi utiliser un tableau de correspondance [x, exp(x)] qui te permettrait de remplacer le calcul systématique de exp(x) par simplement une lecture dans un tableau, créé une bonne fois pour toutes et stocke en mémoire. Cela introduit certes une approximation, mais pas forcément plus importante que celle réalisée en négligeant l'influence des particules les plus lointaines, si le "pas" de ton tableau est suffisamment fin. Par contre, je pense que cela peut réduire le temps de calcul de beaucoup, si j'en crois le nombre d'appels à la fonction exponentielle que tu réalises.

Je ne sais pas du tout si le calcul d'un carré est couteux en temps de calcul, mais si c'est le cas, tu peux aussi appliquer cette méthode pour le calcul des distances entre particules (calculer (x2-x1)^2 + (y2-y1)^2 après avoir regardé les valeurs de (x2-x1)^2 et de (y2-y1)^2 dans un tableau de correspondance de type [x,x^2].

Tiens-nous au courant de ton avancée, et de ce qui marche ou ne marche pas! Bon courage!

In Vino Veritas

C'est à peu près çà.

Avec 1000 particules, tu appelles 1000 fois miseAJour() qui doit ressembler à çà:

Code:

---

1 2 3 4 5

Pour chaque particule Calcul de la contribution de la particule Fin Pour Calcul du nouvel état de la particule

---

Evite au maximum de faire des new dans le Pour (le code à l'intérieur est appelé 1 million de fois pour chaque pas de temps), et éventuellement dans le reste de la méthode miseAJour().

Pour un programme graphique sur lequel j'ai travaillé (représentation en 3D de molécules), on était allé jusqu'à supprimer tous les new dans les méthodes utilisées pendant le dessin (quitte à passer par des attributs) pour éviter d'avoir des déclenchements de GC.

Elle est vraiment grosse ta méthode miseAJour() ? Si elle est raisonnable, tu peux toujours nous la montrer.

Bonjour,

je fais du jeu vidéo en Java, dont un actuellement (http://www.anadoncamille.com/) et j'aime les simulations de vie.

Donc je travaille régulièrement avec des milliers d'individus (cf LoveDrake dans AnAcondA). Là tu te retrouves avec un problème de gestion de voisinage, tu as un moteur de collisions à faire.

=====

Une optimisation qui te feras gagner du temps est le découpage par zones. Dans un extrême tu fais une zone comme avant et dans l'autre tu en fais plein de minuscules. Plus la zone type de ton découpage est petite, moins tu auras de voisins à traiter, mais plus tu auras de zones à calculer.

Tu dois étudier la case de la particules et ses voisines directes, pour éviter les effets de bords. Ces effets se manifestent quand deux particules voisines ne sont pas traitées comme voisines car sur deux zones différentes alors qu'elles devraient être traitées comme des voisines. C'est pourquoi dans le découpage par zone, tu traites chaque case et ses 8 voisines.

Chaque zone peut contenir x particules. Il te font donc dans chaque zone un vecteur "liste de particules" que tu tiens à jour pour tout déplacement.

Tu fais la liste des voisins de ta particule en ajoutant la liste des voisins de la case de ta particule, plus la liste des particules des 8 cases voisines.
Après tu fais tes calculs de distance et de répulsion sur cette liste réduite.

Voilà pour les zones.

=====

Pour les calculs, les tables de mémorisation f[x] = r sont les plus performantes.
Si ta fonction est bornée en entrée, c'est à dire que A <= x <= B, c'est idéal et tu peux choisir la taille de ton tableau, stocker les calculs et voir la différence. Peut être que cette optimisation t'épargnera la précédente.

Si ta fonction n'est pas bornée, c'est autre chose, peux-tu la segmenter, l'approximer dans certaines zones?

Bonne optimisation ! :king:

En repensant aux fonctions précalculable, je ne connais pas la forme de ta fonction, mais si elle est périodique, comme sin(a) tu peux faire quelque chose dans ce style : http://www.developpez.net/forums/sho...79#post2372879