Multithreading sur calcul lourd : augmentation de performance décevante.

Version imprimable

27/05/2009, 15h40
pleasereset

Multithreading sur calcul lourd : augmentation de performance décevante.

Bonjour à tous,

Loin d'être expert en C# (junior en labo de recherche au japon :zoubi:), je conçoit et développe actuellement une application de reconnaissance de forme 3D (cylindres) à partir d'un nuage de points.
Comme vous vous doutez, la phase de calcul est lourde, et pour raccourcir le temps de traitement je me suis évidemment tourné vers le multithreading.

L'approche qui me semblait la plus efficace est : séparer la charge de travail en deux (ou plus suivant le nombre de cpu), et lancer un thread calcul lourd pour chaque "part de boulot".
Le thread 'maman' :mouarf: attends patiemment que les calculs soient terminés, collecte et synthétise les résultats.

Mon souci est le suivant : alors qu'en mono-thread, j'utilise sans défaillir 50% du CPU, avec deux threads, j'utilise seulement 70/85% du CPU... ce qui m'épate, vu qu'il a de quoi s'occuper.

Trace Windows 1 Thread (thread de calcul en rouge) :
http://img43.imageshack.us/img43/6336/trace1cpu.png

Trace Windows 2 Threads (threads de calcul en rouge et bleu) :
http://img41.imageshack.us/img41/5485/trace2cpu.png

Aucune synchro entre les deux threads, donc pas d'attente mutuelle "explicite". L'objet à traiter est crée dans le thread "maman", et donc partagé entre les deux threads, mais ils utilisent différentes zones de cet objet (imaginer une matrice, chaque thread traite 50% de la matrice).

De fait, je constate un ralentissement du temps de traitement moyen d'une "unité" de travail (chaque thread accomplissant 60 unités de travail) :
- 1 thread : 134ms par unité de travail, 15,2s pour le total
- 2 threads : 212ms par unité de travail, 13s pour le total

Je sollicite donc vos cerveaux experts 8-) pour me dire que faire pour augmenter les performances de mon application !

(Tout refaire en C++ n'est pas une option, j'ai choisi C# car j'ai des délais de développement serrés ;))
27/05/2009, 15h52
emmr.rida

Tout refaire?! Non, biensure. Mais seulement les parties les plus critiques du calcul.
27/05/2009, 16h06
theMonz31

faire du multithread veut pas forcement dire augmenter les performances au final... sauf si le truc va tourner sur plusieurs Core..

Parallel extension pourrait te tenter (fais une recherche)...

sinon, ya surement moyen d'optimiser ton code :)
27/05/2009, 16h32
pleasereset

Il y'a en effet sûrement moyen d'optimiser mon code et mon algorithme de travail, et j'y planche, j'y planche... ;)

Cependant, ce qui me chiffonne pour l'instant c'est le fait de ne pas saturer les CPU avec deux threads, alors que je sature un CPU avec un thread.

En effet mon application est vouée à tourner sur des machines dual/quad core dont je veux utiliser le potentiel au maximum.

Est-il possible d'utiliser Parallel Extensions sous .NET 3.5 ?

Je viens de faire une série de tests qui m'étonne, sur un Core 2 Duo 2.5Ghz, sous Windows 7 :

