Código de C ++ para probar la conjetura de Collatz más rápido que el ensamblaje escrito a mano: ¿por qué?

Escribí estas dos soluciones para Project Euler Q14 , en ensamblaje y en C ++. Son el mismo enfoque idéntico de fuerza bruta para probar la conjetura de Collatz . La solución de ensamblaje se ensambló con

nasm -felf64 p14.asm && gcc p14.o -o p14 

El C ++ fue comstackdo con

 g++ p14.cpp -o p14 

Asamblea, p14.asm

 section .data fmt db "%d", 10, 0 global main extern printf section .text main: mov rcx, 1000000 xor rdi, rdi ; max i xor rsi, rsi ; i l1: dec rcx xor r10, r10 ; count mov rax, rcx l2: test rax, 1 jpe even mov rbx, 3 mul rbx inc rax jmp c1 even: mov rbx, 2 xor rdx, rdx div rbx c1: inc r10 cmp rax, 1 jne l2 cmp rdi, r10 cmovl rdi, r10 cmovl rsi, rcx cmp rcx, 2 jne l1 mov rdi, fmt xor rax, rax call printf ret 

C ++, p14.cpp

 #include  using namespace std; int sequence(long n) { int count = 1; while (n != 1) { if (n % 2 == 0) n /= 2; else n = n*3 + 1; ++count; } return count; } int main() { int max = 0, maxi; for (int i = 999999; i > 0; --i) { int s = sequence(i); if (s > max) { max = s; maxi = i; } } cout << maxi << endl; } 

Conozco las optimizaciones del comstackdor para mejorar la velocidad y todo, pero no veo muchas maneras de optimizar aún más mi solución de ensamblaje (hablando programáticamente, no matemáticamente).

El código C ++ tiene el módulo de cada término y división en cualquier término par, donde el ensamblaje es solo una división por trimestre.

Pero el ensamblaje tarda en promedio 1 segundo más que la solución C ++. ¿Por qué es esto? Lo pido principalmente por curiosidad.

Tiempos de ejecución

Mi sistema: 64 bit Linux en 1.4 GHz Intel Celeron 2955U (microarchitecture Haswell).

  • g++ (no optimizado): prom 1272 ms

  • g++ -O3 avg 578 ms

  • asm original (div) avg 2650 ms

  • Asm (shr) avg 679 ms

  • @johnfound asm , ensamblado con nasm avg 501 ms

  • @hidefromkgb asm avg 200 ms

  • @hidefromkgb asm optimizado por @Peter Cordes avg 145 ms

  • @Veedrac C ++ avg 81 ms con -O3 , 305 ms con -O0

Si crees que una instrucción DIV de 64 bits es una buena forma de dividir por dos, entonces no es de extrañar que la salida de asm del comstackdor -O0 código escrito a mano, incluso con -O0 (comstackción rápida, sin optimización adicional, y almacenar / recargar en la memoria después / antes de cada statement C para que un depurador pueda modificar las variables).

Consulte la guía Optimizing Assembly de Agner Fog para aprender a escribir asm eficiente. También tiene tablas de instrucciones y una guía de microarch para detalles específicos para CPU específicas. Ver también la wiki de la etiqueta x86 para más enlaces perf.

Consulte también esta pregunta más general sobre cómo superar el comstackdor con un asm escrito a mano: ¿el lenguaje ensamblador en línea es más lento que el código nativo de C ++? . TL: DR: sí, si lo haces mal (como esta pregunta).

Por lo general, está bien dejar que el comstackdor haga su trabajo, especialmente si intenta escribir C ++ que puede comstackr de manera eficiente . Además, ¿el ensamblaje es más rápido que los lenguajes comstackdos? . Uno de los enlaces de respuestas a estas diapositivas ordenadas muestra cómo varios comstackdores de C optimizan algunas funciones realmente simples con trucos geniales.


 even: mov rbx, 2 xor rdx, rdx div rbx 

En Intel Haswell, div r64 es 36 uops, con una latencia de 32-96 ciclos y un rendimiento de uno por 21-74 ciclos. (Más los 2 uops para configurar RBX y cero RDX, pero la ejecución fuera de servicio puede ejecutarlos anticipadamente). Las instrucciones de conteo alto como DIV están microcodificadas, lo que también puede causar cuellos de botella en el extremo frontal. En este caso, la latencia es el factor más relevante porque es parte de una cadena de dependencia transportada por bucle.

shr rax, 1 hace la misma división sin firmar: es 1 uop, con latencia de 1c , y puede ejecutar 2 por ciclo de reloj.

A modo de comparación, la división de 32 bits es más rápida, pero sigue siendo horrible frente a los cambios. idiv r32 es 9 uops, 22-29c de latencia, y uno por 8-11c de rendimiento en Haswell.


Como puede ver al mirar la salida del -O0 de gcc ( explorador del comstackdor Godbolt ), solo usa instrucciones de turnos . clang -O0 se comstack ingenuamente como creías, incluso usando IDIV de 64 bits dos veces. (Al optimizar, los comstackdores usan ambas salidas de IDIV cuando la fuente hace una división y módulo con los mismos operandos, si usan IDIV en absoluto)

