Pregunta ¿Por qué este código C ++ es más rápido que mi ensamblaje escrito a mano para probar la conjetura de Collatz?


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

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

El C ++ fue compilado con

g++ p14.cpp -o p14

Montaje, 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 <iostream>

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 compilador 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 (microarquitectura Haswell).


737
2017-11-01 06:12


origen


Respuestas:


Si crees que una instrucción DIV de 64 bits es una buena manera de dividir por dos, entonces no es de extrañar que la salida de asm del compilador supere tu código escrito a mano, incluso con -O0 (compila rápidamente, sin optimización adicional, y almacena / recarga a la memoria después / antes de cada instrucción C para que un depurador pueda modificar las variables).

Ver Guía de optimización 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 el  etiqueta wiki para más enlaces perf.

Consulte también esta pregunta más general sobre cómo superar el compilador 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 compilador haga su trabajo, especialmente si intenta escribir C ++ que pueda compilar eficientemente. Ver también ¿el ensamblaje es más rápido que los lenguajes compilados?. Uno de los enlaces de respuestas a estas diapositivas ordenadas mostrando cómo varios compiladores 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 un 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 realiza la misma división sin firmar: es 1 uop, con latencia 1cy 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 tiene 9 uops, 22-29c de latencia y uno por 8-11c en Haswell.


Como se puede ver al mirar gcc's -O0 salida de asm (Godbolt compilador explorador), solo usa instrucciones de turnos. sonido metálico -O0 compila ingenuamente como usted pensó, incluso usando IDIV de 64 bits dos veces. (Al optimizar, los compiladores 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 inhabilitar. Esto incluye el reconocimiento de división por constante y el uso de turnos (potencia de 2) o un inverso multiplicativo de coma fija (no potencia de 2) para evitar IDIV (ver div_by_13 en el enlace de godbolt anterior).

gcc -Os (optimizar para el tamaño) hace use IDIV para la división no poder-de-2, desafortunadamente incluso en casos donde el código inverso multiplicativo es solo un poco más grande pero mucho más rápido.


Ayudando al compilador

(resumen para este caso: uso uint64_t n)

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

Mire su salida asm (en Godbolt, o vea ¿Cómo eliminar el "ruido" de la salida del conjunto GCC / clang?) Cuando el compilador no hace código óptimo en primer lugar: Escribir su fuente de C / C ++ de una manera que guíe al compilador 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 compiladores también son una buena fuente de ideas: a veces el clang hará algo genial, y puede hacer que gcc lo haga a mano haciendo lo mismo: ver esta respuesta y lo que hice con el bucle no desenrollado en el código de @ Veedrac a continuación).

Este enfoque es portátil, y en 20 años algún compilador futuro puede compilarlo 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. p.ej. comparar y rama macro fusión no existía en ese momento. Lo que ahora es óptimo para el asm artesanal para una microarquitectura podría no ser óptimo para otras CPU actuales y futuras.  Comentarios sobre la respuesta de @ johnfound analice 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á lo correcto. (O -march=native.) O -mtune=... simplemente sintonizar, sin usar instrucciones que otras CPU podrían no ser compatibles.

Tengo la sensación de que guiar al compilador a lo que es bueno para una CPU actual que te importe no debería ser un problema para futuros compiladores. Es de esperar que sean mejores que los compiladores 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 compilador 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 compilación. Otras optimizaciones también se ven afectadas. Leer 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 que agrega sobrecarga.)

En este caso: tu 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 las entradas negativas, consulte el SAR ingrese la entrada manual de ref) (IDK si gcc intentó y no pudo probar que n no puede ser negativo, o qué. El desbordamiento firmado es un comportamiento indefinido, por lo que debería haber sido capaz de hacerlo).

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


Por cierto, gcc's optimizado la salida de ASM se ve bastante bien (usando unsigned long n): el bucle interno se inserta en main() Haz 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 de FLAGS de cmov (producido por TEST) es más rápido de producir que la entrada RAX (de 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 compilador

GCC hizo un muy buen trabajo aquí. Podría guardar un byte de código usando inc edx en lugar de add edx, 1, porque nadie se preocupa por P4 y sus dependencias falsas para las instrucciones de modificación parcial de la bandera.

También podría guardar todas las instrucciones de MOV, y TEST: SHR establece CF = el bit desplazado, para que podamos usar cmovc en 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. (Hecho de la diversión: SHR con recuento! = 1 en Nehalem o antes causa un bloqueo si lee los resultados de la bandera. Así es como lo hicieron single-uop. La codificación especial shift-by-1 está bien, sin embargo).

