it-swarm-es.tech

Código de C++ para probar la conjetura de Collatz más rápido que la Asamblea escrita a mano, ¿por qué?

Escribí estas dos soluciones para Proyecto Euler Q14 , en Assembly y en C++. Son el mismo enfoque de fuerza bruta idéntico para probar la conjetura de Collatz . La solución de montaje fue ensamblada con

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

El C++ fue compilado 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 <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 formas de optimizar aún más mi solución de ensamblaje (hablando programáticamente no matemáticamente).

El código C++ tiene módulo para cada término y división para cada término par, donde Asamblea es solo una división por término par.

Pero la Asamblea está tomando en promedio 1 segundo más que la solución C++. ¿Por qué es esto? Lo pregunto por curiosidad.

Tiempos de ejecucion

Mi sistema: Linux de 64 bits en Intel Celeron 2955U a 1.4 GHz (microarquitectura Haswell).

778
jeffer son

Si piensa 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 asm del compilador supere su código escrito a mano, incluso con -O0compilación rápida, sin optimización adicional, y almacenamiento/recarga en la memoria después/antes de cada sentencia C para que un depurador pueda modificar las variables).

Consulte la guía de Optimización de ensamblajes de Agner Fog para aprender a escribir asm eficientes. También tiene tablas de instrucciones y una guía de microarcas para detalles específicos para CPU específicas. Vea también la etiqueta x86 wiki para más enlaces de perf.

Vea también esta pregunta más general sobre vencer al compilador con asm escrito a mano: ¿Es el lenguaje ensamblador en línea más lento que el código C++ nativo? . 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 de manera eficiente. ¿También ve ensamblaje más rápido que los lenguajes compilados? . Una de las respuestas está vinculada a estas diapositivas limpias que muestran cómo varios compiladores de C optimizan algunas funciones realmente simples con trucos geniales.


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

En Intel Haswell, div r64es 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 orden puede ejecutarse temprano). Las instrucciones de alto uop-count como DIV están microcodificadas, lo que también puede causar cuellos de botella en el front-end. 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 1c de latencia, 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 en comparación con los cambios. idiv r32 es 9 uops, 22-29c de latencia y uno por rendimiento de 8-11c en Haswell.


Como se puede ver al mirar la salida de -O0 asm de gcc ( Explorador de Godbolt Explorer ), solo usa las instrucciones de turnos. Clang -O0 compila ingenuamente como pensaste, incluso usando IDIV de 64 bits dos veces. optimizando, los compiladores usan ambas salidas de IDIV cuando la fuente realiza una división y un 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 reconocer la división por constante y usar los cambios (potencia de 2) o un inverso multiplicativo de punto fijo (sin potencia de 2) para evitar IDIV (consulte div_by_13 en el enlace de godbolt anterior).

gcc -Osoptimizar para el tamaño) hace usa IDIV para la división sin potencia de 2, desafortunadamente 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 compilador

(resumen para este caso: use uint64_t n)

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

Mire la salida de su asm (en Godbolt, o vea ¿Cómo eliminar el "ruido" de la salida de GCC/clang Assembly? ). Cuando el compilador no crea un código óptimo en primer lugar: Escribir su fuente de C/C++ de una manera que guíe al compilador para hacer un mejor código suele ser el mejor enfoque. Usted debe saber asm, y saber qué eficiente, pero usted aplica este conocimiento de manera indirecta. Los compiladores también son una buena fuente de ideas: a veces, clang hará algo genial, y puede sostener a gcc para que haga lo mismo: vea 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 el hardware futuro (x86 o no), tal vez utilizando la nueva extensión ISA o la auto-vectorización. El x86-64 asm escrito a mano desde hace 15 años no suele estar optimizado para Skylake. p.ej. La macro-fusión de compare y ramificada no existía entonces. Lo que es óptimo ahora para asm hecho a mano para una microarquitectura 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=... solo para sintonizar, sin utilizar instrucciones que otras CPU no puedan admitir.

Mi sensación es que guiar el compilador a un controlador que es bueno para una CPU actual que le interesa no debería ser un problema para los compiladores futuros. Esperamos que sean mejores que los compiladores actuales para encontrar formas de transformar el código, y pueden encontrar una forma que funcione para las futuras CPU. Independientemente, el futuro x86 probablemente no será terrible en nada que sea bueno en el x86 actual, y el futuro compilador evitará cualquier trampa específica de asm al implementar algo como el movimiento de datos desde su fuente de C, si no ve algo mejor.

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

