Почему в этом коде на Rust нет штрафа за ошибку предсказания ветвления?

Question

Я написал эту очень простую функцию на Rust:

fn iterate(nums: &Box<[i32]>) -> i32 {
    let mut total = 0;
    let len = nums.len();
    for i in 0..len {
        if nums[i] > 0 {
            total += nums[i];
        } else {
            total -= nums[i];
        }
    }

    total
}

Я написал базовый тест, который вызывает метод с упорядоченным и перемешанным массивами:

fn criterion_benchmark(c: &mut Criterion) {
    const SIZE: i32 = 1024 * 1024;

    let mut group = c.benchmark_group("Branch Prediction");

    // setup benchmarking for an ordered array
    let mut ordered_nums: Vec<i32> = vec![];
    for i in 0..SIZE {
        ordered_nums.push(i - SIZE/2);
    }
    let ordered_nums = ordered_nums.into_boxed_slice();
    group.bench_function("ordered", |b| b.iter(|| iterate(&ordered_nums)));

    // setup benchmarking for a shuffled array
    let mut shuffled_nums: Vec<i32> = vec![];
    for i in 0..SIZE {
        shuffled_nums.push(i - SIZE/2);
    }
    let mut rng = thread_rng();
    let mut shuffled_nums = shuffled_nums.into_boxed_slice();
    shuffled_nums.shuffle(&mut rng);
    group.bench_function("shuffled", |b| b.iter(|| iterate(&shuffled_nums)));

    group.finish();
}

criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);

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

Я видел упоминания об условных инструкциях по перемещению, но если я otool -tv исполняемый файл (я работаю на Mac), я не вижу его в iterate вывод метода.

Может ли кто-нибудь пролить свет на то, почему в Rust нет заметной разницы в производительности между упорядоченным и неупорядоченным случаями?

Answer 1

Итог: LLVM смог удалить / скрыть ветку с помощьюcmov инструкция или действительно умная комбинация инструкций SIMD.

---

Я использовал Godbolt для просмотра полной сборки (с-C opt-level=3). Ниже я объясню важные части сборки.

Начинается это так:

        mov     r9, qword ptr [rdi + 8]         ; r9 = nums.len()
        test    r9, r9                          ; if len == 0
        je      .LBB0_1                         ;     goto LBB0_1
        mov     rdx, qword ptr [rdi]            ; rdx = base pointer (first element)
        cmp     r9, 7                           ; if len > 7
        ja      .LBB0_5                         ;     goto LBB0_5
        xor     eax, eax                        ; eax = 0
        xor     esi, esi                        ; esi = 0
        jmp     .LBB0_4                         ; goto LBB0_4

.LBB0_1:
        xor     eax, eax                        ; return 0
        ret

Здесь функция различает 3 разных "состояния":

• Срез пуст → немедленно вернуть 0
• Длина среза ≤ 7 → используйте стандартный последовательный алгоритм (LBB0_4)
• Длина среза> 7 → используйте алгоритм SIMD (LBB0_5)

Итак, давайте посмотрим на два разных типа алгоритмов!

Стандартный последовательный алгоритм

Помни это rsi (esi) а также rax (eax) были установлены в 0 и что rdx является базовым указателем на данные.

.LBB0_4:
        mov     ecx, dword ptr [rdx + 4*rsi]    ; ecx = nums[rsi]
        add     rsi, 1                          ; rsi += 1
        mov     edi, ecx                        ; edi = ecx
        neg     edi                             ; edi = -edi
        cmovl   edi, ecx                        ; if ecx >= 0 { edi = ecx }
        add     eax, edi                        ; eax += edi
        cmp     r9, rsi                         ; if rsi != len
        jne     .LBB0_4                         ;     goto LBB0_4
        ret                                     ; return eax

