Повышение скорости SmallVec на 60% и почему это не должно иметь для вас значения

Перевод | Автор оригинала: troubles.md

smallvec - это библиотека, разработанная командой Servo для уменьшения количества выделений для динамических массивов в случае, если большинство из этих массивов меньше определенного размера. Например, если вы создаете вектор, который обычно содержит менее 100 элементов, но может иметь больше, вы можете уменьшить нагрузку на распределитель, используя SmallVec следующим образом: 

fn print_iterator<T>(i: T)
where
  T: Iterator,
  T::Item: Debug,
{
  // Before...
  let vec: Vec<T::Item> = i.collect();
  // After
  let vec: SmallVec<[T::Item; 100]> = i.collect();
  
  println!("{:?}", vec);
}

Реализация концептуально очень проста и выглядит примерно так: 

// Implemented for `[T; 1]`, `[T; 2]`, etc.
trait Array {
    type Item;

    fn ptr(&self) -> *const Item;
    fn ptr_mut(&self) -> *mut Item;
    fn size() -> usize;
}

enum SmallVec<T: Array> {
    Inline {
        len: usize,
        buffer: T,
    },
    Heap(Vec<T::Item>),
}

Реальная реализация более сложна с точки зрения оптимизации, но по сути это то, что вы видите выше. Если длина меньше, чем T::size(), он будет хранить элементы встроенными (в стеке), если он станет больше, тогда он скопирует элементы в кучу, что потребует затрат на выделение и копирование существующих элементы. Основные преимущества этого заключаются не в избежании выделения, а в большей эффективности кеширования при хранении значений SmallVec в массиве.

Поскольку malloc работает быстро, во многих случаях на самом деле использовать SmallVec медленнее, чем просто использовать Vec, потому что единовременные затраты на начальное выделение минимальны по сравнению с затратами на время жизни из-за повышенной сложности SmallVec. Вы можете видеть, что переход на Vec на самом деле улучшает скорость многих собственных тестов SmallVec1:

namesmallvec.bench ns/itervec.bench ns/iterdiff ns/iterdiff %speedup
extend_from_slice52651325.00%x 0.80
extend_from_slice_small2329626.09%x 0.79
extend20069-131-65.50%x 2.90
extend_small3928-11-28.21%x 1.39
from_slice19936-163-81.91%x 5.53
from_slice_small3830-8-21.05%x 1.27
insert1,2221,23190.74%x 0.99
insert_small121114-7-5.79%x 1.06
macro_from_elem21840-178-81.65%x 5.45
macro_from_elem_small6032-28-46.67%x 1.88
push357369123.36%x 0.97
push_small5753-4-7.02%x 1.08
macro_from_list4733-14-29.79%x 1.42
pushpop306253-53-17.32%x 1.21

Vec медленнее только для одного метода - extend_from_slice. Как ни странно, SmallVec работает еще быстрее в случае, если требуется выделить extension_from_slice. При беглом взгляде на исходный код std кажется, что SmallVec может получить преимущество при встраивании, поскольку Vec::extend_from_slice не помечен #[inline].

Даже с улучшением extend_from_slice по-прежнему сложно использовать SmallVec. Даже в том случае, когда SmallVec находится в стеке - когда у него должно быть преимущество - он все равно медленнее.

Подождите, однако, это не единственная разница между ними в том, что SmallVec должен проверять, является ли он встроенным или размещенным в куче? Почему from_elem (который тестирует макрос vec! [Val; N] и эквивалентный макрос smallvec! [Val; N]) более чем в 5 раз медленнее для SmallVec, и почему он работает почти в 3 раза медленнее, даже если он медленнее, когда он в стеке? Оказывается, очевидно, что у этой библиотеки были серьезные недостатки, которые не присущи дизайну. Давайте посмотрим, как выглядят SmallVec::from_elem и SmallVec::extend: 

