Explication souhaitée: log10 plus rapide que log et log2, mais uniquement avec O2 et supérieur

Question

J'ai besoin d'utiliser une fonction logarithme dans certains de mon code, mais la base n'a pas d'importance. Donc je me mis à le choix entre log(), log2(), et log10() de la performance, à condition que j'ai trouvé de différences significatives. (Je vais me référer à ces fonctions en tant que ln, lb, et lg respectivement).

Pourquoi suis-je de plaisanter à ce sujet? Parce que je vais être l'appel de la fonction, aussi souvent que les crédits de 400 000 000 de fois par itération d'un algorithme d'optimisation. Ce n'est ni option ni le sujet de ma question.

J'ai mis en place certaines vraiment des tests de base, comme suit:

timespec start, end;
double sum = 0, m;

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
for (int n = 1; n < INT_MAX; ++n)
{
    m = n * 10.1;
    sum += log(m);
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

cout << "ln=";
cout << diff(start, end).tv_sec << ":" << diff(start, end).tv_nsec << endl;

... // likewise for log2 and log10

(timespec diff(timespec démarrer, timespec fin) si vous le désirez....)

Les résultats suivants ont été obtenus:

GCC v4.6.3

-O0
ln=140:516853107
lb=155:878100147
lg=173:534086352

-O1
ln=133:948317112
lb=144:78885393
lg=163:870021712

-O2
ln=9:108117039
lb=9:134447209
lg=4:87951676

-O3
ln=9:102016996
lb=9:204672042
lg=4:153153558

J'ai regardé à la sortie de la compilation avec -S, mais je n'ai pas une assez bonne emprise sur l'assembleur pour comprendre pleinement les différences. -S sortie de: -O0 -S, -O3-S

Pourquoi est - lg optimiser mieux avec O2/O3?

EDIT: le code Source, remarque la faute de frappe dans la troisième boucle, c'est la cause de log10 apparente plus rapide (mult. obtenir optimisé out). J'ai accepté la réponse, je crois, est la plus proche, puisque la question a été fermée, mais j'ai beaucoup appris de drhirsch et janneb réponses.

Answer 1

Cela va dépendre de la mise en œuvre de la log() les fonctions de la bibliothèque C, compilateur de la version, de l'architecture matérielle, et ainsi de suite. De toute façon, ci-dessous, je suis en utilisant GCC 4.4 sur x86-64 avec la glibc 2.11.

Modification de l'exemple afin que je rajoute une ligne

cout << "sum=" << sum << endl;

ce qui empêche le compilateur à partir de l'optimisation de loin le log() appelle, comme je l'ai mentionné dans un commentaire, j'ai le timings (en secondes seulement, -O2):

• journal: 98s
• log2: 105s
• log10: 120s

Ces timings semblent à peu près cohérente avec l'-O0 et O1 timings dans le post original; à la hausse des niveaux d'optimisation le journal des évaluations sont optimisés à l'écart, d'où l'-O2 -O3 résultats sont donc différents.

En outre, en regardant l'exemple de journal avec la "perf" profiler, le top 5 des délinquants dans le rapport sont

# Samples: 3259205
#
# Overhead         Command              Shared Object  Symbol
# ........  ..............  .........................  ......
#
    87.96%             log  /lib/libm-2.11.1.so        [.] __ieee754_log
     5.51%             log  /lib/libm-2.11.1.so        [.] __log
     2.88%             log  ./log                      [.] main
     2.84%             log  /lib/libm-2.11.1.so        [.] __isnan
     0.69%             log  ./log                      [.] log@plt

Sauf pour le principal, tous les autres symboles sont liés à l'log() de l'appel. Pour résumer, nous pouvons conclure que 97% de la durée totale d'utilisation de cet exemple est passé dans le journal().

La mise en œuvre de l' __ieee754_journal peut être trouvé ici, dans la glibc repo git. En conséquence, les autres implémentations sont: log2, log10. Notez que les liens ci-dessus sont à la TÊTE des versions, de la version publiée de voir leurs branches correspondantes

Answer 2

Malheureusement, l'OP a omis de nous montrer le code d'origine, il choisit d'obfusquer le code légèrement la conversion à l'assemblée.

Dans l'assemblée du code de l'OP lié (annotations par moi):

.L10:
    cvtsi2sd %ebx, %xmm0         // convert i to double
    xorpd    %xmm1, %xmm1        // zero 
    mulsd    .LC0(%rip), %xmm0   // multiply i with 10.1
    ucomisd   %xmm0, %xmm1       // compare with zero
    jae       .L31               // always below, never jump

    addl    $1, %ebx             // i++
    cmpl    $2147483647, %ebx    // end of for loop
    jne     .L10
    ...
.L31:
    call    log10, log2, whatever...  // this point is never reached

On peut voir que l'appel à l' log n'est jamais exécutée, surtout si vous marchez à travers elle avec gdb. Tous les code ne sont 2³¹ multiplications et des comparaisons d'un double.

Cela explique aussi l'étonnante augmentation de la vitesse d'exécution de la fonction log par un facteur de 30 lorsqu'il est compilé avec -O2, dans le cas où quelqu'un trouve cela étrange aussi.

Edit:

for (int n = 1; n < INT_MAX; ++n)
{
    m = n * 10.1;
    sum += log(m);
}

Le compilateur n'est pas capable d'optimiser complètement la boucle de loin, parce qu'elle n'est pas en mesure de prouver que l'appel à log réussira toujours - il a des effets secondaires, si l'argument est négatif. Alors, elle remplace la boucle par une comparaison avec zéro l' log est exécuté seulement si le résultat de la multiplication est de moins en moins ou en dessous de zéro. Ce qui signifie qu'il n'est jamais exécutée :-)

Ce qui reste dans la boucle est de la multiplication et de l'essai, si le résultat peut être négatif.

Un résultat intéressant qui se passe si j'ajoute -ffast-math pour les options du compilateur, ce qui soulage le compilateur de la stricte conformité IEEE:

ln=0:000000944
lb=0:000000475
lg=0:000000357

Answer 3

Vous êtes à l'approche du problème de manière incorrecte et sont de sauter à des conclusions.

Utilisation de l'horloge n'est pas suffisant pour le profilage. Utilisation décent profiler à la place de l'horloge (gprof ou AQTime7). Profiler doit être en mesure de fournir par ligne les horaires. Votre problème est que vous considérez que le goulot d'étranglement se situe au sein de la fonction log. Toutefois int-à-flotteur de conversion n'est pas vraiment rapide et peut être aussi un goulot d'étranglement. Une autre chose est que gcc est livré avec le code source que vous pouvez lire.

Maintenant, en supposant que le goulot d'étranglement se trouve en fait dans la fonction log:

Comme vous êtes censé le savoir, doubles ont une précision limitée - seulement 15..17 chiffres après la virgule. Cela signifie qu'avec les plus grandes logarithme en base, vous aurez tôt atteindre situation quand vous frappez la précision de la limite.

I. e. 10^(log10(2^32) + 10^-15) - 2^32 == 9.8895 * 10^-6, mais 2^(log2(2^32) + 10^-15) - 2^32 == 2.977 * 10^-6 et 100^(log100(2^32) + 10^-15) - 2^32 == 0.00001977également log2(INT_MAX) > log10(INT_MAX) Cela signifie qu'avec les plus grandes logarithme en base, si la fonction logarithme essaie de "recherche" pour un bon résultat, ça va plus vite frappé situation où la modification prédit résultat n'est plus possible en raison de l'arrondissement des erreurs. Cependant, ce n'est encore qu'une supposition.

Il y a d'autres façons de calculer le logarithme. Par exemple, log10(x) == ln(x)/ln(10) si logarithme de la fonction de calcul de cette façon, vous obtiendrez près de mêmes périodes.

Ma recommandation serait de (arrêtez de perdre du temps,) profil de votre programme avec autre chose que de l'horloge (fonctions de réinventer la roue est une mauvaise idée, et non pas en utilisant les outils de profilage est de réinventer la roue, en plus d'une bonne profiler seront en mesure de fournir pour la ligne de timings de l'intérieur de la fonction log), lire code source de gcc pour le journal des fonctions(il est disponible, après tout) et de l'assemblée de sortie. Si vous ne comprenez pas l'assemblée de sortie, ce sera une bonne occasion pour apprendre à lire.

Si il est VRAIMENT important d'accélérer le logarithme de la fonction, et des algorithmes d'optimisation n'est pas VRAIMENT possible (si logarithme est vraiment un goulot d'étranglement, vous pouvez mettre en cache les résultats, par exemple), vous pouvez essayer de trouver plus rapidement l'implémentation de l'algorithme, mais si j'étais vous, dans ce cas, je serais tout simplement essayer de jeter le matériel au problème par la parallélisation de la tâche, par exemple.

