Ответ 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() - лучший способ суммировать все элементы массива. И изменение этого во втором примере не приводит к каким-либо заметным различиям в испускаемой сборке. Вы должны использовать короткие и идиоматические версии, если только вы не измерили, что это ухудшает производительность.