En este caso: su n tiene un tipo con signo, y gcc usa la secuencia SAR/SHR/ADD que proporciona el redondeo correcto. (IDIV y "redondeo" de desplazamiento aritmético para entradas negativas, vea SAR insn set ref manual entry ). (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ía haber usado uint64_t n, para que solo pueda SHR. Y, por lo tanto, es portátil para los sistemas donde long es solo de 32 bits (por ejemplo, x86-64 Windows).


Por cierto, gcc's optimizado asm se ve bastante bien (usando unsigned long n): el bucle interno que se alinea 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 el bucle es:

  • LEA de 3 componentes (3 ciclos)
  • cmov (2 ciclos en Haswell, 1c en Broadwell o posterior).

Total: 5 ciclos por iteración, cuello de botella de latencia. La ejecución fuera de orden se encarga 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 a 5c/iter).

La entrada FLAGS de cmovproducida 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 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 una latencia cero (manejada en el momento del registro-renombrar). (Todavía toma 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 LEA es parte del cuello de botella en otras CPU.

El cmp/jne tampoco forma parte de la ruta crítica: no se transporta en bucle, porque 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 buen trabajo aquí. Podría guardar un byte de código usando inc edx EN LUGAR DE add edx, 1 , porque a nadie le importa P4 y sus dependencias falsas para las instrucciones de modificación de marca parcial.

También podría guardar todas las instrucciones MOV, y el TEST: SHR establece CF = el bit cambiado, por lo que podemos 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 inteligente: elimine el CMP bifurcando el resultado del indicador de SHR y usándolo para CMOV: cero solo si n era 1 (o 0) para comenzar. (Dato curioso: SHR con cuenta! = 1 en Nehalem o anterior provoca un bloqueo si lees los resultados de la bandera . Así es como lo hicieron con un solo uop. Sin embargo, la codificación especial de cambio por 1 está bien. )

Evitar MOV no ayuda con la latencia en absoluto en Haswell ( ¿Puede MOV de x86 realmente ser "gratuito"? ¿Por qué no puedo reproducir esto en absoluto? ). Ayuda a significativamente en CPU 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-LEA y CMOV de BD tienen una 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 en el rendimiento se convierten en un problema, ya que solo tiene dos conductos ALU enteros. Ver la respuesta de @ johnfound , donde tiene resultados de temporización de una CPU AMD.

Incluso en Haswell, esta versión puede ayudar un poco al evitar algunos retrasos ocasionales en los que un uop no crítico roba un puerto de ejecución de uno en la ruta crítica, lo que retrasa la ejecución en 1 ciclo. (Esto se llama un conflicto de recursos). También guarda un registro, que puede ayudar cuando se realizan varios valores de n en paralelo en un bucle intercalado (ver más abajo).

_ (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 requiere dos agregados separados), pero solo 1c con 2 o menos componentes (un agregado). Algunas CPU (como Core2) hace 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 para que no haya 2c uops , de lo contrario, la LEA de 3 componentes sería solo 2c como Bulldozer. (LEA de 3 componentes también es más lento en AMD, pero no tanto).

Por lo tanto, lea rcx, [rax + rax*2]/inc rcx tiene una latencia de solo 2c, 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 adicional, que normalmente no vale la pena para ahorrar 1c de latencia, pero la latencia es el principal cuello de botella aquí y Haswell tiene una tubería lo suficientemente amplia como para manejar el rendimiento adicional de 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. problemas de pequeña escala. (Dados entre miles y millones de veces más de tiempo para pensar en ello, por supuesto. Los compiladores no usan algoritmos exhaustivos para buscar todas las formas posibles de hacer las cosas, porque eso llevaría demasiado tiempo al optimizar muchos de los contenidos en línea. código, que es lo que hacen mejor. Tampoco modelan la canalización en la microarquitectura objetivo, al menos no con el mismo detalle que IACA u otras herramientas de análisis estático, solo utilizan algunas heurísticas. )


El desenrollamiento de bucle simple no ayudará; este cuello de botella se cuelga de la latencia de una cadena de dependencia transmitida por bucle, no en la sobrecarga/rendimiento del bucle. ya que la CPU tiene mucho tiempo para intercalar instrucciones de dos subprocesos. Esto significaría paralelizar el bucle en main, pero eso está bien porque cada subproceso puede simplemente verificar un rango de n valores y producir un par de enteros como resultado.

El intercalado a mano dentro de un solo hilo puede ser viable, también. Tal vez calcular la secuencia para un par de números en paralelo, ya que cada uno solo lleva un par de registros, y todos pueden actualizar el mismo max/maxi. crea más paralelismo a nivel de instrucción .

El truco es decidir si esperar hasta que todos los valores de n hayan llegado a 1 antes de obtener otro par de valores de n de inicio, o si se debe romper y obtener un nuevo punto de inicio por solo uno que llegó a la condición final, sin tocar los registros de otra secuencia Probablemente es mejor mantener cada cadena trabajando en datos útiles, de lo contrario tendrías que incrementar condicionalmente su contador.


Tal vez podría incluso hacer esto con SSE empacado-comparar cosas para incrementar condicionalmente el contador de los elementos vectoriales donde n aún no ha alcanzado 1. Y luego, para ocultar la latencia aún más prolongada de una implementación de incremento condicional SIMD, deberá mantener en el aire más vectores de valores de n. Tal vez solo valga la pena con 256b vector (4x uint64_t).

Creo que la mejor estrategia para realizar la detección de un 1 "sticky" es enmascarar el vector de todos los agregados 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 a mano.


Mejora algorítmica/implementación:

Además de 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. Memoize para detectar finales comunes a secuencias. O incluso mejor, mire 8 bits finales a la vez (la respuesta de Gnasher)

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

Así que el bucle 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 una cantidad significativamente menor de iteraciones, pero los cambios en el conteo de variables son lentos en las CPU de la familia SnB de Intel sin BMI2. 3 uops, 2c de latencia. (Tienen una dependencia de entrada en FLAGS porque cuenta = 0 significa que las marcas no están modificadas. Manejan esto como una dependencia de datos y toman múltiples uops porque una uop solo puede tener 2 entradas (de todas formas pre-HSW/BDW)). Este es el tipo al que se refieren las personas que se quejan del diseño loco-CISC de x86. Hace que las CPU x86 sean más lentas de lo que serían si el ISA se diseñara desde cero hoy, incluso de una manera casi similar. (es decir, esto es 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 posteriormente) en la ruta crítica, por lo que alarga significativamente la latencia total de la cadena de dependencia transmitida por bucle. Sin embargo, elimina cualquier necesidad de un CMOV, o para preparar un registro con n>>1, sin embargo. _ (La respuesta de @Veedrac supera todo esto al diferir tzcnt/shift para múltiples iteraciones, lo cual es altamente efectivo (ver más abajo).

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

TZCNT se desempeña mucho mejor que BSF en las CPUs 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 solo guarda el byte si eso es lo único que importa. TZCNT en Intel (pre-Skylake) aún tiene una dependencia falsa en el operando de salida supuestamente de solo escritura, al igual que BSF, para admitir el comportamiento no documentado de que BSF con entrada = 0 deja su destino sin modificar. Por lo tanto, debe evitarlo a menos que se optimice solo para Skylake, por lo que no se gana nada con el byte REP adicional. (Intel a menudo va más allá de lo que requiere el manual x86 ISA, para evitar romper el código ampliamente utilizado que depende de algo que no debería, o que está deshabilitado retroactivamente. Por ejemplo, Windows 9x no asume ninguna especulación captura previa de entradas de TLB , que era segura 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 la misma depuración falsa que POPCNT: vea esta Q&A . Esta es la razón por la que en la salida de asm de gcc para el código de @ Veedrac, ve que rompe la cadena de dep con xor-zeroing en el registro que se usará como destino de TZCNT, cuando no usa dst = src. Dado que TZCNT/LZCNT/POPCNT nunca dejan su destino sin definir o sin modificar, esta dependencia falsa de la salida en las CPU de Intel es simplemente un error/limitación de rendimiento. Presumiblemente, vale la pena que algunos transistores/potencias hagan que se comporten como otros elementos que van a la misma unidad de ejecución. El único lado positivo del software está en la interacción con otra limitación de la microarquitectura: pueden micro-fusionar un operando de memoria con un modo de direccionamiento indexado en Haswell, pero en Skylake, donde Intel eliminó la dependencia falsa para LZCNT/TZCNT " Un-laminate "modos de direccionamiento indexado, mientras que POPCNT todavía puede micro-fusionar cualquier modo addr.


Mejoras a ideas/código de otras respuestas:

la respuesta de @ hidefromkgbtiene una buena observación de que tienes la garantía de poder hacer un cambio a la derecha después de un 3n + 1. Puedes calcular esto de manera aún más eficiente que simplemente dejando de lado los controles entre los pasos. La implementación de asm Sin embargo, en esa respuesta se interrumpe (depende de OF, que no está definido después de SHRD con un conteo> 1), y lento: ROR rdi,2 es más rápido que SHRD rdi,rdi,2, y usar dos instrucciones CMOV en la ruta crítica es más lento que un TEST adicional que Se puede ejecutar en paralelo.

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

También se mejoró la impresión de salida para convertirla en una cadena y hacer una write() en lugar de escribir una char a la vez. Esto minimiza el impacto en el cronometraje de todo el programa con perf stat ./collatzpara registrar los contadores de rendimiento), y eliminé la ofuscación de algunos de los asm no críticos.


_ (Código de @veedrac

Conseguí una aceleración muy pequeña desde el desplazamiento a la derecha tanto como nosotros know necesitamos hacer, y verificando para continuar el ciclo. Desde 7.5s para limit = 1e8 hasta 7.275s, en Core2Duo (Merom), con un factor de desenrollado de 16.

código + comentarios en Godbolt . No uses esta versión con clang; hace algo tonto con el defer-loop. Usar un contador tmp k y luego agregarlo a count luego cambia lo que hace el clang, pero eso ligeramente duele gcc.

Vea la discusión en los comentarios: El código de Veedrac es excelente en las CPU con BMI1 (es decir, no Celeron/Pentium)

1818
Peter Cordes

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 hacer el código mejor que el compilador, y esta situación particular es una buena ilustración de esta afirmación.

La diferencia de tiempo que está viendo es porque 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 puede optimizarse para 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 como:

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

La salida de ambos programas es la misma: secuencia máxima = 525 en i = 837799.

95
johnfound

Para obtener más rendimiento: un simple cambio 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 pruebes. Así que podrías guardar algunas declaraciones 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 un big win: Si observas los 8 bits más bajos de n, todos los pasos hasta que se dividan 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 entonces 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  -> ???? ???? ????

Por lo tanto, todos estos pasos se pueden predecir, y 256k + 1 se reemplaza por 81k + 1. Algo similar sucederá para todas las combinaciones. Así que puedes hacer un bucle con una instrucción de cambio grande:

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 en el que alcanzó 1 por primera vez. Luego continúe con el bucle "normal" o prepare una tabla que le indique cuántos pasos más se necesitan para alcanzar 1.

PD. Sospecho fuertemente que la sugerencia de Peter Cordes lo haría aún más rápido. No habrá ramas condicionales en absoluto, excepto una, y esa se predecirá correctamente, excepto cuando el bucle realmente termine. Así que 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, 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 se produce una ralentización cuando las tablas ya no caben en la memoria 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 en realidad podemos calcular el número de pasos (según el número de iteraciones del bucle).

Podríamos redefinir el problema ligeramente: Reemplace n con (3n + 1)/2 si es impar, y reemplace n con n/2 si es par. Luego, cada iteración hará exactamente 8 pasos, pero se podría considerar trampa :-) Así que supongamos que hubo r operaciones n <- 3n + 1 y s 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 precomputada, cuántas iteraciones se necesitan desde cualquier punto de inicio n ≤ 1,000,000 y luego calculando r como arriba, redondeado al número entero más cercano, daremos el resultado correcto a menos que s sea realmente grande.

21
gnasher729

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

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

  • Al atravesar la secuencia, solo podemos obtener 3 casos posibles en la vecindad 2 del elemento actual N (se muestra primero):

    1. [par] [impar]
    2. [impar] [par]
    3. [par] [par]

    Saltar más allá de estos 2 elementos significa calcular (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1 y N >> 2, respectivamente.

    Probemos que en 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, por lo que si asumimos (sin pérdida de generalidad) que N tiene una longitud de 2 bits y sus bits son ba de más a menos significativos, entonces a = 1, y lo siguiente se mantiene

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

    donde B = !b. Cambiar el primer resultado a la derecha nos da exactamente lo que queremos.

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

    Como se demostró, podemos recorrer los elementos de la secuencia 2 a la vez, utilizando una sola operación ternaria. Otra reducción de tiempo de 2 ×.

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 Asamblea!

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;

Usa estos comandos para compilar:

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

Vea la C y una versión mejorada/solucionada de errores del asm por Peter Cordes en Godbolt . (Nota del editor: Perdón por poner mis cosas en tu respuesta, pero mi respuesta alcanzó el límite de caracteres de 30k de los enlaces + texto de Godbolt)

18
hidefromkgb

Los programas C++ se traducen a programas de ensamblaje durante la generación de código de 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 de compilador a compilador. Así que un compilador inteligente de C++ puede producir código binario más óptimo y eficiente que un código de ensamblador tonto.

Sin embargo, creo que su metodología de perfiles tiene ciertos defectos. Las siguientes son pautas generales para perfilar:

  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 usa la CPU de forma intensiva (o sondeo en la red).
  2. Su tamaño de datos debe ser mayor en tamaño.
  3. Su prueba debe durar más de 5-10 segundos.
  4. No confíe en una sola muestra. Realiza tu prueba N veces. Recopile los resultados y calcule la media o la mediana del resultado.

Para el problema de Collatz, puede obtener un aumento significativo en el rendimiento al almacenar en caché las "colas". Este es un intercambio de tiempo/memoria. Consulte: memoization ( https://en.wikipedia.org/wiki/Memoization ). También puede 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 __== "__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))
5

Incluso sin mirar el ensamblaje, la razón más obvia es que /= 2 probablemente está 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.

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


En una nota no relacionada, si n es impar, la expresión n*3+1 siempre será par. Así que no hay necesidad de comprobarlo. Puedes cambiar esa rama a

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

Así que toda la declaración sería entonces

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

De los comentarios:

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

Para muchos números será no desbordante.

Si será desbordamiento - para una de esas semillas iniciales desafortunadas, es muy probable que el número de desbordamiento converja hacia 1 sin otro desbordamiento.

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

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

2 ^ 64 se desbordarán a cero, que es un bucle infinito indefinido según el algoritmo (termina solo con 1), pero la solución más óptima en la respuesta finalizará debido a que shr rax produce 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 de algoritmo indefinido, pero la respuesta optimizada de johnfound se recuperará al salir de ZF = 1. El cmp rax,1 de Peter Cordes terminará en un bucle infinito (QED variante 1, "cheapo" a través del número 0 no definido).

¿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 confusa para tener una idea seria, cómo tratarla 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 convertirá lentamente cada factor primo no-2 del número original (o intermedio) en una potencia de 2, tarde o temprano . Por lo tanto, no debemos preocuparnos por el bucle infinito para las series originales, solo el desbordamiento puede obstaculizarnos.

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

Hay tres valores que desbordan a 0: 227, 170 y 85 (85 va directamente a 0, otros dos avanzan hacia 85).

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

Curiosamente, hice un chequeo, que es el primer número que sufre un truncamiento de 8 bits, ¡y ya 27 está afectado! Alcanza el valor 9232 en la serie correcta no truncada (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 de manera no truncada es 13120 (para el 255), el número máximo de pasos para converger a 1 es aproximadamente 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 de origen, ¿qué tiene de especial? : -O 9232 = 0x2410 ... hmmm .. ni idea.

Desafortunadamente, no puedo comprender en profundidad esta serie, ¿por qué converge y cuáles son las implicaciones de truncarlos a k bits, pero con la condición de terminación cmp number,1 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 desbordante para el caso de 8 bits es una especie de alerta, parece que si cuenta el número de pasos para alcanzar el valor 1, obtendrá un resultado incorrecto para la mayoría de los números del conjunto total de enteros de k bits. Para los enteros de 8 bits, los 146 números de 256 han afectado las series por truncamiento (algunos de ellos aún pueden alcanzar el número correcto de pasos por accidente, tal vez, soy demasiado perezoso para comprobarlo).

4
Ped7g

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

test rax, 1
jpe even

... tiene un 50% de probabilidades de predecir mal la sucursal, y eso será caro.

Es casi seguro que el compilador realiza ambos cálculos (lo que cuesta mucho más debido a que el div/mod es una latencia bastante larga, por lo que el complemento múltiple es "gratuito") y continúa con un CMOV. Lo cual, por supuesto, tiene un cero porcentaje de probabilidad de ser mal predicho.

4
Damon

Como respuesta genérica, no dirigida específicamente a esta tarea: en muchos casos, puede acelerar significativamente cualquier programa realizando mejoras a un alto nivel. Como calcular los datos una vez en lugar de varias veces, evitando el trabajo innecesario por completo, utilizando 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.

Al escribir código de ensamblador, es posible mejorar en lo que hace un compilador de optimización, pero es un trabajo duro. Y una vez hecho esto, 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 se puede usar en un lenguaje de alto nivel, el ensamblaje en línea suele ser ú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 tienes éxito construyendo algo, descubriendo por qué es lento, construyendo algo mejor, encontrando por qué es lento, y así sucesivamente. Eso es muy, muy difícil de usar ensamblador. Un mejor algoritmo a la mitad de la velocidad posible usualmente vencerá a un peor algoritmo a toda velocidad, y obtener la velocidad máxima en ensamblador no es trivial.

3
gnasher729