- 1 thread : 1 unit de calcul en 132ms moyenne, 120 units traitées en 14.9s
- 2 threads : 219ms / 13.4s
- 3 threads : 239ms / 10s (et j'approche 99% d'utilisation cpu, pourtant, il n'y a aucune attente IO ou autre dans mon thread de calcul)
- 4 threads : 323ms / 10.8s
- 5 threads : 368ms / 9.7s
- 6 threads : 413ms / 10.2s

L'augmentation du temps de traitement d'une unité de calcul m'étonne lors du passage 1 à 2 threads (ayant deux cores, elle devrait rester sensiblement équivalente), mais surtout, lors du passage à 3 threads, elle évolue peu... alors que théoriquement je n'ai pas assez de CPU pour mener 3 threads à bien.
28/05/2009, 14h39
Mac LAK

Un processeur multicœurs n'est PAS un système multi-CPU, contrairement à ce que l'on pourrait penser... Notamment, tu n'as qu'un seul bus mémoire !

Ce qui fait que si tes deux threads, même correctement répartis sur les cœurs (réglage de l'affinité), cherchent à taper dans la mémoire en même temps, et bien l'un des deux attendra que l'autre aie fini. D'où ton pourcentage d'utilisation CPU non-optimal, alors qu'il l'est avec 3 threads, en fait (N+1) threads, N étant le nombre de coeurs.

Une fois les données chargées et/ou en cache et/ou les threads synchronisés "de force" entre eux, tu te retrouves à priori avec un thread occupé à charger, et deux qui bossent, avec un "cycle" entre les threads.

Si tu veux optimiser plus lourdement ton calcul, il faudra peut-être repenser ton algo : par exemple, avoir un thread "serveur" qui s'occupe de récupérer les données en RAM, et qui alimente les threads de calcul avec des données suffisamment courtes pour tenir à coup sûr dans le cache.

En attendant, sur le type de calcul que tu sembles faire, un si faible gain indique sans nul doute que les transferts mémoire sont trop coûteux par rapport au temps de calcul... Tu n'as gagné "que" 33% de temps total, alors que la phase de calcul "pure" devrait avoir gagné 50% au bas mot. La différence, c'est le chargement / stockage des données, le transfert mémoire donc.
Tu peux toutefois continuer à accélérer en prenant comme base (N+1) threads par rapport au nombre de cœurs, ce sera toujours mieux que rien, mais arriver à (1/N) du temps "monothread" impose à mon avis de repenser ta parallélisation...
28/05/2009, 15h00
pleasereset

Merci beaucoup pour ta réponse claire et concise qui éclaire ma lanterne !

Une question de pure curiosité, sur un CPU comme l'AMD Phenom ou l'Intel Core i7, intégrant le controleur mémoire au CPU, le problème se pose toujours ? (Y'a t'il toujours un seul bus mémoire par CPU ou un bus par core ?)

En effet tu as vu très clair dans mon application, l'exécution d'une unité de données suppose la lecture de beaucoup de données (par exemple, l'estimation de la normale d'une surface en un point dans un nuage de points suppose la lecture des points environnants... à la louche, au minimum 256Ko de données (donc trop pour le L1 d'un core).

L'approche thread RAM et thread de calcul semble intéressante... si j'arrive à réduire le volume de données à traiter à moins de 64Ko si je comprends bien, et si la séléction des données pour arriver à ces 64Ko n'est pas trop couteuse.

Dur dur !
29/05/2009, 10h04
Mac LAK

Citation:

Envoyé par pleasereset

Merci beaucoup pour ta réponse claire et concise qui éclaire ma lanterne !

De rien ! :mouarf:

Citation:

Envoyé par pleasereset

Une question de pure curiosité, sur un CPU comme l'AMD Phenom ou l'Intel Core i7, intégrant le controleur mémoire au CPU, le problème se pose toujours ? (Y'a t'il toujours un seul bus mémoire par CPU ou un bus par core ?)

Multicœurs = un seul bus mémoire... Le contrôleur ne sert qu'à améliorer la gestion du problème que j'ai décrit, mais c'est tout.

Citation:

Envoyé par pleasereset

En effet tu as vu très clair dans mon application, l'exécution d'une unité de données suppose la lecture de beaucoup de données (par exemple, l'estimation de la normale d'une surface en un point dans un nuage de points suppose la lecture des points environnants... à la louche, au minimum 256Ko de données (donc trop pour le L1 d'un core).

Ce n'était pas dur de "voir" le souci, en fait : c'est un grand classique, qui est devenu encore plus classique depuis la démocratisation intensive des CPU à plusieurs cœurs.
N'oublie pas quelque chose de TRÈS important : dans BEAUCOUP de cas, l'optimisation d'un algo parallèle passe par une "simple" ... réorganisation des données !!!

Exemple typique : un calcul matriciel... Suivant ce que tu fais (calcul sur lignes ou calculs sur colonnes), les performances ne sont pas du tout les mêmes : dans l'un des cas, tu lis des données séquentielles en mémoire (=> tu peux profiter des lectures en burst depuis la RAM), dans l'autre elles sont séparées par des dizaines / centaines / milliers d'octets les unes des autres (=> bonjour le bronx côté optimisation, surtout si les données sont inférieures à la taille du mot-machine et/ou non alignées...).

Ce qui fait que pour optimiser lourdement un calcul matriciel, il est parfois nécessaire... de dupliquer les données ! Avec une version de la matrice "normale", et l'autre "transposée". Bien sûr, cela n'est efficace que si la matrice est souvent lue et peu souvent écrite.

Bref, comme tu le vois, la solution n'est pas forcément triviale, et, désolé de te l'apprendre, faut aussi parfois mettre les mains dans la tripaille, et savoir comment sont réellement rangées les données, pour pouvoir l'optimiser.

Les langages managés (C#, Java) ou interprétés peuvent être efficaces sur certains types de parallélisme, notamment le clustering, ou tout calcul parallèle où l'acquisition des données est coûteuse par rapport au calcul (ex : transfert par Internet, acquisition depuis un médium "lent", etc.).
Mais pour le calcul lourd, avec plusieurs CPU / cœurs, il est POSSIBLE que ta solution passe impérativement par du C / C++.

Rassures-toi, en C#, c'est facile à incorporer, cf. l'aide de "DllImport" sur MSDN.

Citation:

Envoyé par pleasereset

L'approche thread RAM et thread de calcul semble intéressante... si j'arrive à réduire le volume de données à traiter à moins de 64Ko si je comprends bien, et si la séléction des données pour arriver à ces 64Ko n'est pas trop couteuse.

Certes, il vaut mieux connaître la taille du cache L1, et pouvoir tenir dedans... Toutefois, même si tu mords sur le cache L2, cela n'a pas beaucoup d'importance... Le cache L2 est "lent" par rapport au L1, mais par rapport à de la RAM, c'est monstrueusement plus rapide, vu qu'il n'y a pas de problèmes de multiplexage du bus.

Commence déjà par analyser la dispersion en mémoire de tes éléments, ainsi que leur alignement. N'oublie pas : pour lire un octet en RAM, tu en lis TOUJOURS au minimum quatre, le mot-mémoire complet... Mais tu n'en utilises qu'un seul, ce qui est une perte de temps lourde si jamais tu as des invalidations de cache qui se goupillent mal.
29/05/2009, 10h42
alavoler

Ce post est prodigieusement intéressant

Merci à Mac LAK d'avoir su apporter ses connaissances et de les avoir expliquées avec simplicité
29/05/2009, 14h36
Zubrowka31

J'ai eu le même genre de problème, a savoir, calcul sur des millions d'enregistrement d'une BDD. Étant donné que les données n'était pas liées entre elles, chaque Thread "fils", instancie son propre objet pour le traitement évitant ainsi tout probleme de synchro entre les threads.

Citation:

Envoyé par pleasereset

L'objet à traiter est crée dans le thread "maman", et donc partagé entre les deux threads, mais ils utilisent différentes zones de cet objet

Peut être quand travaillant sur deux objet distinct et en fusionnant les deux deux objets apres ton join, tu pourrais grappiller un petit peu!

Sinon topic très intéressant!
29/05/2009, 17h46
Guulh

Le parallélisme, il faudra probablement qu'on s'y mette tous :) Mais vu que son exploitation efficace dépend de la gestion de la mémoire, et qu'elle est manuelle en C++ et automatisée en C#, je ne pense pas que les mêmes recettes puissent s'appliquer indifféremment. En tous, comme le soulignait theMonz, c'est un sujet sur lequel planche l'équipe .Net de Microsoft. cf ce blog, entre autres.
29/05/2009, 18h06
Mac LAK

Citation:

Envoyé par Guulh

Le parallélisme, il faudra probablement qu'on s'y mette tous :)

C'est déjà le cas : tu vois souvent des projets monothreads ET monoserveurs ET monoclients ? :D

Citation:

Envoyé par Guulh

Mais vu que son exploitation efficace dépend de la gestion de la mémoire, et qu'elle est manuelle en C++ et automatisée en C#, je ne pense pas que les mêmes recettes puissent s'appliquer indifféremment.

Faux. Son exploitation efficace dépend de l'algorithme à 90%, et si tu "penses" mal, le système fera au mieux avec les boulets que tu lui auras attaché aux pieds... C'est pour ça que simplement threader un algo "normal" en pensant le paralléliser améliore très souvent les performances, mais rarement dans les proportions que l'on espérait (cas précis et exact de l'OP...).

Citation:

Envoyé par Guulh

En tous, comme le soulignait theMonz, c'est un sujet sur lequel planche l'équipe .Net de Microsoft. cf ce blog, entre autres.

Ils peuvent plancher tant qu'ils veulent, ils ne pourront jamais prévoir l'infinité d'algorithmes parallèles possibles, sans même parler des tailles de données, des corrélations avec les caches, des optimisations dues au langage et/ou à l'organisation des données, etc.
Ils peuvent aider (un peu) sur des algos "bateau" assez récurrents... Pas sur tout.

La meilleure optimisation de programme parallèle, ça reste le jus de cerveau... Et ceci restera vrai jusqu'à l'avènement de l'IA "réelle", donc pas pour demain.
29/05/2009, 18h49
Guulh

Citation:

Envoyé par Mac LAK

C'est déjà le cas : tu vois souvent des projets monothreads ET monoserveurs ET monoclients ? :D

On joue sur les mots :) Avec .Net, le multithreading est souvent encapsulé dans des composants. BackGroundWorker dans les clients, threads qui se crée quand un client remoting se connecte à un serveur, etc. Et la seule chose à laquelle il faut faire gaffe, c'est de correctement locker les objets accédés depuis plusieurs threads.
Là, c'est pour des raisons de perf en milieu multi-core / multi-CPU uniquement que l'on devrait écrire son code d'une certaine façon plutôt que d'une autre. C'est ça, qui me semble nouveau.

Citation:

Envoyé par Mac LAK

Faux. Son exploitation efficace dépend de l'algorithme à 90%,

Certes oui ; mais gestion de la mémoire et algo ne sont-ils pas liés ? Etant donné le mode de création et d'allocation différent des objets, ce qui serait optimal dans un langage ne le serait pas dans l'autre, et comme tu l'as dit, au final, "il est POSSIBLE que ta solution passe impérativement par du C / C++."

Citation:

Envoyé par Mac LAK

Ils peuvent aider (un peu) sur des algos "bateau" assez récurrents... Pas sur tout.

C'est déjà vrai dans bien d'autres domaines, ça ! A mon avis, ce qui fait la force de .Net, c'est que ça facilite grandement 90% des tâches les plus courantes. Et vu que dans l'énorme majorité des projets, la maintenabilité prévaut largement sur la performance (bon peut être pas dans le cas de l'OP, certes)...
30/05/2009, 03h40
Mac LAK

Citation:

Envoyé par Guulh

On joue sur les mots :) Avec .Net, le multithreading est souvent encapsulé dans des composants. BackGroundWorker dans les clients, threads qui se crée quand un client remoting se connecte à un serveur, etc. Et la seule chose à laquelle il faut faire gaffe, c'est de correctement locker les objets accédés depuis plusieurs threads.

Mouais, bon, je n'appelle quand même pas des threads de connexion ou un thread de calcul "seul" (qui n'a pour seul but que d'empêcher un freeze de l'IHM) de la programmation parallèle...
Surtout que .NET n'a rien inventé à ce sujet : je t'encourage à aller voir du côté de Delphi, pour citer un des plus connus, où c'est comme ça depuis des années.

Citation:

Envoyé par Guulh

Là, c'est pour des raisons de perf en milieu multi-core / multi-CPU uniquement que l'on devrait écrire son code d'une certaine façon plutôt que d'une autre. C'est ça, qui me semble nouveau.

Pourtant, ça ne l'est pas. Comme je l'ai dit, c'est du grand classique... OK, je reconnais qu'avoir eu des cours intensifs de programmation parallèle aide à trouver ça "classique"... :mrgreen:

Citation:

Envoyé par Guulh

Certes oui ; mais gestion de la mémoire et algo ne sont-ils pas liés ? Etant donné le mode de création et d'allocation différent des objets, ce qui serait optimal dans un langage ne le serait pas dans l'autre, et comme tu l'as dit, au final, "il est POSSIBLE que ta solution passe impérativement par du C / C++."

Si tu cherches la performance pure, déjà, les langages managés sont une mauvaise idée, tout comme de façon générale ce qui simplifie un peu trop la vie (la STL en est un excellent exemple, c'est très facile de la mettre à genoux si l'on utilise du "lourd"...).
Ceci étant dit, un langage managé et/ou des objets / entités de haut niveau PEUVENT aider à mettre au point plus rapidement un algo, en évitant justement la tripaille interne qui est toujours longue à mettre au point.
Une fois l'algo "propre" et surtout, optimal, là tu peux remettre un coup de boost à ton programme en le faisant en natif et en collant le plus possible au matériel.

Mais passer direct en natif, en se contraignant en plus par rapport au hard, SANS avoir un algo parfaitement au point, c'est réellement un casse-gueule de première... L'algo d'abord, l'optimisation après. Dans le cas de l'OP, c'est manifestement l'algo qui pêche car il provoque un goulet d'étranglement au niveau de la mémoire (mauvaise séparation et/ou organisation des données).

Un objet, ça alloue la mémoire "automatiquement" si tu l'as bien voulu : t'as souvent (pour ne pas dire toujours) la possibilité d'aligner les données sur les mots-machine, c'est même souvent le cas par défaut. Ensuite, un objet, c'est une VMT, puis les données dans l'ordre de déclaration... T'as une légère surconsommation mémoire, plus une légère perte de temps à l'appel des méthodes si elles sont virtuelles, mais c'est tout. Côté accès aux données, c'est pareil qu'une structure.

Citation:

Envoyé par Guulh

C'est déjà vrai dans bien d'autres domaines, ça ! A mon avis, ce qui fait la force de .Net, c'est que ça facilite grandement 90% des tâches les plus courantes. Et vu que dans l'énorme majorité des projets, la maintenabilité prévaut largement sur la performance (bon peut être pas dans le cas de l'OP, certes)...

La force de .NET, c'est d'avoir Microsoft derrière... Côté puissance de dev, je suis désolé, mais ça ne vaut pas tripette par rapport à Visual C++ (gestion des versions Debug / Release pitoyable en C#, gestion des solutions et des dépendances nettement régressives par rapport à ce qui était devenu la "norme" en C++, etc.).
Côté puissance de l'API, je trouve Delphi largement supérieur, avec un langage bien plus fortement typé, une vitesse d'exécution bien supérieure et un système RAD dont Microsoft devrait sérieusement songer à s'inspirer.

Le seul point fort de .NET à mon sens, c'est qu'il supporte plusieurs langages / modes [web, natif, applets, ...] sur la même API de base, et qu'il donne accès à la quasi-totalité des fonctions de l'OS facilement. Mais sûrement pas quelques futures librairies d'aide au parallélisme qui ne seront "utiles" que pour des problèmes très simples, déjà maîtrisés depuis des années dans la plupart des langages natifs.

Pour le reste... On en est au framework 3.5, je crois, et pour l'instant je ne vois aucune raison, à titre personnel, pour passer sur .NET à la place de mon Delphi favori : y'a pas photo côté maintenabilité et rapidité de développement... Le seul gain de .NET, c'est qu'il faut reconnaître que WPF est nettement moins "usine à gaz" que les MFC pour le développement d'IHM, même si c'est au prix d'une vitesse d'exécution légèrement réduite.
30/05/2009, 05h39
Guulh

Citation:

Envoyé par Mac LAK

Surtout que .NET n'a rien inventé à ce sujet : je t'encourage à aller voir du côté de Delphi, pour citer un des plus connus, où c'est comme ça depuis des années.

Ah, mais je n'ai jamais rien pretendu de tel. Puis tant qu'a pinailler, Delphi est a peine plus vieux (1995 vs 2000)

Citation:

Envoyé par Mac LAK

Pourtant, ça ne l'est pas. Comme je l'ai dit, c'est du grand classique...

Dans les programmes de calcul, tel que celui de l'OP, je n'en doute pas, puisque c'est la perf qui prime ; mais pour les dev interne dans l'industrie ?

Citation:

Envoyé par Mac LAK

Si tu cherches la performance pure, déjà, les langages managés sont une mauvaise idée, tout comme de façon générale ce qui simplifie un peu trop la vie (la STL en est un excellent exemple, c'est très facile de la mettre à genoux si l'on utilise du "lourd"...).
Ceci étant dit, un langage managé et/ou des objets / entités de haut niveau PEUVENT aider à mettre au point plus rapidement un algo, en évitant justement la tripaille interne qui est toujours longue à mettre au point.
Une fois l'algo "propre" et surtout, optimal, là tu peux remettre un coup de boost à ton programme en le faisant en natif et en collant le plus possible au matériel.

Mais passer direct en natif, en se contraignant en plus par rapport au hard, SANS avoir un algo parfaitement au point, c'est réellement un casse-gueule de première... L'algo d'abord, l'optimisation après. Dans le cas de l'OP, c'est manifestement l'algo qui pêche car il provoque un goulet d'étranglement au niveau de la mémoire (mauvaise séparation et/ou organisation des données).

Un objet, ça alloue la mémoire "automatiquement" si tu l'as bien voulu : t'as souvent (pour ne pas dire toujours) la possibilité d'aligner les données sur les mots-machine, c'est même souvent le cas par défaut. Ensuite, un objet, c'est une VMT, puis les données dans l'ordre de déclaration... T'as une légère surconsommation mémoire, plus une légère perte de temps à l'appel des méthodes si elles sont virtuelles, mais c'est tout. Côté accès aux données, c'est pareil qu'une structure.

N'ayant aucune competence particulière en la matière, je me contente d'écouter religieusement :)

Citation:

Côté puissance de l'API, je trouve Delphi largement supérieur, avec un langage bien plus fortement typé, une vitesse d'exécution bien supérieure et un système RAD dont Microsoft devrait sérieusement songer à s'inspirer.

Independamment de .Net, je trouve que C# a une syntaxe simple et bien foutue. Probablement inspiree de Delphi, puisque ce cher Anders Hejslberg a quitte Borland pour le creer :) Et pour ce qui est de l'API, j'en sais rien. Elle satisfait les besoins de mesprojets, en tous cas.

Citation:

Mais sûrement pas quelques futures librairies d'aide au parallélisme qui ne seront "utiles" que pour des problèmes très simples, déjà maîtrisés depuis des années dans la plupart des langages natifs.

Mais peut être pas maitrisés par pleasereset. Et puisque l'OP bosse en C#, autant connaitre les outils par defaut deja proposes en standard, avant d'approfondir si besoin. Ce qui risque en effet d'etre necessaire dans le cas du parallelisme :aie: Je ne sais pas si c'est un domaine plus complexe que d'autres, qui se preterait moins bien a la création d'une API satisfaisant simplement 90% des cas.

Héhé beau débat ;)

Citation:

Mais passer direct en natif, en se contraignant en plus par rapport au hard, SANS avoir un algo parfaitement au point, c'est réellement un casse-gueule de première... L'algo d'abord, l'optimisation après. Dans le cas de l'OP, c'est manifestement l'algo qui pêche car il provoque un goulet d'étranglement
au niveau de la mémoire (mauvaise séparation et/ou organisation des données).

Voilà le pourquoi du comment je suis en C#. L'algo est un proto et je voulais me concentrer dessus, pouvoir avancer très vite, modifier de gros blocs rapidement, ce qui aurait été impossible en C++ (du moins pour moi), et tant pis si je dois y concéder 300% de vitesse.

(300% okay, 1000%, pas okay ;))

Pour le débat .Net over Delphi, j'ai rien à ajouter au sujet, je ne connais pas assez pour juger. Cependant c'est assez hors sujet car dans mon cas... j'ai choisi .Net car C# était dans mon panel de connaissances, et pas le temps d'apprendre un nouveau langage avant de me lancer (puis j'avais besoin d'une visualisation 3D à développer en deux temps trois mouvements, XNA était parfait pour ça).

Citation:

Et vu que dans l'énorme majorité des projets, la maintenabilité prévaut largement sur la performance (bon peut être pas dans le cas de l'OP, certes)...

