Por que há um grande impacto no desempenho ao fazer um loop sobre uma matriz com 240 ou mais elementos?

Ao executar um loop de soma em uma matriz no Rust, notei uma enorme queda de desempenho quando CAPACITY> = 240. CAPACITY= 239 é cerca de 80 vezes mais rápido.

Existe otimização de compilação especial que Rust está fazendo para matrizes "curtas"?

Compilado com 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());
}

Resumo : abaixo de 240, o LLVM desenrola completamente o loop interno e isso permite que ele perceba que ele pode otimizar o loop de repetição, quebrando sua referência.

Você encontrou um limite mágico acima do qual o LLVM para de executar determinadas otimizações . O limite é 8 bytes * 240 = 1920 bytes (sua matriz é uma matriz de usizes, portanto, o comprimento é multiplicado por 8 bytes, assumindo a CPU x86-64). Nesse benchmark, uma otimização específica - realizada apenas para o comprimento 239 - é responsável pela enorme diferença de velocidade. Mas vamos começar devagar:

(Todo o código nesta resposta é compilado -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
}

Esse código simples produzirá aproximadamente o conjunto que se esperaria: um loop adicionando elementos. No entanto, se você alterar 240para 239, o conjunto emitido difere bastante. Veja no Godbolt Compiler Explorer . Aqui está uma pequena parte da montagem:

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

É o que se chama desenrolamento de loop : o LLVM cola o corpo do loop por um bocado de tempo para evitar a execução de todas essas "instruções de gerenciamento de loop", ou seja, aumentando a variável do loop, verifique se o loop terminou e o salto para o início do loop. .

Caso você esteja se perguntando: as paddqinstruções e similares são instruções SIMD que permitem resumir vários valores em paralelo. Além disso, dois registros SIMD de 16 bytes ( xmm0e xmm1) são usados ​​em paralelo para que o paralelismo no nível da instrução da CPU possa executar basicamente duas dessas instruções ao mesmo tempo. Afinal, eles são independentes um do outro. No final, os dois registros são somados e, em seguida, somados horizontalmente até o resultado escalar.

As modernas CPUs x86 convencionais (não Atom de baixa potência) podem realmente realizar 2 cargas vetoriais por clock quando atingem o cache L1d, e a paddqtaxa de transferência também é de pelo menos 2 por clock, com latência de 1 ciclo na maioria das CPUs. Consulte https://agner.org/optimize/ e também esta seção de perguntas e respostas sobre vários acumuladores para ocultar a latência (do FP FMA para um produto escalar) e gargalo na taxa de transferência.

O LLVM desenrola pequenos loops alguns quando não está totalmente desenrolando e ainda usa vários acumuladores. Geralmente, gargalos de largura de banda de front-end e latência de back-end não são um grande problema para os loops gerados por LLVM, mesmo sem o desenrolamento completo.

Mas o desenrolar do loop não é responsável por uma diferença de desempenho do fator 80! Pelo menos não se desenrola sozinho. Vamos dar uma olhada no código de benchmarking real, que coloca um loop dentro de outro:

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
}

( No Godbolt Compiler Explorer )

A montagem CAPACITY = 240parece normal: dois loops aninhados. (No início da função, há bastante código apenas para inicializar, o que ignoraremos.) Para 239, no entanto, parece muito diferente! Vemos que o loop de inicialização e o loop interno foram desenrolados: até agora, o esperado.

A diferença importante é que, para o 239, o LLVM conseguiu descobrir que o resultado do loop interno não depende do loop externo! Como conseqüência, o LLVM emite código que basicamente executa apenas o loop interno (calculando a soma) e depois simula o loop externo adicionando sumvárias vezes!

Primeiro, vemos quase a mesma montagem acima (a montagem que representa o loop interno). Depois vemos isso (comentei para explicar a assembléia; os comentários com *são 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 você pode ver aqui, o resultado do loop interno é obtido, somado quantas vezes o loop externo seria executado e retornado. O LLVM só pode executar essa otimização porque entendeu que o loop interno é independente do loop externo.

Isso significa que o tempo de execução muda de CAPACITY * IN_LOOPSparaCAPACITY + IN_LOOPS . E isso é responsável pela enorme diferença de desempenho.

Uma observação adicional: você pode fazer algo sobre isso? Na verdade não. O LLVM precisa ter limites mágicos, pois sem eles as otimizações do LLVM podem levar uma eternidade para serem concluídas em determinado código. Mas também podemos concordar que esse código era altamente artificial. Na prática, duvido que uma diferença tão grande ocorra. A diferença devido ao desenrolar do loop completo geralmente não é o fator 2 nesses casos. Portanto, não precisa se preocupar com casos de uso reais.

Como uma última observação sobre o código Rust idiomático: arr.iter().sum()é uma maneira melhor de resumir todos os elementos de uma matriz. E alterar isso no segundo exemplo não leva a diferenças notáveis ​​na montagem emitida. Você deve usar versões curtas e idiomáticas, a menos que tenha medido que isso prejudica o desempenho.

Além da resposta de Lukas, se você quiser usar um iterador, tente o seguinte:

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

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

Obrigado a Chris Morgan pela sugestão sobre o padrão de alcance.

A montagem otimizada é muito boa:

example::bar:
        movabs  rax, 14340000000
        ret