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

11 minutos de lectura

¿Por que el codigo C para probar la conjetura de
rosghub

Escribí estas dos soluciones para Proyecto Euler Q14, en ensamblador y en C++. Implementan un enfoque de fuerza bruta idéntico para probar el Conjetura de Collatz. La solución de montaje se montó 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>

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = 3*n + 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;
        }
    }
    std::cout << maxi << std::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++ usa módulo cada término y división cada dos términos, mientras que el código ensamblador solo usa una sola división cada dos términos.

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

tiempos de ejecución

Mi sistema: Linux de 64 bits en Intel Celeron 2955U de 1,4 GHz (microarquitectura Haswell).

  • g++ (sin optimizar): promedio de 1272 ms.
  • g++ -O3: promedio de 578 ms.
  • asm (div) (original): promedio de 2650 ms.
  • asm (shr): promedio de 679 ms.
  • @johnfound asm (ensamblado con NASM): promedio de 501 ms.
  • @hidefromkgb asm: promedio de 200 ms.
  • @hidefromkgb asm, optimizado por @Peter Cordes: promedio de 145 ms.
  • @Veedrac C++: promedio de 81 ms con -O3305 ms con -O0.

  • ¿Ha examinado el código ensamblador que genera GCC para su programa C++?

    – ruakh

    1 de noviembre de 2016 a las 6:14

  • Compilar con -S para obtener el ensamblado que generó el compilador. El compilador es lo suficientemente inteligente como para darse cuenta de que el módulo hace la división al mismo tiempo.

    – usuario3386109

    1 de noviembre de 2016 a las 6:15

  • Creo que tus opciones son 1. Su técnica de medición es defectuosa, 2. El compilador escribe mejor ensamblaje que usted, o 3. El compilador usa magia.

    – Galik

    1 de noviembre de 2016 a las 6:16


  • Genere el asm con el código C + números de línea entretejidos y compare notas.

    – leyendas2k

    1 de noviembre de 2016 a las 6:23

  • @jefferson El compilador puede usar una fuerza bruta más rápida. Por ejemplo, tal vez con instrucciones SSE.

    – usuario253751

    1 de noviembre de 2016 a las 6:25