GCC no tiene un modo totalmente ingenuo; siempre se transforma a través de GIMPLE, lo que significa que algunas “optimizaciones” no se pueden desactivar . Esto incluye el reconocimiento de división por constante y el uso de cambios (potencia de 2) o un multiplicativo inverso de coma fijo (sin potencia de 2) para evitar IDIV (ver div_by_13 en el enlace de godbolt anterior).

gcc -Os (optimize for size) usa IDIV para la división non-power-of-2, lamentablemente incluso en los casos en que el código inverso multiplicativo es solo un poco más grande pero mucho más rápido.


Ayudando al comstackdor

(resumen para este caso: use uint64_t n )

En primer lugar, es interesante observar la salida optimizada del comstackdor. ( -O3 ). -O0 velocidad es básicamente sin sentido.

Mire la salida de su ASM (en Godbolt, o vea ¿Cómo eliminar el “ruido” de la salida del conjunto GCC / clang? ). Cuando el comstackdor no hace un código óptimo en primer lugar: Escribir el código C / C ++ de una manera que guíe al comstackdor a hacer un mejor código suele ser el mejor enfoque . Tienes que saber asm, y saber qué es eficiente, pero aplicas este conocimiento indirectamente. Los comstackdores también son una buena fuente de ideas: a veces el clang hará algo genial y usted puede mantener a mano gcc haciendo lo mismo: vea esta respuesta y lo que hice con el ciclo no desenrollado en el código de @ Veedrac más abajo).

Este enfoque es portátil, y en 20 años algún comstackdor futuro puede comstackrlo para lo que sea eficiente en hardware futuro (x86 o no), tal vez usando una nueva extensión ISA o auto-vectorización. El asno x86-64 escrito a mano de hace 15 años generalmente no estaría optimizado para Skylake. por ejemplo, la macro-fusión de comparación y ramificación no existía en ese momento. Lo que ahora es óptimo para el asm artesanal para una microarchitecture podría no ser óptimo para otras CPU actuales y futuras. Los comentarios sobre la respuesta de @ johnfound discuten las principales diferencias entre AMD Bulldozer e Intel Haswell, que tienen un gran efecto en este código. Pero en teoría, g++ -O3 -march=bdver3 y g++ -O3 -march=skylake harán lo correcto. (O -march=native .) O -mtune=... para sintonizar, sin usar instrucciones que otras CPU podrían no ser compatibles.

Tengo la sensación de que guiar al comstackdor a lo que es bueno para una CPU actual que te importe no debería ser un problema para futuros comstackdores. Es de esperar que sean mejores que los comstackdores actuales para encontrar formas de transformar el código, y puedan encontrar una forma que funcione para las CPU futuras. De todos modos, el futuro x86 probablemente no sea terrible para nada que sea bueno en x86 actual, y el futuro comstackdor evitará cualquier error específico de asm mientras implementa algo como el movimiento de datos de su fuente C, si no ve algo mejor.

El asm escrito a mano es una caja negra para el optimizador, por lo que la propagación constante no funciona cuando la línea entrante hace que una entrada sea una constante en tiempo de comstackción. Otras optimizaciones también se ven afectadas. Lee https://gcc.gnu.org/wiki/DontUseInlineAsm antes de usar asm. (Y evite el asm en línea estilo MSVC: las entradas / salidas tienen que pasar por la memoria, lo que agrega una sobrecarga ).

En este caso : su n tiene un tipo firmado, y gcc usa la secuencia SAR / SHR / ADD que proporciona el redondeo correcto. (IDIV y “ronda” de desplazamiento aritmético de forma diferente para entradas negativas, consulte la entrada de entrada de SAR en la entrada manual de ref ). (IDK si gcc probó y no pudo demostrar que n no puede ser negativo, o qué. El desbordamiento con signo es un comportamiento indefinido, por lo que debería haber sido capaz de).

Deberías haber usado uint64_t n , entonces solo puede SHR. Y, por lo tanto, es portátil para los sistemas en los que el long es solo de 32 bits (por ejemplo, x86-64 Windows).


Por cierto, la salida optimizada del asm de gcc se ve bastante bien (usando unsigned long n ) : el bucle interno que se inserta en main() hace esto:

  # from gcc5.4 -O3 plus my comments # edx= count=1 # rax= uint64_t n .L9: # do{ lea rcx, [rax+1+rax*2] # rcx = 3*n + 1 mov rdi, rax shr rdi # rdi = n>>1; test al, 1 # set flags based on n%2 (aka n&1) mov rax, rcx cmove rax, rdi # n= (n%2) ? 3*n+1 : n/2; add edx, 1 # ++count; cmp rax, 1 jne .L9 #}while(n!=1) cmp/branch to update max and maxi, and then do the next n 

El bucle interno no tiene sucursales, y la ruta crítica de la cadena de dependencia transportada por bucle es:

  • LEA de 3 componentes (3 ciclos)
  • cmov (2 ciclos en Haswell, 1c en Broadwell o más adelante).

Total: 5 ciclos por iteración, cuello de botella de latencia . La ejecución fuera de orden se ocupa de todo lo demás en paralelo con esto (en teoría: no he probado con contadores de rendimiento para ver si realmente se ejecuta en 5c / iter).

La entrada FLAGS de cmov (producida por TEST) es más rápida de producir que la entrada RAX (desde LEA-> MOV), por lo que no está en la ruta crítica.

