Discussion :

[Aleph69]

À lire un peu la discussion : lire trente-six fois la même valeur dans un vecteur, le compilateur doit pouvoir l'optimiser, si on lui donne les bonnes hypothèses (pas de modification concurrente, chaque opération de lecture n'altère en rien le contenu), non ?

Sur un code manipulant peu de données comme celui-là, j'imagine que c'est possible mais je ne peux pas l'affirmer (on peut pas tester toutes les configurations possibles de compilation) donc je préfère faire le boulot (simple et rapide) moi-même en promouvant quelques scalaires. Sur un plus grand nombre de données, l'argument du temps d'accès constant en RAM pour une zone mémoire contigüe ne tient plus car l'ordre d'accès a directement un impact sur la réutilisation des caches (principe de localité).

[Aleph69]

D'accord sans problème. Mais pour le moment, j'ai pas vu de changement d'algo (mais j'ai lu en diagonal) et surtout pas vu de calcul de complexité algorithmique.

Dès le départ, une modification a été proposée pour réduire le nombre d'opérations. Et pour effectuer ce changement de manière explicite, j'ai besoin de détruire la structuration des données imposée par les conteneurs.

Ce que j'ai vu ressemble beaucoup à de la micro optimisation. Et quand on voit la remarque de CedricMocquillon comme quoi le code généré est identique et celle de dourouc05 sur le fait que le compilo fait déjà un gros boulot, ma remarque reste : tant qu'on ne prouve pas l'amélioration (que soit de façon théorique par un calcul de complexité ou pratique par des mesures), ce ne sont pas des améliorations, mais que de la théorie

Non, si tu testes une optimisation théorique avec un profileur ou tout autre chose dépendant de l'architecture, tu biaises de facto les résultats. Ce n'est pas parce que sur ta machine, avec ton compilateur et tes options de compilation, les optimisations sont faites automatiquement (même code assembleur qu'avec le codage manuel) que cela sera vrai en modifiant l'un de ces paramètres. Le test de CedricMocquillon n'est plus nécessairement vrai sur la machine de Gobelin88 (principe de reproductibilité de l'expérience violé) et en plus, dans ce cas particulier, l'implémentation est différente (non utilisation des cv:Vec3d).

[gbdivers]

Attend, on est bien d'accord qu'il s'agit simplement de restructuration du code, pas d'un changement d'algorithme. Ou alors montre moi les calculs de complexité pour prouver que tu gagnes quelques chose en terme de complexité algorithmique.

Et si ce n'est pas un changement de complexité algorithmique, alors ça doit être prouvé en pratique par des tests et profiling. Par exemple, ta "promotion" de variables, rien de dit que le compilateur ne fait déjà pas ce boulot (mise en cache ? en registre ?)

Bref, je suis d'accord avec toi que ce sont des améliorations que l'on peut proposer. Mais sans validation pratique par des tests, pour moi, ça n'a pas de valeur

[Aleph69]

Attend, on est bien d'accord qu'il s'agit simplement de restructuration du code, pas d'un changement d'algorithme. Ou alors montre moi les calculs de complexité pour prouver que tu gagnes quelques chose en terme de complexité algorithmique.

Je t'assure que l'algorithme a bien été modifié. C'est la deuxième partie du deuxième message de cette discussion. Je n'ai pas développé le calcul de complexité puisqu'il est trivial. J'ai simplement indiqué qu'on gagnait une opération à chaque fois.

Et si ce n'est pas un changement de complexité algorithmique, alors ça doit être prouvé en pratique par des tests et profiling.

La limite c'est que tu ne peux pas généraliser à partir de ta validation statistique. Si tu gagnes en rapidité, cela n'induit rien quant aux autres architectures/compilations. Idem si tu perds en rapidité. L'inférence est purement transductive : tu dois tout reprendre si tu changes les conditions de l'expérience. C'est d'ailleurs pour cette raison qu'il y a tant de recherches sur la transformation automatique de programme (génération de code optimisé en fonction de l'architecture à partir de tests statistiques).

Par exemple, ta "promotion" de variables, rien de dit que le compilateur ne fait déjà pas ce boulot (mise en cache ? en registre ?)

Effectivement, rien ne le dit. D'ailleurs, beaucoup sont capables de le faire dans les cas simples comme celui-ci. Je dis juste que lorsque c'est si simple et rapide à faire, je préfère le faire moi-même pour que mon optimisation soit la mieux portée possible sur d'autres couples (architecture, compilation). Je préfère miser sur ce que je sais faire plutôt que sur ce que je "crois" que "tout" compilateur "devrait" savoir faire.

[gobelin88]

