Dividir eficientemente el valor no firmado por una potencia de dos, redondeando hacia arriba

optimization x86 (9)

Dividir eficientemente el valor no firmado por una potencia de dos, redondeando hacia arriba

[Reescribir] dada la aclaración de OP con respecto al poder de 2 .

La parte redondeada o el techo es fácil cuando el desbordamiento no es una preocupación. Simple añadir q-1, luego cambiar.

De lo contrario, como la posibilidad de redondeo depende de todos los bits de pmenor tamaño q, primero se necesita la detección de esos bits antes de que se desplacen.

uint64_t divide_A(uint64_t p, uint64_t q) { bool round_up = p & (q-1); return (p >> lg64(q)) + round_up; }

Esto supone que el código tiene una lg64(uint64_t x)función eficiente , que devuelve el registro de base-2 x, si xes una potencia de dos.

Quiero implementar ^una división entera sin signo por un poder arbitrario de dos, redondeando , de manera eficiente. Entonces, lo que quiero, matemáticamente, es ceiling(p/q) ⁰ . En C, la implementación de strawman, que no aprovecha el dominio restringido de q podría ser similar a la siguiente función ¹ :

/** q must be a power of 2, although this version works for any q */ uint64_t divide(uint64_t p, uint64_t q) { uint64_t res = p / q; return p % q == 0 ? res : res + 1; }

... por supuesto, no quiero usar división o mod a nivel de máquina, ya que eso toma muchos ciclos incluso en hardware moderno. Estoy buscando una reducción de la fuerza que use turnos y / o alguna otra (s) operación (es) barata (s), aprovechando el hecho de que q es una potencia de 2.

Puede suponer que tenemos una función eficiente de lg(unsigned int x) , que devuelve el registro base-2 de x , si x es una potencia de dos.

El comportamiento indefinido está bien si q es cero.

Tenga en cuenta que la solución simple: (p+q-1) >> lg(q) no funciona en general; inténtelo con p == 2^64-100 and q == 256 ² por ejemplo.

Detalles de la plataforma

Me interesan las soluciones en C, que probablemente tengan un buen desempeño en una variedad de plataformas, pero en aras de la concreción, otorgando la recompensa y debido a que cualquier discusión definitiva sobre el rendimiento debe incluir una arquitectura de destino, seré específico sobre cómo los probaré:

CPU Skylake
gcc 5.4.0 con -O3 -march=haswell compilación -O3 -march=haswell

El uso de gcc builtins (como bitscan / leader zero builtins) está bien, y en particular he implementado la función lg() que dije que estaba disponible de la siguiente manera:

inline uint64_t lg(uint64_t x) { return 63U - (uint64_t)__builtin_clzl(x); } inline uint32_t lg32(uint32_t x) { return 31U - (uint32_t)__builtin_clz(x); }

Verifiqué que estos compilaban en una sola instrucción bsr , al menos con -march=haswell , a pesar de la aparente participación de una resta. Por supuesto, es libre de ignorar estos y utilizar cualquier otro componente que desee en su solución.

Punto de referencia

Escribí un benchmark de benchmark para las respuestas existentes, y compartiré y actualizaré los resultados a medida que se realicen los cambios.

Escribir un buen punto de referencia para una operación pequeña y potencialmente en línea es bastante difícil. Cuando el código está integrado en un sitio de llamada, gran parte del trabajo de la función puede desaparecer, especialmente cuando está en un bucle ³ .

Simplemente puede evitar todo el problema de alineación asegurándose de que su código no esté en línea: declararlo en otra unidad de compilación. Traté de hacerlo con el bench binario, pero en realidad los resultados son bastante inútiles. Casi todas las implementaciones están vinculadas a 4 o 5 ciclos por llamada, pero incluso un método ficticio que no hace otra cosa que return 0 lleva el mismo tiempo. Así que en su mayoría solo estás midiendo la call + ret head. Además, casi nunca vas a usar las funciones de esta manera, a menos que lo arruines, estarán disponibles para la alineación y eso lo cambia todo .

Por lo tanto, los dos puntos de referencia en los que me concentraré más son las que llaman repetidamente al método que se está probando en un bucle, lo que permite la optimización, la función cruzada, el levantamiento de bucles e incluso la vectorización.

Hay dos tipos generales de referencia: la latencia y el rendimiento. La diferencia clave es que en la referencia de latencia, cada llamada a divide depende de la llamada anterior, por lo que en general las llamadas no se pueden superponer fácilmente ⁴ :

uint32_t bench_divide_latency(uint32_t p, uint32_t q) { uint32_t total = p; for (unsigned i=0; i < ITERS; i++) { total += divide_algo(total, q); q = rotl1(q); } return total; }

Tenga en cuenta que el total acumulado depende de la salida de cada llamada de división, y que también es una entrada para la llamada de divide .

La variante de rendimiento, por otro lado, no alimenta la salida de una división a la siguiente. Esto permite que el trabajo de una llamada se superponga con uno posterior (tanto por el compilador, pero especialmente la CPU), e incluso permite la vectorización:

uint32_t bench_divide_throughput(uint32_t p, uint32_t q) { uint32_t total = p; for (unsigned i=0; i < ITERS; i++) { total += fname(i, q); q = rotl1(q); } return total; }

Tenga en cuenta que aquí introducimos el contador de bucles como el dividendo; esto es variable , pero no depende de la llamada de división anterior.

Además, cada punto de referencia tiene tres tipos de comportamiento para el divisor, q :

Divisor constante en tiempo de compilación. Por ejemplo, una llamada a divide(p, 8) . Esto es común en la práctica, y el código puede ser mucho más simple cuando se conoce el divisor en el momento de la compilación.
Divisor invariante. Aquí el divisor no se conoce en el momento de la compilación, pero es constante para todo el ciclo de evaluación comparativa. Esto permite un subconjunto de las optimizaciones que hace la constante de tiempo de compilación.
Divisor variable. El divisor cambia en cada iteración del bucle. Las funciones de referencia anteriores muestran esta variante, utilizando una instrucción "rotar a la izquierda 1" para variar el divisor.

Combinando todo, obtienes un total de 6 benchmarks distintos.

Resultados

En general

Para los fines de elegir un mejor algoritmo general, observé cada uno de los 12 subconjuntos para los algoritmos propuestos: (latency, throughput) x (constant a, invariant q, variable q) x (32-bit, 64-bit) y asignado una puntuación de 2, 1 o 0 por subprueba de la siguiente manera:

El mejor (es) algoritmo (s) (dentro del 5% de tolerancia) recibe una puntuación de 2.
Los algoritmos "suficientemente cercanos" (no más de un 50% más lentos que los mejores) reciben una puntuación de 1.
Los algoritmos restantes puntúan cero.

Por lo tanto, la puntuación total máxima es 24, pero ningún algoritmo logró eso. Aquí están los resultados totales totales:

╔═══════════════════════╦═══════╗ ║ Algorithm ║ Score ║ ╠═══════════════════════╬═══════╣ ║ divide_user23_variant ║ 20 ║ ║ divide_chux ║ 20 ║ ║ divide_user23 ║ 15 ║ ║ divide_peter ║ 14 ║ ║ divide_chrisdodd ║ 12 ║ ║ stoke32 ║ 11 ║ ║ divide_chris ║ 0 ║ ║ divide_weather ║ 0 ║ ╚═══════════════════════╩═══════╝

Entonces, para los propósitos de este código de prueba específico, con este compilador específico y en esta plataforma , user2357112 "variant" (con ... + (p & mask) != 0 ) se desempeña mejor, vinculado con la sugerencia de chux (que está en código idéntico de hecho).

Aquí están todas las sub-puntuaciones que se suman a lo anterior:

╔══════════════════════════╦═══════╦════╦════╦════╦════╦════╦════╗ ║ ║ Total ║ LC ║ LI ║ LV ║ TC ║ TI ║ TV ║ ╠══════════════════════════╬═══════╬════╬════╬════╬════╬════╬════╣ ║ divide_peter ║ 6 ║ 1 ║ 1 ║ 1 ║ 1 ║ 1 ║ 1 ║ ║ stoke32 ║ 6 ║ 1 ║ 1 ║ 2 ║ 0 ║ 0 ║ 2 ║ ║ divide_chux ║ 10 ║ 2 ║ 2 ║ 2 ║ 1 ║ 2 ║ 1 ║ ║ divide_user23 ║ 8 ║ 1 ║ 1 ║ 2 ║ 2 ║ 1 ║ 1 ║ ║ divide_user23_variant ║ 10 ║ 2 ║ 2 ║ 2 ║ 1 ║ 2 ║ 1 ║ ║ divide_chrisdodd ║ 6 ║ 1 ║ 1 ║ 2 ║ 0 ║ 0 ║ 2 ║ ║ divide_chris ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ ║ divide_weather ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ ║ 64-bit Algorithm ║ ║ ║ ║ ║ ║ ║ ║ ║ divide_peter_64 ║ 8 ║ 1 ║ 1 ║ 1 ║ 2 ║ 2 ║ 1 ║ ║ div_stoke_64 ║ 5 ║ 1 ║ 1 ║ 2 ║ 0 ║ 0 ║ 1 ║ ║ divide_chux_64 ║ 10 ║ 2 ║ 2 ║ 2 ║ 1 ║ 2 ║ 1 ║ ║ divide_user23_64 ║ 7 ║ 1 ║ 1 ║ 2 ║ 1 ║ 1 ║ 1 ║ ║ divide_user23_variant_64 ║ 10 ║ 2 ║ 2 ║ 2 ║ 1 ║ 2 ║ 1 ║ ║ divide_chrisdodd_64 ║ 6 ║ 1 ║ 1 ║ 2 ║ 0 ║ 0 ║ 2 ║ ║ divide_chris_64 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ ║ divide_weather_64 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ 0 ║ ╚══════════════════════════╩═══════╩════╩════╩════╩════╩════╩════╝

Aquí, cada prueba se denomina como XY, con X en {Latencia, Rendimiento} e Y en {Constante Q, Invariante Q, Variable Q}. Entonces, por ejemplo, LC es "Prueba de latencia con constante q".

Análisis

En el nivel más alto, las soluciones pueden dividirse aproximadamente en dos categorías: rápido (los 6 primeros clasificados) y lento (los dos inferiores). La diferencia es mayor: todos los algoritmos rápidos fueron los más rápidos en al menos dos subpruebas y, en general, cuando no terminaron primero, cayeron en la categoría "suficientemente cerca" (solo las excepciones son las vectorizaciones fallidas en el caso de stoke y chrisdodd ). Sin embargo, los algoritmos lentos obtuvieron un puntaje de 0 (ni siquiera cerca) en cada prueba. Así que en su mayoría puedes eliminar los algoritmos lentos de una mayor consideración.

Auto-vectorización

Entre los algoritmos rápidos , un gran diferenciador fue la capacidad de auto-vectorize .

Ninguno de los algoritmos fue capaz de auto-vectorizar en las pruebas de latencia, lo que tiene sentido, ya que las pruebas de latencia están diseñadas para enviar su resultado directamente a la siguiente iteración. Así que realmente solo se pueden calcular los resultados de forma serial.

Para las pruebas de rendimiento, sin embargo, muchos algoritmos fueron capaces de auto-vectorizar para el caso de Q constante y Q invariante . En ambas pruebas, el divisor q es invariante de bucle (y en el primer caso es una constante de compilación). El dividendo es el contador de bucle, por lo que es variable, pero predecible (y en particular un vector de dividendos se puede calcular de manera trivial sumando 8 al vector de entrada anterior: [0, 1, 2, ..., 7] + [8, 8, ..., 8] == [8, 9, 10, ..., 15] ).

En este escenario, gcc pudo vectorizar peter , stoke , chux , user23 y user23_variant . No fue capaz de vectorizar chrisdodd por alguna razón, probablemente porque incluía una rama (pero los condicionales no previenen estrictamente la vectorización, ya que muchas otras soluciones tienen elementos condicionales pero aún vectorizados). El impacto fue enorme: los algoritmos vectorizados mostraron una mejora de 8x en el rendimiento sobre las variantes que no lo eran, pero que por lo demás eran rápidas.

Sin embargo, la vectorización no es gratis! Aquí están los tamaños de función para la variante "constante" de cada función, con el Vec? Columna que muestra si una función vectorizada o no:

Size Vec? Name 045 N bench_c_div_stoke_64 049 N bench_c_divide_chrisdodd_64 059 N bench_c_stoke32_64 212 Y bench_c_divide_chux_64 227 Y bench_c_divide_peter_64 220 Y bench_c_divide_user23_64 212 Y bench_c_divide_user23_variant_64

La tendencia es clara: las funciones vectorizadas toman aproximadamente 4 veces el tamaño de las no vectorizadas. Esto se debe a que los bucles centrales en sí mismos son más grandes (las instrucciones vectoriales tienden a ser más grandes y hay más de ellas), y porque la configuración del bucle y especialmente el código posterior al bucle es mucho más grande: por ejemplo, la versión vectorizada requiere una reducción de Suma todas las sumas parciales en un vector. El recuento de bucles es fijo y un múltiplo de 8, por lo que no se genera ningún código de cola, pero si fuera variable, el código generado sería aún mayor.