De manera similar, el MOV-> SHR que produce la entrada de RDI de CMOV está fuera de la ruta crítica, porque también es más rápido que el LEA. MOV en IvyBridge y más tarde tiene latencia cero (manejado en el tiempo de cambio de nombre de registro). (Todavía se necesita un uop, y una ranura en la tubería, por lo que no es gratis, solo cero latencia). El MOV adicional en la cadena de depósito LEA es parte del cuello de botella en otras CPU.

El cmp / jne tampoco forma parte de la ruta crítica: no se transmite por bucle, ya que las dependencias de control se manejan con predicción de bifurcación + ejecución especulativa, a diferencia de las dependencias de datos en la ruta crítica.


Venciendo al comstackdor

GCC hizo un muy buen trabajo aquí. Podría ahorrar un byte de código usando inc edx lugar de add edx, 1 , porque a nadie le importa P4 y sus dependencias falsas para las instrucciones de modificación de indicador parcial.

También podría guardar todas las instrucciones MOV, y el TEST: SHR establece CF = el bit desplazado, por lo que podemos usar cmovc lugar de test / cmovz .

  ### Hand-optimized version of what gcc does .L9: #do{ lea rcx, [rax+1+rax*2] # rcx = 3*n + 1 shr rax, 1 # n>>=1; CF = n&1 = n%2 cmovc rax, rcx # n= (n&1) ? 3*n+1 : n/2; inc edx # ++count; cmp rax, 1 jne .L9 #}while(n!=1) 

Vea la respuesta de @ johnfound para otro truco ingenioso: elimine el CMP ramificándolo en el resultado de la bandera de SHR así como también utilizándolo para CMOV: cero solo si n fue 1 (o 0) para empezar. (Dato curioso : SHR con count! = 1 en Nehalem o antes provoca un locking si lees los resultados de la bandera . Así es como lo hicieron single-uop. Sin embargo, la encoding especial shift-by-1 está bien).

Evitar MOV no ayuda con la latencia en absoluto en Haswell ( ¿Puede el MOV de Can x86 ser realmente “libre”? ¿Por qué no puedo reproducir esto en absoluto? ). Ayuda significativamente en CPUs como Intel pre-IvB y AMD Bulldozer-family, donde MOV no tiene latencia cero. Las instrucciones MOV desperdiciadas del comstackdor afectan la ruta crítica. Los complejos de LEA y CMOV de BD son de latencia más baja (2c y 1c respectivamente), por lo que es una fracción mayor de la latencia. Además, los cuellos de botella de rendimiento se convierten en un problema, ya que solo tiene dos tubos de ALU enteros. Vea la respuesta de @ johnfound , donde tiene los resultados de sincronización de una CPU AMD.

Incluso en Haswell, esta versión puede ayudar un poco al evitar algunas demoras ocasionales cuando un uop no crítico roba un puerto de ejecución de uno en la ruta crítica, retrasando la ejecución en 1 ciclo. (Esto se llama conflicto de recursos). También guarda un registro, que puede ayudar al hacer múltiples valores de n en paralelo en un bucle intercalado (ver a continuación).

La latencia de LEA depende del modo de direccionamiento , en las CPU de la familia Intel SnB. 3c para 3 componentes ( [base+idx+const] , que toma dos adiciones separadas), pero solo 1c con 2 o menos componentes (un complemento). Algunas CPU (como Core2) hacen incluso una LEA de 3 componentes en un solo ciclo, pero la familia SnB no lo hace. Peor aún, la familia Intel SnB estandariza las latencias, por lo que no hay 2 uups , de lo contrario, las LEA de 3 componentes serían solo 2c, como Bulldozer. (LEA de 3 componentes también es más lenta en AMD, pero no tanto).

Entonces lea rcx, [rax + rax*2] / inc rcx tiene solo 2c de latencia, más rápido que lea rcx, [rax + rax*2 + 1] , en las CPU de la familia Intel SnB como Haswell. Punto de equilibrio en BD, y peor en Core2. Cuesta un uop extra, que normalmente no vale la pena para ahorrar 1c de latencia, pero la latencia es el mayor cuello de botella aquí y Haswell tiene una tubería lo suficientemente amplia como para manejar el rendimiento extra UOP.

Ni gcc, icc, ni clang (en godbolt) usaron la salida CF de SHR, siempre usando AND o TEST . Comstackdores tontos. : P Son grandes piezas de maquinaria compleja, pero un humano inteligente a menudo puede vencerlos en problemas de pequeña escala. (¡Por supuesto, miles o millones de veces más tiempo para pensarlo!) Los comstackdores no usan algoritmos exhaustivos para buscar todas las formas posibles de hacer las cosas, porque eso llevaría demasiado tiempo cuando se optimiza una gran cantidad de código en línea, que es lo que lo hacen mejor. Tampoco modelan la tubería en la microarchitecture objective, al menos no con el mismo detalle que IACA u otras herramientas de análisis estático, solo usan algo de heurística.)


El simple bucle de desenrollar no ayudará ; este bucle obstaculiza la latencia de una cadena de dependencia transportada por bucle, no en la sobrecarga / rendimiento del bucle. Esto significa que haría bien con hyperthreading (o cualquier otro tipo de SMT), ya que la CPU tiene mucho tiempo para intercalar instrucciones de dos hilos. Esto significaría paralelizar el bucle en main , pero está bien porque cada thread solo puede verificar un rango de n valores y producir un par de enteros como resultado.

