В сети часто можно услышать, что в Rust доступ по индексу со слайсом (как, например, my_slice[i]) работает медленно, и вместо этого в целях повышения производительности вы должны организовать свой код как‑нибудь иначе.
Детали этого, однако, зачастую туманны. Мало где можно найти какие‑либо внятные замеры производительности, и нет почти никакой документации по устранению этих накладных расходов, не прибегая к unsafe коду.
Поэтому я решил поделиться с вами опытом и методами, которые я обнаружил в процессе удаления проверок выхода индекса за границы (далее просто «проверка границ»), а также удаления unsafe кода, где это возможно, из множества громоздких крейтов.
В этой статье я расскажу:
Каковы типичные накладные расходы на проверку границ при доступе по индексу.
Как избежать проверки границ без использования
unsafeкода.Как убедиться, что проверки границ были устранены.
Как замерять производительность и профилировать Rust‑код.
Как нам сконструировать самую дешевую проверку границ в случае, когда она все‑таки необходима.
Что такое проверка границ?
Рассмотрим следующий код:
let array = [0, 1, 2, 3];
let a = array[1]; // все хорошо
let b = array[7]; // индекс выходит за границы массива!Доступ к 7-му элементу массива некорректен, потому что массив состоит всего из 4 элементов, и 7-го элемента в нем нет.
В C это привело бы к доступу к какой‑нибудь случайной памяти за пределами предполагаемого диапазона, что называется переполнением буфера.
Пресловутый Heartbleed является разновидностью переполнения буфера, но большинство уязвимостей этой категории не имеют таких кричащих названий, потому что их просто огромное множество. Тем не менее запись за пределами предполагаемого диапазона является очень распространенным способом для злоумышленника выполнить свой код на вашем компьютере, который позволяет сделать буквально все, что он захочет — украсть данные кредитной карты, майнить криптовалюту, шпионить за вами и т. д. Вот почему считается, что переполнение буфера — самая опасная уязвимость в программном обеспечении.
Чтобы избежать этого, при каждом доступе по индексу Rust добавляет так называемые проверки границ (bounds checks), которые гарантируют, что переполнение буфера никогда не произойдет — что‑то вроде этого:
// примерная реализации оператора доступа по индексу [i]
pub fn index(slice: &[T], idx: usize) {
if idx < slice.len() {
// TODO: небезопасно получить доступ по индексу и вернуть результат
} else {
// TODO: вызвать панику и завершить программу
}
}Если вы попытаетесь получить доступ по некорректному индексу,чтобы не создавать уязвимость, программа, написанная на Rust, запаникует.
Хотя это хорошая мера с точки зрения безопасности, это снижает производительность, потому что кода, который должен выполнять ЦП, становится больше.
Действительно ли проверки границ замедляют работу приложения?
Реальное влияние проверок границ на производительность на удивление низкое.
Наибольшее влияние от удаления проверок границ, которое я когда‑либо видел в реальном коде, было 15%, но обычно выигрыш в производительности находится в диапазоне от 1% до 3%, и даже эти показатели достижимы только в коде, который обрабатывает огромные массивы числовых данных.
Иногда вы можете наблюдать более заметное влияние (как мы скоро увидим!), если удаление проверок границ позволит компилятору выполнять другие оптимизации.
Тем не менее, производительность кода, не работающего с большими массивами числовых данных, вероятно, вообще не заметит какого‑либо влияния проверок границ.
Попробуйте сами!
Пока я буду объяснять результаты, которые я получил, нет ничего лучше, чем проверить это все самому. Поэтому я подготовил репозиторий со всем кодом и предоставлю вам все необходимые команды, чтобы вы сами могли убедиться воочию.
Если вы уже установили Rust, запустите эти команды, чтобы получить код и все необходимые инструменты:
cargo install cargo-show-asm hyperfine
git clone https://github.com/Shnatsel/bounds-check-cookbook
cd bounds-check-cookbook
cargo build --releaseДавайте взглянем на проверку границ в реальном коде
Для наших экспериментов нам понадобится простой пример, поэтому давайте напишем функцию, которая вычисляет Числа Фибоначчи и записывает их в Vec:
#[inline(never)] // чтобы дальше нам было легче работать с ассемблерным кодом
fn fibonacci_vec(length: usize) -> Vec<u64> {
// Выделяем память на всю длину заранее, чтобы избежать дорогостоящих перераспределений.
// Кроме того, vec![0; length] уже запрашивает у ОС обнуленную память, поэтому нам не нужно тратить время на заполнение Vec нулями — у ОС обычно всегда есть небольшое количество обнуленной памяти
let mut fib = vec![0; length];
// Заполняем Vec числами Фибоначчи
if length > 1 {
fib[1] = 1; // доступ по индексу! проверка границ! Но только один раз, так что это не страшно
}
if length > 2 {
for i in 2..length {
fib[i] = fib[i-1] + fib[i-2]; // доступ по индексу в цикле! О, нет!
}
}
fib // нет необходимости явно использовать return, потому что это последний оператор
}
pub fn main() {
// считываем длину во время выполнения, чтобы компилятор не мог просто предварительно вычислить ряд Фибоначчи
let arg = std::env::args().nth(1).expect("Please specify length");
let length: usize = arg.parse().expect("That's not a number!");
// вызываем интересующую нас функцию
let fibonacci = fibonacci_vec(length);
// и выводим результат, чтобы компилятор не удалил его как неиспользуемый код
println!("{:?}", fibonacci.last());
}Компилятор очень хорош в удалении любого кода, который не вызывается, и в предварительном вычислении всего, что он может вычислить заранее. Мне пришлось провернуть в main пару трюков, чтобы убедиться, что этого не произойдет, чтобы мы могли увидеть проверки границ во время выполнения.
Давайте откроем ассемблерный код и посмотрим, как выглядят проверки границ:
cargo asm --rust --bin fibvec_naive_indexing fibonacci_vecЭто команда выдаст нам оптимизированный ассемблерный код функции fibonacci_vec (то есть инструкции, которые ЦП будет фактически выполнять) вместе с Rust‑кодом, на основе которого они сгенерированы.
Вы можете заниматься этим, даже если толком не разбираетесь в ассемблере! Достаточно просто оценить объем сгенерированного ассемблерного кода и найти имена функций.
Давайте сначала посмотрим на цикл внутри функции, а конкретно на часть fib[i] = fib[i-1] + fib[i-2];, просто найдя ее в выводе cargo asm:
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/fibvec_naive_indexing.rs : 15
fib[i] = fib[i-1] + fib[i-2]; // доступ по индексу в цикле! О, нет!
add rsi, qword ptr [rbp + 8rax - 24]
mov qword ptr [rbp + 8rdi], rsiИ это все? Всего две инструкции!
И действительно, если немного пролистать вниз, то мы найдем еще код, относящийся к этой функции — не все находится в одном месте:
.LBB10_11:
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/fibvec_naive_indexing.rs : 15
fib[i] = fib[i-1] + fib[i-2]; // indexing in a loop! Oh no!
dec rdi
lea rdx, [rip + .L__unnamed_7]
jmp .LBB10_14
.LBB10_13:
mov rdi, r14
.LBB10_14:
mov rsi, r14
call qword ptr [rip + core::panicking::panic_bounds_check@GOTPCREL]
ud2Мы здесь наблюдаем то, как компилятор структурировал код, который срабатывает, когда индекс не проходит проверку границ. Этот путь кода приводит к панике, а паника случается редко. Поэтому компилятор перетасовал код таким образом, что мы даже не загружаем код, следствием выполнения которого будет паника, пока он нам действительно не понадобится. Умно!
Впрочем, вернемся к ассемблерному коду! Похоже, что core::panicking::panic_bounds_check — это паника из‑за неудачи при проверке границ, происходящая в ассемблерном коде, связанном с нашей строкой кода. Так вот как они выглядят!
Давайте посмотрим, происходит ли проверка границ для фрагмента if length > 1 { fib[1] = 1; } за пределами нашего цикла…
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/fibvec_naive_indexing.rs : 10
if length > 1 {
cmp r14, 2
jb .LBB10_17
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/fibvec_naive_indexing.rs : 11
fib[1] = 1;
mov qword ptr [rbp + 8], 1А здесь проверки границ нет! Компилятор был достаточно умен, чтобы понять, что когда length строго больше 1, неудача при проверке границ невозможна. Наш Vec с именем fib также имеет длину строго больше 1, поэтому fib[1] всегда находится в допустимых границах.
Однако, похоже, он не понял, что то же самое относится и к циклу, в частности к строчке с fib[i] = fib[i-1] + fib[i-2];.
Может быть, мы можем как-нибудь ему помочь?
Помощь оптимизатору
Мы собираемся внести в код два изменения, которые помогут оптимизатору понять, что индекс не провалит проверки границ никогда:
Вместо перебора до значения
length, которое является просто целым числом, мы будем перебирать индексы доfib.len(), чтобы компилятору стало очевидно, что индекс всегда находится в допустимых пределах.Вместо прямого использования Vec мы создадим из него один слайс и будем перебирать по нему. Это сделает для компилятора очевидным тот факт, что длина не меняется.
Таким образом мы получим следующий код:
// Посмотреть генерируемый ассемблерный код можно с помощью:
// cargo asm --rust --bin fibvec_clever_indexing fibonacci_vec
#[inline(never)] // чтобы дальше нам было легче работать с ассемблерным кодом
fn fibonacci_vec(length: usize) -> Vec<u64> {
let mut fib = vec![0; length];
{
// В отличие от Vec, размер слайса нельзя изменить
let fib = fib.as_mut_slice();
if length > 1 {
fib[1] = 1;
}
if length > 2 {
// Теперь компилятор знает, что fib имеет фиксированный размер, и мы итерируем точно в пределах его длины
for i in 2..fib.len() {
fib[i] = fib[i-1] + fib[i-2]; // больше никаких проверок границ!
}
}
}
fib
}main() без изменений, полный код можно найти здесь
И давайте сверимся с cargo asm — командой, которую можно найти в приведенном выше коде:
.LBB10_16:
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/fibvec_clever_indexing.rs : 16
fib[i] = fib[i-1] + fib[i-2]; // // больше никаких проверок границ!
add rdx, qword ptr [rax + 8*rdi - 16]
mov qword ptr [rax + 8*rdi], rdx
mov rcx, qword ptr [rax + 8*rdi - 8]
add rcx, rdx
mov qword ptr [rax + 8*rdi + 8], rcx
add rdx, rcx
mov qword ptr [rax + 8*rdi + 16], rdx
... // какой-то нерелевантный код, который я опустил
.LBB10_13:
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/fibvec_clever_indexing.rs : 16
fib[i] = fib[i-1] + fib[i-2]; // no more bounds checks!
add rdx, qword ptr [rax + 8*rsi - 16]
mov qword ptr [rax + 8*rsi], rdxАссемблерный код снова почему-то разделен на две части, но проверка границ пропала.
Но отразилось ли это на скорости выполнения программы? Давай выясним!
$ hyperfine 'target/release/fibvec_naive_indexing 1000000000' 'target/release/fibvec_clever_indexing 1000000000'
Benchmark 1: target/release/fibvec_naive_indexing 1000000000
Time (mean ± σ): 3.612 s ± 0.040 s [User: 1.435 s, System: 2.132 s]
Range (min … max): 3.546 s … 3.693 s 10 runs
Benchmark 2: target/release/fibvec_clever_indexing 1000000000
Time (mean ± σ): 3.133 s ± 0.019 s [User: 0.995 s, System: 2.103 s]
Range (min … max): 3.106 s … 3.163 s 10 runs
Summary
'target/release/fibvec_clever_indexing 1000000000' ran
1.15 ± 0.01 times faster than 'target/release/fibvec_naive_indexing 1000000000'Если вы работаете под Windows, возможно, вам придется добавить .exe к этим путям.
Новый код быстрее на целых 15%! Обычно это не повод открывать шампанское, но это самый большой прирост производительности от устранения проверок границ, который я когда-либо видел, так что это практически лучшее, на что мы могли надеяться.
И хотя этот пример был несколько надуманным, я использовал эти приемы, чтобы ускорить крейт fastblur на 15%. (Хотя перед этим я сократил время выполнения в 6 раз с помощью других средств).
Апдейт: в примере с fastblur также помог доступ по индексу в слайсе вместо &mut Vec, больше информации об этом вы можете найти здесь. Таким образом, выигрыш от удаления проверок границ на самом деле составляет менее 15%.
Небольшое отступление: оптимизации во время компиляции
Теперь давайте также попробуем это на 64-битном ARM процессоре, чисто для подтверждения.
$ hyperfine 'target/release/fibvec_naive_indexing 1000000000' 'target/release/fibvec_clever_indexing 1000000000'
Benchmark 1: target/release/fibvec_naive_indexing 1000000000
Time (mean ± σ): 3.320 s ± 0.024 s [User: 1.131 s, System: 2.179 s]
Range (min … max): 3.263 s … 3.346 s 10 runs
Benchmark 2: target/release/fibvec_clever_indexing 1000000000
Time (mean ± σ): 3.226 s ± 0.019 s [User: 1.092 s, System: 2.127 s]
Range (min … max): 3.209 s … 3.263 s 10 runs
Summary
'target/release/fibvec_clever_indexing 1000000000' ran
1.03 ± 0.01 times faster than 'target/release/fibvec_naive_indexing 1000000000'И здесь все вернулся в ожидаемый диапазон 3%. Здесь мы не наблюдаем никакого огромного прироста в 15%.
А вот ассемблерный код на ARM поражает своей лаконичностью:
.LBB10_7:
// /home/shnatsel/bounds-check-cookbook/src/bin/fibvec_clever_indexing.rs : 16
fib[i] = fib[i-1] + fib[i-2]; // больше никаких проверок границ!
ldur x11, [x9, #-16]
... // мной был опущена одна нерелевантная строка
// /home/shnatsel/bounds-check-cookbook/src/bin/fibvec_clever_indexing.rs : 16
fib[i] = fib[i-1] + fib[i-2]; // больше никаких проверок границ!
add x10, x11, x10
str x10, [x9], #8Мы не видим никаких проверок границ! И здесь всего лишь 3 инструкции, что подразумевает не так много работы для процессора, так что этот код должен выполняться очень быстро.
Что на происходит на самом деле?
Напомним, что удаление проверок границ само по себе не имеет большого значения. Вы увидите хоть сколько‑нибудь значимый прирост только в том случае, если удаление проверок границ позволило компилятору выполнить другие оптимизации.
Если мы вернемся назад и присмотримся к ассемблерному коду x86 fibonacci_vec без проверки границ, то мы можем заметить, что это почти одни и те же строки, повторяющиеся снова и снова, что подозрительно похоже на размотку цикла.
Почему это происходит на x86, а на ARM нет? Не имею ни малейшего понятия. Она должна выполняться и там, и там — это базовая оптимизация, которая никак не должна быть связана с процессором.
Для сравнения я попробовал сделать это на POWER9 процессоре, и компилятор, похоже, размотал цикл еще больше и hyperfine рапортует о внушительном приросте производительности в 1.78 ± 0.04 раза, так что я просто отправил багрепорт в rustc, и пусть с этим разбираются люди, знающие, как работают компиляторы.
Важным выводом для нас является следующее: оптимизирующие компиляторы решают NP‑трудную задачу за очень короткое время, и всегда будут случаи, когда они не справляются должным образом.
Хуже того, эти тонкости разнятся от версии к версии. Даже если компилятор в среднем улучшится, он может ухудшить ваш конкретный код! Автоматическая векторизация, например, такая вот общеизвестно непостоянна, что невероятно расстраивает, потому что она может значительно повысить производительность, когда она работает.
Я обнаружил, что оптимизации, которые удаляют проверки границ, очень надежны — как только вы заставите их работать, они, как правило, продолжают работать и на следующих версиях компилятора. Таким образом, вы можете смело использовать эти методы и рассчитывать, что они не сломаются в будущем. Но это лишь часть работы, ответственная за прирост на 3%!
Поскольку размотка цикла, отвечающая за прирост производительности на 15%, работает на x86, но не на ARM, я бы не стал делать ставку на ее надежную работу в будущем. Такова печальная реальность решения NP‑трудных задач за очень короткое время.
К счастью, в реальных программах, которые не проводят все время выполнения в одном высоконагруженном цикле, эти различия выражены намного меньше — регрессии в одном месте уравновешиваются улучшениями в другом.
Небольшое отступление: бенчмаркинг
Итак, вас мог возникнуть вопрос, почему я использую hyperfine и морочу себя всеми этими хлопотами с написанием нетривиального main()?
Почему бы мне просто не использовать cargo bench или criterion или что‑нибудь еще, специально предназначенное для бенчмаркинга?
Это опять же связано с тенденцией компилятора предварительно вычислять все, что он может, и удалять весь код, который не приводит к каким‑либо изменениям в выводе.
Если возвращаемое значение функции нигде не используется и функция не вызывает панику, компилятор просто удалит ее!
Это то, что нужно для производственного кода, и то, что совсем не нужно для замеров производительности.
Вы можете попытаться бороться с этим, обернув входные и выходные данные в std::hint::black_box(), но обернуть все правильно сложно, и какие именно оптимизации это тормозит непонятно.
Я обхожу все это, создавая двоичный файл, который считывает входные данные, и эти входные данные подставляются только тогда, когда программа уже запущена, поэтому у компилятора нет возможности предварительно вычислить что‑либо. Она также выводит результат, поэтому компилятор не может удалить функцию fibonacci_vec как неисполняемый код.
Наличие отдельных двоичных файлов также упрощает проверку ассемблерного кода и профилирование, как вы сами скоро увидите!
С другой стороны, я должен использовать Vec большой длины с целью получения легко измеримого времени выполнения, а это делает бенчмарки непоказательными с точки зрения обработки небольших Vec из‑за факторов, связанных с кэшем процессора.
Теперь давайте вернемся к нашим экспериментам с проверками границ.
Просто используйте итераторы
Опытные пользователи Rust, наверное, уже сорвали горло, кричали мне об этом все время, пока читали эту статью — во всяком случае, до этого момента!
Rust предоставляет удобные итераторы, которые позволяют вам работать с коллекциями, не беспокоясь о проверках границ, ошибках смещения на единицу и тому подобном.
Они также позволяют вам более четко выразить то, чего вы хотите достичь, если вы помните имена всех итераторов или всегда используете IDE, которая способна отображать документацию, что, по моему мнению, является довольно большим преимуществом!
Итак, давайте перепишем наш код, используя итераторы. Нам нужны скользящие окна над нашим Vec, и для этого есть удобный итератор, который называется windows, так что его и попробуем:
// Это не скомпилируется :(
fn fibonacci_vec(length: usize) -> Vec<u64> {
let mut fib = vec![0; length];
if length > 1 {
fib[1] = 1;
}
if length > 2 {
// это итератор; он полностью исключает проверки границ
for window in &mut fib.windows(3) {
// здесь нет проверок границ, потому что и размер окна,
// и каждый индекс известны во время компиляции
window[2] = window[1] + window[0]
}
}
fib
}Ну дела, этот код не компилируется! Проблема в том, что windows() дает нам слайсы, доступные только для чтения, и мы не можем производить запись через них. Для большинства других итераторов существует соответствующие _mut() версии, которые дают изменяемые слайсы, но windows_mut(), увы, не существует. Но почему?
Оказывается, windows_mut() нельзя реализовать как обычный итератор в Rust, потому что если бы вы .collect() его, скажем, в Vec, вы бы получили множество накладывающихся изменяемых слайсов — но Rust требует, чтобы каждый фрагмент памяти был изменяем исключительно из одного места за раз!
То, что мы ищем, это так называемый потоковый итератор, из которого нельзя сделать .collect(), и, похоже, в стандартной библиотеке такого еще нет. Поэтому нам придется немного изменить наш код:
// Посмотреть генерируемый ассемблерный код можно с помощью:
// cargo asm --rust --bin fibvec_iterator fibonacci_vec
#[inline(never)] // чтобы дальше нам было легче работать с ассемблерным кодом
fn fibonacci_vec(length: usize) -> Vec<u64> {
let mut fib = vec![0; length];
if length > 1 {
fib[1] = 1;
}
if length > 2 {
let mut grandparent = 0;
let mut parent = 1;
// это итератор; он полностью исключает проверки границ
for val in &mut fib[2..] {
let current = grandparent + parent;
*val = current;
grandparent = parent;
parent = current;
}
}
fib
}main() без изменений, полный код можно найти здесь
Этот код уже работает, и мы можем использовать cargo asm чтобы убедиться, что здесь нет никаких проверок границ. На Rust 1.65 на моем компьютере он работает немного быстрее, чем наша предыдущая попытка, примерно на 2%. На версии 1.66 прирост производительности еще больше:
$ hyperfine 'target/release/fibvec_naive_indexing 1000000000' 'target/release/fibvec_clever_indexing 1000000000' 'target/release/fibvec_iterator 1000000000'
Benchmark 1: target/release/fibvec_naive_indexing 1000000000
Time (mean ± σ): 3.530 s ± 0.056 s [User: 1.452 s, System: 2.027 s]
Range (min … max): 3.450 s … 3.616 s 10 runs
Benchmark 2: target/release/fibvec_clever_indexing 1000000000
Time (mean ± σ): 3.111 s ± 0.058 s [User: 1.037 s, System: 2.038 s]
Range (min … max): 3.039 s … 3.207 s 10 runs
Benchmark 3: target/release/fibvec_iterator 1000000000
Time (mean ± σ): 2.763 s ± 0.057 s [User: 0.666 s, System: 2.078 s]
Range (min … max): 2.686 s … 2.847 s 10 runs
Summary
'target/release/fibvec_iterator 1000000000' ran
1.13 ± 0.03 times faster than 'target/release/fibvec_clever_indexing 1000000000'
1.28 ± 0.03 times faster than 'target/release/fibvec_naive_indexing 1000000000'И он также обеспечивает хороший прирост производительности на ARM:
$ hyperfine 'target/release/fibvec_naive_indexing 1000000000' 'target/release/fibvec_clever_indexing 1000000000' 'target/release/fibvec_iterator 1000000000'
Benchmark 1: target/release/fibvec_naive_indexing 1000000000
Time (mean ± σ): 3.324 s ± 0.024 s [User: 1.160 s, System: 2.154 s]
Range (min … max): 3.285 s … 3.354 s 10 runs
Benchmark 2: target/release/fibvec_clever_indexing 1000000000
Time (mean ± σ): 3.257 s ± 0.022 s [User: 1.112 s, System: 2.136 s]
Range (min … max): 3.232 s … 3.297 s 10 runs
Benchmark 3: target/release/fibvec_iterator 1000000000
Time (mean ± σ): 2.968 s ± 0.025 s [User: 0.782 s, System: 2.175 s]
Range (min … max): 2.929 s … 3.011 s 10 runs
Summary
'target/release/fibvec_iterator 1000000000' ran
1.10 ± 0.01 times faster than 'target/release/fibvec_clever_indexing 1000000000'
1.12 ± 0.01 times faster than 'target/release/fibvec_naive_indexing 1000000000'К счастью, это не какая-то уникальная особенность итераторов — программа с такой же структурой, но с использованием индексации с подсказками оптимизатору такая же быстрая.
Но обратите внимание, что мы должны были значительно видоизменить то, как мы реализуем вычисление. Итераторы очень удобны, если вы пишете код с нуля, и вам по-хорошему следует их использовать, но встроить их в существующий код может быть достаточно сложно. А некоторые шаблоны вообще нельзя реализовать с помощью итераторов.
Апдейт: после выпуска этой статьи в документацию по стандартной библиотеке были добавлены инструкции по эмуляции
windows_mut(). Актуальный пример вычисления чисел Фибоначчи можно найти здесь.
И, наконец, здесь я использовал цикл for с итератором, а из-за этого компилятор может пропустить некоторые “очевидные” оптимизации. Если вы вместо этого используете .foreach на итераторе, компилятор должен лучше справиться с оптимизацией кода. Это особенно актуально, если у вас есть цепочка адаптеров итераторов, наподобие .skip().filter().take() или даже длиннее.
Поэтому, если вы обнаружите себя пишущим длинные цепочки итераторов, возможно, вам стоит сравнить их с реализацией на основе индексов с подсказками оптимизатору, подобной той, которую я описал ранее. Или сделать, как я покажу дальше.
Добавьте утверждение перед загруженным циклом
Давайте же где-нибудь задействуем функцию, которую мы написали.
Теперь, когда у нас есть Vec, заполненный числами Фибоначчи, мы можем написать функцию, которая проверяет, есть ли в другом Vec числа Фибоначчи, просто сравнивая их. Если наш Vec достаточно мал, чтобы поместиться в кэш процессора, это получится быстрее, чем производить вычисления снова и снова!
Наивная реализация может выглядеть как-то так:
// Посмотреть генерируемый ассемблерный код можно с помощью:
// cargo asm --rust --bin comparison_naive is_fibonacci
#[inline(never)] // чтобы дальше нам было легче работать с ассемблерным кодом
fn is_fibonacci(input: &[u64], fibonacci: &[u64]) -> bool {
for i in 0..input.len() {
if input[i] != fibonacci[i] { // проверка границ!
return false;
}
}
true
}
fn fibonacci_vec(length: usize) -> Vec<u64> {
// как и в прошлый раз - версия с итератором
}
pub fn main() {
// Дважды вычисляем Фибоначчи и сравниваем полученные Vec
// Детали не так важны, но вы можете найти их в полном листинге, если вам все-таки интересно
}Полный код можно найти здесь
Взглянем на ассемблерный код:
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/comparison_naive.rs : 6
if input[i] != fibonacci[i] { // две проверки границ!
cmp rcx, r9
je .LBB9_5
// /rustc/897e37553bba8b42751c67658967889d11ecd120/library/core/src/num/uint_macros.rs : 466
unsafe { intrinsics::unchecked_add(self, rhs) }
lea r8, [r9 + 1]
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/comparison_naive.rs : 6
if input[i] != fibonacci[i] { // две проверки границ!
mov rax, qword ptr [rdi + 8*r9]
cmp rax, qword ptr [rdx + 8*r9]
je .LBB9_1
... // тут были нерелевантные строки, сгенерированные для другого кода
.LBB9_5:
.cfi_def_cfa_offset 16
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/comparison_naive.rs : 6
if input[i] != fibonacci[i] { // две проверки границ!
lea rdx, [rip + .L__unnamed_3]
mov rdi, rcx
mov rsi, rcx
call qword ptr [rip + core::panicking::panic_bounds_check@GOTPCREL]
ud2О нет — проверки границ вернулись! Функция is_fibonacci() имеет их в высоконагруженном цикле.
Здесь мы должны проверять границы, потому что мы не знаем длины ни одного из этих слайсов заранее. Это необходимо для корректности работы программы! Но что мы можем здесь сделать, так это выполнить проверку границ только один раз вне цикла, что сделает ее стоимость незначительной в сравнении с тем, как она выполняется для каждого элемента в текущей реализации.
Давайте удостоверимся, что размеры одинаковы прежде чем мы войдем в цикл, и используйте прием перебора только до .len(), который вы уже видели раньше:
// Посмотреть генерируемый ассемблерный код можно с помощью:
// cargo asm --rust --bin comparison_clever is_fibonacci
#[inline(never)] // чтобы дальше нам было легче работать с ассемблерным кодом
fn is_fibonacci(input: &[u64], fibonacci: &[u64]) -> bool {
// Обрезаем один слайс до длины другого, чтобы компилятор знал,
// что длины одинаковы, прежде чем мы войдем в цикл
let fibonacci = &fibonacci[..input.len()];
for i in 0..input.len() {
if input[i] != fibonacci[i] { // Теперь в цикле нет проверок границ!
return false;
}
}
true
}Полный код можно найти здесь
И вуаля, больше никаких проверок границ внутри нагруженного цикла:
// /home/shnatsel/Code/bounds-check-cookbook/src/bin/comparison_clever.rs : 11
if input[i] != fibonacci[i] { // No bounds checks in the loop now!
mov rcx, qword ptr [rdi + 8*rax]
cmp rcx, qword ptr [rdx + 8*rax]
je .LBB9_2Вот и все, это весь ассемблерный код, который генерируется для строки с доступом по индексу.
Это также можно сделать с применением итератора, но на практике вы скорее всего будете просто использовать оператор == для сравнения слайсов. Код безусловно является надуманным — здесь было важно продемонстрировать технику оптимизации.
Я ускорил крейт jpeg-декодера, используя этот подход, так что вы можете взглянуть на него, если вам интересно посмотреть применение этой техники в реальном коде. Там я использовал assert!’ы вместо слайсов, но принцип тот же.
Самое замечательное в этом подходе то, что у вас не может быть слишком много assert!’ов — лишние будут удалены компилятором, как и проверки границ!
Продолжение следует.
Материал подготовлен в преддверии старта курса "Rust Developer. Basic".
Также всех желающих приглашаем на открытый урок «Области применения и инфраструктура Rust», который состоится уже сегодня вечером. На этом занятии рассмотрим, в каких областях Rust применяется на практике и какие готовые решения он предоставляет для направлений: Backend, Frontend и WebAssembly, Blockchain, Gamedev.