Evitar MOV no ayuda con la latencia en absoluto en Haswell (¿Puede el MOV de 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 compilador 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. Ver 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 n valores en paralelo en un bucle intercalado (ver a continuación).

La latencia de LEA depende del modo de direccionamiento, en 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, La familia Intel SnB estandariza las latencias por lo que no hay 2 uops, de lo contrario, el LEA de 3 componentes sería solo 2c, como Bulldozer. (LEA de 3 componentes también es más lenta en AMD, pero no tanto).

Asi que lea rcx, [rax + rax*2] / inc rcx es solo 2c de latencia, más rápido que lea rcx, [rax + rax*2 + 1], en 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. Compiladores 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 compiladores 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 microarquitectura objetivo, 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 ciclo en main, pero eso está bien porque cada hilo solo puede verificar un rango de n valores y producir un par de números enteros como resultado.

El entrelazado manual en un único hilo también podría 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 está en decidir si esperar hasta que todo el n los valores han alcanzado 1 antes de obtener otro par de inicio n valores, o si se debe dividir y obtener un nuevo punto de inicio para uno que alcanzó la condición final, sin tocar los registros de la otra secuencia. Probablemente sea mejor que cada cadena trabaje con datos útiles, de lo contrario tendrías que incrementar su contador en forma condicional.


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

Creo que la mejor estrategia para hacer la detección de un 1 "adhesivo" es enmascarar el vector de todos los que usted agrega para incrementar el contador. Entonces, después de haber 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. p.ej. memorizar 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 hacer 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. Todavía es compatible con hacer escalar múltiples ns en paralelo en diferentes registros enteros, sin embargo.

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 (latencia de 1 uop / 1c).

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. Elimina cualquier necesidad de un CMOV, o para preparar un registro de tenencia n>>1, aunque. La respuesta de @ Veedrac supera todo esto posponiendo el tzcnt / shift para iteraciones múltiples, que es altamente efectivo (ver abajo).

Podemos usar de forma segura BSF o TZCNT indistintamente, 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 tiene un rendimiento mucho mejor que BSF en las CPU AMD que lo admiten, 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 compiladores 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 de ISA x86 requiere, para evitar romper el código ampliamente utilizado que depende de algo que no debería, o que se desaconseja retroactivamente. Windows 9x no asume ninguna captación especulativa de entradas de 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: ver esta Q & A. Esta es la razón por la que en la salida del asm de gcc para el código de @ Veedrac, lo ves rompiendo la cadena de dep con xor-zeroing en el registro 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 microarquitectura: 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, "deslaminan" los modos de direccionamiento indexados mientras que POPCNT aún puede microfusionar cualquier modo addr.


Mejoras a ideas / código de otras respuestas:

@ hidefromkgb's answer 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ápido que SHRD rdi,rdi,2y el uso de dos instrucciones CMOV en la ruta crítica es más lento que una TEST adicional que se puede ejecutar en paralelo.

Puse C ordenada / mejorada (que guía al compilador para producir mejores asm), y probé + trabajar más rápido asm (en los comentarios debajo de C) en Godbolt: ver el enlace en @ hidefromkgb's answer. (Esta respuesta alcanzó el límite de 30k de las grandes URL de Godbolt, pero los enlaces cortos pueden pudrirse y eran 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() en lugar de escribir un char a la vez. Esto minimiza el impacto en el tiempo de todo el programa con perf stat ./collatz (para registrar contadores de rendimiento), y desactivé algunos de los asm no críticos.


El código de @ Veedrac

Tengo una aceleración muy pequeña por el cambio a la derecha tanto como saber necesita hacer y verificar para continuar 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. Usando un contador de tmp k y luego agregarlo a count luego cambia lo que hace clang, pero eso ligeramente duele gcc.

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


1747
2017-11-01 07:04



Afirmar que el compilador de C ++ puede producir un código más óptimo que un programador de lenguaje ensamblador competente es un error muy grave. Y especialmente en este caso. El humano siempre puede mejorar el código que el compilador 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 compilar este código, FreshLib es necesario.

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 compila con -O0: 430 ms contra 1900 ms), y más de dos veces más rápido (430 ms contra 830 ms) cuando se compila el código C ++ con -O3.

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


93
2017-11-01 08:29



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í está un grande win: si miras los 8 bits más bajos de n, todos los pasos hasta que los dividas por 2 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 declaración 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á ramas 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.


19
2017-11-02 10:04