El entrelazado manual en un único hilo también puede ser viable . Tal vez calcule la secuencia de un par de números en paralelo, ya que cada uno solo toma un par de registros, y todos pueden actualizar el mismo max / maxi . Esto crea más paralelismo a nivel de instrucción .

El truco es decidir si esperar hasta que todos los n valores hayan alcanzado 1 antes de obtener otro par de valores de inicio n , o si se debe dividir y obtener un nuevo punto de inicio para solo uno que alcanzó la condición final, sin tocar los registros para el otra secuencia. Probablemente sea mejor que cada cadena trabaje con datos útiles, de lo contrario tendrías que incrementar su contador en forma condicional.


Incluso podría hacer esto con SSE empaquetado-compare cosas para incrementar condicionalmente el contador para elementos vectoriales donde n no había llegado a 1 todavía. Y luego, para ocultar la latencia aún más larga de una implementación de incremento condicional SIMD, necesitaría mantener más vectores de n valores en el air. Tal vez solo valga la pena con el vector 256b (4x uint64_t ).

Creo que la mejor estrategia para detectar 1 “adhesivo” es enmascarar el vector de todos los que se agregan para incrementar el contador. Entonces, después de que hayas visto un 1 en un elemento, el vector de incremento tendrá un cero, y + = 0 es un no-op.

Idea no probada para vectorización manual

 # starting with YMM0 = [ n_d, n_c, n_b, n_a ] (64-bit elements) # ymm4 = _mm256_set1_epi64x(1): increment vector # ymm5 = all-zeros: count vector .inner_loop: vpaddq ymm1, ymm0, xmm0 vpaddq ymm1, ymm1, xmm0 vpaddq ymm1, ymm1, set1_epi64(1) # ymm1= 3*n + 1. Maybe could do this more efficiently? vprllq ymm3, ymm0, 63 # shift bit 1 to the sign bit vpsrlq ymm0, ymm0, 1 # n /= 2 # There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure. Probably worth it vpblendvpd ymm0, ymm0, ymm1, ymm3 # variable blend controlled by the sign bit of each 64-bit element. I might have the source operands backwards, I always have to look this up. # ymm0 = updated n in each element. vpcmpeqq ymm1, ymm0, set1_epi64(1) vpandn ymm4, ymm1, ymm4 # zero out elements of ymm4 where the compare was true vpaddq ymm5, ymm5, ymm4 # count++ in elements where n has never been == 1 vptest ymm4, ymm4 jnz .inner_loop # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero vextracti128 ymm0, ymm5, 1 vpmaxq .... crap this doesn't exist # Actually just delay doing a horizontal max until the very very end. But you need some way to record max and maxi. 

Puede y debe implementar esto con intrínsecos, en lugar de asm escritos a mano.


Mejora algorítmica / de implementación:

Además de simplemente implementar la misma lógica con un asm más eficiente, busque formas de simplificar la lógica o evite el trabajo redundante. por ejemplo, memoize para detectar finales comunes de secuencias. O mejor aún, observe 8 bits finales a la vez (respuesta de Gnasher)

@EOF señala que tzcnt (o bsf ) podría usarse para realizar múltiples n/=2 iteraciones en un solo paso. Probablemente sea mejor que la vectorización SIMD, porque ninguna instrucción SSE o AVX puede hacer eso. Sin embargo, todavía es compatible con hacer múltiples escalas en paralelo en diferentes registros enteros.

Entonces, el ciclo podría verse así:

 goto loop_entry; // C++ structured like the asm, for illustration only do { n = n*3 + 1; loop_entry: shift = _tzcnt_u64(n); n >>= shift; count += shift; } while(n != 1); 

Esto puede hacer significativamente menos iteraciones, pero los cambios de conteo variable son lentos en las CPU de la familia Intel SnB sin BMI2. 3 uops, 2 latencia. (Tienen una dependencia de entrada en los FLAGS porque count = 0 significa que los flags no están modificados. Manejan esto como una dependencia de datos, y toman múltiples uops porque un uop solo puede tener 2 entradas (pre-HSW / BDW de todos modos)). Este es el tipo de gente que se queja del diseño loco de CISC de x86. Hace que las CPU x86 sean más lentas de lo que serían si el ISA se diseñase desde el principio, incluso de manera similar. (es decir, esto forma parte del “impuesto x86” que cuesta velocidad / potencia). SHRX / SHLX / SARX (BMI2) son una gran ganancia (1 uop / 1c de latencia).

También coloca tzcnt (3c en Haswell y más adelante) en la ruta crítica, por lo que alarga significativamente la latencia total de la cadena de dependencia transportada por bucle. Sin embargo, elimina la necesidad de un CMOV o de preparar un registro que contenga n>>1 . La respuesta de @ Veedrac supera todo esto posponiendo el tzcnt / shift para iteraciones múltiples, que es altamente efectivo (ver abajo).

Podemos usar BSF o TZCNT de manera intercambiable, porque n nunca puede ser cero en ese punto. El código máquina de TZCNT se decodifica como BSF en CPU que no admiten BMI1. (Los prefijos sin sentido se ignoran, por lo que REP BSF se ejecuta como BSF).