C'est mon cas... du moins la maintenabilité à court terme, vu que je suis toujours en train d'inventer mon algo au fur et à mesure du développement (j'ai un plan, mais je ne sais pas en détail parmi mes options ce qui fonctionne et ne fonctionne pas... j'avance au pas à pas)

REVENONS A NOS MOUTONS :mouarf:

Donc si j'ai bien compris, pour multithreader efficace sur un multicore, il faut threader petit, le coup de séparer tout le boulot en deux créeant un goulot d'étranglement au niveau de la RAM.

La question qui me reste c'est, jusqu'où faut-il descendre ?

Question subsidiaire : je passe beaucoup de temps à parcourir des tableaux de cette classe :
Code:

1 2 3 4 5 6 7 8 9 public class Point { VertexPositionColor _data; PointCloud _cloud = null; Vector3 _normal = Vector3.Zero; bool CanVote = true; (...méthodes et accesseurs...) }
Passer en valuetype (struct point) aiderait à résorber le goulot d'etranglement mémoire qui m'arrive ? (en virant l'indirection à la lecture du tableau).

[Details : VertexPositionColor(valuetype) = 3 floats + 1 int, PointCloud = reference, Vector3(valuetype) = 3 floats]

30/05/2009, 11h26
davidkungfu

Pour moi les perfs sur .NET seront toujours inférieures à celles d'un langage comme Delphi 7 (le dernier basé sur l'API Win32 je crois) parce que en .NET tu lances une machine virtuelle qui te met une couche entre la machine et ton soft, le code compilé est executé par la machine virtuelle qui ensuite fait appel au langage machine.