Это простой цикл, перебирающий все элементы num. В теле цикла есть небольшая хитрость: из исходного элементаecx, отрицательное значение сохраняется в edi. Используяcmovl, ediперезаписывается исходным значением, если это исходное значение положительно. Что означает, чтоediвсегда будет положительным (т.е. содержать абсолютное значение исходного элемента). Затем он добавляется кeax (который возвращается в конце).

Так что ваши if ветка была спрятана в cmovинструкция. Как вы можете видеть в этом тесте, время, необходимое для выполненияcmovинструкция не зависит от вероятности условия. Замечательная инструкция!

Алгоритм SIMD

Версия SIMD состоит из нескольких инструкций, которые я не буду вставлять здесь полностью. Основной цикл обрабатывает сразу 16 целых чисел!

        movdqu  xmm5, xmmword ptr [rdx + 4*rdi]
        movdqu  xmm3, xmmword ptr [rdx + 4*rdi + 16]
        movdqu  xmm0, xmmword ptr [rdx + 4*rdi + 32]
        movdqu  xmm1, xmmword ptr [rdx + 4*rdi + 48]

Они загружаются из памяти в регистры xmm0, xmm1, xmm3 а также xmm5. Каждый из этих регистров содержит четыре 32-битных значения, но для простоты представьте, что каждый регистр содержит ровно одно значение. Все следующие инструкции работают с каждым значением этих регистров SIMD индивидуально, так что ментальная модель в порядке! Мое объяснение ниже также будет звучать так, как будтоxmm регистры будут содержать только одно значение.

Теперь основная уловка заключается в следующих инструкциях (которые обрабатывают xmm5):

        movdqa  xmm6, xmm5      ; xmm6 = xmm5 (make a copy)
        psrad   xmm6, 31        ; logical right shift 31 bits (see below)
        paddd   xmm5, xmm6      ; xmm5 += xmm6
        pxor    xmm5, xmm6      ; xmm5 ^= xmm6

Логический сдвиг вправо заполняет "биты пустого высокого порядка" (те "сдвинутые в" слева) со значением бита знака. Сдвигая на 31, мы получаем только знаковый бит в каждой позиции! Таким образом, любое положительное число превратится в 32 нуля, а любое отрицательное число превратится в 32 единицы. Такxmm6 сейчас либо 000...000 (если xmm5 положительный) или 111...111 (если xmm5 отрицательный).

Далее этот искусственный xmm6 добавлен к xmm5. Еслиxmm5 был положительным, xmm6 равно 0, поэтому добавление не изменится xmm5. Еслиxmm5 был отрицательным, однако мы добавляем 111...111 что эквивалентно вычитанию 1. Наконец, мы xor xmm5 с xmm6. Опять же, еслиxmm5 был положительным в начале, мы xor с 000...000что не имеет эффекта. Еслиxmm5 был отрицательным вначале, мы xor с 111...111, то есть мы переворачиваем все биты. Итак, для обоих случаев:

• Если элемент был положительным, мы ничего не меняем (add а также xor не подействовали)
• Если элемент был отрицательным, мы вычитали 1 и перевернули все биты. Это отрицание с дополнением до двух!

Итак, с помощью этих 4 инструкций мы вычислили абсолютное значение xmm5! Здесь снова нет ветки из-за этого трюка с битами. И помни, чтоxmm5 на самом деле содержит 4 целых числа, так что это довольно быстро!

Это абсолютное значение теперь добавляется в аккумулятор, и то же самое делается с тремя другими. xmmрегистры, которые содержат значения из среза. (Мы не будем подробно обсуждать оставшийся код.)

SIMD с AVX2

Если мы позволим LLVM выдавать инструкции AVX2 (через -C target-feature=+avx2), он может даже использовать pabsd инструкция вместо четырех "хитрых" инструкций:

vpabsd  ymm2, ymmword ptr [rdx + 4*rdi]

Он загружает значения прямо из памяти, вычисляет абсолютное значение и сохраняет его в ymm2в одной инструкции! И помни, чтоymm регистры вдвое больше, чем xmm регистры (подходит для восьми 32-битных значений)!