Rapide de multiplication/division par 2 pour des flotteurs et des doubles (C/C++)

Dans le logiciel, je suis en train d'écrire, je suis en train de faire des millions de multiplication ou de division par 2 (ou puissances de 2) de mes valeurs. J'aimerais vraiment que ces valeurs int pour que je puisse accéder à la bitshift opérateurs

int a = 1;
int b = a<<24

Cependant, je ne peux pas, et je dois coller avec du double.

Ma question est : comme il y a une représentation standard des doubles (signe, exposant mantisse), est-il un moyen de jouer avec l'exposant pour obtenir rapidement des multiplications/divisions par une puissance de 2?

Je peut même supposer que le nombre de bits va être fixe (le logiciel fonctionne sur les ordinateurs qui ont toujours 64 bits de long double)

P. S : Et oui, l'algorithme surtout n'ces opérations. C'est le goulot d'étranglement (c'est déjà multithread).

Edit : Ou suis-je totalement dans l'erreur et intelligent compilateurs déjà d'optimiser les choses pour moi?

Des résultats temporaires (avec Qt pour mesurer le temps, overkill, mais je n'ai pas de soins):

#include <QtCore/QCoreApplication>
#include <QtCore/QElapsedTimer>
#include <QtCore/QDebug>

#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);

while(true)
{
    QElapsedTimer timer;
    timer.start();

    int n=100000000;
    volatile double d=12.4;
    volatile double D;
    for(unsigned int i=0; i<n; ++i)
    {
        //D = d*32;      //200 ms
        //D = d*(1<<5);  //200 ms
        D = ldexp (d,5); //6000 ms
    }

    qDebug() << "The operation took" << timer.elapsed() << "milliseconds";
}

return a.exec();
}

Pistes suggèrent que D = d*(1<<5); et D = d*32; exécuter dans le même temps (200 ms) alors que D = ldexp (d,5); est beaucoup plus lent (6000 ms). Je savoir que c'est un micro de référence, et que tout à coup, ma RAM a explosé parce que Chrome a soudainement demandé de calcul de Pi dans mon dos chaque fois que je lance ldexp(), donc ce test ne vaut rien. Mais je vais le garder quand même.

Sur l'autre, je vais avoir du mal à faire reinterpret_cast<uint64_t *> parce qu'il y a un const violation (qui semble être le volatile mot-clé interfère)

Ne présumez pas que c'est le goulot d'étranglement juste parce que c'est multithread. Nous avons eu une application multithread que nous avons trouvé était un goulot d'étranglement dans de nombreux endroits différents de ce que nous attendions? Comment exactement avez-vous profiler?
Comme toujours, l'application n'est pas profilé assez. Je veux dire, j'ai utilisé CacheGrind, et il semble que je passe la plupart de mon temps dans une fonction qui effectue principalement des multiplications. Il semble. Mais j'ai écrit que c'était le goulot d'étranglement parce que je suis plus intéressé par les idées théoriques derrière la multiplication par 2 que dans "la petite considérations" (bien sûr, je pourrais optimiser mes requêtes SQL, mais honnêtement, je suis assez sûr que ça va être vide de sens, comparativement à la multiplication des trucs, et, surtout, je n'aime pas ^^)
Rappelez-vous, 1<<5 est une constante, de sorte que le compilateur va optimiser d*32.
Ouais, je "sais" ^^ Mais il y a eu des discussions sur la façon de camoufler le compilateur avec des trucs bizarres (en gros, certaines opérations se résument à *32 mais le compilateur ne veut pas "voir" c'). Et il y a juste une ligne =)
En général, l'accès à la mémoire et les requêtes SQL sont beaucoup beaucoup plus lent alors des choses comme des multiplications en C++. Je suis désolé de dire cela, mais de "petite considérations" est peut-être précisément ce que sont la cause de votre goulot d'étranglement.
Que puis-je dire d'autre que : I used CacheGrind, and it seems I spend most of my time in a function that does mostly multiplications? Oui, bien sûr, la fonction rend également plus, et de répartir des données sur la pile, mais je pense avoir une bonne estimation de la situation.
1) Votre boucle besoins de dérouler. 2) CacheGrind dit que vous êtes pour la plupart dans des calculs de routine? C'est une alarme! En une seule étape le code à l'assemblée, le niveau de langue et assurez-vous qu'il fait rien de plus que ce que vous attendiez. Il ne devrait pas être l'appel de quoi que ce soit. 3) le Multi-threading n'est pas de rendre le code plus rapide. Il a juste étend sur plus de processeurs, au mieux. 4) Si le rendement est ce que vous aimez, apprendre cette technique.

