Почему при зацикливании массива с 240 или более элементами сильно сказывается производительность?

При выполнении цикла суммирования для массива в Rust я заметил огромное падение производительности, когда CAPACITY> = 240. CAPACITY = 239 примерно в 80 раз быстрее.

Есть ли специальная оптимизация компиляции, которую Rust делает для "коротких" массивов?

Скомпилировано с 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());
}

Ответ 1

Резюме: ниже 240, LLVM полностью развертывает внутренний цикл, и это позволяет ему заметить, что он может оптимизировать повторный цикл, ломая ваш тест.

Вы нашли магический порог, выше которого LLVM прекращает выполнение определенных оптимизаций. Порог составляет 8 байт * 240 = 1920 байт (ваш массив является массивом usize с, поэтому длина умножается на 8 байт, предполагая процессор x86-64). В этом тесте одна конкретная оптимизация - только для длины 239 - отвечает за огромную разницу в скорости. Но давайте начнем медленно:

(Весь код в этом ответе скомпилирован с -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
}

Этот простой код будет производить примерно ожидаемую сборку: цикл, добавляющий элементы. Однако, если вы измените 240 на 239, испускаемая сборка будет сильно отличаться. Смотрите это в Godbolt Compiler Explorer. Вот небольшая часть сборки:

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

Это то, что называется развертыванием цикла: LLVM вставляет тело цикла много времени, чтобы избежать необходимости выполнять все эти "инструкции по управлению циклом", т.е. увеличивать переменную цикла, проверять, завершился ли цикл, и перейти к началу цикла.

Если вам интересно: paddq и аналогичные инструкции являются SIMD-инструкциями, которые позволяют суммировать несколько значений параллельно. Кроме того, два 16-байтовых регистра SIMD (xmm0 и xmm1) используются параллельно, так что параллелизм ЦП на уровне команд может в основном выполнять две из этих команд одновременно. Ведь они независимы друг от друга. В конце оба регистра суммируются, а затем суммируются по горизонтали до скалярного результата.

Современные основные x86-процессоры (не Atom с низким энергопотреблением) действительно могут выполнять 2 векторных нагрузки за такт, когда они попадают в кэш L1d, и пропускная способность paddq также составляет не менее 2 на такт, с задержкой в 1 цикл на большинстве процессоров. См. https://agner.org/optimize/, а также этот Q & A о нескольких аккумуляторах, чтобы скрыть задержку (FP FMA для точечного продукта) и узкое место по пропускной способности.

LLVM выполняет развертывание небольших циклов, когда оно не полностью развернуто, и все еще использует несколько аккумуляторов. Поэтому обычно узкие места в полосе пропускания и задержке во внутренней части не являются большой проблемой для циклов, генерируемых LLVM, даже без полного развертывания.

Но развертывание цикла не несет ответственности за разницу производительности в 80 раз! По крайней мере, не развертывание цикла в одиночку. Давайте взглянем на реальный код тестирования, который помещает один цикл в другой:

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
}

(в проводнике компилятора Godbolt)

Сборка для CAPACITY = 240 выглядит нормально: две вложенные циклы. (В начале функции есть некоторый код только для инициализации, который мы проигнорируем.) Однако для 239 это выглядит совсем иначе! Мы видим, что цикл инициализации и внутренний цикл были развернуты: до сих пор так ожидалось.

Важным отличием является то, что для 239 LLVM смог выяснить, что результат внутреннего цикла не зависит от внешнего цикла! Как следствие, LLVM испускает код, который в основном сначала выполняет только внутренний цикл (вычисляя сумма), а затем имитирует внешний цикл, складывая sum несколько раз!

Сначала мы видим почти ту же сборку, что и выше (сборка, представляющая внутренний цикл). После этого мы видим это (я прокомментировал, чтобы объяснить сборку; комментарии с * особенно важны):

        ; 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'

Как вы можете видеть здесь, результат внутреннего цикла берется, складывается так часто, как внешний цикл запускался, а затем возвращался. LLVM может выполнять эту оптимизацию только потому, что понимает, что внутренний цикл не зависит от внешнего.

Это означает, что время выполнения изменяется с CAPACITY * IN_LOOPS на CAPACITY + IN_LOOPS. И это ответственно за огромную разницу в производительности.

Дополнительное примечание: вы можете что-нибудь с этим сделать? На самом деле, нет. У LLVM должны быть такие магические пороги, что без них LLVM-оптимизация могла бы длиться вечно для определенного кода. Но мы также можем согласиться с тем, что этот код был очень искусственным. На практике я сомневаюсь, что такая огромная разница будет иметь место. Разница, связанная с развертыванием полного цикла, в этих случаях обычно даже не равна коэффициенту 2. Поэтому не нужно беспокоиться о реальных случаях использования.

Последнее замечание о идиоматическом коде Rust: arr.iter().sum() - лучший способ суммировать все элементы массива. И изменение этого во втором примере не приводит к каким-либо заметным различиям в испускаемой сборке. Вы должны использовать короткие и идиоматические версии, если только вы не измерили, что это ухудшает производительность.

Ответ 2

В дополнение к ответу Лукаса, если вы хотите использовать итератор, попробуйте следующее:

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

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

Спасибо @Chris Morgan за предложение о шаблоне диапазона.

оптимизированная сборка довольно хороша:

example::bar:
        movabs  rax, 14340000000
        ret