Comment accélérer la conversion de nombres flottants en nombres entiers?

Nous effectuons beaucoup de conversions de nombres entiers en virgule flottante dans notre projet. Fondamentalement, quelque chose comme ça

for(int i = 0; i < HUGE_NUMBER; i++) int_array[i] = float_array[i]; 

La fonction C par défaut qui effectue la conversion prend beaucoup de temps.

Existe-t-il un moyen de contourner le problème (peut-être une fonction réglée à la main) qui pourrait accélérer un peu le processus? Nous ne nous soucions pas beaucoup de la précision.

La plupart des autres réponses ici tentent simplement d’éliminer le temps système de la boucle.

Seule la réponse de deft_code permet de cerner le véritable problème, à savoir que convertir un nombre à virgule flottante en nombres entiers coûte extrêmement cher pour un processeur x86. La solution de deft_code est correcte, bien qu’il ne donne aucune citation ou explication.

Voici la source de l’astuce, avec quelques explications, ainsi que des versions spécifiques à votre choix d’arrondir vers le haut, le bas ou vers zéro: Connaissez votre FPU

Désolé de fournir un lien, mais tout ce qui est écrit ici, à moins de reproduire cet excellent article, ne va pas éclaircir les choses.

 inline int float2int( double d ) { union Cast { double d; long l; }; volatile Cast c; cd = d + 6755399441055744.0; return cl; } // this is the same thing but it's // not always optimizer safe inline int float2int( double d ) { d += 6755399441055744.0; return reinterpret_cast(d); } for(int i = 0; i < HUGE_NUMBER; i++) int_array[i] = float2int(float_array[i]); 

Le double paramètre n'est pas une erreur! Il y a moyen de faire cette astuce avec des flotteurs directement, mais ça devient laide d'essayer de couvrir tous les cas critiques. Sous sa forme actuelle, cette fonction arrondira le nombre entier le plus proche si vous souhaitez la troncature, utilisez plutôt 6755399441055743.5 (0,5 de moins).

J’ai effectué des tests sur différentes méthodes de conversion de float à int. La réponse courte est de supposer que votre client a des CPU compatibles SSE2 et de définir l’indicateur de compilation / arch: SSE2. Cela permettra au compilateur d’utiliser les instructions scalaires SSE, deux fois plus rapides que la technique des nombres magiques.

Sinon, si vous avez de longues chaînes de flotteurs à moudre, utilisez les options emballées SSE2.

Il y a une instruction FISTTP dans le jeu d’instructions SSE3 qui fait ce que vous voulez, mais quant à savoir si elle peut ou non être utilisée et produire des résultats plus rapides que libc, je n’en ai aucune idée.

Le temps est-il suffisamment long pour compenser le coût de démarrage de quelques tâches?

En supposant que vous disposiez d’un processeur multicœur ou de plusieurs processeurs, il s’agirait d’une tâche sortingviale à mettre en parallèle sur plusieurs threads.

La clé est d’éviter la fonction _ftol (), qui est inutilement lente. Votre meilleure option pour de longues listes de données telles que celle-ci consiste à utiliser l’instruction SSE2, cvtps2dq, pour convertir deux valeurs float emballées en deux unités int64 emballées. Faites-le deux fois (en obtenant quatre int64 sur deux registres SSE) et vous pouvez les mélanger pour obtenir quatre int32 (en perdant les 32 premiers bits de chaque résultat de conversion). Vous n’avez pas besoin d’assemblage pour faire cela; MSVC expose les éléments insortingnsèques du compilateur aux instructions appropriées – _mm_cvtpd_epi32 () si ma mémoire est fidèle .

Dans ce cas, il est très important que vos tableaux float et int soient alignés sur 16 octets afin que les éléments insortingnsèques de chargement / stockage SSE2 puissent fonctionner à une efficacité maximale. De plus, je vous recommande un peu de pipeline de logiciels et de traiter seize flottants à la fois dans chaque boucle, par exemple (en supposant que les “fonctions” ici sont en fait des appels aux insortingnsèques du compilateur):

 for(int i = 0; i < HUGE_NUMBER; i+=16) { //int_array[i] = float_array[i]; __m128 a = sse_load4(float_array+i+0); __m128 b = sse_load4(float_array+i+4); __m128 c = sse_load4(float_array+i+8); __m128 d = sse_load4(float_array+i+12); a = sse_convert4(a); b = sse_convert4(b); c = sse_convert4(c); d = sse_convert4(d); sse_write4(int_array+i+0, a); sse_write4(int_array+i+4, b); sse_write4(int_array+i+8, c); sse_write4(int_array+i+12, d); } 

La raison en est que les instructions SSE ont une longue latence. Par conséquent, si vous suivez immédiatement une charge dans xmm0 avec une opération dépendante sur xmm0, vous obtiendrez un décrochage. Avoir plusieurs registres "en vol" cache à la fois un peu la latence. (Théoriquement, un compilateur omniscient qui sait tout pourrait tout simplement contourner ce problème, mais ce n’est pas le cas en pratique.)

En cas d'échec de cette opération SSE juju, vous pouvez fournir l'option / QIfist à MSVC, ce qui l'amènera à émettre le poing d' opcode unique au lieu d'un appel à _ftol; cela signifie qu'il utilisera simplement le mode d'arrondi qui sera défini dans la CPU sans s'assurer qu'il s'agit de l'opération tronquée spécifique de ANSI C. Les documents Microsoft disent que / QIfist est déconseillé car leur code en virgule flottante est rapide, mais un désassembleur vous montrera que cela est inutilement optimiste. Même / fp: fast résulte simplement en un appel à _ftol_sse2, qui, bien que plus rapide que l'énorme _ftol, rest un appel de fonction suivi d'une opération SSE latente, et donc inutilement lent.

En passant, je suppose que vous êtes sur l'archive x86 - si vous êtes sur PPC, il existe des opérations VMX équivalentes, ou vous pouvez utiliser l'astuce multiplication-nombre-magique mentionnée ci-dessus suivie d'un vsel (pour masquer le bits non-mantisse) et un magasin aligné.

Vous pourrez peut-être charger tous les entiers dans le module SSE de votre processeur à l’aide d’un code d’assemblage magique, puis créer le code équivalent pour définir les valeurs sur ints, puis les lire en tant que flottants. Je ne suis pas sûr que ce serait plus rapide cependant. Je ne suis pas un gourou de l’ESS, donc je ne sais pas comment faire cela. Peut-être que quelqu’un d’autre peut intervenir.

Dans Visual C ++ 2008, le compilateur génère lui-même des appels SSE2. Si vous créez une version avec des options d’optimisation maximales et examinez un désassemblage (même si certaines conditions doivent être remplies, jouez avec votre code).

Consultez cet article d’Intel pour accélérer les conversions de nombres entiers:

http://software.intel.com/en-us/articles/latency-of-floating-point-to-integer-conversions/

Selon Microsoft, l’option de compilateur / QIfist est obsolète dans VS 2005, car la conversion d’entiers a été accélérée. Ils oublient de dire comment cela a été accéléré, mais consulter la liste de désassemblage pourrait donner un indice.

http://msdn.microsoft.com/en-us/library/z8dh4h17(vs.80).aspx

la plupart des compilateurs c génèrent des appels vers _ftol ou quelque chose de différent pour chaque conversion de float en int placer un commutateur de conformité à virgule flottante réduit (comme fp: fast) peut aider – SI vous comprenez ET acceptez les autres effets de ce commutateur. En dehors de cela, placez la chose dans un assemblage étroit ou dans une boucle insortingnsèque, si vous êtes ok et comprenez les différents comportements d’arrondi. pour les grandes boucles comme votre exemple, vous devez écrire une fonction qui configure les mots de contrôle à virgule flottante une fois, puis arrondit le volume avec uniquement des instructions fistp, puis réinitialise le mot de contrôle – SI vous êtes d’accord avec un chemin de code uniquement x86, mais au moins vous ne modifierez pas l’arrondi. lisez les instructions fld et fistp fpu et le mot de contrôle fpu.

Quel compilateur utilisez-vous? Dans les compilateurs C / C ++ les plus récents de Microsoft, il existe une option sous C / C ++ -> Génération de code -> Modèle en virgule flottante, qui comporte des options: rapide, précis, ssortingct. Je pense que la précision est la valeur par défaut et fonctionne en émulant les opérations de PF dans une certaine mesure. Si vous utilisez un compilateur MS, comment cette option est-elle définie? Cela aide-t-il à le régler sur “rapide”? Dans tous les cas, à quoi ressemble le déassembly?

Comme indiqué par trente-sept ci-dessus, le processeur peut convertir float<->int en une seule instruction, et il ne va pas plus vite que cela (à moins d’une opération SIMD).

Notez également que les processeurs modernes utilisent la même unité FP pour les numéros FP simples (32 bits) et doubles (64 bits). Ainsi, à moins que vous ne tentiez d’économiser de la mémoire en stockant beaucoup de flottants, il n’y a vraiment aucune raison de préférer le float aux doubles.

Sur Intel, votre meilleur choix est les appels en ligne SSE2.

Je suis surpris par votre résultat. Quel compilateur utilisez-vous? Êtes-vous en train de comstackr avec l’optimisation à fond? Avez-vous confirmé en utilisant valgrind et Kcachegrind que c’est là que se trouve le goulot d’étranglement? Quel processeur utilisez-vous? À quoi ressemble le code d’assemblage?

La conversion elle-même devrait être compilée en une seule instruction. Un compilateur qui optimise bien devrait dérouler la boucle afin que plusieurs conversions soient effectuées par test-and-branch. Si cela ne se produit pas, vous pouvez dérouler la boucle à la main :

 for(int i = 0; i < HUGE_NUMBER-3; i += 4) { int_array[i] = float_array[i]; int_array[i+1] = float_array[i+1]; int_array[i+2] = float_array[i+2]; int_array[i+3] = float_array[i+3]; } for(; i < HUGE_NUMBER; i++) int_array[i] = float_array[i]; 

Si votre compilateur est vraiment pathétique, vous devrez peut-être l'aider avec les sous-expressions courantes, par exemple,

 int *ip = int_array+i; float *fp = float_array+i; ip[0] = fp[0]; ip[1] = fp[1]; ip[2] = fp[2]; ip[3] = fp[3]; 

Faites un rapport avec plus d'informations!

Si vous ne vous souciez pas beaucoup de la sémantique d’arrondi, vous pouvez utiliser la fonction lrint() . Cela permet une plus grande liberté d’arrondi et peut être beaucoup plus rapide.

Techniquement, c’est une fonction C99, mais votre compilateur l’expose probablement en C ++. Un bon compilateur le liera également à une instruction (un testament G ++ moderne).

documentation de lrint

arrondir seulement excellent tour, seul l’utilisation 6755399441055743.5 (0.5 de moins) pour arrondir ne fonctionnera pas.

6755399441055744 = 2 ^ 52 + 2 ^ 51 décimales débordantes à la fin de la mantisse, en laissant le nombre entier souhaité dans les bits 51 à 0 du registre fpu.

Dans IEEE 754
6755399441055744.0 =

exposant signe mantisse
0 10000110011 1000000000000000000000000000000000000000000000000000

6755399441055743.5 comstackra toutefois également 010000110011100000000000000000000000000000000000000000000000

le 0,5 déborde de la fin (arrondi au-dessus), raison pour laquelle cela fonctionne en premier lieu.

pour effectuer la troncature, vous devez append 0,5 à votre double, puis les chiffres de garde doivent veiller à arrondir au résultat correct obtenu de cette façon. faites également attention à linux gcc 64 bits, où long signifie plutôt gênant un entier 64 bits.

Si vous avez des baies très volumineuses (plus de quelques Mo – taille du cache du processeur), chronométrez votre code et voyez quel est le débit. Vous êtes probablement en train de saturer le bus de mémoire, pas l’unité FP. Recherchez la bande passante théorique maximale de votre CPU et voyez si vous vous en approchez.

Si vous êtes limité par le bus de mémoire, des threads supplémentaires ne feront qu’empirer les choses. Vous avez besoin d’un meilleur matériel (mémoire plus rapide, processeur différent, carte mère différente).


En réponse au commentaire de Larry Gritz …

Vous avez raison: la FPU est un goulot d’étranglement majeur (et l’utilisation de l’astuce xs_CRoundToInt permet de très bien saturer le bus de la mémoire).

Voici quelques résultats de test pour un processeur Core 2 (Q6600). La bande passante théorique de la mémoire principale de cette machine est de 3,2 Go / s (les largeurs de bande L1 et L2 sont beaucoup plus élevées). Le code a été compilé avec Visual Studio 2008. Résultats similaires pour les optimisations 32 bits et 64 bits et avec / O2 ou / Ox.

  ÉCRIT UNIQUEMENT ...
   1866359 ticks avec 33554432 éléments de masortingce (33554432 touched).  Bande passante: 1.91793 Go / s
   154749 ticks avec 262144 éléments de masortingce (33554432 touched).  Bande passante: 23,1313 Go / s
   108816 ticks avec 8192 éléments de masortingce (33554432 touched).  Bande passante: 32.8954 Go / s

 UTILISER LE CASTING ...
   5236122 ticks avec 33554432 éléments de masortingce (33554432 touched).  Bande passante: 0.683625 Go / s
   2014309 ticks avec 262144 éléments de masortingce (33554432 touched).  Bande passante: 1.77706 Go / s
   1967345 ticks avec 8192 éléments de tableau (33554432 touched).  Bande passante: 1.81948 Go / s

 UTILISATION DE xs_CRoundToInt ...
   1490583 ticks avec 33554432 éléments de masortingce (33554432 touched).  Bande passante: 2.40144 Go / s
   1079530 ticks avec 262144 éléments de masortingce (33554432 touched).  Bande passante: 3.31584 Go / s
   1008407 ticks avec 8192 éléments de masortingce (33554432 touched).  Bande passante: 3.5497 Go / s 

(Code source Windows):

 // floatToIntTime.cpp : Defines the entry point for the console application. // #include  #include  using namespace std; double const _xs_doublemagic = double(6755399441055744.0); inline int xs_CRoundToInt(double val, double dmr=_xs_doublemagic) { val = val + dmr; return ((int*)&val)[0]; } static size_t const N = 256*1024*1024/sizeof(double); int I[N]; double F[N]; static size_t const L1CACHE = 128*1024/sizeof(double); static size_t const L2CACHE = 4*1024*1024/sizeof(double); static size_t const Sz[] = {N, L2CACHE/2, L1CACHE/2}; static size_t const NIter[] = {1, N/(L2CACHE/2), N/(L1CACHE/2)}; int main(int argc, char *argv[]) { __int64 freq; QueryPerformanceFrequency((LARGE_INTEGER*)&freq); cout << "WRITING ONLY..." << endl; for (int t=0; t<3; t++) { __int64 t0,t1; QueryPerformanceCounter((LARGE_INTEGER*)&t0); size_t const niter = NIter[t]; size_t const sz = Sz[t]; for (size_t i=0; i