Pourquoi sol () est-il si lent?

https://stackoverflow.com/questions/824118

05-07-2019
|

Question

J’ai récemment écrit du code (ISO / ANSI C) et j’ai été surpris de la piètre performance qu’il a obtenue. En bref, il est apparu que le coupable était la floor() fonction. Non seulement cela a été lent, mais cela n’a pas été vectorisé (avec le compilateur Intel, alias ICL).

Voici quelques points de repère pour la réalisation d'un plancher pour toutes les cellules d'une matrice 2D:

VC:  0.10
ICL: 0.20

Comparez cela à une distribution simple:

VC:  0.04
ICL: 0.04

Comment <=> peut-il être aussi lent qu'une simple distribution?! 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 <=>?

PS: Voici la boucle que je comparais:

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]);
        }
    }
}

La solution

Plusieurs facteurs rendent le sol plus lent qu’une distribution et empêchent la vectorisation.

Le plus important:

floor peut modifier l'état global. Si vous transmettez une valeur trop importante 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ébordement 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 floor rendrait votre programme plus lent.

Certains compilateurs ont des drapeaux spéciaux qui permettent au compilateur d’optimiser certaines règles rarement utilisées de la norme c. Par exemple, GCC peut être informé 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 créer votre propre fonction de sol à l'aide de 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.

Autres conseils

Si vous allez convertir le résultat de l'opération floor() en un entier, et que le dépassement de capacité ne vous inquiète pas, 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 branchements (mieux utiliser le pipeline) 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));
}

La mise en oeuvre la plus rapide pour un grand tableau sur des processeurs x86 modernes serait

changez le mode d'arrondi de la MXCSR FP en arrondi vers -Infinity (ou floor) . En C, cela devrait être possible avec fenv substance ou _mm_getcsr / _mm_setcsr.
effectue une boucle sur le tableau en effectuant _mm_cvtps_epi32 sur des 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 dans la destination.)

cvtps2dq xmm0, [rdi] est un micro-fusionné sur n'importe quel processeur Intel ou AMD depuis K10 ou Core 2. ( https://agner.org/optimize/ ) Même chose pour le mode 256 bits Version AVX, 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 égalité)

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 - & Gt; 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 pour un flottant compacté - > int avec troncation (remarque: extra cvttps2dq dans le mnémonique). Ou pour scalaire, allant de XMM à des registres entiers, t ou cvttss2si pour scalaire cvttsd2si en entier scalaire.

Avec un certain déroulement des boucles et / ou une bonne optimisation, cela devrait être possible sans goulot d'étranglement au niveau du front-end, seulement un débit de stockage de 1 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 une cadence de conversion pleine par horloge.) Par exemple, 16, 32 ou 64 octets par cycle, avec SSE2, AVX ou AVX512.

Sans changer le mode d'arrondi actuel, vous avez besoin de SSE4.1 double pour arrondir un roundps à l'entier le plus proche -fno-math-errno en utilisant le choix du mode 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 votre format de destination ultime de toute façon.)

(Avec les bonnes options du compilateur, telles que -march et les bonnes -msse4 ou roundsd xmm1, xmm0, 1 options, les compilateurs peuvent utiliser roundsd en ligne avec -march=haswell ou l'équivalent scalaire et / ou double précision, par exemple <=>, mais cela coûte 2 uops et a un débit d'horloge sur Haswell pour les scalaires ou les vecteurs. En fait, gcc8.2 entrera en ligne <=> pour <=> même sans option de calcul rapide, comme vous pouvez le constater sur l'explorateur du compilateur Godbolt . Mais c'est avec <=>. 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 implémenter 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(-1) == -1: par exemple, PSEUDO_FLOOR(-1) == -2 mais <=>, mais il est suffisamment proche pour la plupart des utilisations.

Une version réellement sans branches qui nécessite une conversion unique entre les domaines de nombre à virgule flottante et de nombre entier décalerait la valeur x vers toutes les plages positives ou toutes négatives, puis lirait / tronquerait et la décalerait de nouveau.

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 non débordante.

Sur les plates-formes 64 bits, le code d'origine utilisant une valeur intermédiaire int64_t se traduira par un noyau à trois instructions, identique à celui disponible pour int32_t, plage réduite / étage, où |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;
}

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 pile, la copie des paramètres et la récupération du résultat. Le 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).
Probablement floor () est déjà optimisé.
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? Le programme Perles de programmation de Jon Bentley propose un excellent aperçu des optimisations possibles. / li>

Double tour rapide

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

Journal du 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

Test

void test(char* name, double (*f)(double))
{
    int it = std::numeric_limits<int>::max();

    clock_t begin = clock();

    for(int i=0; i<it; i++)
    {
        f(double(i)/1000.0);
    }
    clock_t end = clock();

    cout << "test " << name << " " << double(end - begin) / CLOCKS_PER_SEC << endl;

}

int main(int argc, char **argv)
{

    test("custom_1",round);
    test("native_1",std::round);
    test("custom_2",round);
    test("native_2",std::round);
    test("custom_3",round);
    test("native_3",std::round);
    return 0;
}

Résultat

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

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow