Pourquoi est-floor() si lent?

Si vous êtes en train de convertir le résultat de la floor() opération à un int, et si vous n'êtes pas inquiet au sujet de dépassement, alors 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 */
}

La réelle plus rapide de la mise en œuvre pour un grand tableau moderne sur les Processeurs x86 serait

• changer le MXCSR FP arrondissement mode d'arrondi vers -l'Infini (aka floor). En C, cela devrait être possible avec fenv des trucs, ou _mm_getcsr /_mm_setcsr.

• boucle sur le tableau faisant _mm_cvtps_epi32 sur SIMD vecteurs, la conversion de 4 floats d'entier de 32 bits en utilisant le mode d'arrondi courant. (Et à stocker le résultat des vecteurs de la destination.)

  cvtps2dq xmm0, [rdi] est un seul micro-fusion uop sur n'importe quel PROCESSEUR Intel ou AMD depuis K10 ou Core 2. (https://agner.org/optimize/) Même pour les 256 bits AVX version, avec YMM vecteurs.

• de rétablir le courant mode d'arrondi à la normale IEEE mode par défaut, à l'aide de la valeur d'origine de la MXCSR. (arrondi au plus proche, même avec un tie-break)

Ce qui permet de charger + conversion de + rangement 1 SIMD vecteur de résultats par cycle d'horloge, aussi vite qu'avec la troncature. (SSE2 a un FP->int instruction de conversion pour la troncation, précisément parce qu'il est très souvent nécessaire par les compilateurs C. Dans les mauvais jours avec x87, même (int)x nécessaire de changer le x87 mode d'arrondi de troncature et puis retour. cvttps2dq pour les paniers float->int avec la troncature (note de l'extra t dans le mnémonique). Ou pour les scalaires, passant de XMM entier registres, cvttss2si ou cvttsd2si scalaires double de scalaire entier.

Avec certains déroulement de la boucle et/ou de bons d'optimisation, cela devrait être possible sans les goulots d'étranglement sur le front-end, à seulement 1-par-horloge magasin de débit supposant l'absence de cache-miss goulets d'étranglement. (Et sur Intel avant de Skylake, également un goulot d'étranglement sur 1-par-horloge paniers de conversion de débit.) c'est à dire 16, 32, ou 64 octets par cycle, à l'aide de SSE2, AVX, ou AVX512.

---

Sans changer le mode d'arrondi courant, vous avez besoin SSE4.1 roundps pour arrondir un float à l'entier le plus proche float en utilisant votre choix de modes d'arrondi. Ou vous pouvez utiliser l'une des astuces de la des spectacles dans d'autres réponses que de travail pour des flotteurs avec de petites suffisamment d'ampleur pour s'adapter à un entier signé de 32 bits, puisque c'est votre ultime destination de toute façon.)

---

(Avec les bonnes options de compilation, comme -fno-math-errno, et le droit -march ou -msse4 options, les compilateurs peuvent inline floor à l'aide de roundps, ou le scalaire et/ou de double précision équivalente, par exemple roundsd xmm1, xmm0, 1, mais cela coûte 2 uops et dispose de 1 par 2 horloge débit sur Haswell scalaires ou des vecteurs. En fait, gcc8.2 sera inline roundsd pour floor même sans aucun fast-options de mathématiques, comme vous pouvez le voir sur la Godbolt compilateur explorer. Mais c'est avec -march=haswell. Ce n'est malheureusement pas de référence pour x86-64, de sorte que vous devez l'activer si votre ordinateur prend en charge.)

Un fait dépourvu de branches version qui nécessite une seule conversion entre virgule flottante entier et les domaines à un déplacement de la valeur x à tous positifs ou négatifs à la plage, fonte/truncate et déplacement de retour.

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 mise en œuvre se fonde sur la valeur temporaire x +- offset ne déborde pas.

Sur les plates-formes 64 bits, le code d'origine à l'aide de int64_t intermédiaire de la valeur de trois instructions du noyau, la même disposition pour int32_t réduction de l'éventail de plancher/plafond, 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;
}

Rapide à double tour

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

---

Terminal journal

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

Type coulée et l'utilisation de votre cerveau est environ 3 fois plus rapide que l'utilisation des fonctions natives.