Alors qu'en Delphi 7 ton programme est compilé en langage machine directement, sans intermédiaire, et là... oh...ça va vite :-)

Pour la question du ValueType, en feintant intelligement, la réponse est oui, on y gagne :)

J'ai optimisé un petit peu mon algo en suivant les préceptes du LAK :mouarf:, et j'obtiens du code du style :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Parallel.For(0, neighboors.Count, delegate(int i) { Point[] lpoints = neighboors[i].Points; Vector3[] lpointsCache = neighboors[i].PointsCache; PointDistance[] lpd = new PointDistance[lpoints.Length]; for (int k = 0; k < lpoints.Length; k++) { lpd[k].p = lpoints[k]; lpd[k].d = p.DistanceTo(lpointsCache[k]); } lock (pd) { lpd.CopyTo(pd, j); j += lpd.Length; } });
Je me demande si dans cet exemple, lPoints et lPointsCache (les tableaux complets) sont chargés en cache, ou bien il n'utilise que le pointeur et va taper à chaque fois loin pour accéder aux données ?

Je gagnerais à faire une copie locale du tableau ?

Note : je suis super content :D en utilisant TPL aux endroits critiques pour casser des boucles "ni trop grosses ni trop petites" (en volume mémoire à traiter) en threads et en ayant joué un peu avec la structure des données - merci LAK -, j'accroche les 5secondes de temps de calcul, 99% d'occupation (à comparer aux 13s du début de post).

Cependant, ce joli score n'est obtenu que sous Windows XP... sur ma machine Windows7, je reste coincé dans les 13 secondes... mais avec une occupation CPU autour de 40% :calim2:

01/06/2009, 03h32
Mac LAK

Allez, réponses en bloc, v'là le pavé... :D

Citation:

Envoyé par Guulh

Dans les programmes de calcul, tel que celui de l'OP, je n'en doute pas, puisque c'est la perf qui prime ; mais pour les dev interne dans l'industrie ?

Pareil... Voire pire : j'ai rarement fait autant de programmation parallèle qu'en secteur industriel ! :mrgreen:

Citation:

Envoyé par Guulh

Independamment de .Net, je trouve que C# a une syntaxe simple et bien foutue. Probablement inspiree de Delphi, puisque ce cher Anders Hejslberg a quitte Borland pour le creer :) Et pour ce qui est de l'API, j'en sais rien. Elle satisfait les besoins de mesprojets, en tous cas.

Je dirais juste qu'il n'est pas aussi strict / propre que Delphi, sûrement à cause du goût du C à l'intérieur. A titre strictement personnel, je trouve qu'il a les lourdeurs de Java, du C++, mais pas leurs avantages. Je peux me tromper, je n'ai pas assez travaillé avec pour le connaître aussi bien que d'autres langages. Toujours est-il qu'il ne m'attire pas plus que ça...

