La división es una de las operaciones más caras en procesadores modernos. No tiene que ir muy lejos como prueba: Agner Fog [
1 ] transmite que en los procesadores Intel / AMD podemos obtener fácilmente la latencia en 25-119 ciclos de reloj y un rendimiento recíproco: 25-120. Traducido al ruso - ¡
LENTO ! Sin embargo, existe la oportunidad de evitar la instrucción de división en su código. Y en este artículo, le diré cómo funciona, en particular en los compiladores modernos (ya han podido hacerlo durante 20 años), y también le diré cómo se puede usar el conocimiento adquirido para hacer que el código sea mejor, más rápido y más potente.
En realidad, estoy hablando de: si el divisor se conoce en la etapa de compilación, es posible reemplazar la división entera con la multiplicación y un cambio lógico a la derecha (y a veces puedes prescindir de ella en absoluto; ciertamente estoy hablando de la implementación en el lenguaje de programación). Suena muy alentador: la operación de multiplicación de enteros y un desplazamiento a la derecha por, por ejemplo, Intel Haswell no tomará más de 5 ciclos de reloj. Solo queda entender cómo, por ejemplo, al realizar la división de enteros por 10, para obtener el mismo resultado mediante la multiplicación de enteros y un desplazamiento lógico a la derecha? La respuesta a esta pregunta radica en la comprensión ... Aritmética de punto fijo (en adelante, FPA). Un poco de lo básico.
Cuando se usa FP, el exponente (exponente 2 => la posición del punto en la representación binaria del número) no se guarda en el número (a diferencia de la aritmética de coma flotante, vea IEE754), pero se considera una cantidad acordada conocida por los programadores. Solo se retiene la mantisa (lo que viene después del punto decimal). Un ejemplo:
0.1 - en notación binaria tiene 'representación infinita', que se indica entre paréntesis en el ejemplo anterior; esta parte se repetirá de vez en cuando, siguiéndose entre sí en notación FP binaria del número 0.1.En el ejemplo anterior, si usamos registros de 16 bits para almacenar números FP, no podemos ajustar la representación FP del número 0.1 en dicho registro sin perder precisión, y esto a su vez afectará el resultado de todos los cálculos adicionales en los que está involucrado el valor de este registro.
Supongamos que se nos da un número entero A de 16 bits y una fracción de B. de 16 bits. El producto de A por B da como resultado un número con 16 bits en la parte entera y 16 bits en la parte fraccionaria. Para obtener solo la parte entera, obviamente, debe desplazar el resultado 16 bits hacia la derecha.
Felicitaciones, la introducción a la FPA ha terminado.
Formamos la siguiente hipótesis: para realizar una división entera por 10, necesitamos multiplicar el número divisible por la representación FP del número 0.1, tomar la parte entera y la materia en el sombrero ... espere un minuto ... ¿El resultado será preciso, más precisamente, la parte entera? - Después de todo, como recordamos, en nuestra memoria solo se almacena una versión aproximada del número 0.1. A continuación, he escrito tres representaciones diferentes de 0.1: una representación infinitamente precisa de 0.1, truncada después del bit 16 sin redondeo, una representación de 0.1, y truncada después del bit 16 con redondeo, una representación de 0.1.
Permítanos estimar los errores de truncar representaciones del número 0.1:
Para que el resultado de multiplicar el entero A por la aproximación de 0.1 para dar la parte entera exacta, necesitamos:
cualquiera
Es más conveniente usar la primera expresión: cuando
siempre obtenemos la identidad (pero, fíjate, no todas las decisiones son más que suficientes en el marco de este problema). Resolviendo, obtenemos
. Es decir, al multiplicar cualquier número A de 14 bits truncando al redondear la representación de 0.1, siempre obtenemos la parte entera exacta, que obtendríamos multiplicando infinitamente exactamente 0.1 por A. Pero, por convención, estamos multiplicando números de 16 bits, lo que significa , en nuestro caso, la respuesta será inexacta y no podemos confiar en la simple multiplicación truncando con redondeando hacia arriba 0.1. Ahora, si pudiéramos guardar en la representación FP del número 0.1 no 16 bits, pero, digamos, 19, 20, entonces todo estaría bien. ¡Y después de todo lo que podemos!
Observamos cuidadosamente la representación binaria, truncando con redondeando hacia arriba 0.1: los tres bits más altos son cero, lo que significa que no hacen ninguna contribución al resultado de la multiplicación (nuevos bits).
Por lo tanto, podemos cambiar nuestro número a la izquierda en tres bits, redondear hacia arriba y, después de hacer la multiplicación y el cambio lógico a la derecha, primero por 16 y luego por 3 (es decir, generalmente hablando a la vez por 19), obtenemos la parte entera exacta deseada. . La prueba de la exactitud de tal multiplicación de '19' bits es similar a la anterior, con la única diferencia de que funciona correctamente para números de 16 bits. Un razonamiento similar también es cierto para números de mayor capacidad, y no solo para la división por 10.
Anteriormente, escribí que, en términos generales, puede prescindir de cualquier cambio, limitándose a la multiplicación. Como? Ensamblador x86 / x64 en el tambor:
En los procesadores modernos, hay un comando MUL (también hay análogos IMUL, MULX - BMI2), que, tomando uno, digamos un parámetro de 32/64 bits, es capaz de realizar una multiplicación de 64/128 bits, guardando el resultado en partes en dos registros (los 32/64 bits más altos y menores, respectivamente):
MUL RCX ; RCX RAX, (128 ) RDX:RAX
Deje que se almacene algún número entero de 62 bits A en el registro RCX, y deje que la representación FA de 64 bits que se trunca con el redondeo del número 0.1 se almacene en el registro RAX (aviso, no hay desplazamientos a la izquierda). Después de completar la multiplicación de 64 bits, obtenemos que los 64 bits más altos del resultado se almacenan en el registro RDX o, más precisamente, la parte entera, que será exacta para números de 62 bits. Es decir, no se necesita un desplazamiento hacia la derecha (SHR, SHRX). La presencia de dicho cambio carga la canalización del procesador, independientemente de si es compatible con OOOE o no: al menos hay una dependencia adicional en la cadena más larga de estas dependencias (también conocida como Cadena de dependencia). Y aquí, es muy importante mencionar que los compiladores modernos, al ver una expresión de la forma some_integer / 10, generan automáticamente código de ensamblador para todo el rango de números divisibles. Es decir, si sabe que sus números son siempre de 53 bits (esto es exactamente lo que sucedió en mi tarea), recibirá la instrucción de cambio adicional de todos modos. Pero, ahora que comprende cómo funciona esto, puede reemplazar fácilmente la división usted mismo con la multiplicación, sin depender de la misericordia del compilador. Por cierto, obtener los bits altos de un producto de 64 bits en código C ++ se implementa mediante algo como mulh, que, según el código Asm, debería ser equivalente a las líneas de la instrucción {I} MUL {X} anterior.
Quizás con la llegada de los contratos (en C ++ 20 no estamos esperando) la situación mejorará y, en algunos casos, ¡podemos confiar en el automóvil! Aunque esto es C ++, el programador es responsable de todo aquí, no de otra manera.
El razonamiento descrito anteriormente: se aplica a cualquier divisor de constantes, bueno, y debajo hay una lista de enlaces útiles:
[1] https://www.agner.org/optimize/instruction_tables.pdf[2] Más empinado que Agner Fogh[3] Canal de Telegram con información útil sobre optimizaciones para Intel / AMD / ARM[4] Sobre la división por completo, pero en inglés