Étant un peu intrigué j'ai tenté une comparaison entre deux codes (je n'ai pas vraiment pu mettre ton code puisque je n'ai pas les structures de données d'opencv et je n'ai pas réimplémenté la partie sur la normalisation de la box):

...

Après ce code d'exemple est relativement simple, il faudrait le templatiser pour qu'il puisse faire l'interpolation sur un ensemble de valeurs (c'est ton cas apparemment puisque tu utilises des cv::Vec3d). Mais au final je pense pas que ça fera une différence sur le code généré (à tester quand même).

Peut etre que dans mon cas le compilateur de visual que j'utilise n'a pas su faire la simplification arithmétique (peut etre pk j'utilise cv::Vec3d... je sais pas...)

En tout cas dans mon cas, le fait de supprimer explicitement 7*3 (j'ai des vecteurs) multiplications, constitue la meilleure optimisation effectuée.

[gobelin88]

@gobelin88
comment mesure tu les améliorations de performances ?
tu as mesuré les gains apportés par les différentes versions du code testé ?
tu as testé avec quel type de données ?

toutes les améliorations proposées ont un sens que si tu as mesuré une différence qui te semble suffisamment significative dans le contexte particulier de ton application. Imagine, si tu fais tes calculs sur des données dont le chargement prend 90% du temps, les améliorations proposées n'auront aucun impact.

Toujours faire du profiling pour optimiser du code

Seul le profiling te dira si tu as des problèmes de cache miss, d'allocation, d'accès, etc. Tout les conseils que l'on t'a donné ne sont que des optimisations théoriques tant que tu n'as pas testé leurs impacts réél. Dis autrement, ça ne sera des améliorations du code que lorsque tu auras prouvé que ce sont des améliorations et pas de la masturbation intellectuelle

J'utilise un timer précis de opencv pour mesurer une différence de temps .

Je n'ai pas d'autre outils à ma disposition pour faire du profiling, mais la solution précédente me semble viable.

[white_tentacle]

Je t'assure que l'algorithme a bien été modifié. C'est la deuxième partie du deuxième message de cette discussion. Je n'ai pas développé le calcul de complexité puisqu'il est trivial. J'ai simplement indiqué qu'on gagnait une opération à chaque fois.

En général, on n’appelle pas ce type d’optimisations modification de l’algorithme. C’est une optimisation purement calculatoire (factorisation), l’algorithme n’a pas changé d’un pouce. Ça ne veut pas dire qu’elle ne sert à rien (et il semble bien qu’elle serve !), mais ce n’est pas ce qu’on entend usuellement par modification de l’algorithme.

La limite c'est que tu ne peux pas généraliser à partir de ta validation statistique. Si tu gagnes en rapidité, cela n'induit rien quant aux autres architectures/compilations. Idem si tu perds en rapidité. L'inférence est purement transductive : tu dois tout reprendre si tu changes les conditions de l'expérience. C'est d'ailleurs pour cette raison qu'il y a tant de recherches sur la transformation automatique de programme (génération de code optimisé en fonction de l'architecture à partir de tests statistiques).

À ce niveau là, tu optimises forcément pour une archi et un compilateur donné. Quitte à user du préprocesseur si tu as des comportements différents.

Après, j’ai du mal à imaginer des cas ou tes modifications rendraient le code plus lent que l’original (saturation des registres ? je n’y crois pas trop…). Du coup, je ne peux difficilement te donner tort de les faire, tant que la lisibilité du code n’en pâtit pas .

edit : je n’avais pas fait gaffe, mais combien est sizeof(cv::vec3d) ? Parce que là, tu échanges des accès à un tableau (donc des calculs d’adresse) contre des copies d’objet, du coup, pas étonnant qu’on semble ne rien gagner sur ce point. Il faudrait peut-être plutôt utiliser des références peur les tmp, non ?

[gobelin88]

edit : je n’avais pas fait gaffe, mais combien est sizeof(cv::vec3d) ? Parce que là, tu échanges des accès à un tableau (donc des calculs d’adresse) contre des copies d’objet, du coup, pas étonnant qu’on semble ne rien gagner sur ce point. Il faudrait peut-être plutôt utiliser des références peur les tmp, non ?

Right

sizeof(cv::Vec3d)==24 --> references utiles pour les tmp

[Aleph69]

Bonjour white_tentacle,

En général, on n’appelle pas ce type d’optimisations modification de l’algorithme. C’est une optimisation purement calculatoire (factorisation), l’algorithme n’a pas changé d’un pouce. Ça ne veut pas dire qu’elle ne sert à rien (et il semble bien qu’elle serve !), mais ce n’est pas ce qu’on entend usuellement par modification de l’algorithme.

Je tellement surpris parce ce que tu affirmes que je me dis qu'on ne doit sûrement pas parler de la même chose. Pour être clair, remplacer les opérations écrites

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

a*(1-b)+c*b

par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

a+(c-a)*b

c'est bien changer d'algorithme. Outre le fait que la complexité temporelle soit réduite, la stabilité numérique est également améliorée. Il existe un exemple historique d'une modification aussi simple que celle-ci qui conduit à une stabilisation fondamentale du procédé d'orthonormalisation de Gram-Schmidt : en précision finie la perte d'orthogonalité est arbitrairement grande pour l'algorithme de Gram-Schmidt classique (CGS) tandis qu'elle est bornée pour l'algorithme de Gram-Schmidt modifié (MGS). Affirmer qu'on est en présence du même algorithme me paraît exagéré : en analyse numérique, personne ne le fait et on distingue bien les deux algorithmes. Pourtant, dans ce cas, même la complexité temporelle est la même : on a juste modifié l'ordre des opérations. Un algorithme est aussi défini par son comportement en précision finie (stabilité numérique).

EDIT : mais dans le cadre de discussion, réduire la complexité spatiale ou temporelle d'un algorithme suffit pour dire qu'on a changé d'algorithme. De même, améliorer la stabilité numérique d'un algorithme suffit pour dire qu'on a changé d'algorithme. Ce n'est d'ailleurs pas pour rien si on apprend aux étudiants à faire des calculs de complexité dans les cours d'algorithmique. En revanche, c'est dommage qu'on les fasse rarement analyser numériquement des algorithmes.

Du coup, je ne peux difficilement te donner tort de les faire, tant que la lisibilité du code n’en pâtit pas .

Effectivement, personne n'a parlé de la lisibilité du code; tu fais bien de le mentionner!

[Aleph69]

En tout cas dans mon cas, le fait de supprimer explicitement 7*3 (j'ai des vecteurs) multiplications, constitue la meilleure optimisation effectuée.

Super! Je suis content si j'ai pu t'aider!

[CedricMocquillon]

Ce qui n'était pas très clair (et que ne l'est pas encore pour moi) c'est ce que tu cherches à interpoler: généralement le but est de déterminer la valeur d'une fonction partiellement connues en certains point en un point inconnu. Généralement les points connus constituent une grille; dans le cas tri-linéaire, on se place dans le cas 3d, tu as donc besoin des points encadrant le point cherché et des valeurs de la fonction à interpoler sur ces 8 points.

A priori ta fonction est à valeurs dans R^3 ce qui créer un peu de confusion (avec les coordonnées de l'espace 3d); la plupart du temps c'est une fonction à valeurs dans R d'où le code que j'ai proposé et l'un des premiers d'Aleph69 à base de double et le fait qu'on ait pas pensé tout de suite aux références.

Après dans les quelques tests que j'avais effectué, visual n'arrivait pas à optimiser la partie proposée par Aleph69 (le gain d'une multiplication par interpolation linéaire).

Enfin pour ce qui est de la partie sur la complexité, tout dépend à quel niveau on se place: dans mon domaine, ce qui nous intéresse c'est la complexité en O() (on cherche principalement le comportement lorsque n tends vers l'infini) après il y a des domaines où on se bat sur la complexité "précise" de l'algo (il me semble dans ce cas qu'on utilise la notation o()) ce qui est le cas ici. C'est vrai que naturellement pour moi on change pas la complexité de l'algo car j'entends O mais si on parle de la complexité o y'a pas à discuter, le complexité est bien différente (et meilleure dans la solution proposée par Aleph)

[Aleph69]

Enfin pour ce qui est de la partie sur la complexité, tout dépend à quel niveau on se place: dans mon domaine, ce qui nous intéresse c'est la complexité en O() (on cherche principalement le comportement lorsque n tends vers l'infini) après il y a des domaines où on se bat sur la complexité "précise" de l'algo (il me semble dans ce cas qu'on utilise la notation o()) ce qui est le cas ici. C'est vrai que naturellement pour moi on change pas la complexité de l'algo car j'entends O mais si on parle de la complexité o y'a pas à discuter, le complexité est bien différente (et meilleure dans la solution proposée par Aleph)