Respuesta recomendada por Intel

  • Probé el enfoque vectorizado hace un tiempo, no ayudó (porque puedes hacerlo mucho mejor en código escalar con tzcnt y está bloqueado en la secuencia de ejecución más larga entre sus elementos vectoriales en el caso vectorizado).

    – FEO

    1 de noviembre de 2016 a las 8:57

  • @EOF: no, quise decir salir del bucle interno cuando cualquier una de los elementos vectoriales hits 1en lugar de cuando ellos todos tener (fácilmente detectable con PCMPEQ/PMOVMSK). Luego usa PINSRQ y otras cosas para jugar con el único elemento que terminó (y sus contadores), y vuelve al bucle. Eso puede convertirse fácilmente en una pérdida, cuando se sale del ciclo interno con demasiada frecuencia, pero significa que siempre se realizan 2 o 4 elementos de trabajo útil en cada iteración del ciclo interno. Sin embargo, es un buen punto sobre la memorización.

    – Peter Cordes

    1 de noviembre de 2016 a las 9:27


  • @jefferson Lo mejor que logré es godbolt.org/g/1N70Ib. Esperaba poder hacer algo más inteligente, pero parece que no.

    – Veedrac

    2 de noviembre de 2016 a las 21:47

  • Lo que me sorprende de respuestas increíbles como esta es el conocimiento que se muestra con tanto detalle. Nunca conoceré un idioma o sistema a ese nivel y no sabría cómo hacerlo. Bien hecho señor

    – camden_kid

    4 de noviembre de 2016 a las 17:24

  • @csch: gracias. Me alegro de que tanta gente haya sacado algo de lo que escribí. Estoy muy orgulloso de él y creo que hace un buen trabajo al explicar algunos conceptos básicos de optimización y detalles específicos relevantes para este problema.

    – Peter Cordes

    12 de noviembre de 2017 a las 15:14

  • Eh, eso es inteligente. SHR establece ZF solo si EAX era 1 (o 0). Me perdí eso al optimizar gcc’s -O3 salida, pero detecté todas las demás optimizaciones que realizó en el bucle interno. (Pero, ¿por qué usa LEA para el incremento del contador en lugar de INC? Está bien golpear las banderas en ese punto y conducir a una desaceleración en cualquier cosa excepto quizás P4 (falsa dependencia de las banderas antiguas tanto para INC como para SHR). LEA puede ‘ t ejecutarse en tantos puertos y podría generar conflictos de recursos que retrasarían la ruta crítica con más frecuencia).

    – Peter Cordes

    1 de noviembre de 2016 a las 8:44

  • Oh, en realidad Bulldozer podría tener un cuello de botella en el rendimiento con la salida del compilador. Tiene un CMOV de latencia más bajo y un LEA de 3 componentes que Haswell (que estaba considerando), por lo que la cadena de distribución transportada por bucles tiene solo 3 ciclos en su código. Tampoco tiene instrucciones MOV de latencia cero para registros enteros, por lo que las instrucciones MOV desperdiciadas de g ++ en realidad aumentan la latencia de la ruta crítica y son un gran problema para Bulldozer. Entonces, sí, la optimización manual realmente supera al compilador de manera significativa para las CPU que no son lo suficientemente modernas como para masticar las instrucciones inútiles.

    – Peter Cordes

    1 de noviembre de 2016 a las 9:02


  • Decir que el compilador de C++ es mejor es un error muy grave. Y especialmente en este caso. El ser humano siempre puede hacer que el código sea mejor que el y este problema en particular es una buena ilustración de esta afirmación.“Puedes revertirlo y sería igual de válido”.Reclamando un humano es mejor es muy mal error. Y especialmente en este caso. El humano siempre puede hacer el código. peor que el y este en particular pregunta es una buena ilustración de esta afirmación.“Así que no creo que tengas razón aquí, tales generalizaciones están mal.

    – luk32

    1 de noviembre de 2016 a las 15:16

  • @ luk32 – Pero el autor de la pregunta no puede ser ningún argumento, porque su conocimiento del lenguaje ensamblador es casi nulo. Todos los argumentos sobre humano vs compilador, implícitamente asumen humanos con al menos un nivel medio de conocimiento de asm. Más: El teorema “El código escrito por humanos siempre será mejor o igual que el código generado por el compilador” es muy fácil de probar formalmente.

    – johnfound

    1 de noviembre de 2016 a las 15:28

  • @ luk32: un humano experto puede (y generalmente debería) comenzar con la salida del compilador. Entonces, siempre que compare sus intentos para asegurarse de que sean realmente más rápidos (en el hardware de destino que está ajustando), no puede hacerlo peor que el compilador. Pero sí, tengo que estar de acuerdo en que es una declaración un poco fuerte. Los compiladores generalmente lo hacen mucho mejor que los codificadores novatos de ASM. Pero generalmente es posible guardar una instrucción o dos en comparación con lo que crean los compiladores. (Sin embargo, no siempre en la ruta crítica, dependiendo de uarch). Son piezas muy útiles de maquinaria compleja, pero no son “inteligentes”.

    – Peter Cordes

    1 de noviembre de 2016 a las 15:31


  • O cree tablas de búsqueda de datos para las constantes de multiplicación y suma, en lugar de un cambio. Indexar dos tablas de 256 entradas es más rápido que una tabla de salto y los compiladores probablemente no estén buscando esa transformación.

    – Peter Cordes

    2 de noviembre de 2016 a las 11:03

  • Hmm, pensé por un minuto que esta observación podría probar la conjetura de Collatz, pero no, por supuesto que no. Por cada 8 bits finales posibles, hay un número finito de pasos hasta que se acaban. Pero algunos de esos patrones finales de 8 bits alargarán el resto de la cadena de bits en más de 8, por lo que esto no puede descartar un crecimiento ilimitado o un ciclo repetitivo.

    – Peter Cordes

    2 de noviembre de 2016 a las 11:09

  • Actualizar countnecesitas una tercera matriz, ¿verdad? adders[] no le dice cuántos desplazamientos a la derecha se realizaron.

    – Peter Cordes

    2 de noviembre de 2016 a las 22:06


  • Para tablas más grandes, valdría la pena usar tipos más estrechos para aumentar la densidad de caché. En la mayoría de las arquitecturas, una carga de extensión cero desde un uint16_t es muy barato. En x86, es tan barato como la extensión cero desde 32 bits unsigned int para uint64_t. (MOVZX de la memoria en las CPU Intel solo necesita un uop de puerto de carga, pero las CPU AMD también necesitan la ALU). Oh, por cierto, ¿por qué estás usando size_t por lastBits? Es un tipo de 32 bits con -m32e incluso -mx32 (modo largo con punteros de 32 bits). Definitivamente es el tipo incorrecto para n. Solo usa unsigned.

    – Peter Cordes

    2 de noviembre de 2016 a las 22:21

  • Sí, no he realizado ningún perfil formal, pero los he ejecutado varias veces y soy capaz de distinguir 2 segundos de 3 segundos. De todos modos gracias por responder. Ya recogí una gran cantidad de información aquí.

    – rosghub

    1 de noviembre de 2016 a las 6:50

  • probablemente no sea sólo un error de medición, el código asm escrito a mano utiliza una instrucción DIV de 64 bits en lugar de un desplazamiento a la derecha. Mira mi respuesta. Pero sí, medir correctamente también es importante.

    – Peter Cordes

    1 de noviembre de 2016 a las 7:05


  • Las viñetas son un formato más apropiado que un bloque de código. Deje de poner su texto en un bloque de código, porque no es código y no se beneficia de una fuente monoespaciada.

    – Peter Cordes

    1 de noviembre de 2016 a las 9:33

  • Realmente no veo cómo esto responde a la pregunta. Esta no es una pregunta vaga sobre si el código ensamblador o el código C++ puede que ser más rápido — es una pregunta muy específica sobre código real, que ha proporcionado amablemente en la pregunta misma. Su respuesta ni siquiera menciona nada de ese código, ni hace ningún tipo de comparación. Claro, sus consejos sobre cómo comparar son básicamente correctos, pero no lo suficiente como para dar una respuesta real.

    – Cody gris

    1 de noviembre de 2016 a las 14:51

  • Sí, no he realizado ningún perfil formal, pero los he ejecutado varias veces y soy capaz de distinguir 2 segundos de 3 segundos. De todos modos gracias por responder. Ya recogí una gran cantidad de información aquí.

    – rosghub

    1 de noviembre de 2016 a las 6:50

  • probablemente no sea sólo un error de medición, el código asm escrito a mano utiliza una instrucción DIV de 64 bits en lugar de un desplazamiento a la derecha. Mira mi respuesta. Pero sí, medir correctamente también es importante.

    – Peter Cordes

    1 de noviembre de 2016 a las 7:05


  • Las viñetas son un formato más apropiado que un bloque de código. Deje de poner su texto en un bloque de código, porque no es código y no se beneficia de una fuente monoespaciada.

    – Peter Cordes

    1 de noviembre de 2016 a las 9:33

  • Realmente no veo cómo esto responde a la pregunta. Esta no es una pregunta vaga sobre si el código ensamblador o el código C++ puede que ser más rápido — es una pregunta muy específica sobre código real, que ha proporcionado amablemente en la pregunta misma. Su respuesta ni siquiera menciona nada de ese código, ni hace ningún tipo de comparación. Claro, sus consejos sobre cómo comparar son básicamente correctos, pero no lo suficiente como para dar una respuesta real.

    – Cody gris

    1 de noviembre de 2016 a las 14:51

  • Hay algún patrón en la ramificación; por ejemplo, un número impar siempre va seguido de un número par. Pero a veces, 3n+1 deja múltiples ceros finales, y ahí es cuando esto predice mal. Comencé a escribir sobre la división en mi respuesta y no abordé esta otra gran bandera roja en el código del OP. (Tenga en cuenta también que usar una condición de paridad es realmente extraño, en comparación con solo JZ o CMOVZ. También es peor para la CPU, porque las CPU Intel pueden fusionar macro TEST/JZ, pero no TEST/JPE. Agner Fog dice que AMD puede fusionar cualquier TEST/CMP con cualquier JCC, por lo que en ese caso solo es peor para los lectores humanos)

    – Peter Cordes

    6 de noviembre de 2016 a las 16:14


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad