Pourquoi sol () est-il si lent?

J’ai récemment écrit du code (ISO / ANSI C) et j’ai été surpris de la médiocre performance obtenue. En bref, il s’est avéré que le coupable était la fonction floor() . Non seulement c’était lent, mais cela ne s’est pas vectorisé (avec le compilateur Intel, alias ICL).

Voici quelques points de repère pour la réalisation de l’étage pour toutes les cellules d’une masortingce 2D:

 VC: 0.10 ICL: 0.20 

Comparez cela à un casting simple:

 VC: 0.04 ICL: 0.04 

Comment floor() peut floor() être plus lent qu’un simple casting?! Il fait essentiellement la même chose (sauf pour les nombres négatifs). 2ème question: Est-ce que quelqu’un est au courant d’une implémentation ultra-rapide de floor() ?

PS: Voici la boucle que je faisais le benchmarking:

 void Floor(float *matA, int *intA, const int height, const int width, const int width_aligned) { float *rowA=NULL; int *intRowA=NULL; int row, col; for(row=0 ; row<height ; ++row){ rowA = matA + row*width_aligned; intRowA = intA + row*width_aligned; #pragma ivdep for(col=0 ; col<width; ++col){ /*intRowA[col] = floor(rowA[col]);*/ intRowA[col] = (int)(rowA[col]); } } } 

Un certain nombre de choses rendent le sol plus lent qu’une dissortingbution et empêche la vectorisation.

Le plus important:

floor peut modifier l’état global. Si vous transmettez une valeur trop énorme pour être représentée sous la forme d’un entier au format float, la variable errno est définie sur EDOM . Une manipulation spéciale pour NaN est également effectuée. Tout ce comportement concerne les applications qui souhaitent détecter le dépassement de capacité et gérer la situation d’une manière ou d’une autre (ne me demandez pas comment).

La détection de ces conditions problématiques n’est pas simple et représente plus de 90% du temps d’exécution du sol. L’arrondi réel est peu coûteux et pourrait être en ligne / vectorisé. En outre, il y a beaucoup de code, donc intégrer la totalité de la fonction de sol rendrait votre programme plus lent.

Certains compilateurs ont des drapeaux spéciaux qui permettent au compilateur d’optimiser certaines des règles rarement utilisées de la norme c. Par exemple, on peut dire à GCC que errno ne vous intéresse pas du tout. Pour ce faire, passez -fno-math-errno ou -ffast-math . ICC et VC peuvent avoir des drapeaux de compilation similaires.

Btw – Vous pouvez lancer votre propre fonction de plancher en utilisant des moulages simples. Vous devez simplement gérer les cas négatifs et positifs différemment. Cela peut être beaucoup plus rapide si vous n’avez pas besoin du traitement spécial des débordements et des NaN.

Si vous allez convertir le résultat de l’opération floor() en un entier, et si vous ne craignez pas de débordement, le code suivant est beaucoup plus rapide que (int)floor(x) :

 inline int int_floor(double x) { int i = (int)x; /* truncate */ return i - ( i > x ); /* convert trunc to floor */ } 

Plancher et plafond sans twigments (mieux utiliser la pipiline) sans vérification d’erreur

 int f(double x) { return (int) x - (x < (int) x); // as dgobbi above, needs less than for floor } int c(double x) { return (int) x + (x > (int) x); } 

ou en utilisant le sol

 int c(double x) { return -(f(-x)); } 

L’implémentation la plus rapide pour un grand tableau sur les processeurs x86 modernes serait

  • changez le mode d’arrondi MXCSR FP pour arrondir vers -Infinity (aka floor ) . En C, cela devrait être possible avec fenv , ou _mm_getcsr / _mm_setcsr .
  • boucle sur le tableau en faisant _mm_cvtps_epi32 sur les vecteurs SIMD, en convertissant 4 float s en entier 32 bits en utilisant le mode d’arrondi en cours. (Et stocker les vecteurs de résultat à la destination.)

    cvtps2dq xmm0, [rdi] est une cvtps2dq xmm0, [rdi] micro-fusionnée sur n’importe quel processeur Intel ou AMD depuis K10 ou Core 2. ( https://agner.org/optimize/ ) Idem pour la version AVX 256 bits, avec vecteurs YMM.

  • rétablit le mode d’arrondi actuel sur le mode par défaut IEEE normal, en utilisant la valeur d’origine du MXCSR. (arrondi au plus proche, avec même comme tie-break)

Cela permet de charger + convertir + de stocker 1 vecteur SIMD de résultats par cycle d’horloge, aussi rapidement qu’avec la troncature . (SSE2 a une instruction spéciale de conversion FP-> int pour la troncature, justement parce que les compilateurs le demandent très souvent. Dans l’ancien temps avec x87, même (int)x nécessitait de changer le mode d’arrondi x87 en troncature, puis en arrière. cvttps2dq pour emballé float-> int avec troncature (notez le t supplémentaire dans la mnémonique) ou pour scalaire, en passant de XMM aux registres entiers, cvttss2si ou cvttsd2si pour scalaire double en scalaire entier.

Avec un certain déroulement des boucles et / ou une bonne optimisation, ceci devrait être possible sans goulot d’étranglement au niveau du front-end, juste un débit de magasin par horloge en supposant qu’il n’y ait pas de goulots d’étranglement en mémoire cache. (Et sur Intel avant Skylake, également goulot d’étranglement sur un débit de conversion compacté par horloge.) Soit 16, 32 ou 64 octets par cycle, en utilisant SSE2, AVX ou AVX512.


Sans changer le mode d’arrondi actuel, vous avez besoin d’ roundps SSE4.1 pour arrondir un float au nombre entier le plus proche en utilisant votre choix de modes d’arrondi. Vous pouvez également utiliser l’une des astuces présentées dans d’autres réponses qui s’appliquent aux flottants de magnitude suffisamment petite pour tenir dans un entier signé de 32 bits, car c’est de toute façon le format de destination ultime.)


(Avec les bonnes options du compilateur, telles que -fno-math-errno , et les bonnes options -march ou -msse4 , les compilateurs peuvent utiliser des roundps , ou l’équivalent scalaire et / ou double précision, par exemple roundsd xmm1, xmm0, 1 , mais cela coûte 2 uops et a une cadence d’horloge sur 2 pour Haswell en scalaire ou en vecteurs. En fait, gcc8.2 enchaîne roundsd pour le floor même sans aucune option de calcul rapide, comme vous pouvez le constater sur l’explorateur du compilateur Godbolt . with -march=haswell . Ce n’est malheureusement pas la base pour x86-64, vous devez donc l’activer si votre ordinateur le supporte.)

Oui, floor() est extrêmement lent sur toutes les plateformes car il doit mettre en œuvre de nombreux comportements à partir de la spécification IEEE fp. Vous ne pouvez pas vraiment l’utiliser dans les boucles intérieures.

J’utilise parfois une macro pour approcher floor ():

 #define PSEUDO_FLOOR( V ) ((V) >= 0 ? (int)(V) : (int)((V) - 1)) 

Il ne se comporte pas exactement comme floor() : par exemple, floor(-1) == -1 mais PSEUDO_FLOOR(-1) == -2 , mais il est suffisamment proche pour la plupart des utilisations.

Une version réellement sans twigs qui nécessite une seule conversion entre les domaines à virgule flottante et les domaines entiers décalerait la valeur x vers toutes les plages positives ou toutes négatives, puis la décalerait / tronquerait et la décalerait vers l’arrière.

 long fast_floor(double x) { const unsigned long offset = ~(ULONG_MAX >> 1); return (long)((unsigned long)(x + offset) - offset); } long fast_ceil(double x) { const unsigned long offset = ~(ULONG_MAX >> 1); return (long)((unsigned long)(x - offset) + offset ); } 

Comme indiqué dans les commentaires, cette implémentation repose sur la valeur temporaire x +- offset ne débordant pas.

Sur les plates-formes 64 bits, le code d’origine utilisant la valeur intermédiaire int64_t se traduira par un kernel à trois instructions, identique à celui disponible pour la plage int32_t à plage réduite plancher / ceil, où |x| < 0x40000000 |x| < 0x40000000 -

 inline int floor_x64(double x) { return (int)((int64_t)(x + 0x80000000UL) - 0x80000000LL); } inline int floor_x86_reduced_range(double x) { return (int)(x + 0x40000000) - 0x40000000; } 
  1. Ils ne font pas la même chose. floor () est une fonction. Par conséquent, son utilisation entraîne un appel de fonction, l’allocation d’un cadre de stack, la copie des parameters et la récupération du résultat. Casting n’est pas un appel de fonction, il utilise donc des mécanismes plus rapides (je pense qu’il peut utiliser des registres pour traiter les valeurs).
  2. Floor () est probablement déjà optimisé.
  3. Pouvez-vous tirer davantage de performances de votre algorithme? Peut-être que changer de ligne et de colonne peut aider? Pouvez-vous mettre en cache des valeurs communes? Toutes les optimisations de votre compilateur sont-elles activées? Pouvez-vous changer de système d’exploitation? un compilateur? La programmation de Pearls de Jon Bentley propose une excellente synthèse des optimisations possibles.

Double tour rapide

 double round(double x) { return double((x>=0.5)?(int(x)+1):int(x)); } 

Journal de terminal

test custom_1 8.3837

test native_1 18.4989

test custom_2 8.36333

test native_2 18.5001

test custom_3 8.37316

test native_3 18.5012


Tester

 void test(char* name, double (*f)(double)) { int it = std::numeric_limits::max(); clock_t begin = clock(); for(int i=0; i 

Résultat

Taper et utiliser votre cerveau est environ 3 fois plus rapide que d'utiliser des fonctions natives.