TZCNT funciona mucho mejor que BSF en CPUs AMD que lo soportan, por lo que puede ser una buena idea usar REP BSF , incluso si no le importa configurar ZF si la entrada es cero en lugar de la salida. Algunos comstackdores hacen esto cuando usas __builtin_ctzll incluso con -mno-bmi .

Realizan lo mismo en las CPU de Intel, así que simplemente guarde el byte si eso es todo lo que importa. TZCNT en Intel (pre-Skylake) todavía tiene una falsa dependencia en el operando de salida supuestamente de solo escritura, al igual que BSF, para soportar el comportamiento no documentado de que BSF con input = 0 deja su destino sin modificar. Por lo tanto, debe solucionarlo a menos que optimice solo para Skylake, por lo que no hay nada que ganar con el byte REP adicional. (Intel a menudo va más allá de lo que el manual ISA x86 requiere, para evitar romper código ampliamente utilizado que depende de algo que no debería, o que se anula retroactivamente. Por ejemplo, Windows 9x no asume ninguna captación especulativa de entradas TLB , que era seguro cuando se escribió el código, antes de que Intel actualizara las reglas de administración de TLB ).

De todos modos, LZCNT / TZCNT en Haswell tiene el mismo depósito falso que POPCNT: vea esta pregunta y respuesta . Esta es la razón por la cual en la salida asm de gcc para el código de @ Veedrac, lo ves rompiendo la cadena de dep con xor-zeroing en el registro que está a punto de usar como destino de TZCNT, cuando no usa dst = src. Como TZCNT / LZCNT / POPCNT nunca dejan su destino indefinido o sin modificar, esta falsa dependencia en la salida de las CPU Intel es puramente una falla / limitación de rendimiento. Es de suponer que vale la pena algunos transistores / poder para que se comporten como otros uops que van a la misma unidad de ejecución. El único lado visible del software está en la interacción con otra limitación microarchitecture: pueden microfundir un operando de memoria con un modo de direccionamiento indexado en Haswell, pero en Skylake donde Intel eliminó la dependencia falsa para LZCNT / TZCNT que “no laminan” modos de direccionamiento indexados mientras que POPCNT aún puede microfusionar cualquier modo addr.


Mejoras a ideas / código de otras respuestas:

La respuesta de @ hidefromkgb tiene una buena observación de que está garantizado que podrá hacer un cambio a la derecha después de un 3n + 1. Puede calcular esto de manera aún más eficiente que simplemente omitiendo los controles entre los pasos. Sin embargo, la implementación de asm en esa respuesta está rota (depende de OF, que no está definida después de SHRD con un recuento> 1), y lenta: ROR rdi,2 es más rápida que SHRD rdi,rdi,2 , y utiliza dos instrucciones CMOV en la ruta crítica es más lento que una prueba adicional que se puede ejecutar en paralelo.

Puse C ordenada / mejorada (que guía al comstackdor para producir mejor asm), y probé + trabajar asm más rápido (en los comentarios debajo de C) arriba en Godbolt: vea el enlace en la respuesta de @ hidefromkgb . (Esta respuesta alcanzó el límite de 30k de las grandes URL de Godbolt, pero los enlaces cortos pueden pudrirse y fueron demasiado largos para goo.gl de todos modos).

También mejoró la impresión de salida para convertir a una cadena y hacer una write() lugar de escribir un carácter a la vez. Esto minimiza el impacto en el tiempo de todo el progtwig con perf stat ./collatz (para registrar contadores de rendimiento), y desactivé algunos de los asm no críticos.


El código de @ Veedrac

Obtuve una aceleración muy pequeña por el cambio hacia la derecha tanto como sabemos que hay que hacer, y comprobamos que continúe el ciclo. Desde 7.5s para límite = 1e8 hasta 7.275s, en Core2Duo (Merom), con un factor de desenrollamiento de 16.

código + comentarios en Godbolt . No use esta versión con clang; hace algo tonto con el defer-loop. Usar un contador de tmp k y luego sumrlo para count más tarde cambia lo que hace clang, pero eso lastima un poco a gcc.

Ver discusión en comentarios: el código de Veedrac es excelente en CPU con BMI1 (es decir, no Celeron / Pentium)

Afirmar que el comstackdor de C ++ puede producir un código más óptimo que un progtwigdor de lenguaje ensamblador competente es un error muy grave. Y especialmente en este caso. El humano siempre puede mejorar el código que el comstackdor puede, y esta situación particular es una buena ilustración de esta afirmación.

La diferencia de tiempo que está viendo se debe a que el código de ensamblaje en la pregunta está muy lejos de ser óptimo en los bucles internos.

(El siguiente código es de 32 bits, pero se puede convertir fácilmente a 64 bits)

Por ejemplo, la función de secuencia se puede optimizar a solo 5 instrucciones:

  .seq: inc esi ; counter lea edx, [3*eax+1] ; edx = 3*n+1 shr eax, 1 ; eax = n/2 cmovc eax, edx ; if CF eax = edx jnz .seq ; jmp if n<>1 

