Optimisation d’une opération de division et de conversion en virgule flottante

J’ai la formule suivante

float mean = (r+b+g)/3/255.0f;

Je veux accélérer les choses. Il y a les conditions préalables suivantes

 0<= mean <= 1 and 0 <= r,g,b <= 255 and r, g, b are unsigned chars

Donc, si j’essaie d’utiliser le fait que >> 8 est comme diviser par 256 et j’utilise quelque chose comme

 float mean = (float)(((r+b+g)/3) >> 8);

cela retournera toujours 0. Y a-t-il un moyen de sauter la coûteuse division float tout en obtenant une moyenne comprise entre 0 et 1?

Pré-convertissez vos divisions en une constante multiplicable:

 a / 3 / 255

est le même que

 a * (1 / (3 * 255))

alors pré-calcul:

 const float AVERAGE_SCALE_FACTOR = 1.f / (3.f * 255.f)

alors juste faire

 float mean = (r + g + b) * AVERAGE_SCALE_FACTOR;

puisque la multiplication est généralement beaucoup plus rapide que la division.

vous comparez évidemment la moyenne à autre chose, qui est également comprise entre 0 et 1. Et si vous multipliez simplement cette valeur par 255 à la place?

Permet de découvrir ce qu’un vrai compilateur fait réellement avec ce code, allons-nous? J’aime mingw gcc 4.3 (x86). J’ai utilisé “gcc test.c -O2 -S -c -Wall”

Cette fonction:

  float calc_mean (caractère non signé, caractère non signé, non signé b)
 {
     retour (r + b + g) /3/255.0f;
 }

génère ce code object (l’entrée de fonction et le code de sortie ont été supprimés pour plus de clarté. J’espère que les commentaires que j’ai ajoutés sont approximativement corrects):

  movzbl 12 (% ebp),% edx;  edx = g
  movzbl 8 (% ebp),% eax;  eax = r
  addl% eax,% edx;  edx = eax + edx
  movzbl 16 (% ebp),% eax;  eax = b
  addl% eax,% edx;  edx = eax + edx
  movl $ 1431655766,% eax; 
  imull% edx;  edx * = un const
  flds LC0;  mettre un const dans le reg virgule flottante
  pushl% edx;  mettre edx sur la stack
  fidivrl (% esp);  float reg / = haut de la stack

Considérant que cette fonction:

  float calc_mean2 (caractère non signé, caractère non signé, non signé b)
 {
     const float AVERAGE_SCALE_FACTOR = 1.f / (3.f * 255.f);
     return (r + b + g) * AVERAGE_SCALE_FACTOR;
 }

génère ceci:

  movzbl 12 (% ebp),% eax    
  movzbl 8 (% ebp),% edx
  addl% edx,% eax
  movzbl 16 (% ebp),% edx
  addl% edx,% eax
  flds LC2
  pushl% eax
  fimull (% esp)

Comme vous pouvez le constater, la deuxième fonction est meilleure. Comstackr avec -freciprocal-math convertit le fidivrl de la première fonction en un fimull, ce qui devrait être une amélioration. Mais la deuxième fonction est toujours meilleure.

Cependant, si vous considérez qu’un processeur de bureau moderne a quelque chose comme un pipeline à 18 étapes et qu’il est capable d’exécuter plusieurs de ces instructions par cycle, vous pouvez voir que les performances de ces fonctions seront dominées par des blocages dus à des dépendances de données. J’espère que votre programme a cet extrait de code en ligne et qu’il se déroule en boucle.

Considérer un si petit fragment de code isolé n’est pas idéal. C’est un peu comme conduire une voiture avec des jumelles collées à vos orbites. Zoom sur l’homme!

Comme l’a montré Andrew, la fonction d’origine n’est pas du tout optimisée. Le compilateur n’a pas pu, car vous divisiez d’abord la sum par un entier, puis par un float. Ce n’est pas la même chose que de multiplier par le facteur d’échelle moyen susmentionné. Si vous voulez changer (r + g + b) /3/255.0f en (r + g + b) /3.0f/255.0f, le compilateur pourrait l’optimiser pour utiliser fimull automatiquement.

Il est très courant d’optimiser de telles opérations pour une plate-forme, plutôt que sous la forme d’un algorithme ou en tant que portable C. Le blog Virtual Dub mérite d’être lu, car il fournit des conseils sur la manière de procéder dans les logiciels destinés aux architectures x86 et x64. entrées sur l’optimisation des moyennes de pixels 1 2 .