Multiplica por 7 de manera eficiente.

Recientemente me encontré con la siguiente pregunta de la entrevista:

¿Cómo puedes multiplicar un número por 7 de una manera eficiente y optimizada?

Sé que puedo multiplicar por 8 (o desplazar a la izquierda por tres bits) y luego restar el valor original:

num = (num << 3) - num; 

pero hay otras soluciones

Para obtener un múltiplo de 7 de una manera eficiente:

 7 

7 es un múltiplo de 7. Eso responde a la pregunta que hizo, pero estoy seguro de que no responde a la pregunta que quiere hacer.

EDITAR: Lo anterior se basa en el título original de la pregunta, que acabo de corregir.

Para multiplicar por 7 de manera eficiente, solo escribe, por ejemplo:

 x * 7 

e invoca tu comstackdor con optimización. Deje que el comstackdor determine si una sola instrucción MUL o algo parecido (x<<3) - x es más eficiente para la máquina actual .

Hay otra pregunta implícita aquí: ¿qué respuesta buscaba el entrevistador? Espero que "deje que el comstackdor se preocupe por eso" sería una respuesta aceptable. (x<<3) - x es probablemente la microoptimización más obvia, pero puede producir respuestas incorrectas si x<<3 desborda, y dependiendo del sistema puede ser más lento que una instrucción MUL.

(Si yo fuera el entrevistador, me impresionaría más una buena explicación y comprensión de los problemas que una respuesta específica).

EDITAR

Pensándolo bien, los tipos de microoptimizaciones que se han discutido aquí podrían ser útiles si sabe más sobre los posibles valores de x que el comstackdor. Si sabe, debido a la naturaleza de la lógica de su progtwig, que x siempre estará en el rango de 0..10, entonces una tabla de búsqueda podría ser más rápida que una operación de multiplicación. O si sabe que x está en ese rango el 99% del tiempo, una tabla de búsqueda con un retroceso a una multiplicación real podría ser lo que necesita.

Pero si el análisis del comstackdor del flujo de su progtwig no le permite probar que x siempre está en ese rango, entonces no puede realizar este tipo de optimización.

Pero tales circunstancias son muy raras. Y cuando su código se ejecuta en un nuevo entorno donde x puede ser 11 (quizás se esté ejecutando en un dispositivo con una pantalla más grande), kaboom . Y la mejora del rendimiento muy probablemente no fue significativa en primer lugar.

Hay momentos en que la microoptimización es apropiada, pero hay un costo sustancial en el tiempo de desarrollo y prueba. Hazlo solo si las mediciones reales indican que vale la pena.

Para un rango limitado, puede usar una tabla de búsqueda:

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

Esto puede sonar tonto (y probablemente sea para este caso específico), pero a menudo es útil para cosas donde hay un costo real de cálculo. Simplemente no estoy seguro de que multiplicar por siete sea uno de esos casos.

Para empezar, multiplicar x por 7 (o desplazar x tres bits a la izquierda y luego restar x ) es una operación que se puede hacer completamente dentro de la CPU. Con una búsqueda en la tabla, es posible que vea una multiplicación por cuatro (desplace dos bits a la izquierda) seguido de un agregado para obtener la dirección correcta, pero luego tiene que acceder a la memoria para realizar la búsqueda real, incluso con almacenamiento en caché y todo lo demás. Los maravillosos trucos que las CPU actuales son capaces de hacer, probablemente van a ralentizar las cosas.

También hay una buena posibilidad de que tu comstackdor ya sepa todos los trucos sobre cómo multiplicar rápido. Si su siete es una constante (o const int o equivalente), el comstackdor probablemente ya habrá elegido la forma más rápida y es muy probable que los escritores del comstackdor sepan mucho más sobre este tipo de cosas que los simples mortales 🙂 (a)

Pero para los casos en los que el costo de cálculo es relativamente alto, calcular una vez los valores e incluirlos en su código como una tabla de búsqueda es una de las estrategias de optimización estándar (compensar el tiempo por el espacio).


(a) Examine el siguiente código:

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

Con la comstackción normal de gcc , mult7 sale como el turno a la izquierda tres y resta truco:

 _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 

En -O3 (lo que me gusta llamar el nivel de optimización de locura), todo está integrado en main con:

 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 

Tenga en cuenta que esta acción de integración solo es posible debido a la naturaleza estática de la función; si fuera visible para el vinculador, tendría que mantenerse como una función separada en caso de que otro archivo de objeto fuera necesario para llamarla.