Todo el código se ve así:

 include "%lib%/freshlib.inc" @BinaryType console, compact options.DebugMode = 1 include "%lib%/freshlib.asm" start: InitializeAll mov ecx, 999999 xor edi, edi ; max xor ebx, ebx ; max i .main_loop: xor esi, esi mov eax, ecx .seq: inc esi ; counter lea edx, [3*eax+1] ; edx = 3*n+1 shr eax, 1 ; eax = n/2 cmovc eax, edx ; if CF eax = edx jnz .seq ; jmp if n<>1 cmp edi, esi cmovb edi, esi cmovb ebx, ecx dec ecx jnz .main_loop OutputValue "Max sequence: ", edi, 10, -1 OutputValue "Max index: ", ebx, 10, -1 FinalizeAll stdcall TerminateAll, 0 

Para comstackr este código, se necesita FreshLib .

En mis pruebas, (procesador AMD A4-1200 de 1 GHz), el código anterior es aproximadamente cuatro veces más rápido que el código C ++ de la pregunta (cuando se comstack con -O0 : 430 ms frente a 1900 ms) y más de dos veces más rápido (430 ms vs. 830 ms) cuando el código de C ++ se comstack con -O3 .

El resultado de ambos progtwigs es el mismo: secuencia máxima = 525 en i = 837799.

Para obtener más rendimiento: un cambio simple es observar que después de n = 3n + 1, n será par, por lo que puede dividir por 2 inmediatamente. Y n no será 1, por lo que no es necesario que lo pruebe. Para que pueda guardar unas pocas sentencias if y escribir:

 while (n % 2 == 0) n /= 2; if (n > 1) for (;;) { n = (3*n + 1) / 2; if (n % 2 == 0) { do n /= 2; while (n % 2 == 0); if (n == 1) break; } } 

Aquí hay una gran ganancia: si miras los 8 bits más bajos de n, todos los pasos hasta que los dividas por 2 y ocho veces están completamente determinados por esos ocho bits. Por ejemplo, si los últimos ocho bits son 0x01, eso es en binario, su número es ???? 0000 0001 luego los siguientes pasos son:

 3n+1 -> ???? 0000 0100 / 2 -> ???? ?000 0010 / 2 -> ???? ??00 0001 3n+1 -> ???? ??00 0100 / 2 -> ???? ???0 0010 / 2 -> ???? ???? 0001 3n+1 -> ???? ???? 0100 / 2 -> ???? ???? ?010 / 2 -> ???? ???? ??01 3n+1 -> ???? ???? ??00 / 2 -> ???? ???? ???0 / 2 -> ???? ???? ???? 

De modo que todos estos pasos se pueden predecir, y 256k + 1 se reemplaza con 81k + 1. Algo similar ocurrirá con todas las combinaciones. Entonces puedes hacer un ciclo con una gran statement de cambio:

 k = n / 256; m = n % 256; switch (m) { case 0: n = 1 * k + 0; break; case 1: n = 81 * k + 1; break; case 2: n = 81 * k + 1; break; ... case 155: n = 729 * k + 425; break; ... } 

Ejecute el ciclo hasta n ≤ 128, porque en ese punto n podría convertirse en 1 con menos de ocho divisiones por 2, y hacer ocho o más pasos a la vez le haría perder el punto donde alcanza el 1 por primera vez. Luego, continúe con el ciclo “normal” o prepare una tabla que indique cuántos pasos más se necesitan para llegar a 1.

PD. Sospecho fuertemente que la sugerencia de Peter Cordes lo haría aún más rápido. No habrá twigs condicionales, excepto una, y esa será pronosticada correctamente, excepto cuando el ciclo realmente termine. Entonces el código sería algo así como

 static const unsigned int multipliers [256] = { ... } static const unsigned int adders [256] = { ... } while (n > 128) { size_t lastBits = n % 256; n = (n >> 8) * multipliers [lastBits] + adders [lastBits]; } 

En la práctica, usted mediría si el procesamiento de los últimos 9, 10, 11, 12 bits de n a la vez sería más rápido. Para cada bit, el número de entradas en la tabla se duplicaría, y exijo una desaceleración cuando las tablas ya no encajan en la caché L1.

PPS. Si necesita el número de operaciones: en cada iteración hacemos exactamente ocho divisiones por dos, y un número variable de operaciones (3n + 1), por lo que un método obvio para contar las operaciones sería otra matriz. Pero podemos calcular el número de pasos (en función del número de iteraciones del ciclo).

Podríamos redefinir el problema ligeramente: reemplace n con (3n + 1) / 2 si es impar, y reemplace n con n / 2 si es par. Entonces, cada iteración hará exactamente 8 pasos, pero podrías considerar que hacer trampa 🙂 Asume que hubo r operaciones n < - 3n + 1 ys operaciones n <- n / 2. El resultado será exactamente n '= n * 3 ^ r / 2 ^ s, porque n <- 3n + 1 significa n <- 3n * (1 + 1 / 3n). Tomando el logaritmo encontramos r = (s + log2 (n '/ n)) / log2 (3).

Si hacemos el ciclo hasta n ≤ 1,000,000 y tenemos una tabla precalculada cuántas iteraciones se necesitan desde cualquier punto de inicio n ≤ 1,000,000, entonces calculando r como arriba, redondeado al entero más cercano, dará el resultado correcto a menos que s sea verdaderamente grande.