En una nota poco relacionada: ¡más hacks de rendimiento!

  • [la primera «conjetura» ha sido desacreditada finalmente por @ShreevatsaR; remoto]

  • Al atravesar la secuencia, solo podemos obtener 3 casos posibles en el 2-barrio del elemento actual N (mostrado primero):

    1. [incluso] [impar]
    2. [impar] [incluso]
    3. [incluso] [incluso]

    Pasar de largo estos 2 elementos significa calcular (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1 y N >> 2, respectivamente.

    Demostremos que para ambos casos (1) y (2) es posible usar la primera fórmula, (N >> 1) + N + 1.

    El caso (1) es obvio. El caso (2) implica (N & 1) == 1, entonces, si suponemos (sin pérdida de generalidad) que N tiene 2 bits de longitud y sus bits son ba de mayor a menor importancia, luego a = 1, y se cumple lo siguiente:

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

    dónde B = !b. Desplazar a la derecha el primer resultado nos da exactamente lo que queremos.

    Q.E.D .: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1.

    Como se ha demostrado, podemos atravesar la secuencia 2 elementos a la vez, usando una sola operación ternaria. Otra reducción de 2 veces de tiempo.

El algoritmo resultante se ve así:

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;
}

Aquí comparamos n > 2 porque el proceso puede detenerse en 2 en lugar de 1 si la longitud total de la secuencia es impar.

[EDITAR:]

Vamos a traducir esto en conjunto!

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 estos comandos para compilar:

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

Ver la C y una versión mejorada / corregida del asm de Peter Cordes en Godbolt. (Nota del editor: Perdón por poner mis cosas en su respuesta, pero mi respuesta llegó al límite de 30k de Godbolt links + text!)


17
2017-11-01 19:35



Los programas C ++ se traducen a programas ensamblados durante la generación del código máquina a partir del código fuente. Sería virtualmente erróneo decir que el ensamblaje es más lento que C ++. Además, el código binario generado difiere del compilador al compilador. Entonces, un compilador inteligente de C ++ mayo producir código binario más óptimo y eficiente que el código de un ensamblador tonto.

Sin embargo, creo que su metodología de generación de perfiles tiene ciertos defectos. Las siguientes son pautas generales para el perfil:

  1. Asegúrese de que su sistema esté en su estado normal / inactivo. Detenga todos los procesos en ejecución (aplicaciones) que inició o que usan la CPU de forma intensiva (o sondear a través de la red).
  2. Su tamaño de datos debe ser mayor en tamaño.
  3. Su prueba debe ejecutarse por algo más de 5-10 segundos.
  4. No confíes solo en una muestra. Realice su prueba N veces. Recolecta resultados y calcula la media o mediana del resultado.

5
2017-11-01 06:26



De los comentarios:

Pero, este código nunca se detiene (debido al desbordamiento de enteros)!?! Yves Daoust

Para muchos números lo hará no rebosar.

Si se será desbordamiento: para una de esas semillas iniciales desafortunadas, el número desbordado muy probablemente converja hacia 1 sin otro desbordamiento.

Todavía esto plantea una pregunta interesante, ¿hay algún número de semilla cíclico de desbordamiento?

Cualquier serie convergente final simple comienza con una potencia de dos valores (¿bastante obvio?).

2 ^ 64 se desbordará a cero, lo que es un bucle infinito indefinido según el algoritmo (termina solo con 1), pero la solución más óptima en respuesta terminará debido a shr rax produciendo ZF = 1.

¿Podemos producir 2 ^ 64? Si el número inicial es 0x5555555555555555, es un número impar, el siguiente número es 3n + 1, que es 0xFFFFFFFFFFFFFFFF + 1 = 0. Teóricamente en un estado indefinido de algoritmo, pero la respuesta optimizada de johnfound se recuperará al salir de ZF = 1. los cmp rax,1 de Peter Cordes terminará en un ciclo infinito (Variante QED 1, "cheapo" a través de undefined 0 número).

¿Qué tal un número más complejo, que creará un ciclo sin 0? Francamente, no estoy seguro, mi teoría matemática es demasiado vaga para tener una idea seria, cómo manejarla de manera seria. Pero intuitivamente diría que la serie convergerá a 1 para cada número: 0 <número, ya que la fórmula 3n + 1 lentamente convertirá cada factor primo no-2 del número original (o intermedio) en una potencia de 2, tarde o temprano . Por lo tanto, no necesitamos preocuparnos por el ciclo infinito para series originales, solo el desbordamiento puede obstaculizarnos.

Así que puse unos pocos números en la hoja y eché un vistazo a los números truncados de 8 bits.

Hay tres valores que se desbordan a 0: 227, 170 y 85 (85 yendo directamente a 0, otros dos progresando hacia 85)

Pero no hay ningún valor para crear semillas de desbordamiento cíclico.