Además, a pesar de la gran mejora en el tiempo de ejecución, la vectorización de gcc es realmente pobre. Aquí hay un extracto de la versión vectorizada de la rutina de Peter:

on entry: ymm4 == all zeros on entry: ymm5 == 0x00000001 0x00000001 0x00000001 ... 4007a4: c5 ed 76 c4 vpcmpeqd ymm0,ymm2,ymm4 4007ad: c5 fd df c5 vpandn ymm0,ymm0,ymm5 4007b1: c5 dd fa c0 vpsubd ymm0,ymm4,ymm0 4007b5: c5 f5 db c0 vpand ymm0,ymm1,ymm0

Este fragmento funciona de forma independiente en 8 elementos DWORD originados en ymm2 . Si tomamos x como un único elemento DWORD de ymm2 , y y el valor entrante de ymm1 estas instrucciones de foud corresponden a:

x == 0 x != 0 x = x ? 0 : -1; // -1 0 x = x & 1; // 1 0 x = 0 - x; // -1 0 x = y1 & x; // y1 0

Así que las primeras tres instrucciones podrían ser reemplazadas por la primera, ya que los estados son idénticos en ambos casos. Entonces, eso es dos ciclos agregados a esa cadena de dependencia (que no se lleva en bucle) y dos uops adicionales. Evidentemente, las fases de optimización de gcc alguna manera interactúan pobremente con el código de vectorización aquí, ya que tales optimizaciones triviales rara vez se pasan por alto en el código escalar. El examen de las otras versiones vectorizadas muestra de manera similar una gran cantidad de rendimiento caído en el suelo.

Ramas vs Ramas libres

Casi todas las soluciones compiladas en código sin sucursales, incluso si el código C tenía condicionales o ramas explícitas. Las partes condicionales eran lo suficientemente pequeñas como para que el compilador generalmente decidiera usar el movimiento condicional o alguna variante. Una excepción es chrisdodd que compiló con una rama (verificando si p == 0 ) en todas las pruebas de rendimiento, pero ninguna de las de latencia. Este es un ejemplo típico de la prueba de rendimiento q constante :

0000000000400e60 <bench_c_divide_chrisdodd_32>: 400e60: 89 f8 mov eax,edi 400e62: ba 01 00 00 00 mov edx,0x1 400e67: eb 0a jmp 400e73 <bench_c_divide_chrisdodd_32+0x13> 400e69: 0f 1f 80 00 00 00 00 nop DWORD PTR [rax+0x0] 400e70: 83 c2 01 add edx,0x1 400e73: 83 fa 01 cmp edx,0x1 400e76: 74 f8 je 400e70 <bench_c_divide_chrisdodd_32+0x10> 400e78: 8d 4a fe lea ecx,[rdx-0x2] 400e7b: c1 e9 03 shr ecx,0x3 400e7e: 8d 44 08 01 lea eax,[rax+rcx*1+0x1] 400e82: 81 fa 00 ca 9a 3b cmp edx,0x3b9aca00 400e88: 75 e6 jne 400e70 <bench_c_divide_chrisdodd_32+0x10> 400e8a: c3 ret 400e8b: 0f 1f 44 00 00 nop DWORD PTR [rax+rax*1+0x0]

La rama en 400e76 omite el caso que p == 0 . De hecho, el compilador podría haber despegado la primera iteración (calculando su resultado explícitamente) y luego evitar el salto por completo, ya que después de eso puede probar que p != 0 . En estas pruebas, la rama es perfectamente predecible, lo que podría dar una ventaja al código que realmente compila utilizando una rama (ya que el código de comparación y rama está esencialmente fuera de línea y casi gratis), y es una gran parte de por qué chrisdodd gana El rendimiento, variable q caso.

Resultados detallados de la prueba

Aquí puede encontrar algunos resultados de pruebas detallados y algunos detalles sobre las pruebas en sí.

Estado latente

Los resultados a continuación prueban cada algoritmo durante 1e9 iteraciones. Los ciclos se calculan simplemente multiplicando la hora / llamada por la frecuencia de reloj. En general, puede suponer que algo como 4.01 es lo mismo que 4.00 , pero las desviaciones más grandes como 5.11 parecen ser reales y reproducibles.

Los resultados para divide_plusq_32 usan (p + q - 1) >> lg(q) pero solo se muestran como referencia, ya que esta función falla para p + q grande. Los resultados para el dummy son una función muy simple: return p + q , y le permite estimar la sobrecarga de referencia ⁵ (la adición en sí debe tomar un ciclo como máximo).

============================== Bench: Compile-time constant Q ============================== Function ns/call cycles divide_peter_32 2.19 5.67 divide_peter_64 2.18 5.64 stoke32_32 1.93 5.00 stoke32_64 1.97 5.09 stoke_mul_32 2.75 7.13 stoke_mul_64 2.34 6.06 div_stoke_32 1.94 5.03 div_stoke_64 1.94 5.03 divide_chux_32 1.55 4.01 divide_chux_64 1.55 4.01 divide_user23_32 1.97 5.11 divide_user23_64 1.93 5.00 divide_user23_variant_32 1.55 4.01 divide_user23_variant_64 1.55 4.01 divide_chrisdodd_32 1.95 5.04 divide_chrisdodd_64 1.93 5.00 divide_chris_32 4.63 11.99 divide_chris_64 4.52 11.72 divide_weather_32 2.72 7.04 divide_weather_64 2.78 7.20 divide_plusq_32 1.16 3.00 divide_plusq_64 1.16 3.00 divide_dummy_32 1.16 3.00 divide_dummy_64 1.16 3.00 ============================== Bench: Invariant Q ============================== Function ns/call cycles divide_peter_32 2.19 5.67 divide_peter_64 2.18 5.65 stoke32_32 1.93 5.00 stoke32_64 1.93 5.00 stoke_mul_32 2.73 7.08 stoke_mul_64 2.34 6.06 div_stoke_32 1.93 5.00 div_stoke_64 1.93 5.00 divide_chux_32 1.55 4.02 divide_chux_64 1.55 4.02 divide_user23_32 1.95 5.05 divide_user23_64 2.00 5.17 divide_user23_variant_32 1.55 4.02 divide_user23_variant_64 1.55 4.02 divide_chrisdodd_32 1.95 5.04 divide_chrisdodd_64 1.93 4.99 divide_chris_32 4.60 11.91 divide_chris_64 4.58 11.85 divide_weather_32 12.54 32.49 divide_weather_64 17.51 45.35 divide_plusq_32 1.16 3.00 divide_plusq_64 1.16 3.00 divide_dummy_32 0.39 1.00 divide_dummy_64 0.39 1.00 ============================== Bench: Variable Q ============================== Function ns/call cycles divide_peter_32 2.31 5.98 divide_peter_64 2.26 5.86 stoke32_32 2.06 5.33 stoke32_64 1.99 5.16 stoke_mul_32 2.73 7.06 stoke_mul_64 2.32 6.00 div_stoke_32 2.00 5.19 div_stoke_64 2.00 5.19 divide_chux_32 2.04 5.28 divide_chux_64 2.05 5.30 divide_user23_32 2.05 5.30 divide_user23_64 2.06 5.33 divide_user23_variant_32 2.04 5.29 divide_user23_variant_64 2.05 5.30 divide_chrisdodd_32 2.04 5.30 divide_chrisdodd_64 2.05 5.31 divide_chris_32 4.65 12.04 divide_chris_64 4.64 12.01 divide_weather_32 12.46 32.28 divide_weather_64 19.46 50.40 divide_plusq_32 1.93 5.00 divide_plusq_64 1.99 5.16 divide_dummy_32 0.40 1.05 divide_dummy_64 0.40 1.04

