Dudochkin Victor
Достижение скорости варпа с помощью Rust
Если вы хотите писать быстрый код на Rust, хорошие новости! Rust позволяет очень легко писать действительно быстрый код. Акцент на абстракции с нулевой стоимостью, отсутствие неявного бокса и управление статической памятью означает, что даже наивный код часто быстрее, чем эквивалент на других языках, и, безусловно, быстрее, чем наивный код на любом столь же безопасном языке. Возможно, однако, как и большинство программистов, вы провели всю свою карьеру программиста в безопасности, будучи изолированными от необходимости думать о каких-либо деталях машины, и теперь вы хотите копнуть немного глубже и выяснить настоящую причину того, что скрипт Python, который вы переписали в Rust работает в 100 раз быстрее и использует 10-ю часть памяти. В конце концов, они оба делают одно и то же и работают на одном процессоре, верно?
Итак, вот руководство по оптимизации, предназначенное для тех, кто умеет программировать, но, возможно, не знает, как оно сопоставляется с реальными единицами и нулями на голом железе вашего процессора. Я постараюсь составить практические советы по оптимизации кода Rust с объяснением причин, по которым он быстрее, чем альтернатива, и мы закончим примером из стандартной библиотеки Rust.
Этот пост предполагает приличное знакомство с программированием, знакомство с Rust новичком и почти полное отсутствие знаний об архитектуре ЦП.
Совет по оптимизации номер один: не делайте этого
Хорошо, я начну с нескольких заявлений об отказе от ответственности, прежде чем перейду к сути. Во-первых, если вы не сталкиваетесь с проблемами производительности при реальном использовании, оптимизируйте код для удобства чтения, прежде чем оптимизировать его для производительности во время выполнения. Как компиляторы, так и люди лучше понимают скучный и простой код, поэтому, если вы напишете его первым, у вас, вероятно, будет «достаточно хорошая» производительность с дополнительным преимуществом, заключающимся в удобстве обслуживания. Если вы напишете хороший, реорганизуемый код, его будет легко изменить, если вы позже поймете, что это расточительно.
Это не значит, что производительность не имеет значения. Не следует оптимизировать только медленные программы. Длительная программа, использующая большое количество ресурсов ЦП, но не вызывающая видимой медлительности, так же плоха, как программа, которая обрабатывает некоторые данные за 30 секунд вместо 3, просто первая тратит впустую батарею, а вторая - время. Оцените время, необходимое для оптимизации кода, с выгодой, которую вы получите от оптимизации.
Причина, по которой ремонтопригодность так важна, заключается в том, что многие оптимизации проводятся по принципу «попробуй и увидишь» - если вы не можете внести радикальные изменения в свой код, не нарушив его, вам будет очень плохо. Теперь, говоря о «попробуй и увидишь»…
Никогда не оптимизируйте вслепую
Существует множество инструментов для отслеживания производительности. Знаменитым инструментом / набором инструментов для C и других системных языков является valgrind, которые чрезвычайно мощны, но могут быть пугающими для начала, поэтому, если вы просто хотите получить быстрый обзор того, что делает ваша программа, с точки зрения проверки производительности прочтите эту статью об анализе Rust с помощью perf, фантастического и простого в использовании инструмента повышения производительности для Linux. Если нет явного изъяна, такого как повсеместное клонирование или явно неоптимальный алгоритм, perf, скорее всего, даст лучшие результаты, чем простая оптимизация того, что «выглядит медленно».
Еще один инструмент, который поможет вам избежать всевозможных подводных камней (не только производительности), довольно краток, но вы уже знали об этом, потому что с самого начала используете его во всем своем коде, верно?
perf также показывает совокупную стоимость каждой функции в течение времени выполнения программы, что подводит меня к следующему пункту:
Не беспокойтесь об оптимизации единовременных затрат
Ваш код анализа конфигурации может быть сколь угодно медленным, и это вряд ли имеет значение. Не просто оптимизируйте самую медленную функцию в своей программе, оптимизируйте ту, которая занимает большую часть времени выполнения. Это может быть одна и та же функция, но если вы улучшите функцию, которая вызывается 1000 раз, на 2 миллисекунды, это лучше, чем улучшение на 1 секунду для функции, которая вызывается один раз.
Улучшите свои алгоритмы
Теперь, как и в каждой статье о производительности, здесь я добавляю обязательный отказ от использования в первую очередь лучших алгоритмов. Не изобретайте новые алгоритмы, если вы этим не зарабатываете на жизнь, но, по всей вероятности, если вы столкнетесь с проблемами производительности, это, скорее всего, будет из-за плохих алгоритмов, чем из-за плохой реализации. Большинство программистов тестируют свой код на небольших наборах данных, но если у вас сложность O (n²), она не появится, пока вы не попробуете ее на более крупном наборе данных. Если вы не знаете, каков ваш алгоритм, что вероятно, поскольку большая часть кода написана без учета определенного алгоритма, просто постарайтесь создать как можно меньше циклов и помните, что каждое использование collect должно перебирать всю коллекцию на хотя бы один раз, поэтому чем больше работы вы сможете выполнить, используя меньшее количество циклов, тем лучше. Тем не менее, это то же самое, что и оптимизация на любом языке, так что это все, что я скажу об алгоритмической сложности. Если вы хотите узнать больше, есть отличные ресурсы.
Учебник по архитектуре ЦП
Так что, возможно, сложность вашего алгоритма не может быть улучшена, и для внесения каких-либо улучшений вам нужно вникнуть в самые мелкие вещи. В этом заключается разница между такими языками, как Rust и C, и такими языками, как Python и Ruby. Вполне возможно, что вы это уже знаете, но стоит перейти, чтобы убедиться, что мы все на одной странице.
Любые вычисления состоят из двух частей: того, что они делают, и того, над чем они работают. Инструкции и данные.
Инструкции хранятся в кэше инструкций - фрагменте действительно, очень быстрой памяти, которая напрямую читается ЦП. Каждая инструкция может помещать и/или принимать данные из регистров ЦП, которые представляют собой небольшое количество небольших фрагментов памяти, 32 или 64 бита в зависимости от размера слова вашего компьютера. Однако в любой момент времени в регистрах может находиться только небольшой объем данных, и вы не можете использовать указатель на регистр, поэтому иногда ЦП должен получить доступ к ОЗУ компьютера. Поскольку оперативная память медленная, ЦП пытается выполнить массовое чтение, а затем сохранить результат во все более мелких и все более быстрых кэшах. Если он пытается получить доступ к данным, которых нет в самом маленьком кэше, он должен прочитать немного больший кеш, продолжая до тех пор, пока он не достигнет ОЗУ. Результат таков: вы хотите, чтобы ваши данные были как можно меньше, а данные, к которым осуществляется совместный доступ, должны быть близко друг к другу, чтобы ЦП загружал как можно больше их одновременно. Этой информации должно быть достаточно, чтобы вы могли прочитать оставшуюся часть этой статьи, но если вы хотите глубже погрузиться в нее, вы можете проверить раздел структуры и реализации на странице Википедии, посвященной процессору.
Держите как можно больше в кеше
Чем дальше ваши данные от вашего процессора, тем медленнее будет ваша программа. Наихудшее место для данных - другой компьютер. Менее ужасное - но все же очень ужасное - место для данных находится на вашем жестком диске. Лучше по-прежнему находится в вашей оперативной памяти, но, как упоминалось ранее, оперативная память работает медленно. Практически лучшее место для ваших данных - это кэш ЦП. Возможно, вы слышали какой-то фольклор о том, что распределение - это плохо, и это основная причина, почему. Доступ к двум разным местоположениям в стеке по очереди - это нормально, поскольку они, скорее всего, находятся в одной строке кеша. Доступ к двум разным местоположениям в куче поочередно происходит значительно медленнее, поскольку гораздо менее вероятно, что они находятся непосредственно рядом друг с другом. Мы скоро выясним, почему это происходит.
Если вам нужно выделить, потому что вам нужны контейнеры переменного размера, совместное владение или принадлежащие объекты-характеристики (см. Ниже, почему вам, вероятно, не нужны объекты-характеристики), попробуйте поместить данные, к которым будет осуществляться доступ последовательно, в ОЗУ, так что, когда ЦП считывает один элемент, он обязательно должен также читать следующие несколько элементов, что означает, что ему не нужно останавливаться в ожидании ОЗУ, чтобы работать с ними.
Эмпирическое правило для определения того, должно ли что-то выделяться: если вы можете сказать мне, сколько места будет использовано значением без запуска программы, оно сохраняется в стеке. Если вы не знаете размер чего-либо до времени выполнения, он размещается в куче.
Это означает, что String, Vec, HashMap и Box
Вот почему вы, возможно, слышали жалобы на то, что Haskell использует связанный список символов для представления строки. Я не собираюсь обыгрывать чудесную тираду ганкро по этому поводу, но достаточно сказать, что это более или менее худшая из возможных структур данных для выбора, когда каждый отдельный элемент мал, а количество элементов велико, потому что для этого нужно для хранения указателя для каждого элемента вместо одного целого числа для всего массива.
Не только это, но и без некоторых действительно сумасшедших оптимизаций компилятора это означает, что каждый элемент не может быть непосредственно после элемента перед ним в памяти. Мы скоро узнаем, как это вычислить, но, по сути, это означает, что тип String в Haskell может вызвать пропуск кэша до двух раз на элемент, тогда как если бы у вас был вектор символов (при условии 32-битных символов), он мог бы только вызвать максимум 1 промах в кэше на каждые 16 элементов. Вот почему специалисты по производительности в таких языках, как Haskell и Lisp, знают, что нужно использовать векторные конструкции, когда это возможно.
Вернувшись в мир Rust, это означает, что вам следует избегать непрямых представлений Vec<Vec<_>> для представления матрицы, поскольку это означает, что каждый sub-vec, скорее всего, будет в другом месте. Используйте структуру данных, которая использует плоский Vec в качестве вспомогательного массива и строится поверх него, если вам действительно не нужно, чтобы внутренние Vec были как зубчатыми (каждый sub-vec имеет разный размер), так и растущими (вы можете изменить размер каждого вспомогательного вектора независимо во время выполнения). Вероятно, вам не понадобится ни то, ни другое, не говоря уже о том и другом. Если вам нужно, чтобы они были одинакового размера, сохраните Vec и кортеж измерения, если вам нужно, чтобы они были зубчатыми, но не нужно, чтобы они могли увеличиваться, сохраните список индексов и возвращайте срезы плоского Vec, используя их. Чтобы понять, почему это хорошо, давайте погрузимся в основы математики. Предположим, что матрица основана на плоском векторе и количестве столбцов (количество строк можно вывести из столбцов + длины данных):
// This isn't how Vec is defined in the standard library but it's a simplified
// version with the same memory layout.
struct Vec<T> {
pointer: *mut T,
capacity: usize,
len: usize,
}
struct Matrix<T> {
data: Vec<T>,
num_columns: usize,
}
Таким образом, матрице с N строками и M столбцами требуется пространство N * M * size_of ::
Metadata size = 4 + 3 * 4 = 16
Maximum 2 cache misses
Data size = 4 * 4 * 4 = 64
Maximum 2 cache misses
Поскольку метаданные и данные могут находиться в разных частях памяти, мы должны отдельно рассчитывать максимальное количество промахов в кэше. И метаданные, и данные могут пересекать строку кэша, и для их загрузки требуется два промаха кеша. Это означает, что вся матрица в худшем случае пропустит кеш 4 раза. Если бы у нас было представление Vec<Vec
Matrix metadata size = 4 + 2 * 4 = 12
Maximum 2 cache misses
Inner vector metadata size = 4 * (4 + 2 * 4) = 48
Maximum 2 cache misses
Data size = 4 * 4 = 16
Maximum 2 cache misses per row (8 cache misses total)
Это означает, что представление Vec<Vec
Еще лучше, если вы статически знаете размер матрицы, вы можете использовать массивы статического размера, такие как [[T; N]; N]. Это даже дешевле, чем плоские векторы, хотя вы, очевидно, не можете использовать их для данных с переменным размером во время выполнения. Массив 4x4 в предыдущем примере будет иметь вид [[f32; 4]; 4] и занимают 64 байта, что означает, что в худшем случае для загрузки потребуется всего 2 промаха кеша.
Хранить как можно больше в регистрах
Теперь самое лучшее место для ваших данных - регистры. Чем больше работы вы можете проделать без нелокальных операций записи, тем больше rustc и LLVM могут предположить о шаблонах доступа к вашим данным. Это хорошо, потому что это означает, что данные могут быть сопоставлены с физическими регистрами ЦП, которые являются самой быстрой памятью на всем вашем компьютере, но даже лучше, если вы сделаете свои данные подходящими для регистров, тогда все, что происходит с этими данными, можно агрессивно оптимизировать. . Запись и чтение через указатели имеют определенные ограничения по порядку, препятствующие оптимизации, но таких ограничений для данных, размещенных в регистрах, нет.
Стоит отметить, что, поскольку Rust ограничивает указатели больше, чем C, ограничения на упорядочение указателей могут быть ослаблены. Это еще не реализовано в LLVM, поскольку большая часть работы по оптимизации основана на использовании правил языков C и C-семейств. Однако даже если они ослабят правила переупорядочения, сохранение данных в регистрах все равно будет проще оптимизировать.
Так как же заставить rustc распределять данные по регистрам? По сути, чем меньше указателей нужно писать во время выполнения, тем лучше. Запись в локальные переменные лучше, чем через изменяемый указатель. Насколько это возможно, вы должны попытаться ограничить изменяемую запись для данных, которыми вы владеете. Таким образом, изменяемый счетчик цикла - это нормально, но передача изменяемой ссылки на счетчик цикла через несколько уровней функций - нет (если, конечно, они не становятся встроенными). На самом деле это просто продолжение одного из моих первых замечаний: чистый, скучный код легче оптимизировать, чем спагетти.
Avoid Box
Канонический способ создания типажных объектов - Box
struct Cons<Head, Tail>(Head, Tail);
Поскольку структуры данных в Rust не добавляют косвенных затрат или накладных расходов на пространство, вы можете рекурсивно реализовать трейт для этой структуры и иметь функцию, которая может принимать любое количество параметров, которая работает так же быстро, как эквивалентная функция, которая принимает фиксированное количество параметров. . Вот пример того, как это может искать функцию, которая принимает список функций и вызывает их:
Версия с аллокацией:
fn call_all_fns(fns: Vec<Box<FnBox() ->()>>) {
for f in fns {
f();
}
}
Версия без аллокации:
struct Cons<First, Second>(First, Second);
trait HCons: Sized {
fn cons<T>(self, other: T) -> Cons<Self, T> {
Cons(self, other)
}
}
impl<T: Sized> HCons for T {}
// This is a hack to get around the fact that manually implementing the `Fn`
// traits is currently unstable.
trait Callable {
fn call(self);
}
impl<F: Fn() ->()> Callable for F {
fn call(self) { self() }
}
impl<First: Callable, Second: Callable> Callable for Cons<First, Second> {
fn call(self) {
self.0.call();
self.1.call();
}
}
fn call_all_fns_no_alloc<T: Callable>(fns: T) {
fns.call();
}
Вот как они оба выглядят при использовании:
fn main() {
let first_fn = || { println!("Hello!"); };
let second_fn = || { println!("World!"); };
call_all_fns(vec![Box::new(first_fn), Box::new(second_fn)]);
let first_fn = || { println!("Hello!"); };
let second_fn = || { println!("World!"); };
call_all_fns_no_alloc(first_fn.cons(second_fn));
}
Функции, переданные в call_all_fns_no_alloc, подходят для встраивания, они не требуют накладных расходов на пространство, а их инструкции и данные находятся непосредственно рядом друг с другом в памяти и, следовательно, получить доступ к ним намного быстрее, чем если бы каждая из них была помещена в коробку. Например, в сочетании есть функция выбора, которая принимает массив, который может содержать объекты трэйтов, но также предоставляет комбинатор .or() (и макрос выбора!, Который расширяется до рекурсивных вызовов .or), который возвращает Or <A, B> Что в свою очередь реализует Parser. Это означает, что диспетчеризация является статической, и все объекты хранятся в памяти по порядку (потому что это всего лишь набор рекурсивных структур). В некоторых случаях вам все равно понадобится динамическая отправка, но использование этого метода означает, что количество случаев, когда это необходимо, очень мало.
Использовать типы данных переменной длины на основе стека
Типы данных фиксированной длины легко сохранить в стеке, но для данных с динамическим размером это не так просто. Однако smallvec, smallstring и temril - это типы данных переменной длины, которые позволяют хранить небольшое количество элементов в стеке (бесстыдный плагин: smallstring был написан мной). Из-за закона малых чисел у вас, скорее всего, будет больше этих маленьких строк, чем больших. Это хорошо, потому что сокращает выделение, но прекрасно, если вы храните их в Vec или HashMap, поскольку у вас будет меньше косвенных обращений и, следовательно, лучшее использование кеша. Хорошее практическое правило - никогда не иметь более одного уровня указателей для разыменования, прежде чем вы достигнете своего значения (НАСА применяет это правило в своем коде C, хотя для надежности, а не для производительности).
Такие библиотеки, как smallvec, отлично подходят для локализации кеша, поскольку массив SmallVec<[T; 4]> будет иметь точно такую же локальность кэша, что и массив из просто T - пока длина каждого SmallVec меньше 8, он просто сохраняется по порядку. Возвращаясь к расчетам промаха кеша, сделанным ранее:
// This is a gross oversimplification of how this type is implemented in the
// crate, but it's enough to explain how it works.
enum SmallVec<T> {
Small([T; 4]),
Big(Vec<T>),
}
type Matrix<T> = SmallVec<SmallVec<T>>;
Пока в SmallVec меньше или равно 4 элемента, размер каждого экземпляра равен размеру данных плюс размер тега, что составляет:
let size_of_data = size_of::<T>() * 4;
let size_of_tag = max(size_of::<u8>(), align_of::<T>());
size_of_data + size_of_tag
Возникает очевидный вопрос: почему размер тега не равен size_of::
Предположим, у нас есть матрица 4x4 f32, это будет означать, что размер матрицы будет:
Inner SmallVec size = 4 * 4 + 4
Matrix size = 4 * (4 * 4 + 4) + 4 = 84
Maximum 3 cache misses
Нам не нужно отдельно вычислять промахи во внутреннем и внешнем кэше, потому что они гарантированно находятся рядом друг с другом в памяти.
С точки зрения кеширования это ничем не хуже плоского векторного представления, но ничто не мешает вам случайно сделать внутренние векторы разной длины и нарушить инвариант, согласно которому строки массива должны быть одинаковой длины.
Я хочу прояснить кое-что: вы никогда не будете делать эти вычисления в процессе оптимизации вашей программы. Это просто некоторое математическое обоснование фольклора вуду о том, что «распределение - это плохо», поскольку этому часто противопоставляется «malloc работает быстро». Оба утверждения верны - фактический процесс выделения и освобождения памяти происходит быстро, но выделяемые структуры данных хуже для случаев использования, требующих максимальной скорости.
Развертывание лупа по-прежнему круто
Устройство Даффа - это весело, но развернутые циклы общей длины массива вряд ли будут быстрее, чем эквивалентный оптимизированный наивный код в настоящее время, поскольку любой оптимизирующий компилятор, достойный своих битов, будет выполнять такую оптимизацию без необходимости искажать ваш код и разрушать будущее - вы день.
При этом, если вы знаете, что размер массива, скорее всего, будет кратен N, попробуйте сделать его &[[T; N]] и работает на [T; N] в каждой итерации. Это уменьшает количество итераций (и, следовательно, количество раз, которое вам нужно пересчитывать переменные цикла) и позволяет компилятору более агрессивно работать с телом цикла.
Вы также можете использовать более классическое развертывание цикла, если это позволяет снизить «силу» ваших операций. Это означает, что если вам нужно вычислить какое-то значение для каждой итерации цикла и вычисление этого значения занимает больше времени, чем само тело, вручную разверните тело, чтобы вы могли рассчитать его меньше. Пример: вы можете реализовать функцию целочисленного логарифма следующим образом:
fn log_base(mut n: usize, base: usize) -> usize {
let mut out = 1;
loop {
if n < base { return out; }
out += 1;
n /= base;
}
}
Однако n /= base; out += 1; вычисляется медленнее, чем n < base. Чтобы воспользоваться этим фактом, вы можете развернуть цикл следующим образом:
fn log_base_unrolled(mut n: usize, base: usize) -> usize {
const UNROLL_COUNT: usize = 4;
// We use a fixed-size array to ensure that we don't get the array count and
// the `out` skip value out of sync.
let premultiplied_base: [_; UNROLL_COUNT] = [
base,
base * base,
base * base * base,
base * base * base * base,
];
let mut out = 1;
loop {
if n < premultiplied_base[0] { return out; }
if n < premultiplied_base[1] { return out + 1; }
if n < premultiplied_base[2] { return out + 2; }
if n < premultiplied_base[3] { return out + 3; }
n /= precalculated_base[UNROLL_COUNT - 1];
out += UNROLL_COUNT;
}
}
Вот тесты, которые я использовал:
#[bench]
fn bench_log_base(b: &mut Bencher) {
b.iter(|| {
let input = black_box(5000000120510250);
assert_eq!(log_base(input, 10), 16);
});
}
#[bench]
fn bench_log_base_unrolled(b: &mut Bencher) {
b.iter(|| {
let input = black_box(5000000120510250);
assert_eq!(log_base(input, 10), 16);
});
}
test::black_box - это волшебная функция, которая не позволяет rustc и LLVM вычислять эти вызовы функций во время компиляции и преобразовывать их в константу, как обычно (на самом деле, это не волшебство, это просто некоторая встроенная сборка, которая ничего не делает , поскольку ни rustc, ни LLVM не будут пытаться оптимизировать все, что было доступно встроенной сборке).
Это дает следующие результаты:
test bench_log_base ... bench: 18 ns/iter (+/- 0)
test bench_log_base_unrolled ... bench: 5 ns/iter (+/- 0)
Подождите, однако, что произойдет, если мы дадим для base непостоянное значение?
#[bench]
fn bench_log_base_nonconstbase(b: &mut Bencher) {
b.iter(|| {
let input = black_box(5000000120510250);
let base = black_box(10);
assert_eq!(log_base(input, base), 16);
});
}
#[bench]
fn bench_log_base_unrolled_nonconstbase(b: &mut Bencher) {
b.iter(|| {
let input = black_box(5000000120510250);
let base = black_box(10);
assert_eq!(log_base_unrolled(input, base), 16);
});
}
test bench_log_base_unrolled_nonconstbase ... bench: 37 ns/iter (+/- 1)
test bench_log_base_nonconstbase ... bench: 199 ns/iter (+/- 5)
Они оба намного медленнее! Можем ли мы сделать лучше? Оказывается, да, мы можем:
fn log_base_increasing(n: usize, base: usize) -> usize {
const UNROLL_COUNT: usize = 4;
let premultiplied_base: [_; UNROLL_COUNT] = [
base,
base * base,
base * base * base,
base * base * base * base,
];
if n < premultiplied_base[0] { return 1; }
if n < premultiplied_base[1] { return 2; }
if n < premultiplied_base[2] { return 3; }
if n < premultiplied_base[3] { return 4; }
let mut out = UNROLL_COUNT + 1;
let mut mul = premultiplied_base[UNROLL_COUNT - 1];
loop {
if n < premultiplied_base[0] * mul { return out; }
if n < premultiplied_base[1] * mul { return out + 1; }
if n < premultiplied_base[2] * mul { return out + 2; }
if n < premultiplied_base[3] * mul { return out + 3; }
mul *= premultiplied_base[UNROLL_COUNT - 1];
out += UNROLL_COUNT;
}
}
#[bench]
fn bench_log_base_increasing(b: &mut Bencher) {
b.iter(|| {
let input = black_box(5000000120510250);
assert_eq!(log_base_increasing(input, 10), 16);
});
}
#[bench]
fn bench_log_base_increasing_nonconstbase(b: &mut Bencher) {
b.iter(|| {
let input = black_box(5000000120510250);
let base = black_box(10);
assert_eq!(log_base_increasing(input, base), 16);
});
}
Теперь посмотрим на результаты:
test bench_log_base ... bench: 18 ns/iter (+/- 0)
test bench_log_base_nonconstbase ... bench: 199 ns/iter (+/- 5)
test bench_log_base_unrolled ... bench: 5 ns/iter (+/- 0)
test bench_log_base_unrolled_nonconstbase ... bench: 37 ns/iter (+/- 1)
test bench_log_base_increasing ... bench: 6 ns/iter (+/- 0)
test bench_log_base_increasing_nonconstbase ... bench: 8 ns/iter (+/- 1)
Оказывается, компилятор делал что-то коварное: он может оптимизировать целочисленное деление на константу в умножение в сочетании со сдвигом. Когда он больше не мог складывать константу в функцию, он значительно замедлился. Можно полагаться на константное сворачивание, если оно позволяет получить значительное ускорение и вы знаете, что функция обычно вызывается с постоянными аргументами, но будьте осторожны. На что следует обратить внимание, - это операторы if и целочисленное деление, которые могут быть намного медленнее с непостоянными значениями по сравнению с константами.
Самый быстрый метод на сегодняшний день преобразуется в f64, вызывает .log (base) на этом, а затем преобразует обратно. Однако он не работает для больших чисел из-за потери точности. Вероятно, сейчас самое время отметить, что, хотя сложение и умножение целых чисел происходит быстрее, чем то же самое для чисел с плавающей запятой, для кода, который выполняет деление на непостоянное значение или что-то более сложное, например тригонометрия, вам обязательно следует использовать числа с плавающей запятой. Компилятор не может выполнить преобразование за вас - он не будет применять оптимизацию, которая делает ваш код менее точным, - но вы можете проверить области, в которых это может быть улучшением, и внести изменения вручную.
asssert! условия заранее
Если вы хотите уменьшить количество неявных утверждений, которые компилируются в код, вместо этого:
fn do_something_with_array(array: &[u8]) -> u8 {
array[0] + array[1] + array[2] + array[3] + array[4] + array[5]
}
Do this:
fn do_something_with_array(array: &[u8]) -> u8 {
assert!(array.len >= 5);
array[0] + array[1] + array[2] + array[3] + array[4] + array[5]
}
1 155 / 5 000 Результаты перевода Это позволяет LLVM понять, что последующие утверждения недоступны, и исключает их. Это полезно для любого кода, который может утверждать несколько различных качеств одних и тех же данных, но особенно полезно для индексации, поскольку мы знаем, что если array [n] завершится успешно, то array [n - 1] также будет успешным. Это похоже на вопрос о массивах фиксированной длины в предыдущем разделе.
По сути, попробуйте объединить проверки в одно утверждение !. Это означает, что последующие проверки становятся статически недоступными. Если LLVM / Rust по-прежнему не оптимизирует его, вы можете переключиться на использование небезопасных методов индексации, убедившись, что они по-прежнему безопасны. Этот совет бессовестно украден из комментария к /r/rust.
Использовать оптимизацию времени компоновки
Обычно Rust может встраивать только функции, которые либо определены внутри контейнера, либо, в случае функций из других библиотек, имеют указанный #[inline]. LTO позволяет компилятору встраивать кросс-крейт за счет снижения скорости во время компиляции. Я придерживаюсь мнения, что время компиляции имеет значение только для отладочных сборок, поэтому я готов пойти на компромисс. Как и во всем остальном, профилируйте и убедитесь, что компромисс оправдан.
Не используйте #[inline(always)]
#[inline (always)] кажется хорошим трэйтом производительности, но правда в том, что оптимизирующие компиляторы действительно хороши в работе, когда функция выиграет от встраивания, а Rust не ограничен более медленным стандартизированным соглашением о вызовах C и может использовать fastcc, что делает вызовы функций чрезвычайно дешевыми. Скорее всего, вы увеличите размер исполняемого файла. Конечно, это займет больше места на жестком диске, но это не такая уж большая проблема. Если у вас есть хотя бы один связанный ресурс, такой как изображения или аудио, они, скорее всего, уменьшат размер вашего исполняемого файла.
Настоящая проблема здесь в том, что это может привести к тому, что ваша программа больше не поместится в кеш-память команд ЦП. ЦП будет обращаться в ОЗУ для выполнения своих инструкций только тогда, когда функции вызываются с инструкциями вне текущей строки кэша. Чем больше ваш двоичный файл, тем больше вероятность этого, и чем больше функций встроено, тем больше ваш двоичный файл. Иметь большой двоичный файл - не конец света, но если вы действительно не уверены, что что-то будет улучшено, если вручную пометить его как встроенный, и у вас есть тесты, подтверждающие это, так же вероятно, что вы замедлитесь. программу с неосторожным встраиванием, чем для ее ускорения.
Итак, теперь я напугал вас встраиванием, давайте поговорим о том, когда вам следует явно добавлять встраиваемые аннотации. Часто вызываемые небольшие функции являются хорошей целью для встраивания. Итератор::next, например, или Deref::deref. Накладные расходы на вызов этих функций могут быть больше, чем время, необходимое для запуска самой функции. Скорее всего, они будут автоматически встроены при внутреннем вызове, но пометка их как #[inline] позволит пользователям вашей библиотеки также встроить их, даже если они не используют LTO. Только функции, помеченные #[inline], будут рассматриваться для встраивания между крэйтами, но это означает, что определение должно храниться в скомпилированной библиотеке, что приведет к раздуванию и увеличению времени компиляции. #[inline (always)] еще более нишевый, но иногда приятно убедиться, что крошечная функция будет встроена, или как своего рода документация, для которой вызов функции бесплатен, если кто-то приходит и пытается вручную встроить ее в улучшить производительность. Однако это действительно очень редко, когда вы захотите сделать это, и лучше всего просто доверять компилятору.
Другой класс функций, которые являются хорошими целями для аннотирования встраивания, - это функции, которые, как вы знаете, часто вызываются с постоянными параметрами. Мы рассмотрим это позже, но {integer}::from_str_radix - отличный пример этого. В большинстве случаев использование этой функции будет иметь константу в качестве второго параметра, и поэтому разумное использование #[inline] мы можем предотвратить ветвление и дорогостоящие операции, такие как разделение, для потребителей нашей библиотеки. Однако не стоит терять сон, поскольку они могут просто использовать оптимизацию времени компоновки, если им нужно выжать все до последней капли производительности.
Кроме того, компилятор иногда действительно ошибается и может упустить возможности встраивания, которые улучшили бы скорость кода. Однако добавляйте аннотацию #[inline (always)] только в том случае, если вы можете доказать с помощью тестов, что это улучшает скорость, а добавление этих аннотаций - своего рода мрачное искусство. Ваши усилия, вероятно, лучше потратить на что-то другое.
Если вы хотите уменьшить размер кода, вы можете попробовать использовать panic = "abort". Это удаляет «посадочные площадки», которые позволяют Rust показывать красивую трассировку стека после паники, и приводит к немедленному завершению программы при любой панике. Я на законных основаниях видел нетривиальное ускорение тестов для оболочки ion после добавления этой опции в сборку релиза, и я могу отнести это только к тому, что больше кода помещается в кэш инструкций. Я не пробовал это со многими другими программами, но, вероятно, это повлияет только на средние и большие проекты. Попробуйте это на своей кодовой базе, это так же просто, как добавить одну строку в Cargo.toml, и это может улучшить скорость вашего кода.
Распараллеливайте, но не так, как вы думаете
Для Haskell существует потрясающая библиотека под названием Haxl, которая автоматически отслеживает зависимости данных ваших сетевых запросов, группирует их и выполняет асинхронно, пока они не пересекаются. Это то, что демонстрирует мощь вычислительных абстракций, таких как монады, и, насколько мне известно, это не то, что имеет, кхм, параллель в каком-либо другом языке. По крайней мере, не для IO. У нас есть эта точная способность в ЦП в течение долгого, долгого времени. ЦП отслеживает зависимости данных вычислений и распараллеливает их, где это возможно.
Причина, по которой зависимости данных имеют значение, заключается в том, что ЦП не выполняет просто одну инструкцию за раз. Пока две инструкции не используют общий регистр, их можно безопасно запускать одновременно, так что это делает ЦП. По сути, это свободный параллелизм без необходимости блокировок, рабочих очередей или чего-либо, что вообще влияет на вашу архитектуру, поэтому вы были бы сумасшедшими, если бы не воспользовались им.
Распараллеливание вычислений также хорошо поддается автовекторизации, то есть процессу, при котором компилятор понимает, что вы делаете одно и то же с несколькими разными значениями, и преобразует это в специальную инструкцию, которая, ну, в общем, делает то же самое с несколькими разными значениями.
Например, компилятор может перевести следующий числовой код:
(a1 + a2) + (b1 + b2) + (c1 + c2) + (d1 + d2)
в одну инструкцию, которая выполняет все четыре подвыражения так же быстро, как одно сложение.
%intermediate-value = add-vectors [%a1 %b1 %c1 %d1] [%a2 %b2 %c2 %d2]
sum-parts %intermediate-value
Пример из практики
Давайте напишем версию usize::from_str_radix, которая будет примерно на 30% быстрее, чем версия в стандартной библиотеке.
// We're redefining these here since they're private in the stdlib
#[derive(Debug, Clone, PartialEq, Eq)]
struct ParseIntError {
kind: IntErrorKind,
}
#[derive(Debug, Clone, PartialEq, Eq)]
enum IntErrorKind {
Empty,
InvalidDigit,
Overflow,
Underflow,
}
#[inline]
fn from_str_radix(input: &str, radix: usize) -> Result<usize, ParseIntError> {
fn to_digit_ascii(ascii: u8, radix: usize) -> Result<usize, ParseIntError> {
let decimal_digit = ascii.wrapping_sub(b'0');
if radix > 10 && decimal_digit > 9 {
let out = (ascii | 32).wrapping_sub(b'a') as usize;
if out > radix - 10 {
Err(ParseIntError { kind: IntErrorKind::InvalidDigit })
} else {
Ok(out + 10)
}
} else {
let decimal_digit = decimal_digit as usize;
if decimal_digit > radix {
Err(ParseIntError { kind: IntErrorKind::InvalidDigit })
} else {
Ok(decimal_digit)
}
}
}
if radix > 36 {
panic!("from_str_radix: radix is too high (maximum 36)");
}
let bytes = input.as_bytes();
if bytes.len() == 0 {
return Err(
ParseIntError { kind: IntErrorKind::Empty }
);
}
let bytes = match bytes[0] {
b'+' => { &bytes[1..] },
b'-' => { return Err(ParseIntError { kind: IntErrorKind::Underflow }) },
_ => bytes,
};
let mut mul = radix;
let mut index = bytes.len() - 1;
let mut output = to_digit_ascii(bytes[index], radix)?;
for &byte in bytes[..index].iter().rev() {
let digit = to_digit_ascii(byte, radix)?;
let next_output = output.wrapping_add(digit * mul);
if output > next_output {
return Err(
ParseIntError { kind: IntErrorKind::Overflow }
);
}
mul *= radix;
output = next_output;
}
Ok(output)
}
Я явно использую функции wrapping_ * не в целях оптимизации (поскольку проверки переполнения удаляются во время выполнения), а потому, что для правильного поведения требуется переполнение. Здесь вы заметите некоторые улучшения:
- Начинаем в конце и работаем в обратном направлении, сохраняя счетчик «мул». Первоначально я написал такую версию, которая работает в прямом направлении и умножает вывод на основание системы счисления в каждом цикле, но обратный метод на 10% быстрее. Похоже, это связано с лучшим параллелизмом на уровне инструкций. Умножения можно распараллеливать, и только сложение зависит от значения предыдущей итерации для вывода, и сложение происходит намного быстрее. Таким образом можно улучшить любые операции сворачивания, используя алгебраические законы (в данном случае закон распределения) для увеличения количества операций, которые могут выполняться параллельно.
- Мы полагаемся на переполнение для проверки сравнений A <x <B. Здесь это полезно только потому, что нам уже нужно значение x - A, поэтому мы сохраняем дополнительное сравнение и побитовое и. В большинстве случаев код A <x && x <B столь же дешев или дешевле, чем x - A <B с переполнением.
- Мы используем | 32, чтобы унифицировать пути кода для прописных и строчных букв, уменьшая количество необходимых сравнений.
- Мы не делаем output + digit * mul, когда output == 0 и mul == 1. Кажется, что это постоянно на 1 нс быстрее, но возможно, что это не имеет значения, и ускорение на 1 нс, которое я вижу, составляет чистое везение. Я повторно проводил тесты как с изменением, так и без него несколько раз и увидел стабильную разницу, но это не исключает удачи. Это проблема микротестов, когда разница становится достаточно маленькой, вы не можете сказать, действительно ли вы делаете это быстрее.
- Мы используем безопасный интерфейс итератора Rust, который работает так же быстро, как идиома C по хранению указателей «начало» и «конец», поэтому вы можете проверить завершение цикла простым ==. Если вы когда-нибудь слышите, как кто-то говорит: «Гарантии безопасности Rust бесполезны, потому что вам нужно опуститься до небезопасного, чтобы получить реальную скорость» (я уже видел это почти дословно раньше на Hacker News), вы можете показать им это.
- Мы не полагаемся на константное сворачивание, чтобы сделать наш код быстрым, но он работает быстрее с постоянным значением для radix. Поэтому мы добавляем #[inline], чтобы позволить последующим крэйтам также применять константное сворачивание.
Метод, который я использовал для этого, является основным методом, который вы должны использовать для любой работы по оптимизации: напишите репрезентативный тест, а затем постепенно настраивайте и повторно запускайте тесты, пока у вас не будет больше циклов. Сделать это для чистых функций намного проще, поэтому первое, что вы должны сделать для оптимизации любой функции, вызываемой в замкнутом цикле, - это сделать ее чистой. Это позволяет избежать косвенной записи и чтения (чтения и записи в места в памяти, которые могут находиться за пределами строк кэша) и значительно упрощает тестирование производительности. Если вы используете разработку через тестирование для обеспечения надежности, это эквивалентно производительности.
Расширение этого для работы со знаковыми целочисленными типами - это упражнение для читателя. Совет: в отличие от C, вы можете полагаться на переполнение целых чисел со знаком с помощью арифметики с дополнением до 2.
Вот функции, которые я использовал для тестирования кода:
#[bench]
fn bench_from_str(b: &mut Bencher) {
b.iter(|| {
let input = black_box("1235112512");
assert_eq!(from_str_radix(input, 10), Ok(1235112512));
let input = black_box("FFaf125A");
assert_eq!(from_str_radix(input, 16), Ok(0xFFaf125A));
});
}
#[bench]
fn bench_from_str_native(b: &mut Bencher) {
b.iter(|| {
let input = black_box("1235112512");
assert_eq!(usize::from_str_radix(input, 10), Ok(1235112512));
let input = black_box("FFaf125A");
assert_eq!(usize::from_str_radix(input, 16), Ok(0xFFaf125A));
});
}
#[bench]
fn bench_from_str_nonconstradix(b: &mut Bencher) {
b.iter(|| {
let input = black_box("1235112512");
let radix = black_box(10);
assert_eq!(from_str_radix(input, radix), Ok(1235112512));
let input = black_box("FFaf125A");
let radix = black_box(16);
assert_eq!(from_str_radix(input, radix), Ok(0xFFaf125A));
});
}
#[bench]
fn bench_from_str_native_nonconstradix(b: &mut Bencher) {
b.iter(|| {
let input = black_box("1235112512");
let radix = black_box(10);
assert_eq!(usize::from_str_radix(input, radix), Ok(1235112512));
let input = black_box("FFaf125A");
let radix = black_box(16);
assert_eq!(usize::from_str_radix(input, radix), Ok(0xFFaf125A));
});
}
#[bench]
fn bench_from_str_1char(b: &mut Bencher) {
b.iter(|| {
let input = black_box("1");
assert_eq!(from_str_radix(input, 10), Ok(1));
let input = black_box("F");
assert_eq!(from_str_radix(input, 16), Ok(0xF));
});
}
#[bench]
fn bench_from_str_native_1char(b: &mut Bencher) {
b.iter(|| {
let input = black_box("1");
assert_eq!(usize::from_str_radix(input, 10), Ok(1));
let input = black_box("F");
assert_eq!(usize::from_str_radix(input, 16), Ok(0xF));
});
}
Результаты:
test bench_from_str ... bench: 22 ns/iter (+/- 7)
test bench_from_str_native ... bench: 36 ns/iter (+/- 0)
test bench_from_str_nonconstradix ... bench: 26 ns/iter (+/- 0)
test bench_from_str_native_nonconstradix ... bench: 39 ns/iter (+/- 0)
test bench_from_str_1char ... bench: 5 ns/iter (+/- 0)
test bench_from_str_native_1char ... bench: 13 ns/iter (+/- 0)
При тестах ниже 1 мс я заметил, что для «раскрутки» процессора может потребоваться некоторое время. Иногда первый тест в наборе занимает на 20-30 нс дольше, чем последующие. Если вы дословно продублируете эталонный тест и возьмете число с наименьшей дисперсией, это позволит избежать проблемы. Я думаю, это связано с тем, что ЦП должен собирать информацию для правильного прогнозирования ветвлений. В идеале вы просто не должны проводить микротест, но некоторые функции законно требуют этого. Не доверяйте тестам, особенно микробенчмаркам, пока не запустите их несколько раз.
Когда я повторно запускал этот конкретный тест (всего не менее 10 раз, не считая тестов, которые я запускал при редактировании кода), чтобы убедиться, что числа были стабильными, и хотя средние значения чрезвычайно стабильны (собственный тест иногда был немного медленнее, Значение 36 нс выше - это то, что я вижу большую часть времени), дисперсия в основном составляет 0–3 нс с пиками 13–26 нс. У меня нет хорошего объяснения этому, ожидайте следующего сообщения с советами по написанию лучших тестов.
Это прекрасный пример того, почему так важна низкоуровневая оптимизация, поскольку именно такая функция может использоваться сотни тысяч раз в парсерах текстовых данных, а ускорение на 10 нс здесь может привести к значительным улучшениям в течение срока службы программа. Это также пример того, почему вам следует по возможности избегать низкоуровневой оптимизации. Исходная реализация этой функции в stdlib - не самый идиоматический код, но он значительно более читабелен, чем этот. Сказав это, тем не менее, это свидетельство приверженности Rust абстракциям с нулевой стоимостью: вы можете писать в основном идиоматический, безопасный код и заставлять его работать, а также эквивалентный код C/C++, который потребует использования небезопасной арифметики указателей.
Подведение итогов
Если бы мне пришлось подытожить трюк с оптимизацией в содержательном фрагменте, готовом для QotW, это было бы так:
Самый быстрый код - это код, который вообще не запускается, второй по скорости код - это код, который никогда не должен ждать.
В идеале вы хотите делать меньше работы, а если вы выполняете минимальный объем работы, вы хотите уменьшить количество времени, которое процессор тратит на ожидание.
Если вам нужно больше советов по производительности Rustic с большим количеством цифр, я бы посчитал превосходное вскрытие ripgrep BurntSushi необходимым для чтения всем, кто хочет писать быстрое программное обеспечение (это было то, что изначально отправило меня в эту глубокую кроличью нору). Чтобы узнать о более общих системных языковых аспектах, ознакомьтесь с докладом Андрея Александреску «Fastware», из которого был адаптирован код from_str_radix и log_base. Многие пункты в этой статье являются расширением пунктов, стоящих за одной из этих двух ссылок.
Я надеюсь, что независимо от того, являетесь ли вы Rustacean софт-оболочкой или седеющим ветераном, это дало вам лучшее представление о том, когда какой-то код может плохо работать, и что с этим делать. Иди, пусть дела идут врум.