impl<A: Array> SmallVec<A> {
  pub fn from_elem(elem: A::Item, n: usize) -> Self {
    let mut v = SmallVec::with_capacity(n);
    v.insert_many(0, (0..n).map(|_| elem.clone()));
    v
  }

  // ...
}

impl<A: Array> Extend<A::Item> for SmallVec<A> {
  fn extend<I>(&mut self, iterable: I)
  where
    I: IntoIterator<Item=A::Item>
  {
    let iter = iterable.into_iter();
    let (lower_size_bound, _) = iter.size_hint();

    let target_len = self.len + lower_size_bound;

    if target_len > self.capacity() {
       self.grow(target_len);
    }

    for elem in iter {
      self.push(elem);
    }
  }
}

Оба кажутся довольно ясными, для расширения вы резервируете ожидаемое количество элементов, а затем выполняете цикл for через итератор, перемещая каждый элемент в новый SmallVec. Для from_elem вы создаете SmallVec, предварительно выделенный нужным вам количеством элементов, а затем вставляете n клонов elem. Постойте, но как выглядит исходный код insert_many? 

impl<A: Array> SmallVec<A> {
  // ...

  pub fn insert_many<I: IntoIterator<Item=A::Item>>(&mut self, index: usize, iterable: I) {
    let iter = iterable.into_iter();
    let (lower_size_bound, _) = iter.size_hint();
    assert!(lower_size_bound <= std::isize::MAX as usize);  // Ensure offset is indexable
    assert!(index + lower_size_bound >= index);  // Protect against overflow
    self.reserve(lower_size_bound);

    unsafe {
      let old_len = self.len;
      assert!(index <= old_len);
      let ptr = self.as_mut_ptr().offset(index as isize);
      ptr::copy(ptr, ptr.offset(lower_size_bound as isize), old_len - index);

      for (off, element) in iter.enumerate() {
        if off < lower_size_bound {
          ptr::write(ptr.offset(off as isize), element);
          self.len = self.len + 1;
        } else {
          // Iterator provided more elements than the hint.
          assert!(index + off >= index);  // Protect against overflow.
          self.insert(index + off, element);
        }
      }

      let num_added = self.len - old_len;
      if num_added < lower_size_bound {
        // Iterator provided fewer elements than the hint
        ptr::copy(ptr.offset(lower_size_bound as isize), ptr.offset(num_added as isize), old_len - index);
      }
    }
  }
}

Ага! Это много кода. Давайте рассмотрим это по крупицам (я удалил утверждения, чтобы сделать логику более понятной): 

let (lower_size_bound, _) = iter.size_hint();

self.reserve(lower_size_bound);

Это резервирует достаточно места для нижней границы итератора, сообщаемой им самим по количеству созданных элементов. Подождите, мы уже знаем, что у нас достаточно места, так как мы только что создали его с помощью with_capacity, а затем использовали итератор с фиксированным размером. Так что это бесполезно. Нам не нужно больше резервировать место. 

let old_len = self.len;

let ptr = self.as_mut_ptr().offset(index as isize);

ptr::copy(ptr, ptr.offset(lower_size_bound as isize), old_len - index);

Это оптимистично копирует любые существующие элементы в конец массива. Это связано с тем, что эта функция позволяет вам вставлять новые элементы в любой момент, а не только в конце, и поэтому, если есть существующие элементы, необходимо сначала переместить их2. Опять же, эти строки бесполезны. Если мы вызываем это из from_elem, мы знаем, что и self.len, и index равны 0, поэтому всегда будет копироваться 0 байтов (без операции). Однако мы все еще тратим циклы на выяснение этого.

for (off, element) in iter.enumerate() {
  if off < lower_size_bound {
    ptr::write(ptr.offset(off as isize), element);
    self.len = self.len + 1;
  } else {
    self.insert(index + off, element);
  }
}

Для каждого элемента делаем ветку. Это означает, что компилятор не может оптимизировать это в memcpy (самый быстрый из возможных методов копирования байтов), потому что для каждого элемента нам нужно проверить, достигли ли мы нижней границы размера. Технически компилятор может оптимизировать это, превратив его в два цикла (известных как деление цикла), а затем заметив, что первый цикл эквивалентен memcpy, но полагаться на него для этого нецелесообразно, поскольку он требует применения нескольких проходов оптимизации в правильный порядок. Опять же, когда мы вызываем эту функцию из from_elem, мы знаем, что она может проходить только через первую ветвь, а не через вторую, поэтому это предотвращает оптимизацию и бесполезно тратит время на проверку <lower_size_bound. 

let num_added = self.len - old_len;
if num_added < lower_size_bound {
  // Iterator provided fewer elements than the hint
  ptr::copy(
    ptr.offset(lower_size_bound as isize),
    ptr.offset(num_added as isize),
    old_len - index
  );
}

Это еще одна ветвь, которая всегда пропускается, когда мы выполняем from_elem, поскольку мы знаем, что итератор каждый раз производит нужное количество элементов. Больше потраченных впустую циклов.

Я не буду подробно останавливаться на том, как это делает Vec, но вы можете проверить код здесь. Важно то, что для многих типов это происходит настолько быстро, насколько это возможно. Много работы было вложено в оптимизацию этого, и это видно. Существует даже специальный метод, который использует способность операционной системы «волшебным образом» возвращать обнуленную память, если элемент, который вы передаете функции, равен 0 (т.е. Vec запрашивает указатель на обнуленную память, а ОС возвращает указатель на память, который она знает, что его следует обнулить, но на самом деле не обнуляет его, пока вы не попытаетесь получить к нему доступ). Он увеличивает длину вектора только один раз после добавления всех элементов. Это намного лучше, чем наш метод увеличения длины вектора на 1 на каждой итерации цикла, потому что вам нужно сделать только одно добавление. Чем больше Vec, тем больше будет разница. Самым большим преимуществом является то, что он использует специализацию для использования memcpy для любого элемента, реализующего Copy. Это означает, что по возможности он будет копировать с помощью SIMD.

Оптимизации, требующие специализации, на самом деле невозможно реализовать в SmallVec, не требуя ночного компилятора, но оказывается, что это не имеет значения. Вы можете просто повторно использовать Vec::from_elem (это то, для чего vec! [Elem; n] desugars), когда вы знаете, что он окажется в куче, и выполнить простой цикл и запись, когда вы знаете, что он будет включен. стек. Вот как это выглядит: 

pub fn from_elem(elem: A::Item, n: usize) -> Self {
  if n > A::size() {
    vec![elem; n].into()
  } else {
    unsafe {
      let mut arr: A = ::std::mem::uninitialized();
      let ptr = arr.ptr_mut();

      for i in 0..n as isize {
        ::std::ptr::write(ptr.offset(i), elem.clone());
      }

      SmallVec {
        data: Inline { array: arr },
        len: n,
      }
    }
  }
}

Нам не нужно использовать волшебную способность ОС вызывать обнуленную память, когда мы создаем что-то в стеке, поскольку это работает на уровне детализации страницы - 4 КБ по умолчанию в Linux - и если вы создаете массив, который велика, то стоимость размещения абсолютно невысока по сравнению с затратами на инициализацию. LLVM может тривиально оптимизировать цикл for в memcpy и даже memset, когда A::Item = u8 (комментарий в заголовке файла перечисляет эту оптимизацию как TODO, но если вы посмотрите на код, вы увидите, что это уже было реализовано). Мы получаем все преимущества сложной реализации Vec, при этом единственная стоимость - проверка n> A::size(), что особенно дешево, потому что A::size() является константой. Здесь вы можете увидеть сгенерированную сборку, я не комментировал ее из-за огромного количества кода, который был сгенерирован раньше, но разница в объеме кода должна прояснить, что этот метод значительно более эффективен.

