arrays - ¿Por qué hay un gran impacto en el rendimiento cuando se recorre una matriz con 240 o más elementos?

performance rust

Question

Al ejecutar un bucle de suma sobre una matriz en Rust, noté una gran caída de rendimiento cuando CAPACITY > = 240. CAPACITY = 239 es aproximadamente 80 veces más rápido.

¿Existe una optimización de compilación especial que Rust está haciendo para los arreglos "cortos"?

Compilado con rustc -C opt-level=3 .

use std::time::Instant;

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

fn main() {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }
    let mut sum = 0;
    let now = Instant::now();
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }
    println!("sum:{} time:{:?}", sum, now.elapsed());
}

Answer 1

Además de la respuesta de Lukas, si desea utilizar un iterador, intente esto:

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

pub fn bar() -> usize {
    (0..CAPACITY).sum::<usize>() * IN_LOOPS
}

Gracias @ Chris Morgan por la sugerencia sobre el patrón de rango.

El montaje optimizado es bastante bueno:

example::bar:
        movabs  rax, 14340000000
        ret

Answer 2

Resumen : debajo de 240, LLVM desenrolla completamente el bucle interno y eso le permite notar que puede optimizar el bucle de repetición, rompiendo su punto de referencia.

Encontraste un umbral mágico por encima del cual LLVM deja de realizar ciertas optimizaciones . El umbral es de 8 bytes * 240 = 1920 bytes (su matriz es una matriz de usize s, por lo tanto, la longitud se multiplica por 8 bytes, suponiendo CPU x86-64). En este punto de referencia, una optimización específica, solo realizada para la longitud 239, es responsable de la gran diferencia de velocidad. Pero comencemos lentamente:

(Todo el código en esta respuesta se compila con -C opt-level=3 )

pub fn foo() -> usize {
    let arr = [0; 240];
    let mut s = 0;
    for i in 0..arr.len() {
        s += arr[i];
    }
    s
}

Este código simple producirá aproximadamente el ensamblado que uno esperaría: un bucle que agrega elementos. Sin embargo, si cambia 240 a 239 , el conjunto emitido difiere bastante. Véalo en Godbolt Compiler Explorer . Aquí hay una pequeña parte de la asamblea:

movdqa  xmm1, xmmword ptr [rsp + 32]
movdqa  xmm0, xmmword ptr [rsp + 48]
paddq   xmm1, xmmword ptr [rsp]
paddq   xmm0, xmmword ptr [rsp + 16]
paddq   xmm1, xmmword ptr [rsp + 64]
; more stuff omitted here ...
paddq   xmm0, xmmword ptr [rsp + 1840]
paddq   xmm1, xmmword ptr [rsp + 1856]
paddq   xmm0, xmmword ptr [rsp + 1872]
paddq   xmm0, xmm1
pshufd  xmm1, xmm0, 78
paddq   xmm1, xmm0

Esto es lo que se denomina desenrollamiento de bucle : LLVM pega el cuerpo del bucle un montón de tiempo para evitar tener que ejecutar todas esas "instrucciones de gestión del bucle", es decir, incrementar la variable del bucle, verificar si el bucle ha finalizado y saltar al inicio del bucle. .

En caso de que se lo pregunte: el paddq e instrucciones similares son instrucciones SIMD que permiten sumar múltiples valores en paralelo. Además, dos registros SIMD de 16 bytes ( xmm0 y xmm1 ) se usan en paralelo para que el paralelismo a nivel de instrucción de la CPU básicamente pueda ejecutar dos de estas instrucciones al mismo tiempo. Después de todo, son independientes entre sí. Al final, ambos registros se suman y luego se suman horizontalmente al resultado escalar.

Las CPU x86 mainstream modernas (no Atom de baja potencia) realmente pueden hacer 2 cargas de vectores por reloj cuando llegan a la caché L1d, y el rendimiento de paddq también es de al menos 2 por reloj, con 1 ciclo de latencia en la mayoría de las CPU. Consulte https://agner.org/optimize/ y también estas preguntas y respuestas sobre los múltiples acumuladores para ocultar la latencia (de FP FMA para un producto de punto) y el cuello de botella en el rendimiento.

LLVM desenrolla pequeños bucles cuando no se desenrolla por completo y aún utiliza múltiples acumuladores. Por lo tanto, los cuellos de botella de latencia de ancho de banda y back-end no son un gran problema para los bucles generados por LLVM, incluso sin un desenrollado completo.

¡Pero el desenrollado de bucle no es responsable de una diferencia de rendimiento del factor 80! Al menos no se desenrolla en bucle solo. Echemos un vistazo al código de evaluación comparativa real, que coloca un bucle dentro de otro:

const CAPACITY: usize = 239;
const IN_LOOPS: usize = 500000;

pub fn foo() -> usize {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }

    let mut sum = 0;
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }

    sum
}

( En Godbolt Compiler Explorer )

El ensamblaje para CAPACITY = 240 parece normal: dos bucles anidados. (Al comienzo de la función hay bastante código solo para inicializar, que ignoraremos). Sin embargo, para 239, ¡se ve muy diferente! Vemos que el ciclo de inicialización y el ciclo interno se desenrollaron: hasta ahora tan esperado.

¡La diferencia importante es que para 239, LLVM pudo descubrir que el resultado del bucle interno no depende del bucle externo! Como consecuencia, LLVM emite código que básicamente solo ejecuta primero el bucle interno (calculando la suma) y luego simula el bucle externo sumando la sum varias veces.

Primero vemos casi el mismo ensamblaje que el anterior (el ensamblaje representa el bucle interno). Luego vemos esto (comenté para explicar el ensamblaje; los comentarios con * son especialmente importantes):

        ; at the start of the function, `rbx` was set to 0

        movq    rax, xmm1     ; result of SIMD summing up stored in `rax`
        add     rax, 711      ; add up missing terms from loop unrolling
        mov     ecx, 500000   ; * init loop variable outer loop
.LBB0_1:
        add     rbx, rax      ; * rbx += rax
        add     rcx, -1       ; * decrement loop variable
        jne     .LBB0_1       ; * if loop variable != 0 jump to LBB0_1
        mov     rax, rbx      ; move rbx (the sum) back to rax
        ; two unimportant instructions omitted
        ret                   ; the return value is stored in `rax`

Como puede ver aquí, se toma el resultado del bucle interno, se suma tan a menudo como el bucle externo se hubiera ejecutado y luego regresado. LLVM solo puede realizar esta optimización porque entiende que el bucle interno es independiente del externo.

Esto significa que el tiempo de ejecución cambia de CAPACITY * IN_LOOPS a CAPACITY + IN_LOOPS . Y esto es responsable de la gran diferencia de rendimiento.

Una nota adicional: ¿puedes hacer algo al respecto? Realmente no. LLVM tiene que tener umbrales mágicos, ya que sin ellos, las optimizaciones de LLVM podrían tardar una eternidad en completarse en cierto código. Pero también podemos estar de acuerdo en que este código fue altamente artificial. En la práctica, dudo que ocurra una diferencia tan grande. La diferencia debido al desenrollamiento de bucle completo generalmente no es siquiera el factor 2 en estos casos. Así que no hay que preocuparse por los casos de uso real.

Como última nota sobre el código idiomático de Rust: arr.iter().sum() es una mejor manera de resumir todos los elementos de una matriz. Y cambiar esto en el segundo ejemplo no conduce a diferencias notables en el ensamblaje emitido. Debe usar versiones cortas e idiomáticas a menos que haya medido que perjudica el rendimiento.