Rendimiento

Aquí están los resultados de las pruebas de rendimiento. Tenga en cuenta que muchos de los algoritmos aquí fueron auto-vectorizados, por lo que el rendimiento es relativamente bueno para ellos: una fracción de un ciclo en muchos casos. Un resultado es que, a diferencia de la mayoría de los resultados de latencia, las funciones de 64 bits son considerablemente más lentas, ya que la vectorización es más efectiva con tamaños de elementos más pequeños (aunque la brecha es más grande de lo que hubiera esperado).

============================== Bench: Compile-time constant Q ============================== Function ns/call cycles stoke32_32 0.39 1.00 divide_chux_32 0.15 0.39 divide_chux_64 0.53 1.37 divide_user23_32 0.14 0.36 divide_user23_64 0.53 1.37 divide_user23_variant_32 0.15 0.39 divide_user23_variant_64 0.53 1.37 divide_chrisdodd_32 1.16 3.00 divide_chrisdodd_64 1.16 3.00 divide_chris_32 4.34 11.23 divide_chris_64 4.34 11.24 divide_weather_32 1.35 3.50 divide_weather_64 1.35 3.50 divide_plusq_32 0.10 0.26 divide_plusq_64 0.39 1.00 divide_dummy_32 0.08 0.20 divide_dummy_64 0.39 1.00 ============================== Bench: Invariant Q ============================== Function ns/call cycles stoke32_32 0.48 1.25 divide_chux_32 0.15 0.39 divide_chux_64 0.48 1.25 divide_user23_32 0.17 0.43 divide_user23_64 0.58 1.50 divide_user23_variant_32 0.15 0.38 divide_user23_variant_64 0.48 1.25 divide_chrisdodd_32 1.16 3.00 divide_chrisdodd_64 1.16 3.00 divide_chris_32 4.35 11.26 divide_chris_64 4.36 11.28 divide_weather_32 5.79 14.99 divide_weather_64 17.00 44.02 divide_plusq_32 0.12 0.31 divide_plusq_64 0.48 1.25 divide_dummy_32 0.09 0.23 divide_dummy_64 0.09 0.23 ============================== Bench: Variable Q ============================== Function ns/call cycles stoke32_32 1.16 3.00 divide_chux_32 1.36 3.51 divide_chux_64 1.35 3.50 divide_user23_32 1.54 4.00 divide_user23_64 1.54 4.00 divide_user23_variant_32 1.36 3.51 divide_user23_variant_64 1.55 4.01 divide_chrisdodd_32 1.16 3.00 divide_chrisdodd_64 1.16 3.00 divide_chris_32 4.02 10.41 divide_chris_64 3.84 9.95 divide_weather_32 5.40 13.98 divide_weather_64 19.04 49.30 divide_plusq_32 1.03 2.66 divide_plusq_64 1.03 2.68 divide_dummy_32 0.63 1.63 divide_dummy_64 0.66 1.71

^a Al menos al especificar sin firmar , evitamos la totalidad de latas de gusanos relacionados con el comportamiento a la derecha de los enteros con signo en C y C ++.

⁰ Por supuesto, esta notación no funciona realmente en C, donde / trunca el resultado, por lo que el ceiling no hace nada. Así que considera que la pseudo-notación en lugar de C. recta

¹ También me interesan las soluciones donde todos los tipos son uint32_t lugar de uint64_t .

² En general, cualquier p y q donde p + q >= 2^64 causa un problema, debido al desbordamiento.

³ Dicho esto, la función debe estar en un bucle, porque el rendimiento de una función microscópica que toma media docena de ciclos solo importa si se llama en un bucle bastante estrecho.

⁴ Esto es un poco simplificado: solo el dividendo p depende de la salida de la iteración anterior, por lo que algunos trabajos relacionados con el procesamiento de q todavía pueden superponerse.

⁵ Utilice estas estimaciones con precaución, sin embargo, los gastos generales no son simplemente aditivos. Si la sobrecarga aparece como 4 ciclos y alguna función f toma 5, es probable que no sea exacto decir que el costo del trabajo real en f es 5 - 4 == 1 , debido a la forma en que se superpone la ejecución.