После этого мы видим огромное улучшение:

namesmallvec.bench ns/itervec.bench ns/iterdiff ns/iterdiff %speedup
macro_from_elem6650-16-24.24%x 1.32

Vec по-прежнему быстрее, но теперь разница всего 16 нс вместо 130 нс. Мне действительно интересно, есть ли способ ускорить преобразование из Vec в SmallVec, потому что это единственное место, откуда может исходить разница, и она должна быть практически мгновенной.

А теперь самое интересное. Давайте снова посмотрим на SmallVec::extend: 

impl<A: Array> Extend<A::Item> for SmallVec<A> {
  fn extend<I>(&mut self, iterable: I)
  where
    I: IntoIterator<Item=A::Item>
  {
    let iter = iterable.into_iter();
    let (lower_size_bound, _) = iter.size_hint();

    let target_len = self.len + lower_size_bound;

    if target_len > self.capacity() {
       self.grow(target_len);
    }

    for elem in iter {
      self.push(elem);
    }
  }
}

Так что в этом плохого? Что ж, давайте посмотрим на источник толчка: 

pub fn push(&mut self, value: A::Item) {
  let cap = self.capacity();

  if self.len == cap {
    self.grow(cmp::max(cap * 2, 1))
  }

  unsafe {
    let end = self.as_mut_ptr()
      .offset(self.len as isize);

    ptr::write(end, value);
    let len = self.len;
    self.set_len(len + 1)
  }
}

Это снова та же проблема - мы знаем, что нам не нужно расти для первых итераций lower_size_bound (потому что мы уже предварительно распределили такое количество элементов), но мы все равно это делаем. Кроме того, мы усложняем работу LLVM - он мог бы понять, что, поскольку мы устанавливаем self.capacity, а затем проверяем его на self.len на каждой итерации цикла, он может разделить цикл на две части и опустить проверку для первого self. .capacity - итерации self.len, а затем выясняют, что записи могут быть векторизованы, но опять же, полагаясь на определенный набор оптимизаций в определенном порядке. Кроме того, мы сохраняем в self.len каждую итерацию цикла, и хотя LLVM может загружать self.len в регистр, увеличивать его там, а затем сохранять его снова, это не достаточно простая оптимизация, чтобы мы могли ожидать, что она будет надежно выполненный. Кроме того, эта оптимизация не может быть выполнена для итератора, который может вызвать панику, поскольку в этом случае нам нужно убедиться, что self.len верен после каждой итерации цикла. Это связано с тем, что другой код мог наблюдать это после паники (даже без catch_panic код в реализациях Drop::drop мог наблюдать это). Мы можем провести эту оптимизацию самостоятельно и сделать код более понятным для LLVM: 

fn extend<I>(&mut self, iterable: I)
where
  I: IntoIterator<Item=A::Item>
{
  let mut iter = iterable.into_iter();
  let (lower_size_bound, _) = iter.size_hint();

  let target_len = self.len + lower_size_bound;

  if target_len > self.capacity() {
    self.grow(target_len);
  }

  // This section is new
  unsafe {
    let ptr = self.as_mut_ptr()
      .offset(self.len() as isize);

    let len = self.len();
    let mut count = 0;
    for p in 0..lower_size_bound as isize {
      if let Some(out) = iter.next() {
        ::std::ptr::write(ptr.offset(p), out);
        count += 1;
      } else {
        break;
      }
    }

    self.set_len(len + count);
  }

  for elem in iter {
    self.push(elem);
  }
}

