В этой статье мы рассмотрим классический конкурентный кольцевой буфер и обсудим, как его можно оптимизировать для повышения производительности. Я покажу вам, как существенно улучшить этот показатель от 5,5 миллионов элементов в секунду до 112 миллионов элементов в секунду — и эти показатели выше, чем в реализациях Boost и Folly. Если вам требуется готовая реализация со всеми этими оптимизациями, посмотрите мою библиотеку SPSCQueue.h.

Кольцевой буфер также называется очередью «один производитель — один потребитель» (SPSC). В ней не бывает ожидания (и, соответственно, не бывает блокировок), это конкурентный примитив. Такая структура данных находит множество вариантов применения, и здесь я рассмотрю передачу сетевых пакетов между сетевым контроллером и драйверами операционной системы. Основная задача, решаемая при этом — выполнение событий ввода/вывода в относительно новом асинхронном API io_uring.

❯ Классический кольцевой буфер

Сначала давайте реализуем простой кольцевой буфер. В C++ его можно определить примерно так:

struct ringbuffer {
  std::vector<int> data_;
  alignas(64) std::atomic<size_t> readIdx_{0};
  alignas(64) std::atomic<size_t> writeIdx_{0};

  ringbuffer(size_t capacity) : data_(capacity, 0) {}
}

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

Также важно отметить, что индексы чтения (readIdx_) и записи (writeIdx_) выравниваются по размеру кэш-линии (alignas(64)). Это делается для уменьшения трафика, связанного с обеспечением когерентности кэша. На AMD64 / x86_64 и ARM размер кэш-линии составляет 64 байта, на других ЦП вам придётся самостоятельно подбирать подходящее выравнивание. Пользуйтесь для этого std::hardware_destructive_interference_size, если есть такая возможность. Может быть интересно подобрать такой вариант выравнивания, который удовлетворял бы сразу нескольким длинам кэш-линий — это пригодится на случай предвыборки смежных линий.

Ситуация сильно напоминает определение собственного кольцевого буфера io_uring в ядре Linux:

struct io_uring {
  u32 head ____cacheline_aligned_in_smp;
  u32 tail ____cacheline_aligned_in_smp;
};

boost::lockfree::spsc также определяет кольцевой буфер примерно таким же образом.

Теперь можно реализовать операцию проталкивания в стек (или записи):

bool push(int val) {
  auto const writeIdx = writeIdx_.load(std::memory_order_relaxed);
  auto nextWriteIdx = writeIdx + 1;
  if (nextWriteIdx == data_.size()) {
    nextWriteIdx = 0;
  }
  if (nextWriteIdx == readIdx_.load(std::memory_order_acquire)) {
    return false;
  }
  data_[writeIdx] = val;
  writeIdx_.store(nextWriteIdx, std::memory_order_release);
  return true;
}

Обратите внимание: один элемент остался неиспользуемым, тем самым мы отмечаем, что очередь полна. Когда writeIdx_ на один элемент отстаёт от readIdx_, очередь точно полна.

Далее реализуем операцию выталкивания из стека (чтения):

bool pop(int &val) {
  auto const readIdx = readIdx_.load(std::memory_order_relaxed);
  if (readIdx == writeIdx_.load(std::memory_order_acquire)) {
    return false;
  }
  val = data_[readIdx];
  auto nextReadIdx = readIdx + 1;
  if (nextReadIdx == data_.size()) {
    nextReadIdx = 0;
  }
  readIdx_.store(nextReadIdx, std::memory_order_release);
  return true;
}

Опять же, отметим: readIdx_ == writeIdx_ означает, что очередь пуста.

Я специально подобрал для элемента очень небольшой размер (sizeof(int) == 4), поскольку при работе с более крупными элементами память будет тратиться в основном на их копирование, а мы не стремимся здесь измерить производительность memcpy(). Разумеется, это также означает, что, если вам приходится оперировать сравнительно крупными элементами, то вы особенно не выиграете от оптимизации кольцевого буфера.

Теперь давайте проанализируем производительность этой очереди. Я написал простой бенчмарк ringbuffer.cpp, проталкивающий 100M элементов между 2 потоками через кольцевой буфер размером 100k. Мы измеряем, сколько времени уйдёт у читающего потока на обработку всех элементов. Скомпилируем ringbuffer.cpp следующим образом:

 g++ -Wall -O3 -march=native -std=c++20 ringbuffer.cpp

Я выполнил эту операцию на 12-ядерном процессоре AMD Ryzen 9 3900X, разместив два потока на разных чиплетах/ядерных комплексах (CCX):

$ perf stat -e cache-misses,cache-references,l2_request_g1.change_to_x ./a.out 1 11
5513850 ops/s

 Performance counter stats for './a.out 1 11':

       349,857,603      cache-misses:u            #   91.228 % of all cache refs    
       383,497,078      cache-references:u                                          
         6,673,242      l2_request_g1.change_to_x:u                                   

      18.137421039 seconds time elapsed

      36.140630000 seconds user
       0.002986000 seconds sys