Esta respuesta es sobre lo que es ideal en asm; Lo que nos gustaría convencer al compilador de emitir para nosotros. (No estoy sugiriendo usar realmente asm en línea, excepto como un punto de comparación cuando se realiza una evaluación comparativa de la salida del compilador. https://gcc.gnu.org/wiki/DontUseInlineAsm ).

ceil_div_andmask obtener una salida de ceil_div_andmask bastante buena de C puro para ceil_div_andmask , ver más abajo. (Es peor que un CMOV en Broadwell / Skylake, pero probablemente sea bueno en Haswell. Sin embargo, la versión de user23 / chux se ve aún mejor para ambos casos). Vale la pena mencionarlo como uno de los pocos casos en los que obtuve el compilador. El asm que quería.

Parece que la idea general de return ((p-1) >> lg(q)) + 1 de Chris Dodd return ((p-1) >> lg(q)) + 1 con manejo de casos especiales para d = 0 es una de las mejores opciones. Es decir, la implementación óptima de esta en asm es difícil de superar con una implementación óptima de cualquier otra cosa. Chux''s (p >> lg(q)) + (bool)(p & (q-1)) también tiene ventajas (como menor latencia de p-> resultado), y más CSE cuando se usa el mismo q para múltiples divisiones. Vea a continuación un análisis de latencia / rendimiento de lo que gcc hace con él.

Si el mismo e = lg(q) se reutiliza para múltiples dividendos, o el mismo dividendo se reutiliza para múltiples divisores, diferentes implementaciones pueden CSE más de la expresión. También pueden vectorizar efectivamente con AVX2 .

Las ramas son baratas y muy eficientes si predicen muy bien , por lo que bifurcarse en d==0 será mejor si casi nunca se toma. Si d==0 no es raro, asm sin ramas tendrá un mejor desempeño en promedio. Lo ideal es escribir algo en C que permita a gcc tomar la decisión correcta durante la optimización guiada por el perfil, y compilar a buen nivel para cualquier caso.

Dado que las mejores implementaciones de asm sin sucursales no agregan mucha latencia en comparación con las implementaciones de ramificaciones, probablemente las ramificaciones sean el camino a seguir, a menos que la ramificación se realice de la misma manera, tal vez el 99% del tiempo. Esto podría ser probable para la bifurcación en p==0 , pero probablemente menos para la bifurcación en p & (q-1) .

Es difícil guiar a gcc5.4 para que emita algo óptimo. Este es mi trabajo en progreso en Godbolt ).

Creo que las secuencias óptimas para Skylake para este algoritmo son las siguientes. (Se muestran como funciones independientes para AMD64 SysV ABI, pero se habla de rendimiento / latencia en el supuesto de que el compilador emitirá algo similar en línea dentro de un bucle, sin RET adjunto).

Rama en acarreo desde el cálculo de d-1 para detectar d == 0 , en lugar de una prueba y bifurcación separadas. Reduce el conteo de uop muy bien, especialmente en la familia SnB donde JC puede macro-fusionar con SUB.

ceil_div_pjc_branch: xor eax,eax ; can take this uop off the fast path by adding a separate xor-and-return block, but in reality we want to inline something like this. sub rdi, 1 jc .d_was_zero ; fuses with the sub on SnB-family tzcnt rax, rsi ; tzcnt rsi,rsi also avoids any false-dep problems, but this illustrates that the q input can be read-only. shrx rax, rdi, rax inc rax .d_was_zero: ret

Dominios fusionados uops: 5 (sin contar ret), y uno de ellos es un xor-zero (sin unidad de ejecución)
Latencia HSW / SKL con predicción de rama exitosa:
- (d == 0): No hay dependencia de datos en d o q, rompe la cadena de dep . (control de dependencia en d para detectar errores de predicción y retirar la rama).
- (d! = 0): q-> resultado: tzcnt + shrx + inc = 5c
- (d! = 0): d-> resultado: sub + shrx + inc = 3c
Rendimiento: probablemente solo se haya estancado en el rendimiento de uop

He intentado, pero no logré que gcc se bifurque en CF a partir del resta, pero siempre quiere hacer una comparación por separado. Sé que se puede convencer a gcc para que se bifurque en CF después de restar dos variables, pero quizás esto falle si una es una constante de tiempo de compilación. (IIRC, esto típicamente compila una prueba de CF con vars sin firmar: foo -= bar; if(foo>bar) carry_detected = 1; )

Sin sucursales con ADC / SBB para manejar el caso d==0 . El manejo a cero agrega solo una instrucción a la ruta crítica (en comparación con una versión sin manejo especial para d == 0), pero también convierte una otra de un INC a sbb rax, -1 para hacer que CF deshaga el -= -1 . Usar un CMOV es más barato en pre-Broadwell, pero requiere instrucciones adicionales para configurarlo.

ceil_div_pjc_asm_adc: tzcnt rsi, rsi sub rdi, 1 adc rdi, 0 ; d? d-1 : d. Sets CF=CF shrx rax, rdi, rsi sbb rax, -1 ; result++ if d was non-zero ret

Uops de dominio fusionado: 5 (sin contar ret) en SKL. 7 en HSW
Latencia SKL:
- q-> resultado: tzcnt + shrx + sbb = 5c
- d-> resultado: sub + adc + shrx (dep en q comienza aquí) + sbb = 4c
Rendimiento: TZCNT se ejecuta en p1. SBB, ADC y SHRX solo se ejecutan en p06. Así que creo que nos encontramos con un cuello de botella en 3 puntos por p06 por iteración, haciendo que esto se ejecute en la mejor iteración por 1.5c .

Si q y d están listos al mismo tiempo, tenga en cuenta que esta versión puede ejecutar SUB / ADC en paralelo con la latencia 3c de TZCNT. Si ambos proceden de la misma línea de caché de falta de caché, es ciertamente posible. En cualquier caso, la introducción de dep en q lo más tarde posible en la cadena de dependencia d-> result es una ventaja.

Conseguir esto de C parece poco probable con gcc5.4. Hay un intrínseco para agregar-con-llevar, pero gcc hace un gran lío. No utiliza operandos inmediatos para ADC o SBB, y almacena el acarreo en un registro entero entre cada operación. gcc7, clang3.9 e icc17 hacen un código terrible a partir de esto.

#include <x86intrin.h> // compiles to completely horrible code, putting the flags into integer regs between ops. T ceil_div_adc(T d, T q) { T e = lg(q); unsigned long long dm1; // unsigned __int64 unsigned char CF = _addcarry_u64(0, d, -1, &dm1); CF = _addcarry_u64(CF, 0, dm1, &dm1); T shifted = dm1 >> e; _subborrow_u64(CF, shifted, -1, &dm1); return dm1; } # gcc5.4 -O3 -march=haswell mov rax, -1 tzcnt rsi, rsi add rdi, rax setc cl xor edx, edx add cl, -1 adc rdi, rdx setc dl shrx rdi, rdi, rsi add dl, -1 sbb rax, rdi ret

CMOV para arreglar todo el resultado : peor latencia del resultado q->, ya que se usa antes en la cadena de depuración d-> result.

ceil_div_pjc_asm_cmov: tzcnt rsi, rsi sub rdi, 1 shrx rax, rdi, rsi lea rax, [rax+1] ; inc preserving flags cmovc rax, zeroed_register ret