InformationsquelleAutor Fezvez | 2011-10-11

c c++division multiplication optimization

8

Vous pouvez supposer IEEE 754 mise en forme, les détails de ce qui peut être assez gnarley (esp. lorsque vous arrivez dans subnormals). Dans la plupart des cas, cependant, cela devrait fonctionner:
```
const int DOUBLE_EXP_SHIFT = 52;
const unsigned long long DOUBLE_MANT_MASK = (1ull << DOUBLE_EXP_SHIFT) - 1ull;
const unsigned long long DOUBLE_EXP_MASK = ((1ull << 63) - 1) & ~DOUBLE_MANT_MASK; 
void unsafe_shl(double* d, int shift) { 
    unsigned long long* i = (unsigned long long*)d; 
    if ((*i & DOUBLE_EXP_MASK) && ((*i & DOUBLE_EXP_MASK) != DOUBLE_EXP_MASK)) { 
        *i += (unsigned long long)shift << DOUBLE_EXP_SHIFT; 
    } else if (*i) {
        *d *= (1 << shift);
    }
} 
```
EDIT: Après avoir fait un certain timing, cette méthode est étrangement plus lent que le double de la méthode sur mon compilateur et de la machine, même dépouillé au minimum le code exécuté:
```
    double ds[0x1000];
    for (int i = 0; i != 0x1000; i++)
        ds[i] = 1.2;

    clock_t t = clock();

    for (int j = 0; j != 1000000; j++)
        for (int i = 0; i != 0x1000; i++)
#if DOUBLE_SHIFT
            ds[i] *= 1 << 4;
#else
            ((unsigned int*)&ds[i])[1] += 4 << 20;
#endif

    clock_t e = clock();

    printf("%g\n", (float)(e - t) / CLOCKS_PER_SEC);
```
Dans le DOUBLE_SHIFT complète de 1,6 secondes, avec une boucle interne de
```
movupd xmm0,xmmword ptr [ecx]  
lea    ecx,[ecx+10h]  
mulpd  xmm0,xmm1  
movupd xmmword ptr [ecx-10h],xmm0
```
Par rapport à 2,4 secondes, autrement, avec une boucle interne de:
```
add dword ptr [ecx],400000h
lea ecx, [ecx+8]  
```
Vraiment inattendue!

