Почему при зацикливании массива с 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());
}
2 ответа
Резюме: ниже 240 LLVM полностью развертывает внутренний цикл, и это позволяет ему заметить, что он может оптимизировать повторный цикл, ломая ваш эталонный тест.
Вы нашли магический порог, выше которого LLVM прекращает выполнение определенных оптимизаций. Порог составляет 8 байт * 240 = 1920 байт (ваш массив представляет собой массив usize s, поэтому длина умножается на 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/ а также этот раздел вопросов и ответов о нескольких аккумуляторах, чтобы скрыть задержку (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 Explorer Compiler Explorer)
Сборка для 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() это лучший способ суммировать все элементы массива. И изменение этого во втором примере не приводит к каким-либо заметным различиям в испускаемой сборке. Вы должны использовать короткие и идиоматические версии, если только вы не измерили, что это ухудшает производительность.
В дополнение к ответу Лукаса, если вы хотите использовать итератор, попробуйте это:
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