On a rather unrelated note: more performance hacks!

  • [the first «conjecture» has been finally debunked by @ShreevatsaR; removed]

  • When traversing the sequence, we can only get 3 possible cases in the 2-neighborhood of the current element N (shown first):

    1. [even] [odd]
    2. [odd] [even]
    3. [even] [even]

    To leap past these 2 elements means to compute (N >> 1) + N + 1 , ((N < < 1) + N + 1) >> 1 and N >> 2 , respectively.

    Let`s prove that for both cases (1) and (2) it is possible to use the first formula, (N >> 1) + N + 1 .

    Case (1) is obvious. Case (2) implies (N & 1) == 1 , so if we assume (without loss of generality) that N is 2-bit long and its bits are ba from most- to least-significant, then a = 1 , and the following holds:

     (N < < 1) + N + 1: (N >> 1) + N + 1: b10 b1 b1 b + 1 + 1 ---- --- bBb0 bBb 

    where B = !b . Right-shifting the first result gives us exactly what we want.

    QED: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N < < 1) + N + 1) >> 1 .

    As proven, we can traverse the sequence 2 elements at a time, using a single ternary operation. Another 2× time reduction.

The resulting algorithm looks like this:

 uint64_t sequence(uint64_t size, uint64_t *path) { uint64_t n, i, c, maxi = 0, maxc = 0; for (n = i = (size - 1) | 1; i > 2; n = i -= 2) { c = 2; while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2) c += 2; if (n == 2) c++; if (c > maxc) { maxi = i; maxc = c; } } *path = maxc; return maxi; } int main() { uint64_t maxi, maxc; maxi = sequence(1000000, &maxc); printf("%llu, %llu\n", maxi, maxc); return 0; } 

Here we compare n > 2 because the process may stop at 2 instead of 1 if the total length of the sequence is odd.

[EDIT:]

Let`s translate this into assembly!

 MOV RCX, 1000000; DEC RCX; AND RCX, -2; XOR RAX, RAX; MOV RBX, RAX; @main: XOR RSI, RSI; LEA RDI, [RCX + 1]; @loop: ADD RSI, 2; LEA RDX, [RDI + RDI*2 + 2]; SHR RDX, 1; SHRD RDI, RDI, 2; ror rdi,2 would do the same thing CMOVL RDI, RDX; Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs. CMOVS RDI, RDX; CMP RDI, 2; JA @loop; LEA RDX, [RSI + 1]; CMOVE RSI, RDX; CMP RAX, RSI; CMOVB RAX, RSI; CMOVB RBX, RCX; SUB RCX, 2; JA @main; MOV RDI, RCX; ADD RCX, 10; PUSH RDI; PUSH RCX; @itoa: XOR RDX, RDX; DIV RCX; ADD RDX, '0'; PUSH RDX; TEST RAX, RAX; JNE @itoa; PUSH RCX; LEA RAX, [RBX + 1]; TEST RBX, RBX; MOV RBX, RDI; JNE @itoa; POP RCX; INC RDI; MOV RDX, RDI; @outp: MOV RSI, RSP; MOV RAX, RDI; SYSCALL; POP RAX; TEST RAX, RAX; JNE @outp; LEA RAX, [RDI + 59]; DEC RDI; SYSCALL; 

Use these commands to compile:

 nasm -f elf64 file.asm ld -o file file.o 

See the C and an improved/bugfixed version of the asm by Peter Cordes on Godbolt . (editor’s note: Sorry for putting my stuff in your answer, but my answer hit the 30k char limit from Godbolt links + text!)

C++ programs are translated to assembly programs during the generation of machine code from the source code. It would be virtually wrong to say assembly is slower than C++. Moreover, the binary code generated differs from compiler to compiler. So a smart C++ compiler may produce binary code more optimal and efficient than a dumb assembler’s code.

However I believe your profiling methodology has certain flaws. The following are general guidelines for profiling:

  1. Make sure your system is in its normal/idle state. Stop all running processes (applications) that you started or that use CPU intensively (or poll over the network).
  2. Your datasize must be greater in size.
  3. Your test must run for something more than 5-10 seconds.
  4. Do not rely on just one sample. Perform your test N times. Collect results and calculate the mean or median of the result.

From comments:

But, this code never stops (because of integer overflow) !?! Yves Daoust

For many numbers it will not overflow.

If it will overflow – for one of those unlucky initial seeds, the overflown number will very likely converge toward 1 without another overflow.

Still this poses interesting question, is there some overflow-cyclic seed number?

Any simple final converging series starts with power of two value (obvious enough?).

2^64 will overflow to zero, which is undefined infinite loop according to algorithm (ends only with 1), but the most optimal solution in answer will finish due to shr rax producing ZF=1.

Can we produce 2^64? If the starting number is 0x5555555555555555 , it’s odd number, next number is then 3n+1, which is 0xFFFFFFFFFFFFFFFF + 1 = 0 . Theoretically in undefined state of algorithm, but the optimized answer of johnfound will recover by exiting on ZF=1. The cmp rax,1 of Peter Cordes will end in infinite loop (QED variant 1, “cheapo” through undefined 0 number).

