Воспроизводимые бенчмарки
Недавно хотел понять, как лучше написать функцию, которая принимает два массива типа u8 и возвращает первую позицию, в которой они отличаются.
Для простоты будем считать, что массивы одинакового размера. Самая простая версия на Rust выглядит так:
pub fn mismatch(s: &[u8], t: &[u8]) -> Option<usize> {
s.iter().zip(t.iter()).position(|(x, y)| x != y)
}Но, как можно увидеть тут, такой код не векторизуется, а честно проверяет символы один за одним.
Как можно сделать лучше?
С теоретической точки зрения все довольно просто. Зачем сравнивать по одному байту, если можно сравнивать несколько за раз? Например, в С++ мы могли бы скастить char * к int *, и сравнивать массивы уже как массивы интов. По сути так мы сравниваем за раз по 4 байта. Когда нашли первую отличающуюся четверку, можно отдельным проходом найти какой именно байт из 4 отличается.
И еще нужно отдельно обработать конец массива, если длина не делится на 4.
На самом деле процессоры умеют обрабатывать больше 4 байт за раз. ymm регистры могут хранить сразу 256 бит (в 8 раз больше i32!). Так что можно разбить исходные массивы на блоки по 32 байта, сравнивать их с помощью simd, а когда нашли отличающийся блок, найти нужный байт в тупую.
chunks_exact
В Rust есть специальный модуль с интринскиками для использования simd напрямую, но код получается довольно сложно читаемый (да и писать его не очень приятно).
Было бы гораздо лучше, если бы компилятор мог сам понять, что можно использовать simd, и сделал бы это явно лучше чем мы руками (учитывая какие инструкции знает текущий процессор и насколько они быстрые). К сожалению ни код выше, ни плюсовый аналог std::mismatch, компилятор не оптимизирует.
Но иногда можно написать код немного по-другому, чтобы компилятор понял, как именно нужно оптимизировать. В данном случае у slice есть функция chunks_exact, которая делит массив на куски одинакового размера (плюс какой-то хвост). После этого компилятор может понять, что у всех кусков одинаковый размер, и их можно сравнивать с помощью simd-инструкций.
Итоговый код получается такой:
pub fn mismatch_fast(s: &[u8], t: &[u8]) -> Option<usize> {
let len = s.len();
const CHUNK_SIZE: usize = 32;
let offset = s
.chunks_exact(CHUNK_SIZE)
.zip(t.chunks_exact(CHUNK_SIZE))
.position(|(c1, c2)| c1 != c2)
.unwrap_or(len / CHUNK_SIZE)
* CHUNK_SIZE;
s[offset..]
.iter()
.zip(t[offset..].iter())
.position(|(c1, c2)| c1 != c2)
.map(|x| x + offset)
}Если посмотреть на генерируемый ассемблер, то вроде бы все ожидаемо, есть какой-то цикл, который загружает в ymm0 регистр вначале данные из одного массива, потом xor-ит с данными из другого, проверяет получился ли 0, сдвигается на 32 байта в двух массивах и переходит к следующей итерации:
Меряем скорость
Один из рекомендованных способов измерять производительность Rust кода это cargo bench.
#![feature(test)]
extern crate test;
#[inline(never)]
pub fn mismatch(s: &[u8], t: &[u8]) -> Option<usize> {
s.iter().zip(t.iter()).position(|(x, y)| x != y)
}
#[inline(never)]
pub fn mismatch_fast(s: &[u8], t: &[u8]) -> Option<usize> {
let len = s.len();
const CHUNK_SIZE: usize = 32;
let offset = s
.chunks_exact(CHUNK_SIZE)
.zip(t.chunks_exact(CHUNK_SIZE))
.position(|(c1, c2)| c1 != c2)
.unwrap_or(len / CHUNK_SIZE)
* CHUNK_SIZE;
s[offset..]
.iter()
.zip(t[offset..].iter())
.position(|(c1, c2)| c1 != c2)
.map(|x| x + offset)
}
#[cfg(test)]
mod tests {
use super::*;
use test::Bencher;
fn gen_inputs() -> (Vec<u8>, Vec<u8>) {
const LEN: usize = 200_000;
const CHANGED_POSITION: usize = 100_500;
let s: Vec<u8> = (0..LEN).map(|x| (x % 10) as u8).collect();
let mut t = s.clone();
t[CHANGED_POSITION] = 1;
assert_ne!(s, t);
(s, t)
}
#[bench]
fn simple(b: &mut Bencher) {
let (s, t) = gen_inputs();
b.iter(|| {
mismatch(&s, &t).unwrap();
});
}
#[bench]
fn fast(b: &mut Bencher) {
let (s, t) = gen_inputs();
b.iter(|| {
mismatch_fast(&s, &t).unwrap();
});
}
}$ cargo bench --quiet running 2 tests test tests::fast ... bench: 48,570 ns/iter (+/- 423) test tests::simple ... bench: 52,240 ns/iter (+/- 3,557) test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out; finished in 1.05s
Хмм, оба способа работают примерно 50мкс, но должно же было быть в 32 раза быстрее? Ну ладно, не в 32, все-таки simd инструкции, наверное, работают чуть дольше чем обычные сравнения, но не настолько же!
Так, ну ладно, давайте запустим perf на коде, который должен был работать быстро:
$ perf record cargo bench --quiet fast ... $ perf report
Но куда делся тот прекрасный простой цикл, который мы видели в Compiler Explorer?
Учимся смотреть ассемблер правильно
Смотреть на ассемблер в выводе perf конечно прикольно, но должен же быть какой-то более простой способ?
Раньше для этого был cargo asm, который вроде бы больше не поддерживается и плохо работает с workspaces. Зато появился какой-то cargo-show-asm. Им и будем пользоваться.
$ cargo asm test_diff::mismatch_fast
В принципе это очень похоже на тот код, который был в Compiler explorer. Но почему в perf мы видели какой-то другой?
На самом деле cargo bench и cargo asm используют разные опции для компиляции (RUSTFLAGS), что может приводить к подобным эффектам. Давайте уберем RUSTFLAGS вообще:
$ RUSTFLAGS="" cargo bench --quiet running 2 tests test tests::fast ... bench: 2,989 ns/iter (+/- 77) test tests::simple ... bench: 52,195 ns/iter (+/- 579) test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out; finished in 1.72s
Хмм, теперь fast версия действительно быстрая, но что же было такое плохое записано в RUSTFLAGS?
На самом деле в ~/.cargo/config у меня прописано, что нужно оптимизировать под локальный процессор. Поэтому воспроизвести это поведение можно так:
$ RUSTFLAGS="-C target-cpu=native -O" cargo bench --quiet running 2 tests test tests::fast ... bench: 48,568 ns/iter (+/- 3,422) test tests::simple ... bench: 52,410 ns/iter (+/- 1,354) test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out; finished in 1.10s
Очень подозрительно, что когда мы даем больше свободы компилятору, он начинает генерировать более медленный код. А еще в Compiler Explorer мы тоже передавали target-cpu=native, и он генерировал нормальный код.
Но давайте все-таки посмотрим на код, который генерируется во время cargo bench. Говорят можно просто передать --emit=asm в RUSTFLAGS, так и сделаем:
$ RUSTFLAGS="-C target-cpu=native -O --emit=asm" cargo bench --quiet running 2 tests test tests::fast ... bench: 2,577 ns/iter (+/- 42) test tests::simple ... bench: 53,892 ns/iter (+/- 2,685) test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out; finished in 2.76s
и потом в target/release/deps/test_diff-af77c0bfbd72c9e5.s можно найти уже знакомый цикл:
Так, стоп, но это же быстрая версия? Мы же ожидали увидеть простыню, которую видели в выводе perf. Хмм, и судя по результату теста, она реально работает быстро (причем даже быстрее чем когда передавали пустой RUSTFLAGS). Т.е. получается от того, что мы захотели посмотреть на asm и передали --emit=asm, все стало работать быстрее?
На самом деле --emit=asm неявно форсит флаг codegen-units=1, поэтому можно передать его сразу и получить такой же эффект:
$ RUSTFLAGS="-C target-cpu=native -O -C codegen-units=1" cargo bench --quiet running 2 tests test tests::fast ... bench: 2,501 ns/iter (+/- 164) test tests::simple ... bench: 53,446 ns/iter (+/- 592) test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out; finished in 1.12s
Скорее всего он же передается в Compiler explorer, поэтому мы видели там быструю версию кода.
Больше оптимизаций
Говорят, чем с большем уровнем оптимизаций компилировать код, тем быстрее он будет работать. Но на самом деле если передать opt-level=3:
$ RUSTFLAGS="-C target-cpu=native -O -C codegen-units=1 -C opt-level=3" cargo bench --quiet running 2 tests test tests::fast ... bench: 49,108 ns/iter (+/- 970) test tests::simple ... bench: 53,382 ns/iter (+/- 693) test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured; 0 filtered out; finished in 0.55s
Кстати, его же можно передать в Compiler Explorer и увидеть к чему приводят оптимизации.
Вывод
