OutOfLine – паттерн размещения в памяти для высокопроизводительных приложений на C++

в 5:48, , рубрики: c++, высокая производительность

Во время работы в Headlands Technologies мне посчастливилось написать несколько утилит для упрощения создания высокопроизводительного кода на C++. Эта статья предлагает обобщенный обзор одной из этих утилит — OutOfLine.

Начнём с поясняющего примера. Предположим, у вас есть система, которая имеет дело с большим количеством объектов файловой системы. Это могут быть обыкновенные файлы, именованные UNIX сокеты или пайпы. По какой-то причине вы открываете много файловых дескрипторов при старте, затем интенсивно с ними работаете, а в конце закрываете дескрипторы и удаляете ссылки на файлы (прим. пер. имеется в виду функция unlink).

Первоначальный (упрощённый) вариант может выглядеть так:

class UnlinkingFD {
  std::string path;
 public:
  int fd;

  UnlinkingFD(const std::string& p) : path(p) {
    fd = open(p.c_str(), O_RDWR, 0);
  }
  ~UnlinkingFD() { close(fd); unlink(path.c_str()); }
  UnlinkingFD(const UnlinkingFD&) = delete;
};

И это хороший, логически обоснованный дизайн. Он полагается на RAII для автоматического освобождения дескриптора и удаления ссылки. Можно создать большой массив таких объектов, поработать с ними, а когда массив прекратит существование, объекты сами очистят все, что было нужно в процессе работы.

Но что насчёт производительности? Предположим, fd используется очень часто, а path только при удалении объекта. Сейчас массив состоит из объектов размером 40 байт, но часто используются только 4 байта. Значит, будет больше промахов в кеше, поскольку нужно "пропускать" 90% данных.

Одним из частых решений такой проблемы является переход от массива структур к структуре массивов. Это обеспечит желаемую производительность, но ценой отказа от RAII. Есть ли вариант, сочетающий преимущества обоих подходов?

Простым компромиссом может быть замена std::string размером 32 байта на std::unique_ptr<std::string>, размер которого только 8 байт. Это позволит уменьшить размер нашего объекта с 40 байт до 16 байт, что является большим достижением. Но это решение по прежнему проигрывает использованию нескольких массивов.

OutOfLine — это инструмент позволяющий без отказа от RAII полностью переместить редко используемые (cold) поля вовне объекта. OutOfLine используется в качестве CRTP базового класса, поэтому первым аргументом шаблона должен быть дочерний класс. Второй аргумент — тип редко используемых (холодных) данных, которые связаны с часто используемым (основным) объектом.

struct UnlinkingFD : private OutOfLine<UnlinkingFD, std::string> {
  int fd;

  UnlinkingFD(const std::string& p) : OutOfLine<UnlinkingFD, std::string>(p) {
    fd = open(p.c_str(), O_RDWR, 0);
  }
  ~UnlinkingFD();
  UnlinkingFD(const UnlinkingFD&) = delete;
};

Так что же из себя представляет этот класс?

template <class FastData, class ColdData>
class OutOfLine {

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

  inline static std::map<OutOfLine const*, std::unique_ptr<ColdData>> global_map_;

OutOfLine может быть использован с любым типом холодных данных, экземпляр которых создается и связывается с основным объектом автоматически.

  template <class... TArgs>
  explicit OutOfLine(TArgs&&... args) {
    global_map_[this] = std::make_unique<ColdData>(std::forward<TArgs>(args)...);
  }

Удаление основного объекта влечет автоматическое удаление связанного холодного объекта:

  ~OutOfLine() { global_map_.erase(this); }

При перемещении (move constructor/move assignment operator) основного объекта, соответствующий ему холодный объект будет автоматически связан с новым основным объектом-преемником. Как следствие, не следует обращаться к холодным данным перемещённого (moved-from) объекта.

  explicit OutOfLine(OutOfLine&& other) { *this = other; }
  OutOfLine& operator=(OutOfLine&& other) {
    global_map_[this] = std::move(global_map_[&other]);
    return *this;
  }

В приведенном примере реализации OutOfLine сделан некопируемым для простоты. При необходимости операции копирования легко добавить, в них достаточно лишь создать и связать копию холодного объекта.