Uops de dominio fusionado: 5 (sin contar ret) en SKL. 6 en HSW
Latencia SKL:
- q-> resultado: tzcnt + shrx + lea + cmov = 6c (peor que ADC / SBB por 1c)
- d-> resultado: sub + shrx (dep en q comienza aquí) + lea + cmov = 4c
Rendimiento: TZCNT se ejecuta en p1. LEA es p15. CMOV y SHRX son p06. SUB es p0156. En teoría, solo se produce un cuello de botella en el rendimiento de uop de dominio fusionado, por lo que una iteración por 1.25c . Con muchas operaciones independientes, los conflictos de recursos del robo de SUB o LEA p1 o p06 no deberían ser un problema de rendimiento porque en 1 iter por 1.25c, ningún puerto está saturado con uops que solo pueden ejecutarse en ese puerto.

CMOV para obtener un operando para SUB : Esperaba poder encontrar una manera de crear un operando para una instrucción posterior que generaría un cero cuando fuera necesario, sin una dependencia de entrada en q, e, o el resultado de SHRX. Esto ayudaría si d está listo antes de q , o al mismo tiempo.

Esto no logra ese objetivo, y necesita un mov rdx,-1 adicional de 7 bytes mov rdx,-1 en el bucle.

ceil_div_pjc_asm_cmov: tzcnt rsi, rsi mov rdx, -1 sub rdi, 1 shrx rax, rdi, rsi cmovnc rdx, rax sub rax, rdx ; res += d ? 1 : -res ret

Versión de menor latencia para CPU anteriores a BDW con CMOV costoso , utilizando SETCC para crear una máscara para AND.

ceil_div_pjc_asm_setcc: xor edx, edx ; needed every iteration tzcnt rsi, rsi sub rdi, 1 setc dl ; d!=0 ? 0 : 1 dec rdx ; d!=0 ? -1 : 0 // AND-mask shrx rax, rdi, rsi inc rax and rax, rdx ; zero the bogus result if d was initially 0 ret

Todavía 4c de latencia desde d-> resultado (y 6 desde q-> resultado), porque SETC / DEC sucede en paralelo con SHRX / INC. Cantidad total de uop: 8. La mayoría de estas insns pueden ejecutarse en cualquier puerto, por lo que debe ser de 1 iter por 2 relojes.

Por supuesto, para pre-HSW, también necesita reemplazar SHRX.

Podemos hacer que gcc5.4 emita algo casi igual de bueno: (aún usa una PRUEBA por separado en lugar de establecer una máscara basada en sub rdi, 1 , pero por lo demás las mismas instrucciones que antes). Véalo en Godbolt .