How about some more complex number, which will create cycle without 0 ? Frankly, I’m not sure, my Math theory is too hazy to get any serious idea, how to deal with it in serious way. But intuitively I would say the series will converge to 1 for every number : 0 < number, as the 3n+1 formula will slowly turn every non-2 prime factor of original number (or intermediate) into some power of 2, sooner or later. So we don't need to worry about infinite loop for original series, only overflow can hamper us.

So I just put few numbers into sheet and took a look on 8 bit truncated numbers.

There are three values overflowing to 0 : 227 , 170 and 85 ( 85 going directly to 0 , other two progressing toward 85 ).

But there’s no value creating cyclic overflow seed.

Funnily enough I did a check, which is the first number to suffer from 8 bit truncation, and already 27 is affected! It does reach value 9232 in proper non-truncated series (first truncated value is 322 in 12th step), and the maximum value reached for any of the 2-255 input numbers in non-truncated way is 13120 (for the 255 itself), maximum number of steps to converge to 1 is about 128 (+-2, not sure if “1” is to count, etc…).

Interestingly enough (for me) the number 9232 is maximum for many other source numbers, what’s so special about it? :-O 9232 = 0x2410 … hmmm.. no idea.

Unfortunately I can’t get any deep grasp of this series, why does it converge and what are the implications of truncating them to k bits, but with cmp number,1 terminating condition it’s certainly possible to put the algorithm into infinite loop with particular input value ending as 0 after truncation.

But the value 27 overflowing for 8 bit case is sort of alerting, this looks like if you count the number of steps to reach value 1 , you will get wrong result for majority of numbers from the total k-bit set of integers. For the 8 bit integers the 146 numbers out of 256 have affected series by truncation (some of them may still hit the correct number of steps by accident maybe, I’m too lazy to check).

You did not post the code generated by the compiler, so there’ some guesswork here, but even without having seen it, one can say that this:

 test rax, 1 jpe even 

… has a 50% chance of mispredicting the branch, and that will come expensive.

The compiler almost certainly does both computations (which costs neglegibly more since the div/mod is quite long latency, so the multiply-add is “free”) and follows up with a CMOV. Which, of course, has a zero percent chance of being mispredicted.

Even without looking at assembly, the most obvious reason is that /= 2 is probably optimized as >>=1 and many processors have a very quick shift operation. But even if a processor doesn’t have a shift operation, the integer division is faster than floating point division.

Edit: your milage may vary on the “integer division is faster than floating point division” statement above. The comments below reveal that the modern processors have prioritized optimizing fp division over integer division. So if someone were looking for the most likely reason for the speedup which this thread’s question asks about, then compiler optimizing /=2 as >>=1 would be the best 1st place to look.


On an unrelated note , if n is odd, the expression n*3+1 will always be even. So there is no need to check. You can change that branch to

 { n = (n*3+1) >> 1; count += 2; } 

So the whole statement would then be

 if (n & 1) { n = (n*3 + 1) >> 1; count += 2; } else { n >>= 1; ++count; } 

As a generic answer, not specifically directed at this task: In many cases, you can significantly speed up any program by making improvements at a high level. Like calculating data once instead of multiple times, avoiding unnecessary work completely, using caches in the best way, and so on. These things are much easier to do in a high level language.

Writing assembler code, it is possible to improve on what an optimising compiler does, but it is hard work. And once it’s done, your code is much harder to modify, so it is much more difficult to add algorithmic improvements. Sometimes the processor has functionality that you cannot use from a high level language, inline assembly is often useful in these cases and still lets you use a high level language.

In the Euler problems, most of the time you succeed by building something, finding why it is slow, building something better, finding why it is slow, and so on and so on. That is very, very hard using assembler. A better algorithm at half the possible speed will usually beat a worse algorithm at full speed, and getting the full speed in assembler isn’t trivial.

For the Collatz problem, you can get a significant boost in performance by caching the “tails”. This is a time/memory trade-off. See: memoization ( https://en.wikipedia.org/wiki/Memoization ). You could also look into dynamic programming solutions for other time/memory trade-offs.

Example python implementation:

 import sys inner_loop = 0 def collatz_sequence(N, cache): global inner_loop l = [ ] stop = False n = N tails = [ ] while not stop: inner_loop += 1 tmp = n l.append(n) if n < = 1: stop = True elif n in cache: stop = True elif n % 2: n = 3*n + 1 else: n = n // 2 tails.append((tmp, len(l))) for key, offset in tails: if not key in cache: cache[key] = l[offset:] return l def gen_sequence(l, cache): for elem in l: yield elem if elem in cache: yield from gen_sequence(cache[elem], cache) raise StopIteration if __name__ == "__main__": le_cache = {} for n in range(1, 4711, 5): l = collatz_sequence(n, le_cache) print("{}: {}".format(n, len(list(gen_sequence(l, le_cache))))) print("inner_loop = {}".format(inner_loop)) 

The simple answer:

  • doing a MOV RBX, 3 and MUL RBX is expensive; just ADD RBX, RBX twice

  • ADD 1 is probably faster than INC here

  • MOV 2 and DIV is very expensive; just shift right

  • 64-bit code is usually noticeably slower than 32-bit code and the alignment issues are more complicated; with small programs like this you have to pack them so you are doing parallel computation to have any chance of being faster than 32-bit code

If you generate the assembly listing for your C++ program, you can see how it differs from your assembly.