Вы видите, что на быстром пути (путь, где iter.size_hint() говорит правду) мы просто непрерывно ptr::write. Мы выполняем переход в цикле, но для большинства итераторов ветвь может быть легко удалена компилятором после мономорфизации - например, для срезов, векторов и оберток вокруг любого из тех, которые сохраняют size_hint. Для тех, где это не так, ветвь else берется не более одного раза за запуск цикла. Это делает его чрезвычайно предсказуемым даже для процессоров с базовыми предикторами ветвления. Затем мы выполняем «реальное» сохранение в поле len только один раз, и счетчик может быть легко помещен в регистр. Эту оптимизацию не может остановить итератор, который может вызвать панику. Поскольку мы сохраняем в памяти только после цикла, в случае паники во время цикла вызывающий код просто увидит значение self.len до того, как мы вошли в цикл. Мы можем выполнить это преобразование, потому что знаем, что утечка данных при панике - это нормально, но LLVM не может, потому что это изменит смысл программы3.

Мы видим, что разница после этой оптимизации большая:

namesmallvec.bench ns/itervec.bench ns/iterdiff ns/iterdiff %speedup
extend10270-32-31.37%x 1.46
extend_small2528312.00%x 0.89

Мы намного ближе к скорости Vec, чем раньше, и, наконец, SmallVec стал быстрее в том случае, когда ему не нужно выделять ресурсы.

Я думаю, что важные выводы из этого заключаются в следующем: вам не нужно выполнять каждую оптимизацию самостоятельно, но вы должны сделать свой код как можно более простым и оптимизируемым. Однако необходимо вручную выполнять любые оптимизации, которые изменяют смысл вашей программы. Даже если кажется, что оптимизация дала небольшой эффект, если вы не можете ожидать, что компилятор выполнит ее, я думаю, что стоит попробовать. Вполне возможно, что это может открыть больше возможностей для оптимизации компилятора. Однако, прежде всего, важно провести сравнительный анализ ваших оптимизаций. Вы не ожидаете, что ваш код будет правильным, если не протестируете его (даже если это тестирование заключается в запуске программы и щелчке мышью), так почему вы ожидаете, что ваш код будет быстрым, если вы не будете тестировать его. SmallVec фактически не имел сравнений с Vec в своем наборе тестов, пока я не написал некоторые из них для целей этой статьи. Есть много крэйтов, которые в настоящее время используют smallvec - crates.io перечисляет 9 страниц крэйтов, использующих его на момент написания. Если вы используете smallvec для повышения производительности, лучше протестировать вашу программу, используя Vec с Vec::with_capacity. Обычно более простая реализация оказывается более быстрой.

Чтобы тесты были честными, я предварительно выделил вектору то же количество элементов, которое SmallVec предварительно выделил в стеке (16). Я считаю, что это справедливо, потому что в реальной программе вы всегда можете легко заменить вызовы Vec::new на Vec::with_capacity (N), где N - это число, которое вы бы поместили в SmallVec::<[T; N]>::новый. Чтобы увидеть точную методологию, вы можете увидеть этот коммит.︎

Во время написания статьи я понял, что эта функция на самом деле не работает. Одна интересная особенность написания небезопасного Rust заключается в том, что безопасному коду нельзя доверять. Вы можете использовать значения из безопасного кода в качестве подсказок, но должно быть невозможно вызвать несостоятельность, вернув неверные значения из безопасного кода. Это означает, например, что Iterator::size_hint может возвращать практически все, что захочет. Кроме того, безопасный код должен иметь возможность паниковать в любой момент, не вызывая несостоятельности (хотя в противном случае разрешено вызывать произвольно плохое поведение, например бесконечные циклы или утечку данных). В этом суть вы можете увидеть визуальное объяснение этой ошибки. На момент написания он все еще не исправлен, но я открыл проблему, по которой вы можете отслеживать ее прогресс.︎

На самом деле LLVM может выполнить приращение в регистре и просто добавить код для фактического сохранения длины в коде аварийной очистки. На самом деле Vec делает это явно с помощью структуры SetLenOnDrop. Опять же, это сложная оптимизация, и вы не можете полагаться на ее применение с помощью LLVM.︎