EDIT 2: Mystère résolu! L'un des changements pour VC11 est maintenant toujours vectorizes virgule flottante boucles, obligeant /arch:SSE2, si VC10, même avec /arch:SSE2 est encore pire avec la version 3.0 secondes avec une boucle interne de:
```
movsd xmm1,mmword ptr [esp+eax*8+38h]  
mulsd xmm1,xmm0  
movsd mmword ptr [esp+eax*8+38h],xmm1  
inc   eax
```
VC10 sans /arch:SSE2 (même avec /arch:ESS) est de 5,3 secondes... au 1/100e de la itérations!!, boucle intérieure:
```
fld         qword ptr [esp+eax*8+38h]  
inc         eax  
fmul        st,st(1)  
fstp        qword ptr [esp+eax*8+30h]
```
Je savais que le x87 FP pile a été vraiment mauvais, mais 500 fois pire, c'est un peu ridicule. Vous n'aurez probablement pas voir ces sortes de la vitesse de la conversion, c'est à dire la matrice de la fpo à l'ESS ou l'int des hacks, puisque c'est le pire des cas de chargement dans le FP de la pile, faire une op, et le stockage, mais c'est un bon exemple de pourquoi x87 est pas la voie à suivre pour n'importe quoi perf. liés à.
- Je vais essayer de voir si c'est efficace!
- D'une certaine manière, je ne pense pas qu'une branche conditionnelle sera plus rapide de le faire simplement un FP de se multiplier.
- J'ai tendance à être d'accord, mais on peut toujours être surpris (bien, j'aimerais être surpris!)
- Ma compréhension est que la virgule flottante est assez lent sur x86 - avoir au moins une des valeurs dans la FP de la pile et de nouveau est. Peu importe, c'est comment le faire si vous voulez éviter la FP pile dans la (très) cas le plus courant.
- Notez que l'utilisation de la plaine de vieux multiplier a permis le compilateur à vectoriser de la boucle, c'est le traitement de deux doubles à la fois. C'est probablement pourquoi il court plus vite et que ce soit une leçon pour tous ceux qui passent de cette façon! 😉
- Cher monsieur, vous avez fait le test qui prouve ce que je voulais savoir (microbenchmark, je sais, mais c'est assez bon pour moi). Merci!
- Pourtant, je suis surpris de voir que le bon vieux add est de 50% plus lent que mulpd, j'ai même essayé de 64bit ajouter en cas de 32bit lire, 64bit étape a été de confondre le prefetcher, c'est toujours à peu près la même vitesse!
- C'est deux addls c'est 50% plus lent qu'un mulpd, si - et rappelez-vous que vous utilisez un entier unité d'exécution pour la variable de boucle incrément de trop, de sorte que certains de la prestation vient d'utiliser une autre unité d'exécution.
- Je suppose que je suis juste utilisé pour les FP être 20x plus lent que l'intégrale 🙂
- x87 FP ne devrait pas être que lente. Peut-être il y a une instruction MMX, quelque part, sans un emms? Re: la vitesse de l'int add vs vecteur SSE2: La boucle va être un goulot d'étranglement en magasin-port de débit. C'est pourquoi d'exploitation sur 16B à un temps gagne. Vous pourriez faire un int ajouter avec l'ESS. paddq ou paddd (peut fonctionner sur port1/port5, 1 cycle de latence, de 0,5 c recip débit)
InformationsquelleAutor Simon Buchan
19

C'est un de ces très spécifique de l'application des choses. Il peut aider dans certains cas et pas dans d'autres. (Dans la grande majorité des cas, une simple multiplication est encore mieux.)

La "intuitive" façon de faire c'est juste pour extraire les bits d'un entier de 64 bits et ajouter la valeur de décalage directement dans l'exposant. (cela fonctionne aussi longtemps que vous n'avez pas touché NAN ou INF)

Donc quelque chose comme ceci:
```
union{
    uint64 i;
    double f;
};

f = 123.;
i += 0x0010000000000000ull;

// Check for zero. And if it matters, denormals as well.
```
Noter que ce code n'est pas C-conforme en quelque sorte, et est indiqué seulement pour illustrer l'idée. Toute tentative de mettre en œuvre ce qui devrait être fait directement à l'assemblée ou intrinsèques SSE.

Cependant, dans plus cas, les frais généraux de déplacer les données de la FP de l'unité à l'entier de l'unité (et de retour) va coûter beaucoup plus que de simplement faire une multiplication d'emblée. C'est particulièrement le cas pour les pré-ESS époque où la valeur doit être stockée de la FPU x87 en mémoire et puis lisez en entier registres.

Dans l'ESS ère, l'Entier de l'ESS et de la FP de l'ESS utiliser le même ISA registres (s'ils ont encore de registre distinct des fichiers). Selon le Agner Brouillard, il y a de 1 à 2 cycle de pénalité pour déplacer des données entre l'Entier de l'ESS et de la FP de l'ESS des unités d'exécution. De sorte que le coût est beaucoup mieux que le x87 époque, mais il est toujours là.

Tout-en-tout, cela dépendra de ce que vous avez sur votre pipeline. Mais dans la plupart des cas, multipliant sera encore plus rapide. J'ai exécuté ce exactement le même problème avant, donc je parle en expérience de première main.

Maintenant avec 256-bit AVX instructions qui prennent uniquement en charge instructions de FP, il y a encore moins d'une incitation à jouer des tours comme ça.
- Aussi, vérifiez pour 0s (et subnormals, plus généralement). Je dois mentionner, si vous êtes en traitement par lot des choses, il est susceptible d'être dans la mémoire principale, dès le début, donc c'est déjà stupide lent.
- Buchan: j'étais juste sur le point d'ajouter que. Bonne prise pour le souligné.
- Re "cela fonctionnera aussi longtemps que ...": il n'est pas garanti pour fonctionner. peut travail pour une application donnée, mais la norme stipule explicitement que cette (paramètre un type d'union et à l'aide d'un type différent pour le lire) n'est pas obligatoire. Pas downvote pour celui-ci puisque nous sommes déjà dans l'optimisation/non-standard des comportements sécuritaires par les regards de celui-ci.
- Correct. Nous sommes déjà au-delà de la norme. J'ai jeté cet exemple juste pour démontrer l'idée. Il est plus pratique de faire à l'aide des registres SSE.
- Il fonctionne lorsque vous savez que la machine de la représentation à virgule flottante. Tant que vous savez ce ne sera pas exécuté sur VAXs (peut-être que certains anciens des mainframes IBM trop), vous savez que sera la norme IEEE 754.
- vous avez réellement, à savoir la représentation de la double et l'entier (il y a piège de représentations et d'autres choses admises par le standard). Vous devez également savoir que votre compilateur ne présumez pas que vous êtes en suivant les règles de l'écriture d'un élément comme un type et en les lisant comme un autre. Cependant, comme déjà indiqué (avec éloquence par Mystique), nous sommes probablement au-delà de la conformité 🙂 Voir stackoverflow.com/questions/7687082/... pour les normes des sections portant sur de ce.
- Wow, merci! Cependant, ermmm, l'ESS? Streaming SIMD Extensions? ISA? Société Internationale d'Arboriculture? FP? Ce sont les trois acronymes que j'ai besoin de plus pour comprendre ton post =)
- ESS = Streaming SIMD Extensions, ISA = Instruction Set Architecture), FP = virgule Flottante, AVX = Advanced Vector Extensions
- Bien sûr, l'aliasing règles, en particulier, sont une douleur, je suis juste contre le peu commun idée que c'est quelque chose d'immoral d'utiliser du code non portable (évidemment où il fait sens).
- D'accord, @Simon, et c'est probablement le sens ici, c'est pourquoi je n'ai pas downvote. Personnellement, bien que je n'en ai ni la preuve dur pour ni l'énergie de le regarder en ce moment :-), je soupçonne aucune optimisation ici sera une perte de temps puisque le compilateur ne serait probablement faire un meilleur travail. Mais, à condition de mesure les suggestions, celui-ci est aussi bon que les autres et au moins il donne des avertissements et des options. Je vais donc +1 pour celle-ci.
- Pourquoi est-ce code pas en C conforme à la réglementation? Je pensais que les syndicats sont l'un des moyens sûrs pour manipuler des valeurs qui alias la même adresse mémoire?
- Je suppose que vous voulez dire que double n'est pas garanti d'être en 64 bits IEEE 754 en C?
- C'était en fait plus à propos de céder à la pression des pairs pour les personnes qui n'avaient aucune idée que le type d'union-beaucoup les jeux de mots est autorisé en C99. Mais la norme IEEE 754 partie s'applique toujours.
InformationsquelleAutor Mysticial
8

Comment sur ldexp?

Une demi-décent compilateur va générer un code optimal sur votre plate-forme.

Mais comme @Clinton points, il vous suffit de l'écrire dans les "évident" devrait faire aussi bien. La multiplication et la division par puissances de deux, c'est un jeu d'enfant pour un compilateur moderne.

Directement munging la représentation à virgule flottante, en plus d'être non-portable, sera presque certainement pas plus vite (et qui risque d'être plus lent).

Et bien sûr, vous ne devriez pas perdre de temps à penser à propos de cette question, à moins que votre outil de profilage vous dit de vous. Mais le genre de personnes qui écoutent ce conseil ne sera jamais en avoir besoin, et ceux qui en ont besoin, il ne sera jamais de l'écouter.

[mise à jour]

OK, alors j'ai essayé ldexp avec g++ 4.5.2. Le cmath en-tête inlines comme un appel à __builtin_ldexp, qui à son tour...

...émet un appel à la libm ldexp fonction. J'aurais pensé que ce builtin serait trivial à optimiser, mais je suppose que les développeurs de GCC n'a jamais eu autour d'elle.

Donc, en multipliant par 1 << p est probablement votre meilleur pari, que vous avez découvert.
- VC fait de même pour la plupart des opérations en virgule flottante - je crois qu'il est de sorte qu'il peut respecter le contrôle de la précision (_control87(), _controlfp(), etc...). Essayez de changer la précision en virgule flottante commutateurs de compilateur...
- ldexp est 6 fois plus lent que le x*pow(2,exp) source: étalonnés sur intel Xeon
InformationsquelleAutor Nemo
5

Le moyen le plus rapide de le faire est probablement:
```
x *= (1 << p);
```
Ce genre de chose qui peut simplement être fait par l'appel d'une instruction machine pour ajouter p à l'exposant. Dire que le compilateur au lieu d'extraire les quelques morceaux avec un masque et de faire quelque chose à la main sera probablement rendre les choses plus lentement, pas plus rapide.

Rappelez-vous, C/C++ n'est pas le langage d'assemblage. À l'aide d'un bitshift l'exploitant n'a pas nécessairement de la compilation d'un bitshift de montage d'opération, ne pas utiliser de multiplication nécessairement compiler à la multiplication. Il y a toutes sortes d'étranges et merveilleux passe des choses comme ce que les registres sont utilisés et à quelles instructions peuvent être exécutées simultanément dont je ne suis pas assez intelligent pour le comprendre. Mais votre compilateur, avec beaucoup de l'homme des années de connaissances et d'expérience et beaucoup de puissance de calcul, est beaucoup mieux à faire de ces jugements.

p.s. Gardez à l'esprit, si votre double sont dans un tableau ou une autre plate structure de données, votre compilateur peut être vraiment intelligents et de l'utilisation de l'ESS à des multiples de 2, voire 4 doubles en même temps. Cependant, en faisant beaucoup de décalage de bits va probablement confondre votre compilateur et de prévenir ce type d'optimisation.
- Je ne suis pas au courant de toute l'architecture avec une "instruction machine pour ajouter p à l'exposant". Mais peut-être qu'il devrait l'être.
- href="https://www.felixcloutier.com/x86/fscale" >x87 fscale exactement ce que fait, mais seulement pour un double d'entrée, pas entier. Il ne x * (1<<trunc(y)), ou x_exponent += trunc(y). Il n'est pas rapide mais: beaucoup plus lent que fmul, à l'instar de 20 à 32 cycles d'horloge classique P5 Pentium vs 3 cycles pour un fmul, et il n'est pas beaucoup mieux sur moderne x86. (agner.org/optimize). Donc fmul avec une constante de 0.5 est bien mieux.
- Mais comme cela et Mysticial la réponse de pointe, moderne SIMD Isa utilisent généralement les mêmes registres pour les FP et vecteur d'entier. Il est possible d'utiliser une instruction de la forme paddd xmm0, xmm1 pour un entier ajouter sur FP modèles de bits entre les instructions comme mulps xmm0, xmm2. Bien sûr, cela ne veut pas gérer le cas où l'exposant sort de la plage, où FP multiplier serait de vous donner l'infini, ou de corriger dépassement de capacité d'un subnormale. (Ou conditionnement de la désinformation-exposant de 0 (subnormale) à tous ceux (NaN ou l'infini selon significande.)
InformationsquelleAutor Clinton
1

Ce que d'autres opérations n'cet algorithme requiert? Vous pourriez être en mesure de briser votre flotte en int paires (//signe de la mantisse et de l'ampleur), faites de votre traitement, et de les reconstituer à la fin.
- Euh, eh bien, je fais un peu de trucs ici et là (multiplication de matrice, etc...) je suppose que cela pourrait être une bonne idée, mais je pense que ça va être une charge de travail (redéfinir +, -, *, ...)
InformationsquelleAutor Thom Smith
1

En multipliant par 2 peut être remplacé par un plus: x *= 2 est équivalent à x += x.

Division par 2 peut être remplacée par une multiplication par 0.5. La Multiplication est généralement beaucoup plus rapide que la division.
- C'est totalement vrai, mais il devient untractable dès que je veux faire quelque chose comme x *= 33554432
- que la multiplication est susceptible d'être effectuée par l'unité de virgule flottante plus rapide que n'importe quel d'optimisation que vous pouvez venir avec.
- Eh bien, c'est juste l'ajout de 25 à l'exposant, donc je pense qu'il y a un sens derrière mon interrogatoires =)
- ne sous-estimez pas la vitesse de la moderne multiplier instruction. Si vous doutez de moi, de mesurer et de voir.
- Je veux dire, le but de ce post est de vérifier s'il existe un moyen plus rapide de faire quelque genre très spécifique de multiplications. Je ne dis pas qu'il existe un moyen plus rapide, mais je trouve ça légitime de se demander.
InformationsquelleAutor Mark Ransom
1

Bien qu'il y a peu/pas d'intérêt pratique pour le traitement des puissances de deux, spécialement pour les float double types, il y a un cas pour cette pour double-double types. Double-double de la multiplication et de la division de l'est compliqué en général, mais est trivial pour la multiplication et la division par une puissance de deux.

E. g. pour
```
typedef struct {double hi; double lo;} doubledouble;
doubledouble x;
x.hi*=2, x.lo*=2; //multiply x by 2
x.hi/=2, x.lo/=2; //divide x by 2
```
En fait, j'ai surchargé << et >> pour doubledouble de sorte qu'il est analogue à entiers.
```
//x is a doubledouble type
x << 2 //multiply x by four;
x >> 3 //divide x by eight.
```
InformationsquelleAutor Z boson
0

En fonction de ce que vous êtes en multipliant, si vous avez des données qui est assez récurrent, une table peut fournir une meilleure performance, au détriment de la mémoire.
- Je ne suis pas sûr si une recherche peut effectivement être plus rapide qu'une multiplication. Pour bien comprendre l'utilisation de tables de consultation pour les tables trigonométriques par exemple, mais pour la multiplication?
InformationsquelleAutor Kevin Guerra

Vous devez vous connecter pour publier un commentaire.