Tu ne peux pas raisonner asymptotiquement dans ce cas précis car le nombre d'opérations est en O(1).

[CedricMocquillon]

Complètement d'accord mais je finis par être "formaté" (je ne me préoccupe que très rarement de la complexité en o() ). Dans tous les cas, en notation O() la complexité des deux algos est identique (en temps constant comme tu l'as indiqué : O(1) ) Mais différente en o() (sans parler des aspects de stabilité numérique)

[Aleph69]

Dans tous les cas, en notation O() la complexité des deux algos est identique (en temps constant comme tu l'as indiqué : O(1) ) Mais différente en o() (sans parler des aspects de stabilité numérique)

Cela n'a pas beaucoup de sens de raisonner ainsi car si l'une des deux constantes explose, la différence est notoire. C'est une erreur classique quand on manipule les notations de Landau de ne pas prendre en compte les constantes et cela a conduit à pas mal d'erreurs d'interprétation en recherche mathématique, en particulier sur les estimations d'erreur et de vitesse de convergence en analyse numérique, mais je ne vais pas entrer dans les détails car cela va devenir technique et pas forcément compréhensible pour le néophyte. Je peux toutefois te faire sentir les choses sur un exemple. Si on suit ton raisonnement, les deux algorithmes suivants ont la même complexité :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
double optimal_millionTimes(double x){return x*1e6;}
double naive_millionTimes(double x)
{return x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+x+...+x;} // ici, x apparaît 1 million de fois

Les deux algorithmes sont en O(1) mais le premier nécessite une opération flottante (multiplication) et sa constante vaut 1, tandis que l'autre en nécessite 1E6-1 (additions) et sa constante vaut 1E6-1.

[CedricMocquillon]

Pour revenir sur le problème de gobelin88, si ta fonction à interpoler est bien définie sur R^3 et à valeurs dans R^3 (et non pas à valeurs dans R), tu devrais regarder du côté des expressions template: lorsque tu fais un calcul (par exemple) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

cv::Vec3d c0 ( c00 + (c10-c00) * Md1 );

tu vas avoir des créations d'objets temporaires (à moins que cv n'implémente déjà les expressions template) ce qui risque d'être la partie la plus coûteuse de ta fonction.

