Сравнение производительности циклов и итераторов

Чтобы определить, что лучше использовать циклы или итераторы, нужно знать, какая реализация быстрее: версия функции search с явным циклом for или версия с итераторами.

Мы выполнили тест производительности, разместив всё содержимое книги (“The Adventures of Sherlock Holmes” by Sir Arthur Conan Doyle) в строку типа String и поискали слово the в её содержимом. Вот результаты теста функции search с использованием цикла for и с использованием итераторов:

test bench_search_for  ... bench:  19,620,300 ns/iter (+/- 915,700)
test bench_search_iter ... bench:  19,234,900 ns/iter (+/- 657,200)

Версия с использованием итераторов была немного быстрее! Мы не будем приводить здесь непосредственно код теста, поскольку идея не в том, чтобы доказать, что решения в точности эквивалентны, а в том, чтобы получить общее представление о том, как эти две реализации близки по производительности.

Для более исчерпывающего теста, вам нужно проверить различные тексты разных размеров в качестве содержимого для contents, разные слова и слова различной длины в качестве query и всевозможные другие варианты. Дело в том, что итераторы, будучи высокоуровневой абстракцией, компилируются примерно в тот же код, как если бы вы написали его низкоуровневый вариант самостоятельно. Итераторы - это одна из абстракций с нулевой стоимостью ( zero-cost abstractions ) в Rust, под которой мы подразумеваем, что использование абстракции не накладывает дополнительных расходов во время выполнения. Аналогично тому, как Бьёрн Страуструп, дизайнер и разработчик C++, определяет нулевые накладные расходы ( zero-overhead ) в книге “Foundations of C++” (2012):

В целом, реализация C++ подчиняется принципу отсутствия накладных расходов: за то, чем вы не пользуетесь, платить не нужно. И далее: тот код, что вы используете, нельзя сделать ещё лучше.

В качестве другого примера приведём код, взятый из аудио декодера. Алгоритм декодирования использует математическую операцию линейного предсказания для оценки будущих значений на основе линейной функции предыдущих выборок. Код использует комбинирование вызовов итератора для выполнения математических вычислений для трёх переменных в области видимости: срез данных buffer, массив из 12 коэффициентов coefficients и число для сдвига данных в переменной qlp_shift. Переменные определены в примере, но не имеют начальных значений. Хотя этот код не имеет большого значения вне контекста, он является кратким, реальным примером того, как Rust переводит идеи высокого уровня в код низкого уровня.

let buffer: &mut [i32];
let coefficients: [i64; 12];
let qlp_shift: i16;

for i in 12..buffer.len() {
    let prediction = coefficients.iter()
                                 .zip(&buffer[i - 12..i])
                                 .map(|(&c, &s)| c * s as i64)
                                 .sum::<i64>() >> qlp_shift;
    let delta = buffer[i];
    buffer[i] = prediction as i32 + delta;
}

Чтобы вычислить значение переменной prediction, этот код перебирает каждое из 12 значений в переменной coefficients и использует метод zip для объединения значений коэффициентов с предыдущими 12 значениями в переменной buffer. Затем, для каждой пары мы перемножаем значения, суммируем все результаты и у суммы сдвигаем биты вправо в переменную qlp_shift.

Для вычислений в таких приложениях, как аудио декодеры, часто требуется производительность. Здесь мы создаём итератор, используя два адаптера, впоследствии потребляющих значение. В какой ассемблерный код будет компилироваться этот код на Rust? На момент написания этой главы он компилируется в то же самое, что вы написали бы руками. Не существует цикла, соответствующего итерации по значениям в «коэффициентах»coefficients: Rust знает, что существует двенадцать итераций, поэтому он «разворачивает» цикл. Разворачивание - это оптимизация, которая устраняет издержки кода управления циклом и вместо этого генерирует повторяющийся код для каждой итерации цикла.

Все коэффициенты сохраняются в регистрах, что означает очень быстрый доступ к значениям. Нет никаких проверок границ доступа к массиву во время выполнения. Все эти оптимизации, которые может применить Rust, делают полученный код чрезвычайно эффективным. Теперь, когда вы это знаете, используйте итераторы и замыкания без страха! Они представляют код в более высокоуровневом виде, но без потери производительности во время выполнения.

Итоги

Замыкания (closures) и итераторы (iterators) это возможности Rust, вдохновлённые идеями функциональных языков. Они позволяют Rust ясно выражать идеи высокого уровня с производительностью низкоуровневого кода. Реализации замыканий и итераторов таковы, что нет влияния на производительность выполнения кода. Это одна из целей Rust, направленных на обеспечение абстракций с нулевой стоимостью (zero-cost abstractions).

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