  OutOfLine(OutOfLine const&) = delete;
  OutOfLine& operator=(OutOfLine const&) = delete;

Теперь, чтобы это было действительно полезно, хорошо бы иметь доступ к холодным данным. При наследовании от OutOfLine класс получает константный и неконстантный методы cold():

  ColdData& cold() noexcept { return *global_map_[this]; }
  ColdData const& cold() const noexcept { return *global_map_[this]; }

Они возвращают соответствующий тип ссылки на холодные данные.

Вот почти и все. Такой вариант UnlinkingFD будет иметь размер 4 байта, предоставит дружественный по отношению к кешу доступ к полю fd и сохранит преимущества RAII. Вся работа, связанная с жизненным циклом объекта, полностью автоматизирована. Когда основной часто используемый объект перемещается, редко используемые холодные данные перемещаются вместе с ним. Когда основной объект удаляется, удаляется и соответствующий ему холодный объект.

Иногда, однако, ваши данные сговариваются, чтобы усложнить вам жизнь — и вы сталкиваетесь с ситуацией в которой основные данные должны быть созданы первыми. Например, они нужны для конструирования холодных данных. Появляется необходимость создавать объекты в обратном порядке относительного того, что предлагает OutOfLine. Для таких случаев нам пригодится "запасной ход" для контроля порядка инициализации и деинициализации.

  struct TwoPhaseInit {};
  OutOfLine(TwoPhaseInit){}
  template <class... TArgs>
  void init_cold_data(TArgs&&... args) {
    global_map_.find(this)->second = std::make_unique<ColdData>(std::forward<TArgs>(args)...);
  }
  void release_cold_data() { global_map_[this].reset(); }

Это ещё один конструктор OutOfLine, который можно использовать в дочерних классах, он принимает тег типа TwoPhaseInit. Если создать OutOfLine таким образом, то холодные данные не будут инициализированы, а объект останется наполовину сконструированным. Для завершения двухфазного конструирования нужно вызвать метод init_cold_data (передав в него аргументы необходимые для создания объекта типа ColdData). Помните, что нельзя вызывать .cold() у объекта, холодные данные которого еще не инициализированы. По аналогии, холодные данные можно удалить досрочно, до выполнения деструктора ~OutOfLine, вызвав release_cold_data.

}; // end of class OutOfLine

Вот теперь все. Итак, что эти 29 строчек кода нам дают? Они представляют собой ещё один возможный компромисс между производительностью и простотой использования. В случаях когда у вас есть объект, часть членов которого используется значительно чаще других, OutOfLine может послужить легким в эксплуатации способом оптимизации кеша, ценой значительного замедления доступа к редко используемым данным.

Мы смогли применить эту технику в нескольких местах — довольно часто возникает потребность дополнить интенсивно используемые рабочие данные дополнительными метаданными, которые необходимы при завершении работы, в редких или неожиданных ситуациях. Будь то информация о пользователях установивших соединение, торговом терминале с которого пришел заказ, или дескриптор аппаратного ускорителя, занятого обработкой биржевых данных — OutOfLine сохранит кеш чистым, когда вы находитесь в критической части вычислений (critical path).

Я подготовил тест, чтобы вы могли увидеть и оценить разницу.

Сценарий Время (нс)
Холодные данные в основном объекте (первоначальный вариант) 34684547
Холодных данные полностью удалены (лучший сценарий ) 2938327
С использованием OutOfLine 2947645

Я получил примерно 10-ти кратное ускорение при использовании OutOfLine. Очевидно, что этот тест разработан для демонстрации потенциала OutOfLine, однако он также показывает насколько существенное влияние на производительность способна оказать оптимизация кеша, равно как и то, что OutOfLine позволяет эту оптимизацию получить. Поддержание кеша свободным от редко используемых данных может обеспечить сложно измеряемое комплексное улучшение показателей остального кода. Как и всегда при оптимизации, доверяйте измерениям больше чем предположениям, тем не менее надеюсь что OutOfLine окажется полезным инструментом в вашей копилке утилит.

Автор: Hokum

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js