Citation:

Envoyé par Guulh

Mais peut être pas maitrisés par pleasereset. Et puisque l'OP bosse en C#, autant connaitre les outils par defaut deja proposes en standard, avant d'approfondir si besoin. Ce qui risque en effet d'etre necessaire dans le cas du parallelisme :aie: Je ne sais pas si c'est un domaine plus complexe que d'autres, qui se preterait moins bien a la création d'une API satisfaisant simplement 90% des cas.

Crois-moi sur parole si tu veux, mais les problèmes de programmation parallèle ont beau être "classiques", ils ne se résolvent pas pour autant grâce à une baguette magique et/ou une API... Ce serait comme prétendre que tout problème d'interblocage se résoud avec un mutex : certes, il en faudra... Mais l'existence d'une API de mutex ne suffira pas, ni de près, ni de loin, pour savoir où les mettre !
L'algo, toujours l'algo, y'a que ça de vrai... :twisted:

Citation:

Envoyé par pleasereset

Voilà le pourquoi du comment je suis en C#. L'algo est un proto et je voulais me concentrer dessus, pouvoir avancer très vite, modifier de gros blocs rapidement, ce qui aurait été impossible en C++ (du moins pour moi), et tant pis si je dois y concéder 300% de vitesse.

En ce sens, tu as eu raison, bien que d'autres langages auraient été tout aussi adaptés à cet "exercice" (Java, pour ne citer que lui).
Il est surtout crucial que tu gardes à l'esprit que C# est un bon outil de prototypage, mais qu'il ne te permettra pas d'obtenir des performances maximales. Tant que tu as ça en tête, tout va bien.