Si quita la static , de hecho la mantiene sin alinear con toda la configuración y el desassembly del marco de la stack, pero al menos sigue utilizando el truco (probablemente más eficiente) que se menciona a continuación. Puede deshacerse del código de marco de stack en gcc si usa -fomit-frame-pointer siempre que esto no afecte negativamente al código, pero esto está comenzando a profundizar un poco en el lado oscuro 🙂

Este truco es usar la instrucción LEA para configurar edx en eax * 8 luego resta eax de eso. La misma teoría que sall/subl en la optimización normal, solo mecánicas ligeramente diferentes.

En pocas palabras, confía en tu comstackdor. Si quieres multiplicar num por 7, usa lo siguiente:

 num *= 7; 

Lo más probable es que, independientemente de la mejora que obtenga de un bash de microoptimización, podría obtener una mejora mucho mejor si observa el nivel macro (selección de algoritmo y estructura de datos, etc.).

La forma en que lo haría sería algo como

 num = (num << 3) - num; 

es decir. 2 ^ 3 = 8, luego reste el número que se multiplica para obtener un múltiplo de 7.

Acabo de comstackr el siguiente código con gcc:

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

y este es un volcado gdb de lo que compiló para:

 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. 

Así que, para mi máquina, cambiar a la izquierda 3 veces y luego restar el número que se multiplica es lo que gcc cree que puede ser óptimo.

EDITAR: Resulta que con un nivel de optimización de al menos 1 ( -O1 ), gcc usa el truco:

 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. 

De hecho, la forma más eficiente de multiplicar por 7 puede ser usar el operador de multiplicar. Depende de la velocidad relativa de las instrucciones respectivas en la plataforma de destino.

En mi opinión, una respuesta completa a esta pregunta de entrevista también debe mencionar lo siguiente:

  1. Este tipo de optimización normalmente es mejor dejarlo en el comstackdor / escritor del comstackdor. (De hecho, según otra respuesta, parece que gcc optimiza este caso).

  2. Usted (como progtwigdor) solo debería dedicar tiempo a esto si 1) hay un problema de rendimiento real (medible) y 2) su generador de perfiles le dice que las declaraciones que está viendo son críticas para el rendimiento.


En su respuesta. Olaf escribió esto:

“No estoy de acuerdo con Stephen C cuando te dice lo que debes (o no debes) hacer. Si todos hicieran eso, no habría innovaciones en la industria del software”.

Parece que Olaf no cree en uno o más de los siguientes:

  • que un ingeniero de software debe dar consejos,
  • que un ingeniero de software debería tomar consejo, o
  • que un empleado / progtwigdor debe evitar perder el tiempo de los jefes en la optimización de la mano sin sentido.

Es cierto que si todos actuaran de acuerdo con los consejos recibidos, habría menos innovación. Pero la otra cara es que el trabajo en cuestión normalmente no requiere mucha innovación. (Y rara vez requiere optimización de mano …)

Además, si ignorar el consejo (la mejor práctica) era una virtud, entonces el 75% de los ingenieros de software dedicarían su tiempo a mantener “goto spaghetti”, el código de ensamblaje o los resultados de la moda de la década de 1990 en la metodología de diseño.

Por lo tanto, al menos debe comprender el consejo y sopesar las posibles consecuencias de ignorarlo. Como el jefe que tiene una visión tenue de su “innovación” (o más precisamente, pérdida de tiempo) en sus proyectos.

Como dice Stephen C, “la forma más eficiente de multiplicar por 7 puede ser el operador de multiplicación”.

En este documento – Latencias de instrucción y rendimiento para los procesadores AMD e Intel x86 – Torbjörn Granlund del Royal Institute of Technology en Estocolmo muestra que una multiplicación sin firma requiere 3/5 ciclos de reloj en modos de 32/64 bits en la architecture K10 y 4 / 4 en Sandy Bridge. Si necesita realizar múltiples multiplicaciones consecutivas, el K10 puede emitir un ciclo de reloj multiplicado cada uno y cada uno en modos de 32/64 bits. Esto significa que puede funcionar en tres multiplicaciones en diferentes etapas simultáneamente (3/1) y 2.5 (5/2) en 64 bits. Sandy Bridge emite uno cada otro / cada ciclo de reloj en 32/64. Esto significa dos (4/2) o cuatro (4/1) instrucciones simultáneamente.

Personalmente, creo que le será difícil mejorar esto con una secuencia de varios turnos. No estoy de acuerdo con Stephen C cuando te dice lo que debes (o no debes) hacer. Si todos hicieran eso, no habría innovaciones en la industria del software.

Así que, ¡adelante!