T ceil_div_andmask(T p, T q) { T mask = -(T)(p!=0); // TEST+SETCC+NEG T e = lg(q); T nonzero_result = ((p-1) >> e) + 1; return nonzero_result & mask; }

Cuando el compilador sabe que p es distinto de cero, toma ventaja y crea un buen código:

// http://.com/questions/40447195/can-i-hint-the-optimizer-by-giving-the-range-of-an-integer #if defined(__GNUC__) && !defined(__INTEL_COMPILER) #define assume(x) do{if(!(x)) __builtin_unreachable();}while(0) #else #define assume(x) (void)(x) // still evaluate it once, for side effects in case anyone is insane enough to put any inside an assume() #endif T ceil_div_andmask_nonzerop(T p, T q) { assume(p!=0); return ceil_div_andmask(p, q); } # gcc5.4 -O3 -march=haswell xor eax, eax # gcc7 does tzcnt in-place instead of wasting an insn on this sub rdi, 1 tzcnt rax, rsi shrx rax, rdi, rax add rax, 1 ret

Chux / user23_variant

solo 3c de latencia desde p-> resultado, y constante q puede CSE mucho.

T divide_A_chux(T p, T q) { bool round_up = p & (q-1); // compiles differently from user23_variant with clang: AND instead of return (p >> lg(q)) + round_up; } xor eax, eax # in-place tzcnt would save this xor edx, edx # target for setcc tzcnt rax, rsi sub rsi, 1 test rsi, rdi shrx rdi, rdi, rax setne dl lea rax, [rdx+rdi] ret

Hacer el SETCC antes de TZCNT permitiría un TZCNT en el lugar, guardando el xor eax,eax . No he visto cómo esto se alinea en un bucle.

Uops de dominio fusionado: 8 (sin contar ret) en HSW / SKL
Latencia HSW / SKL:
- q-> resultado: (tzcnt + shrx (p) | sub + test (p) + setne) + lea (o add) = 5c
- d-> resultado: prueba (dep q comienza aquí) + setne + lea = 3c . (la cadena shrx-> lea es más corta, y por lo tanto no es la ruta crítica)
Rendimiento: Probablemente solo haya un cuello de botella en la interfaz, en un iter por 2c . Guardar el xor eax,eaxdebería acelerar esto hasta uno por 1.75c (pero, por supuesto, cualquier sobrecarga de bucle será parte del cuello de botella, porque los cuellos de botella frontend son así).

Esto parece eficiente y funciona para los firmados si su compilador usa cambios aritméticos a la derecha (generalmente cierto).

#include <stdio.h> int main (void) { for (int i = -20; i <= 20; ++i) { printf ("%5d %5d/n", i, ((i - 1) >> 1) + 1); } return 0; }

Use >> 2para dividir por 4, >> 3para dividir por 8, y ct. Eficiente lghace el trabajo allí.

Incluso puedes dividir por 1! >> 0

La manera eficiente de dividir por una potencia de 2 para un entero sin signo en C es un cambio a la derecha: desplazando la derecha una división por dos (redondeando hacia abajo), así que cambiando a la derecha por n divide por 2 ⁿ (redondeando hacia abajo).

Ahora desea redondear hacia arriba en lugar de hacia abajo, lo que puede hacer sumando primero 2 ⁿ -1, o restando uno antes del turno y agregando uno después (excepto 0). Esto funciona para algo como:

unsigned ceil_div(unsigned d, unsigned e) { /* compute ceil(d/2**e) */ return d ? ((d-1) >> e) + 1 : 0; }

El condicional se puede eliminar utilizando el valor booleano de d para la suma y resta de uno:

unsigned ceil_div(unsigned d, unsigned e) { /* compute ceil(d/2**e) */ return ((d - !!d) >> e) + !!d; }

Debido a su tamaño y al requisito de velocidad, la función debe hacerse estática en línea. Probablemente no hará una diferencia para el optimizador, pero los parámetros deberían ser constantes. Si debe compartirse entre muchos archivos, defínalo en un encabezado:

static inline unsigned ceil_div(const unsigned d, const unsigned e){...

Mi antigua respuesta no funcionó si pera una más que una potencia de dos (gritos). Así que mi nueva solución, utilizando las funciones __builtin_ctzll()y ⁰ disponibles en (lo cual, como un bono, proporciona el logaritmo rápido que mencionó):__builtin_ffsll()gcc

uint64_t divide(uint64_t p,uint64_t q) { int lp=__builtin_ffsll(p); int lq=__builtin_ctzll(q); return (p>>lq)+(lp<(lq+1)&&lp); }

Tenga en cuenta que esto se supone que a long longes de 64 bits. De lo contrario hay que modificarlo un poco.

La idea aquí es que si necesitamos un desbordamiento si y solo si ptiene menos ceros al final q. Tenga en cuenta que para una potencia de dos, el número de ceros finales es igual al logaritmo, por lo que también podemos utilizar esta función incorporada para el registro.

La &&lpparte es solo para el caso de la esquina donde pes cero: de lo contrario, se mostrará 1aquí.

⁰ No se puede usar __builtin_ctzll()para ambos porque no está definido si p==0.

Puedes hacerlo de esta manera, comparando dividiendo n / dcon dividiendo por (n-1) / d.

#include <stdio.h> int main(void) { unsigned n; unsigned d; unsigned q1, q2; double actual; for(n = 1; n < 6; n++) { for(d = 1; d < 6; d++) { actual = (double)n / d; q1 = n / d; if(n) { q2 = (n - 1) / d; if(q1 == q2) { q1++; } } printf("%u / %u = %u (%f)/n", n, d, q1, actual); } } return 0; }

Salida del programa:

1 / 1 = 1 (1.000000) 1 / 2 = 1 (0.500000) 1 / 3 = 1 (0.333333) 1 / 4 = 1 (0.250000) 1 / 5 = 1 (0.200000) 2 / 1 = 2 (2.000000) 2 / 2 = 1 (1.000000) 2 / 3 = 1 (0.666667) 2 / 4 = 1 (0.500000) 2 / 5 = 1 (0.400000) 3 / 1 = 3 (3.000000) 3 / 2 = 2 (1.500000) 3 / 3 = 1 (1.000000) 3 / 4 = 1 (0.750000) 3 / 5 = 1 (0.600000) 4 / 1 = 4 (4.000000) 4 / 2 = 2 (2.000000) 4 / 3 = 2 (1.333333) 4 / 4 = 1 (1.000000) 4 / 5 = 1 (0.800000) 5 / 1 = 5 (5.000000) 5 / 2 = 3 (2.500000) 5 / 3 = 2 (1.666667) 5 / 4 = 2 (1.250000) 5 / 5 = 1 (1.000000)

Actualizar

Publiqué una respuesta temprana a la pregunta original, que funciona, pero no consideré la eficiencia del algoritmo, o que el divisor es siempre una potencia de 2. Realizar dos divisiones era innecesariamente caro.

Estoy utilizando el compilador MSVC de 32 bits en un sistema de 64 bits, por lo que no hay ninguna posibilidad de que pueda proporcionar una mejor solución para el objetivo requerido. Pero es una pregunta interesante, así que he investigado para encontrar que la mejor solución descubrirá el bit del divisor 2 ** n. Usar la función de biblioteca log2funcionó pero fue muy lento. Hacer mi propio turno fue mucho mejor, pero mi mejor solución para C es

unsigned roundup(unsigned p, unsigned q) { return p / q + ((p & (q-1)) != 0); }

Mi solución de ensamblador en línea de 32 bits es más rápida, pero por supuesto eso no responderá la pregunta. Robo algunos ciclos asumiendo que eaxse devuelve como el valor de la función.

unsigned roundup(unsigned p, unsigned q) { __asm { mov eax,p mov edx,q bsr ecx,edx ; cl = bit number of q dec edx ; q-1 and edx,eax ; p & (q-1) shr eax,cl ; divide p by q, a power of 2 sub edx,1 ; generate a carry when (p & (q-1)) == 0 cmc adc eax,0 ; add 1 to result when (p & (q-1)) != 0 } } ; eax returned as function value

Si se puede garantizar que el dividendo / divisor no exceda los 63 (o 31) bits, puede usar la siguiente versión mencionada en la pregunta. Observe cómo p + q podría desbordarse si usan todos los 64 bits. Esto estaría bien si la instrucción SHR cambiara en la bandera de acarreo, pero AFAIK no.

uint64_t divide(uint64_t p, uint64_t q) { return (p + q - 1) >> lg(q); }

Si esas restricciones no se pueden garantizar, solo puede hacer el método de piso y luego agregar 1 si se redondea. Esto puede determinarse verificando si algún bit en el dividendo está dentro del rango del divisor. Nota: p & -p extrae el bit de conjunto más bajo en las máquinas del complemento 2s o la instrucción BLSI

uint64_t divide(uint64_t p, uint64_t q) { return (p >> lg(q)) + ( (p & -p ) < q ); }

Que clang compila para:

bsrq %rax, %rsi shrxq %rax, %rdi, %rax blsiq %rdi, %rcx cmpq %rsi, %rcx adcq $0, %rax retq

Eso es un poco prolijo y usa algunas instrucciones más nuevas, así que quizás haya una manera de usar la bandera de acarreo en la versión original. A ver: la instrucción RCRhace pero parece que sería peor ... tal vez la instrucción SHRD ... Sería algo como esto (no se puede probar en este momento)

xor edx, edx ;edx = 0 (will store the carry flag) bsr rcx, rsi ;rcx = lg(q) ... could be moved anywhere before shrd lea rax, [rsi-1] ;rax = q-1 (adding p could carry) add rax, rdi ;rax += p (handle carry) setc dl ;rdx = carry flag ... or xor rdx and setc shrd rax, rdx, cl ;rax = rdx:rax >> cl ret

1 instrucción más, pero debería ser compatible con procesadores más antiguos (si funciona ... Siempre se intercambia una fuente / destino, siéntase libre de editar)

Apéndice:

He implementado la función lg () que dije que estaba disponible de la siguiente manera:
inline uint64_t lg(uint64_t x) { return 63U - (uint64_t)__builtin_clzl(x); } inline uint32_t lg32(uint32_t x) { return 31U - (uint32_t)__builtin_clz(x); }

Las funciones de registro rápido no se optimizan completamente para bsr en clang y ICC, pero puedes hacer esto:

#if defined(__x86_64__) && (defined(__clang__) || defined(__INTEL_COMPILER)) static inline uint64_t lg(uint64_t x){ inline uint64_t ret; //other compilers may want bsrq here __asm__("bsr %0, %1":"=r"(ret):"r"(x)); return ret; } #endif #if defined(__i386__) && (defined(__clang__) || defined(__INTEL_COMPILER)) static inline uint32_t lg32(uint32_t x){ inline uint32_t ret; __asm__("bsr %0, %1":"=r"(ret):"r"(x)); return ret; } #endif

Ya se ha aplicado una gran cantidad de capacidad mental humana a este problema, con varias variantes de grandes respuestas Cjunto con la respuesta de Peter Cordes que cubre lo mejor que podría esperar en asm, con notas sobre cómo intentar mapearlo de nuevo C.

Así que, mientras los humanos se dan una patada en la lata, ¡pensé que vería lo que un poco de poder informático tiene que decir! Para ello, utilicé el superoptimizador STOKE Stanford para intentar encontrar buenas soluciones para las versiones de 32 y 64 bits de este problema.

Por lo general, un superoptimizer suele ser algo así como una búsqueda de fuerza bruta a través de todas las secuencias de instrucciones posibles hasta que encuentre la mejor por alguna métrica. Por supuesto, con algo así como 1,000 instrucciones que rápidamente se saldrán de control por más de unas pocas instrucciones ¹ . STOKE, por un lado, toma un enfoque aleatorio guiado: realiza mutaciones al azar a un programa candidato existente, evaluando en cada paso una función de costo que tiene en cuenta tanto el rendimiento como la corrección. De todos modos, esa es la de una sola línea: hay muchos papeles si eso avivó tu curiosidad.

Así que en unos pocos minutos STOKE encontró algunas soluciones bastante interesantes. Encontró casi todas las ideas de alto nivel en las soluciones existentes, además de algunas únicas. Por ejemplo, para la función de 32 bits, STOKE encontró esta versión:

neg rsi dec rdi pext rax, rsi, rdi inc eax ret

No usa ninguna cuenta de avance / final-cero o instrucciones de cambio. Más o menos, se utiliza neg esipara convertir el divisor en una máscara con 1s en los bits altos, y luego pexthace el cambio efectivamente utilizando esa máscara. Fuera de ese truco se trata de utilizar el mismo truco que el usuario QuestionC utilizado: decremento p, cambio, incremento p - pero sucede que trabajar aún más para el cero de dividendos, ya que utiliza 64 bits registra para distinguir el caso cero de la gran set-MSB pcaso .

Agregué la versión C de este algoritmo al punto de referencia y lo agregué a los resultados. Es competitivo con los otros buenos algoritmos, empatando primero en los casos de "Variable Q". Se vectoriza, pero no tan bien como los otros algoritmos de 32 bits, ya que necesita matemática de 64 bits y, por lo tanto, los vectores pueden procesar solo la mitad de los elementos a la vez.

Aún mejor, en el caso de 32 bits surgió una variedad de soluciones que utilizan el hecho de que algunas de las soluciones intuitivas que fallan en los casos perimetrales "simplemente funcionan" si utiliza operaciones de 64 bits para una parte. Por ejemplo:

tzcntl ebp, esi dec esi add rdi, rsi sarx rax, rdi, rbp ret

Eso es el equivalente a la return (p + q - 1) >> lg(q)sugerencia que mencioné en la pregunta. Eso no funciona en general ya que para grandes p + qdesborda, pero para 32 bits py qesta solución funciona muy bien al hacer las partes importantes en 64 bits. Conviértalo de nuevo a C con algunos lanzamientos y realmente se da cuenta de que usarlo leahará la suma en una instrucción ¹ :

stoke_32(unsigned int, unsigned int): tzcnt edx, esi mov edi, edi ; goes away when inlining mov esi, esi ; goes away when inlining lea rax, [rsi-1+rdi] shrx rax, rax, rdx ret

Así que es una solución de 3 instrucciones cuando está en línea en algo que ya tiene los valores extendidos en cero en rdiy rsi. La definición de la función independiente necesita las movinstrucciones para extender en cero porque así es como funciona la ABI SysV x64 .

Para la función de 64 bits, no se presentó nada que supere las soluciones existentes, pero sí con algunas cosas interesantes, como:

tzcnt r13, rsi tzcnt rcx, rdi shrx rax, rdi, r13 cmp r13b, cl adc rax, 0 ret

Ese tipo cuenta los ceros finales de ambos argumentos, y luego agrega 1 al resultado si qtiene menos ceros finales p, ya que es cuando necesitas redondear. ¡Inteligente!

En general, se entiende la idea que tenías que shlpor el tzcntmuy rápido (al igual que la mayoría de los seres humanos) y luego se le ocurrió una tonelada de otras soluciones al problema de ajustar el resultado de dar cuenta de redondeo. Incluso logró usar blsiy bzhien varias soluciones. Aquí hay una solución de 5 instrucciones que se le ocurrió:

tzcnt r13, rsi shrx rax, rdi, r13 imul rsi, rax cmp rsi, rdi adc rax, 0 ret

Es básicamente un "multiplicar y verificar" enfoque - tomar el tronco res = p / q, se multiplica de nuevo y si es diferente a pla tuya: return res * q == p ? ret : ret + 1. Guay. Aunque no es realmente mejor que las soluciones de Peter. STOKE parece tener algunas fallas en su cálculo de latencia (piensa que lo anterior tiene una latencia de 5), pero es más como 8 o 9 según la arquitectura. Por lo tanto, a veces se reduce en soluciones que se basan en su cálculo de latencia defectuoso.

¹ Curiosamente, aunque este enfoque de fuerza bruta alcanza su factibilidad alrededor de 5-6 instrucciones: si asume que puede recortar el número de instrucciones para decir 300 eliminando las instrucciones SIMD y x87, entonces necesitará ~ 28 días para probar las 300 ^ 55 secuencias de instrucciones 1.000.000 candidatos / segundo. Tal vez podría reducir eso en un factor de 1,000 con varias optimizaciones, lo que significa menos de una hora para las secuencias de 5 instrucciones y tal vez una semana para las 6 instrucciones. A medida que sucede, la mayoría de las mejores soluciones para este problema caen en esa ventana de instrucciones 5-6 ...

² Sin embargo, esto será lentolea , por lo que la secuencia encontrada por STOKE aún era óptima para lo que optimicé, que era la latencia.

uint64_t exponent = lg(q); uint64_t mask = q - 1; // v divide return (p >> exponent) + (((p & mask) + mask) >> exponent) // ^ round up

El cálculo por separado de la parte de "redondeo" evita los problemas de desbordamiento de (p+q-1) >> lg(q). Dependiendo de qué tan inteligente sea su compilador, podría ser posible expresar la parte de "redondeo" como ((p & mask) != 0)sin bifurcar.