Citation:

Envoyé par pleasereset

Donc si j'ai bien compris, pour multithreader efficace sur un multicore, il faut threader petit, le coup de séparer tout le boulot en deux créeant un goulot d'étranglement au niveau de la RAM.

Oui, c'est effectivement un résumé du problème. Pas complètement exact, mais cela suffira pour aider à le résoudre.

Citation:

Envoyé par pleasereset

La question qui me reste c'est, jusqu'où faut-il descendre ?

C'est là qu'intervient la connaissance du matériel... Toutefois, tu peux déjà descendre "empiriquement" en testant des tailles de données par dichotomie afin de trouver un "optimal" à peu près correct.
Prends des puissances de deux : 1, 2, 4, 8, 16, ... jusqu'à 256 ko de données, essaie-les toutes, et voit quelle est la valeur qui semble apporter le meilleur gain.

Citation:

Envoyé par pleasereset

Question subsidiaire : je passe beaucoup de temps à parcourir des tableaux de cette classe :
<snip>
Passer en valuetype (struct point) aiderait à résorber le goulot d'etranglement mémoire qui m'arrive ? (en virant l'indirection à la lecture du tableau).

[Details : VertexPositionColor(valuetype) = 3 floats + 1 int, PointCloud = reference, Vector3(valuetype) = 3 floats]

Très certainement, parce que tes données à lire ne sont pas contigües en mémoire.
Or, la "base" d'une optimisation au niveau mémoire, c'est d'avoir les données qui sont corrélées les plus proches les unes des autres...
Il te faudrait peut-être revoir l'approche, et ne pas utiliser de classes mais plutôt des vecteurs de données... Quitte à avoir quelque par une classe "simple" qui permet de faire les jointures d'index, si c'est nécessaire.

Citation:

Envoyé par pleasereset

Je me demande si dans cet exemple, lPoints et lPointsCache (les tableaux complets) sont chargés en cache, ou bien il n'utilise que le pointeur et va taper à chaque fois loin pour accéder aux données ?

Impossible à savoir à priori, car tu ne connais pas la tripaille interne du langage... C'est là la "faille" majeure des langages managés.
C'est toutefois très peu probable, il ne doit certainement mettre en cache que le pointeur lui-même, et non pas les données pointées.

Citation:

Envoyé par pleasereset

Je gagnerais à faire une copie locale du tableau ?

Seule et unique réponse à apporter à cela : faut essayer ! :D
Cela étant dit, c'est probable, car tu vas alors forcer la lecture mémoire en question...

Citation:

Envoyé par pleasereset

Note : je suis super content :D en utilisant TPL aux endroits critiques pour casser des boucles "ni trop grosses ni trop petites" (en volume mémoire à traiter) en threads et en ayant joué un peu avec la structure des données - merci LAK -, j'accroche les 5secondes de temps de calcul, 99% d'occupation (à comparer aux 13s du début de post).

Bien !!! Y'a du progrès, là, c'est une bonne chose !

Citation:

Envoyé par pleasereset

Cependant, ce joli score n'est obtenu que sous Windows XP... sur ma machine Windows7, je reste coincé dans les 13 secondes... mais avec une occupation CPU autour de 40% :calim2:

Là, je pense que ton souci vient de l'affinité avec les processeurs, la gestion doit être différente sous Windows 7. Si tu n'utilises bien que deux threads, tu peux forcer le cœur sur lequel chacun s'exécute grâce à la commande d'affinité, et ce n'est pas non plus nuisible sur XP de le faire.
Si tu es à 3 threads de calcul, cela va devenir un peu plus complexe de gérer le truc, par contre...
Bien sûr, faut aussi "compter" le nombre de cœurs présents sur la machine et s'adapter en fonction, mais on en a déjà parlé. Je te conseille quand même vivement de chercher ce nombre en début de programme, de le mettre dans une variable globale et de faire ensuite en fonction de ce nombre pour lancer tes threads.

Voir MSDN pour plus de détails, ainsi que cette page qui t'aidera à utiliser l'API native si jamais l'autre ne convient pas.