Multiplier par 7 de manière efficace

J’ai récemment rencontré la question d’entrevue suivante:

Comment multiplier un nombre par 7 de manière efficace et optimisée?

Je sais que je peux multiplier par 8 (ou par décalage à gauche de trois bits) puis soustraire la valeur d’origine:

num = (num << 3) - num; 

mais existe-t-il d’autres solutions?

Pour obtenir un multiple de 7 de manière efficace:

 7 

7 est un multiple de 7. Cela répond à la question que vous avez posée, mais je suis sûr que cela ne répond pas à la question que vous voulez poser.

EDIT: Ce qui précède est basé sur le titre original de la question, que je viens de corriger.

Pour multiplier efficacement par 7, il suffit d’écrire, par exemple:

 x * 7 

et invoquez votre compilateur avec optimisation. Laissez le compilateur déterminer si une seule instruction MUL ou quelque chose comme (x<<3) - x est plus efficace pour la machine actuelle .

Il y a encore une autre question implicite ici: quelle réponse cherchait l'intervieweur? J'espère que "laisser le compilateur s'en inquiéter" serait une réponse acceptable. (x<<3) - x est probablement la micro-optimisation la plus évidente - mais elle peut donner des réponses incorrectes si x<<3 déborde, et selon le système, il peut être plus lent qu'une instruction MUL.

(Si j'étais l'intervieweur, je serais plus impressionné par une bonne explication et une compréhension des problèmes que par une réponse spécifique.)

MODIFIER

Après reflection, les types de micro-optimisations discutés ici pourraient être utiles si vous en savez plus sur les valeurs possibles de x que le compilateur. Si vous savez, en raison de la nature de la logique de votre programme, que x sera toujours compris dans la plage 0..10, une table de correspondance pourrait facilement être plus rapide qu'une opération de multiplication. Ou si vous savez que x est dans cet intervalle 99% du temps, une table de correspondance avec un repli sur une multiplication réelle pourrait être la solution.

Mais si l'parsing du stream de votre programme par le compilateur ne lui permet pas de prouver que x est toujours dans cette plage, il ne peut pas effectuer ce type d'optimisation.

Mais de telles circonstances sont très rares. Et lorsque votre code s'exécute dans un nouvel environnement où x peut être 11 (il s'exécute peut-être sur un périphérique avec un affichage plus grand), kaboom . Et l’amélioration de la performance n’était probablement pas significative au départ.

Il y a des moments où la micro-optimisation est appropriée, mais le temps de développement et de test représente un coût substantiel. Ne le faites que si les mesures réelles indiquent que cela en vaut la peine.

Pour une plage limitée, vous pouvez utiliser une table de recherche:

 static unsigned int mult7[] = {0, 7, 14, 21, ...}; unsigned int three = 3; unsigned int twenty_one = mult7[three]; 

Cela peut sembler idiot (et c’est probablement le cas dans ce cas précis), mais c’est souvent utile pour des tâches pour lesquelles le calcul représente un coût réel . Je ne suis tout simplement pas certain que la multiplication par sept compte pour l’un de ces cas.

Pour commencer, multiplier x par 7 (ou décaler x trois bits puis soustraire x ) est une opération qui peut être effectuée entièrement à l’intérieur de la CPU. Avec une consultation de table, vous pouvez voir apparaître une multiplication par quatre (décalage de deux bits) suivie d’un ajout pour obtenir la bonne adresse, mais vous devez ensuite accéder à la mémoire pour effectuer la recherche proprement dite, même avec la mise en cache et toutes les autres. Des astuces extraordinaires sont capables des processeurs actuels, cela va probablement ralentir les choses.

Il y a également de bonnes chances que votre compilateur connaisse déjà toutes les astuces pour multiplier rapidement. Si votre seven est une constante (ou const int ou équivalent), le compilateur aura probablement déjà choisi le moyen le plus rapide et il y a de fortes chances pour que les auteurs du compilateur en sachent plus sur ce genre de choses que les simples mortels 🙂 (a)

Mais dans les cas où le coût de calcul est relativement élevé, calculer les valeurs une seule fois et les incorporer dans votre code sous forme de table de recherche est l’une des stratégies d’optimisation standard (temps d’échange d’espace).


(a) Examinez le code suivant:

 #include  static int mult7 (int num) { return num * 7; } int main (int argc, char *argv[]) { printf ("%d\n", mult7 (atoi (argv[1]))); return 0; } 

Avec la compilation normale par gcc , mult7 apparaît comme le décalage gauche trois et soustrait le truc:

 _mult7: pushl %ebp ; stack frame setup. movl %esp, %ebp movl 8(%ebp), %edx ; get value to edx movl %edx, %eax ; and eax. sall $3, %eax ; eax <- eax * 8. subl %edx, %eax ; eax <- eax - edx. popl %ebp ; stack frame teardown and return. ret 

À -O3 (ce que j'aime appeler le niveau d'optimisation insensé), le tout est intégré dans main avec:

 call _atoi movl $LC0, (%esp) leal 0(,%eax,8), %edx ; these two are the relevant instructions. subl %eax, %edx movl %edx, 4(%esp) call _printf 

Notez que cette action en ligne n'est possible qu'en raison de la nature statique de la fonction - si elle était visible par l'éditeur de liens, elle devrait être conservée en tant que fonction distincte au cas où un autre fichier object aurait besoin de l'appeler.

Si vous supprimez la static , elle rest effectivement non alignée avec toute la configuration et le déassembly du cadre de la stack, mais elle utilise au moins toujours le truc (probablement) plus efficace mentionné ci-dessous. Vous pouvez vous débarrasser du code de la stack dans gcc si vous utilisez -fomit-frame-pointer condition que cela n’affecte pas le code, mais cela commence à plonger un peu dans le côté obscur 🙂