Curiosamente hice un chequeo, que es el primer número que sufre de truncamiento de 8 bits, y ya 27 ¡Es afectado! Alcanza el valor 9232 en series apropiadas no truncadas (el primer valor truncado es 322 en el paso 12), y el valor máximo alcanzado para cualquiera de los 2-255 números de entrada en forma no truncada es 13120 (Para el 255 sí mismo), número máximo de pasos para converger a 1 es sobre 128 (+ -2, no estoy seguro si "1" es para contar, etc ...).

Curiosamente (para mí) el número 9232 es el máximo para muchos otros números fuente, ¿qué tiene de especial? : -O 9232 = 0x2410 ... hmmm ... no tengo idea.

Lamentablemente, no puedo comprender a fondo esta serie, ¿por qué converge y cuáles son las implicaciones de truncarlas? k bits, pero con cmp number,1 condición de terminación es ciertamente posible poner el algoritmo en un bucle infinito con un valor de entrada particular que termina como 0 después del truncamiento.

Pero el valor 27 desbordamiento para la caja de 8 bits es una especie de alerta, esto parece que si cuenta el número de pasos para alcanzar el valor 1, obtendrás un resultado incorrecto para la mayoría de los números del total de enteros de k bits. Para los enteros de 8 bits, los 146 números de 256 han afectado a la serie por truncamiento (algunos de ellos todavía pueden alcanzar el número correcto de pasos por accidente, tal vez, soy demasiado flojo para comprobarlo).


4
2017-11-01 17:18



No ha publicado el código generado por el compilador, por lo que hay algunas conjeturas aquí, pero incluso sin haberlo visto, se puede decir que esto:

test rax, 1
jpe even

... tiene un 50% de posibilidades de predecir mal la sucursal, y eso será costoso.

Es casi seguro que el compilador haga ambos cálculos (lo que cuesta más, ya que el mod / mod es bastante largo, por lo que el add-add es "libre") y realiza un seguimiento con un CMOV. Que, por supuesto, tiene un cero por ciento de posibilidades de ser malinterpretado.


4
2017-11-01 19:50



Incluso sin mirar el montaje, la razón más obvia es que /= 2 es probablemente optimizado como >>=1 y muchos procesadores tienen una operación de cambio muy rápida. Pero incluso si un procesador no tiene una operación de cambio, la división entera es más rápida que la división de punto flotante.

Editar:  su kilometraje puede variar en la declaración "División entera es más rápida que la división de punto flotante" más arriba. Los comentarios a continuación revelan que los procesadores modernos han priorizado la optimización de la división de fp sobre la división de enteros. Entonces, si alguien estaba buscando la razón más probable para la aceleración de la pregunta de este hilo, entonces la optimización del compilador /=2 como >>=1 sería el mejor 1er lugar para mirar.


En una nota sin relación, Si n es extraño, la expresión n*3+1 siempre será parejo Entonces no hay necesidad de verificar. Puedes cambiar esa rama a

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

Entonces toda la declaración sería entonces

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

4
2017-11-01 21:16



Como una respuesta genérica, no específicamente dirigida a esta tarea: en muchos casos, puede acelerar significativamente cualquier programa al realizar mejoras en un nivel alto. Como calcular datos una vez en lugar de varias veces, evitar el trabajo innecesario por completo, usar cachés de la mejor manera, y así sucesivamente. Estas cosas son mucho más fáciles de hacer en un lenguaje de alto nivel.

Escribir código ensamblador, es posible para mejorar lo que hace un compilador de optimización, pero es un trabajo duro. Y una vez hecho, su código es mucho más difícil de modificar, por lo que es mucho más difícil agregar mejoras algorítmicas. A veces, el procesador tiene una funcionalidad que no puede usar desde un lenguaje de alto nivel, el ensamblaje en línea a menudo es útil en estos casos y aún le permite usar un lenguaje de alto nivel.

En los problemas de Euler, la mayoría de las veces logras construir algo, encuentras por qué es lento, construyes algo mejor, encuentras por qué es lento, y así sucesivamente. Eso es muy, muy difícil usar ensamblador. Un mejor algoritmo a la mitad de la velocidad posible generalmente superará un algoritmo peor a velocidad máxima, y ​​obtener la velocidad máxima en el ensamblador no es trivial.


3
2017-11-04 17:15



Para el problema de Collatz, puede obtener un impulso significativo en el rendimiento almacenando en caché las "colas". Esta es una compensación de tiempo / memoria. Ver: memoización (https://en.wikipedia.org/wiki/Memoization) También podría buscar soluciones de programación dinámica para otras compensaciones de tiempo / memoria.

Ejemplo de implementación de python:

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))

3
2017-11-05 18:49