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



5 Answers

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 frente a 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.

Question

Escribí estas dos soluciones para el Proyecto Euler Q14 , en ensamblador 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

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 formas de optimizar 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 ensamblaje es solo una división por término par.

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

Tiempos de ejecucion

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




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(que se muestra primero):

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

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

    Let`s demuestran 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, por lo que si asumimos (sin pérdida de generalidad) que N tiene una longitud de 2 bits y que sus bits son bade mayor a menor importancia, entonces a = 1, y lo siguiente es válido:

    (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.

    QED: (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 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 > 2porque 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 ensamblaje!

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 / corregida 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 desde los enlaces + texto de Godbolt!)




De los comentarios:

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

Para muchos números que se no desborde.

Si se va a desbordar - para una de esas semillas iniciales de mala suerte, el número sobrevolado es muy probable que convergen hacia 1 sin otra 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, lo 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 raxZF = 1 produce.

¿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. El cmp rax,1de Peter Cordes terminará en un bucle infinito (QED variante 1, "cheapo" a través de un 0número indefinido ).

¿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 . Así que no tenemos que preocuparnos por el bucle infinito para la serie original, 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, 170y 85( 85yendo directamente a 0, otros dos progresando 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 27está afectado! Alcanza el valor 9232en series no truncadas adecuadas (el primer valor truncado está 322en 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 255mismo), el número máximo de pasos para converger 1es sobre 128(+ -2, no estoy seguro si "1" es contar, etc ...).

Curiosamente (para mí) el número 9232es máximo para muchos otros números de fuente, ¿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 cmp number,1condición de terminación es ciertamente posible poner el algoritmo en un bucle infinito con un valor de entrada particular que termina como 0después truncamiento

Pero el valor que se 27desborda 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).




Incluso sin mirar el ensamblaje, la razón más obvia es que /= 2probablemente está optimizado ya que >>=1muchos 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 de "la división de enteros es más rápida que la división de punto flotante". 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. Así que si alguien estuviera mirando por la razón más probable para el aumento de velocidad, que la pregunta de este hilo pregunta acerca de, a continuación, compilador de optimización /=2como >>=1sería el mejor lugar para buscar primero.

En una nota no relacionada , si nes impar, la expresión n*3+1siempre 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;
}



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



Related