Минимум в массиве

Если долго не писать посты, то так можно совсем забить на канал, так что напишу хотя бы о чем-нибудь простом. Как найти минимальный элемент в массиве (желательно побыстрее)?

Сразу оговорюсь, что результаты сильно зависят от того, в каком окружении вы запускаете код, так что воспроизводимость результатов не гарантирую, а все тесты проводились локально на ноутбуке.

Пусть есть массив из 10^6 элементов типа i32 и мы хотим найти минимум. Чтобы было удобно сравнивать алгоритмы, будем считать сколько раз за 1с можно запустить алгоритм. Например, если считать, что компьютер исполняет 10^9 операций min в секунду, то наш алгоритм выполнится примерно 10^3 раз.

Начнем с самой простой реализации:

fn find_min_iter(a: &[i32]) -> i32 {
    *a.iter().min().unwrap()
}

Один запуск такого алгоритма занимает 481µs, а значит за секунду его можно запустить 2079 раз.

Перепишем менее идиоматично:

fn find_min_for_loop(a: &[i32]) -> i32 {
    let mut min = a[0];
    for &x in a.iter() {
        if x < min {
            min = x;
        }
    }
    min
}

Такой код успевает сработать 7945 раз (почти в 4 раза быстрее!).

Аналогичный код на C (сильно зависит от компилятора) успевает сработать 5898 раз (кошмар, медленнее чем Rust!).

Если вы еще не читали статью Argmin with SIMD на algorithmica.org, то очень рекомендую! Там приведены различные реализации с SIMD интринсиками, которые работают еще быстрее. У меня локально такой алгоритм успевает сработать 14483 за секунду!

С одной стороны это в два раза быстрее чем на Rust, с другой стороны, если нам нужно будет найти минимум в [i64] вместо [i32], то придется все переписывать. Почему вообще компилятор на справляется сам написать такой же эффективный код?

Разгадка очень проста — в нашем алгоритме используются avx2 инструкции, которые по умолчанию не доступны компилятору. И это именно тот самый случай, когда добавление #pragma GCC target("avx2") в ваш код на самом деле ускорит его. И обычный цикл for станет таким же быстрым, как и написанный вручную код с simd инструкциями.

Конструкцию, аналогичную pragma, но для Rust, можно написать так:

fn find_min_iter_avx2(a: &[i32]) -> i32 {
    #[target_feature(enable = "avx2")]
    unsafe fn run(a: &[i32]) -> i32 {
        let mut min = a[0];
        for &x in a.iter() {
            if x < min {
                min = x;
            }
        }
        min
    }
    unsafe { run(a) }
}

И работает она так же быстро, как и версия на С (больше чем в 7 раз быстрее самой первой реализации)!

Так что если вам когда-нибудь надо будет 10^5 раз найти минимум в массиве длиной 10^5, то знайте, что это можно сделать быстрее чем за секунду.