Как видите, здесь достигнута пропускная способность 5.5M элементов в секунду. Вполне согласуется с данными о производительности таких библиотек как boost::lockfree::spsc и folly::ProducerConsumerQueue. Количество промахов кэша (~300M) кажется пропорциональным (трёхкратным) количеству обработанных нами элементов (100M).

❯ Оптимизированный кольцевой буфер

Почему у нас получается по 3 кэш-промаха на каждую пару операций чтения и записи? Рассмотрим операцию чтения: требуется обновить индекс чтения и, следовательно, кэш-линия загружается в кэш L1 в исключительном состоянии (см. протокол MESI). Индекс записи нужно читать по порядку, чтобы убедиться, что очередь не пуста. Поэтому данный индекс загружается в кэш L1 в разделяемом состоянии. Поскольку при операции записи в очередь требуется читать индекс операций чтения, линия этого индекса должна быть вытеснена из кэша или перейти в разделяемое состояние. Теперь при операции чтения нам потребуется потратить часть трафика на обеспечение когерентности кэша, чтобы кэш-линия индекса чтения вернулась в исключительное состояние. В свою очередь, придётся дополнительно обеспечивать когерентность кэша и для операции записи, чтобы кэш-линия индекса записи вернулась в исключительное состояние. В худшем случае получится по одному переходу на новую кэш-линию при изменении состояния с исключительного на разделяемое и обратно. Именно такие смены состояния и учитываются как промахи кэша. Точные детали реализации протокола когерентности кэша неизвестны, но в целом мы работаем примерно по протоколу MESI.

Чтобы сократить этот трафик, затрачиваемый на обеспечение когерентности, читающий и записывающий потоки могут хранить по одной кэшированной копии индекса записи и индекса чтения соответственно. В таком случае, как только читающий заметит, что доступно N элементов для чтения, он кэширует эту информацию, и поэтому при N-1 последующих операциях чтения не требуется обращаться к индексу записи. Аналогично, как только записывающий заметит, что доступно N элементов для записи, он кэширует эту информацию, и поэтому при N-1 последующих операциях записи не требуется обращаться к индексу чтения.

Новый кольцевой буфер будет определяться так:

struct ringbuffer2 {
  std::vector<int> data_{};
  alignas(64) std::atomic<size_t> readIdx_{0};
  alignas(64) size_t writeIdxCached_{0};
  alignas(64) std::atomic<size_t> writeIdx_{0};
  alignas(64) size_t readIdxCached_{0};

  ringbuffer2(size_t capacity) : data_(capacity, 0) {}
}

Операция проталкивания обновляется так, чтобы код сначала сверился с кэшированным индексом чтения (readIdxCached_) и, если она не удастся, попытался повторить её после того, как обновит кэш:

if (nextWriteIdx == readIdxCached_) {
  readIdxCached_ = readIdx_.load(std::memory_order_acquire);
  if (nextWriteIdx == readIdxCached_) {
    return false;
  }
}

Операция выталкивания обновляется схожим образом: сначала код сверяется с кэшированным индексом записи (writeIdxCached_):

if (readIdx == writeIdxCached_) {
  writeIdxCached_ = writeIdx_.load(std::memory_order_acquire);
  if (readIdx == writeIdxCached_) {
    return false;
  }
}

Вот что получится, если повторно прогнать тот же самый бенчмарк с новой реализацией кольцевого буфера:

$ perf stat -e cache-misses,cache-references,l2_request_g1.change_to_x ./a.out 1 11
112287037 ops/s

 Performance counter stats for './a.out 1 11':

        15,010,392      cache-misses:u            #   32.553 % of all cache refs    
        46,110,663      cache-references:u                                          
         6,781,273      l2_request_g1.change_to_x:u                                   

       0.892256380 seconds time elapsed

       1.775185000 seconds user
       0.000996000 seconds sys

Просто супер! Теперь пропускная способность составляет 112M элементов в секунду, а количество промахов кэша существенно сократилось. Если хотите убедиться в этом сами — посмотрите файл ringbuffer.cpp.

❯ Дальнейшие оптимизации

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

При использовании огромных страниц памяти в кольцевом буфере, можно сократить количество TLB-промахов, то есть, непопаданий при работе с буфером ассоциативной трансляции (TLB).

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩

📚 Читайте также:

• ➤ Linux: долгий путь к ленивому вытеснению

• ➤ Новогодняя гирлянда любителя транспорта

• ➤ Артефакт из прошлого на службе настоящего или как я подключал радиолампу к «Умному дому»

• ➤ JavaScript: структуры данных и алгоритмы

• ➤ Бегущий по флешбэкам