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

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

Скомпилировано с помощью rustc -C opt-level=3.

используем 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());
}

Ответы (2)

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



Вы нашли магический порог, выше которого LLVM перестает выполнять определенные оптимизации. Этот порог составляет 8 байт * 240 = 1920 байт (ваш массив является массивом usizes, поэтому длина умножается на 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]
; здесь больше ничего не указано ...
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 Compiler Explorer)

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

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

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

 ; в начале функции `rbx` был установлен в 0

        movq rax, xmm1 ; результат SIMD-суммирования хранится в `rax`.
        add rax, 711 ; добавить недостающие члены в результате разворачивания цикла
        mov ecx, 500000 ; * инициализация переменной внешнего цикла
.LBB0_1:
        add rbx, rax ; * rbx += rax
        add rcx, -1 ; * уменьшение переменной цикла
        jne .LBB0_1 ; * если переменная цикла != 0, перейдите в LBB0_1
        mov rax, rbx ; переместите rbx (сумму) обратно в rax
        ; две несущественные инструкции опущены
        ret ; возвращаемое значение хранится в `rax`.

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

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


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

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

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

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

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

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

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

example::bar:
        movabs  rax, 14340000000
        ret

2022 WebDevInsider