Cette astuce consiste à utiliser l'instruction LEA pour définir edx sur eax * 8 puis soustraire eax de celle-ci. Même théorie que l’optimisation normale sall/subl normale, à la différence des mécanismes légèrement différents.

En bout de ligne, faites confiance à votre compilateur. Si vous voulez multiplier num par 7, utilisez ce qui suit:

 num *= 7; 

Il est probable que quelle que soit l'amélioration obtenue grâce à une telle tentative de micro-optimisation, vous pourriez obtenir une bien meilleure amélioration en regardant au niveau macro (sélection de l'algorithme et de la structure de données, etc.).

La façon dont je le ferais serait quelque chose comme

 num = (num << 3) - num; 

c'est à dire. 2 ^ 3 = 8, puis soustrayez le nombre multiplié pour obtenir un multiple de 7.

Je viens de comstackr le code suivant avec gcc:

 int mul(int num) { return num * 7; } 

et ceci est un dump de GDB de ce qu'il a compilé pour:

 Dump of assembler code for function mul: 0x00000000004004c4 <+0>: push rbp 0x00000000004004c5 <+1>: mov rbp,rsp 0x00000000004004c8 <+4>: mov DWORD PTR [rbp-0x4],0xa 0x00000000004004cf <+11>: mov edx,DWORD PTR [rbp-0x4] 0x00000000004004d2 <+14>: mov eax,edx 0x00000000004004d4 <+16>: shl eax,0x3 0x00000000004004d7 <+19>: sub eax,edx 0x00000000004004d9 <+21>: mov DWORD PTR [rbp-0x4],eax 0x00000000004004dc <+24>: pop rbp 0x00000000004004dd <+25>: ret End of assembler dump. 

Il semble donc que ma machine a changé trois fois à gauche, puis que gcc estime que soustraire le nombre multiplié est peut-être optimal.

EDIT: avec un niveau d’optimisation au moins égal à 1 ( -O1 ), gcc utilise l’astuce suivante:

 Dump of assembler code for function mul: 0x00000000004004e0 <+0>: lea eax,[rdi*8+0x0] 0x00000000004004e7 <+7>: sub eax,edi 0x00000000004004e9 <+9>: ret End of assembler dump. 

En fait, le moyen le plus efficace de multiplier par 7 peut être d’utiliser l’opérateur de multiplication. Cela dépend de la vitesse relative des instructions respectives sur la plate-forme cible.

OMI, une réponse complète à une telle question d’entrevue doit également mentionner les points suivants:

  1. Ce type d’optimisation est normalement préférable de laisser au compilateur / rédacteur du compilateur. (En effet, d’une autre réponse, il semble que gcc optimise ce cas.)

  2. En tant que programmeur, vous ne devriez y consacrer du temps que si 1) il existe un problème de performances réel (mesurable) et 2) votre profileur vous indique que les déclarations que vous regardez sont critiques pour la performance.


Dans sa réponse. Olaf a écrit ceci:

“Je ne suis pas d’accord avec Stephen C lorsqu’il vous dit ce que vous devriez (ou ne devriez pas) faire. Si tout le monde le faisait, il n’y aurait pas d’innovations dans l’indussortinge du logiciel.”

Il semblerait qu’Olaf ne croie pas un ou plusieurs des éléments suivants:

  • qu’un ingénieur logiciel devrait donner des conseils,
  • qu’un ingénieur logiciel devrait prendre conseil, ou
  • qu’un employé / programmeur doit éviter de gaspiller son temps en optimisation manuelle inutile.

Il est vrai que si tout le monde agissait toujours sur les conseils reçus, l’innovation serait moindre. Mais le revers de la médaille est que le travail à effectuer ne nécessite généralement pas beaucoup d’innovation. (Et cela nécessite rarement une optimisation de la main …)

En outre, si ignorer les conseils (meilleure pratique) était une vertu, alors 75% des ingénieurs en logiciel consacreraient leur temps à la maintenance du code de assembly, du code d’assemblage ou des résultats de la méthodologie de conception à la mode des années 1990.

Vous devez donc au moins comprendre le conseil et peser les conséquences éventuelles de l’ignorer. Comme si le patron avait une vision sombre de votre “innovation” (ou plus exactement de la perte de temps) sur ses projets.

Comme le dit Stephen C, “le moyen le plus efficace de multiplier par 7 peut être l’opérateur de multiplication”.

Dans cet article – Latences d’instruction et débit des processeurs AMD et Intel x86 – Torbjörn Granlund de l’Institut royal de technologie de Stockholm montre qu’une multiplication non signée nécessite 3/5 cycles d’horloge en mode 32/64 bits sur architecture K10 et 4 / 4 sur le pont de sable. Si vous devez effectuer plusieurs multiplications consécutives, le K10 peut émettre une multiplication tous les deux cycles d’horloge en mode 32/64 bits. Cela signifie qu’il peut fonctionner sur trois multiplications à différents stades simultanément (3/1) et 2.5 (5/2) en 64 bits. Sandy Bridge en émet un tous les deux / tous les cycles en 32/64. Cela signifie deux (4/2) ou quatre (4/1) instructions simultanément.

Personnellement, je pense que vous aurez du mal à améliorer cela avec une séquence à plusieurs équipes. Je ne suis pas d’accord avec Stephen C lorsqu’il vous dit ce que vous devriez (ou ne devriez pas) faire. Si tout le monde faisait cela, il n’y aurait pas d’innovations dans l’indussortinge du logiciel.

Alors: allez-y!