Answer 4

J'ai remarqué certaines choses. Si j'ai compiler (GCC 4.5.3) votre listing assembleur -O3 -S avec g++ logflt.S -lrt je peux reproduire le problème. Mes horaires sont:

ln=6:984160044
lb=6:950842852
lg=3:64288522

Ensuite, j'ai examiné la sortie avec objdump -SC a.out. Je préfère cela à la recherche dans l' .S fichiers puisqu'il y a des constructions qui je n'ai pas (encore) de comprendre. Le code n'est pas très facile à lire, mais je trouve la suivante:

Avant d'appeler, log ou log2 l'argument est converti à l'aide

400900:       f2 0f 2a c3             cvtsi2sd %ebx,%xmm0
400904:       66 0f 57 c9             xorpd  %xmm1,%xmm1
400908:       f2 0f 59 05 60 04 00    mulsd  0x460(%rip),%xmm0
40090f:       00 
400910:       66 0f 2e c8             ucomisd %xmm0,%xmm1

0x460(%rip) est un parent adresse qui pointe vers la valeur du hex 0000 00000000 33333333 33332440. C'est un de 16 octets de l'ESS double paire à partir de laquelle seule double est important (code scalaire à l'aide de l'ESS). Ce double est - 10.1. mulsd donc effectue la multiplication du C++ ligne, m = n * 10.1;.

log10 est différent:

400a40:       f2 0f 2a c3             cvtsi2sd %ebx,%xmm0
400a44:       66 0f 57 c9             xorpd  %xmm1,%xmm1
400a48:       66 0f 2e c8             ucomisd %xmm0,%xmm1

Je pense que pour le cas de l' log10 vous avez oublié d'effectuer la multiplication! Si vous êtes simplement appeler l' log10 avec la même valeur, encore et encore ... je ne me surprendrait pas si le cpu est assez intelligent pour optimiser qui.

EDIT: je suis maintenant sûr que ce est le problème, parce que dans l'autre liste (-O0 -S) la multiplication est correctement exécutée, donc merci de poster votre code et de laisser les autres me prouver le contraire!

EDIT2: Une façon de GCC pourrait se débarrasser de cette multiplication est par l'utilisation de l'identité suivante:

log(n * 10.1) = log(n) + log(10.1)

Mais dans ce cas log(10.1) devrait être calculé une fois et je ne le vois pas le code. Je doute aussi que GCC ne le ferait que pour l' log10 mais pas pour log et log2.