[gobelin88]

Pour revenir sur le problème de gobelin88, si ta fonction à interpoler est bien définie sur R^3 et à valeurs dans R^3 (et non pas à valeurs dans R), tu devrais regarder du côté des expressions template: lorsque tu fais un calcul (par exemple) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

cv::Vec3d c0 ( c00 + (c10-c00) * Md1 );

tu vas avoir des créations d'objets temporaires (à moins que cv n'implémente déjà les expressions template) ce qui risque d'être la partie la plus coûteuse de ta fonction.

Je confirme que opencv utilise les expressions templates, j'ai regardé dans le code d' OpenCV:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
struct CV_EXPORTS Matx_AddOp {};
struct CV_EXPORTS Matx_SubOp {};
struct CV_EXPORTS Matx_ScaleOp {};
struct CV_EXPORTS Matx_MulOp {};
struct CV_EXPORTS Matx_MatMulOp {};
struct CV_EXPORTS Matx_TOp {};
 
template<typename _Tp, int m, int n> class CV_EXPORTS Matx
{
...

Vec est typedef de Matx ... OpenCV c genial

[white_tentacle]

Affirmer qu'on est en présence du même algorithme me paraît exagéré : en analyse numérique, personne ne le fait et on distingue bien les deux algorithmes. Pourtant, dans ce cas, même la complexité temporelle est la même : on a juste modifié l'ordre des opérations. Un algorithme est aussi défini par son comportement en précision finie (stabilité numérique).

Peut-être que je ne fais pas assez de numérique, ce qui explique ma vision. Mais tes arguments sont convaincants .

[Aleph69]

Peut-être que je ne fais pas assez de numérique, ce qui explique ma vision. Mais tes arguments sont convaincants .

Un grand merci pour ton honnêteté intellectuelle!

[Joel F]

Je confirme que opencv utilise les expressions templates.

Apres au vu de la manière dont il s'en servent, ils pourraient juste ne rien faire ca serait pareil

[Aleph69]

[HS]
Salut Joel,
je suis tombé sur un truc intéressant à propos des E.T. dernièrement, je me suis dit que cela pourrait t'intéresser. Dans le dernier NA Digest a été annoncée la publication d'une nouvelle bibliothèque de calcul, Blaze de son petit nom, qui, au vu des benchmarks, semble plutôt efficace :
http://code.google.com/p/blaze-lib/
L'article associé chez SIAM est assez intéressant mais je l'ai juste survolé :
http://blogs.fau.de/hager/files/2012...berger2012.pdf
Il y a quand même des choses qui me chiffonnent. Je compte refaire moi-même quelques tests de vérification; je les posterai dans le forum à cette occasion.
A noter qu'il il existe un second article dans IEEE mais je n'ai pas vu de preprint.
[/HS]