Кольцевой буфер (ring buffer) — это структура данных фиксированной длины, за последним элементом которой следует первый.

Однажды у меня возникла потребность в кольцевом буфере на C++ для хранения довольно объёмных потоковых данных. Проблема заключалась в том, что мне было необходимо поддерживать непрерывность и упорядоченность данных в памяти, чтобы в любой момент времени я мог считать все элементы буфера одним бесшовным куском в порядке поступления элементов. И сделать это быстро.

Итоговая реализация доступна на гитхабе.

В области computer vision, где я работаю, приходится иметь дело с большими матрицами, вес которых исчисляется сотнями килобайт или даже мегабайтами. Моя задача — хранить в буфере историю последних поступивших матриц размерности , например . Новые матрицы потоком поступают в буфер с определенной периодичностью. С той же периодичностью уходят старые матрицы, сохраняя свежесть всей серии. Эта серия в любой момент времени, который заранее неизвестен, должна быть подана единым тензором на вход рекуррентной нейросетке, которая будет искать временны́е закономерности в этой серии. Для неё важно не нарушать порядок следования элементов, который соответствует времени вставки элемента в буфер. Очевидно, что любые манипуляции с матрицами такого размера обойдутся дорого, как по памяти, так и по вычислительным ресурсам, и нужно искать способы сокращать расходы на любые манипуляции с буфером.

Как правило, кольцевой буфер реализуется одним из двух способов. Либо на базе списков, вроде std::list или std::deque, с чередующимися push-pop, либо через непрерывные плоские массивы, вроде std::vector или boost::circular_buffer, где индекс для вставки нового элемента рассчитывается как [head++ % capacity].

Схема списочного кольцевого буфера
                       ___       ___       ___       ___       ___       ___ 
    Итерация i:       | 0 | --> | 1 | --> | 2 | --> | 3 | --> | 4 | --> | 5 |
                       ‾‾‾       ‾‾‾       ‾‾‾       ‾‾‾       ‾‾‾       ‾‾‾ 
                       ___       ___       ___       ___       ___       ___ 
    Итерация i+1:     | 1 | --> | 2 | --> | 3 | --> | 4 | --> | 5 | --> | 6 |
                       ‾‾‾       ‾‾‾       ‾‾‾       ‾‾‾       ‾‾‾       ‾‾‾ 
                       ___       ___       ___       ___       ___       ___ 
    Итерация i+2:     | 2 | --> | 3 | --> | 4 | --> | 5 | --> | 6 | --> | 7 |
                       ‾‾‾       ‾‾‾       ‾‾‾       ‾‾‾       ‾‾‾       ‾‾‾ 

Схема плоского кольцевого буфера

                       ___ ___ ___ ___ ___ ___ 
    Итерация i:       | 0 | 1 | 2 | 3 | 4 | 5 |
                       ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ 
                                              ^
                                             head

                       ___ ___ ___ ___ ___ ___ 
    Итерация i+1:     | 6 | 1 | 2 | 3 | 4 | 5 |
                       ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ 
                          ^
                         head

                       ___ ___ ___ ___ ___ ___ 
    Итерация i+2:     | 6 | 7 | 2 | 3 | 4 | 5 |
                       ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ 
                              ^
                             head

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

Реализация на базе плоских массивов, с другой стороны, не требует перевыделения памяти, так как новый элемент может быть записан на месте старого. Но такая перезапись создаёт «шов», нарушающий порядок записи элементов при чтении всего буфера. Для поддержания порядка записи требуется удвоение объема буфера и двойная вставка элемента в первую и вторую часть буфера по индексам [i] и [i+M], соответственно.

Схема плоского кольцевого буфера с избыточным копированием

                        ___ ___ ___ ___ ___ ___|___ ___ ___ ___ ___ ___ 
    Итерация i:        | 0 | 1 | 2 | 3 | 4 | 5 | 0 | 1 | 2 | 3 | 4 | 5 |
                        ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ 
                                               ^
                                              head

                        ___ ___ ___ ___ ___ ___|___ ___ ___ ___ ___ ___ 
    Итерация i+1:      | 6 | 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | 4 | 5 |
                        ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ 
                           ^                     ^
                          head                 копия

                        ___ ___ ___ ___ ___ ___|___ ___ ___ ___ ___ ___ 
    Итерация i+2:      | 6 | 7 | 2 | 3 | 4 | 5 | 6 | 7 | 2 | 3 | 4 | 5 |
                        ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ ‾‾‾ 
                               ^                     ^
                              head                 копия

Альтернативу копированию предлагает функцияboost::circular_buffer::linearize(), которая разрезает буфер на две части по шву, приставляя конец одной части к началу другой, таким образом превращая массив в монотонный. Но с точки зрения вычислений это равносильно двойной вставке, так как мы проделываем ту же работу, только не для одного элемента при каждой вставке, а для всего массива по запросу.

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

И тут я вспомнил про концепт виртуальной памяти. Как известно, каждый процесс в современных ОС работает со своим пространством виртуальных адресов. И указатель в программе указывает не на адреса физических ячеек, а на виртуальные адреса, которые транслируются MMU-чипом на физические. Схема расположения физических адресов при этом не обязана совпадать с расположением адресов виртуальных. Я представил, что, по такой схеме можно выделить два виртуальных блока по байт, следующих друг за другом, которые будут транслироваться на общий физический блок. Это означает, что любые манипуляции с памятью первого виртуального блока автоматически отразятся на втором и наоборот. С точки зрения указателя, который может гулять по интервалу , от начала первого блока до конца второго, перепрыгнув на позицию , мы автоматически попадем в начало физического блока: т.е. выполнится условие buf[i] == buf[i+N], где . Таким образом, можно вставлять новые элементы по индексу buf[head++ % capacity] и читать весь массив целиком в любой момент, начиная с buf[head], так как вставленный элемент по индексу [i] автоматически «отзеркалится» в [i+N].

               0                         N                        2N
               |_________________________|_________________________|
               | Первый виртуальный блок | Второй виртуальный блок |
                ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾ ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
                                     \       /
                                      \     /
                                       \   /
                                 _________________
                                | Физический блок |
                                |‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾|
                                0                 N

Внутрянка работы с виртуальной памятью подробно раскрыта в главе Virtual Memory из книги Bryant, Randal E., and David R. O'Hallaron. Computer Systems: A Programmer's Perspective.

Реализация

Позволяет ли C++ реализовать такое на практике? Да, этот трюк уже был проделан (один, два, три) и известен как магический кольцевой буфер.

Сразу скажу, что у такой реализации есть серьезный недостаток — виртуальная память выделяется не байтами, а страницами. Обычно страница занимает 4КБ на x86-64. Это означает, что объем буфера не может быть произвольным, а всегда должен быть кратен размеру страницы (4КБ, 52КБ, 16МБ и и.д.). Для моей задачи это не критично, поскольку самые ходовые размеры матриц кратны размеру страницы. Ещё одна трудность в том, что ручные манипуляции с виртуальной памятью доступны на уровне платформы, а не на уровне стандартной библиотеки. Поэтому для каждой операционки нужно писать свою реализацию буфера. Далее я расскажу про реализации на Linux и Windows.

Приведенные ниже фрагменты кода упрощены для демонстрации. Полная и протестированная реализация доступна в репозитории. В моём рабочем проекте только один поток работает с буфером, поэтому тема thread-safety не поднимается.

Схема для Linux

1. Создать анонимный файл объёма — кусочек будущей оперативной памяти, не имеющей привязки к диску. Физическая память на этом этапе не выделяется;

2. Застолбить виртуальную подложку (base) объёма — ещё не привязанную к физической памяти область виртуальной памяти для хранения двух будущих виртуальных блоков. Очередность выполнения шагов 1 и 2 не играет роли, так как подложка не привязана к анонимному файлу;

3. Разбить подложку на две части, разместив в каждой по виртуальному блоку по адресам &base[0] и &base[N], соответственно. В отличие от самой подложки, эти блоки специальными флагами привязываются к общей физической памяти через анонимный файл. С этого момента можно работать с памятью через указатель base как с обычным указателем.

#include <sys/mman.h>
#include <unistd.h>

void* magicAlloc(size_t size)
{
  // Создать анонимный файл
  int fileDesc = memfd_create("ring_buffer_tempfile", MFD_CLOEXEC);
  ftruncate(fileDesc, size);
  
  // Застолбить виртуальную подложку
  void* base = mmap(
      NULL, 2*size, // Система сама подберет адрес требуемого размера под два будущих блока
      PROT_NONE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); // Создать блок в приватной области памяти, без доступа. 
                                                      // Доступ будет дан двум будущим блокам
  
  // Разместить два виртуальных блока на подложке
  void* leftPage = mmap(
      base, size,                           // Адрес и размер блока
      PROT_READ | PROT_WRITE,               // Права доступа к блоку
      MAP_SHARED | MAP_FIXED, fileDesc, 0); // Привязать анонимный файл к блоку по указанному адресу
  void* rightPage = mmap(
      static_cast<char*>(base) + size, size, // Адрес и размер блока
      PROT_READ | PROT_WRITE,                // Права доступа к блоку
      MAP_SHARED | MAP_FIXED, fileDesc, 0);  // Привязать анонимный файл к блоку по указанному адресу

  return leftPage;
}

В старых релизах (до Linux 3.17) вместо анонимного файла используется область памяти, сопоставляемая с обычным файлом на диске. Я добавил и такую возможность в коде для старых релизов.

Схема для Windows

Принцип тот же, но со своей спецификой. На винде есть понятие granularity — минимальной границы, по которой выравниваются резервируемые виртуальные адреса. Обычно это 64КБ.

1. Создать pagefile-backed секцию объёма — область памяти, привязанную к файлу подкачки, а не к файлу с диска. Это аналог линуксового анонимного файла;

2. Застолбить виртуальную подложку (base) объёма — ещё не привязанную к физической памяти область виртуальной памяти для хранения двух будущих виртуальных блоков. Очередность выполнения шагов 1 и 2 не играет роли, так как подложка не привязана к файлу подкачки;

3. Разбить подложку на два виртуальных блока по адресам &base[0] и &base[N], сопоставив каждую с pagefile-backed секцией. С этого момента можно работать с памятью через указатель base как с обычным указателем.

#include <windows.h>

typedef PVOID(WINAPI *PFN_VirtualAlloc2)(
    HANDLE Process, PVOID BaseAddress, SIZE_T Size, ULONG AllocationType, ULONG PageProtection, MEM_EXTENDED_PARAMETER *ExtendedParameters, ULONG ParameterCount
);

typedef PVOID(WINAPI *PFN_MapViewOfFile3)(
    HANDLE FileMapping, HANDLE Process, PVOID BaseAddress, ULONG64 Offset, SIZE_T ViewSize, ULONG AllocationType, ULONG PageProtection, MEM_EXTENDED_PARAMETER *ExtendedParameters, ULONG ParameterCount
);

PFN_VirtualAlloc2 getVirtualAlloc2(void) {
    HMODULE hMod = GetModuleHandleA("kernelbase.dll");
    if (!hMod) return NULL;
    return (PFN_VirtualAlloc2)GetProcAddress(hMod, "VirtualAlloc2");
}

PFN_MapViewOfFile3 getMapViewOfFile3(void) {
    HMODULE hMod = GetModuleHandleA("kernelbase.dll");
    if (!hMod) return NULL;
    return (PFN_MapViewOfFile3)GetProcAddress(hMod, "MapViewOfFile3");
}

void* magicAlloc(size_t size)
{
  PFN_VirtualAlloc2 pVirtualAlloc2 = getVirtualAlloc2();
  PFN_MapViewOfFile3 pMapViewOfFile3 = getMapViewOfFile3();

  // Создать pagefile-backed секцию
  HANDLE fileDesc = CreateFileMappingW(
      INVALID_HANDLE_VALUE,   // Файл подкачки
      NULL,                   // Защита по умолчанию
      PAGE_READWRITE,         // Доступ на чтение/запись
      0, size,                // Размер
      NULL);
  
  // Застолбить виртуальную подложку
  void* base = pVirtualAlloc2(
      NULL,                                                 // Текущий процесс
      NULL,                                                 // Система сама подберет адрес, выровненный по granularity
      2*size,                                               // Объем
      MEM_RESERVE | MEM_RESERVE_PLACEHOLDER, PAGE_NOACCESS, // Тип: плейсхолдер
      NULL, 0);
  VirtualFree(base, size, MEM_RELEASE | MEM_PRESERVE_PLACEHOLDER);
  
  // Разместить два виртуальных блока на подложке
  void* leftPage = pMapViewOfFile3(
      fileDesc, NULL,                                    // Файл подкачки, текущий процесс
      base, 0, size,                                     // Адрес и размер блока
      MEM_REPLACE_PLACEHOLDER, PAGE_READWRITE, NULL, 0); // Заполнить подложку, отобразить блок в файл подкачки
  void* rightPage = pMapViewOfFile3(
      fileDesc, NULL,                                         // Файл подкачки, текущий процесс
      (void*)(reinterpret_cast<char*>(base) + size), 0, size, // Адрес и размер блока
      MEM_REPLACE_PLACEHOLDER, PAGE_READWRITE, NULL, 0);      // Заполнить подложку, отобразить блок в файл подкачки

  return leftPage;
}

RingBuffer

Итак, «магическая» память выделена. Следующим шагом можно написать свой контейнер для удобной работы с элементами либо свой аллокатор для контейнеров из стандартной библиотеки.

Обычно под кольцевой буфер пишется push-pop интерфейс для создания и чтения объектов из памяти. Но я работаю не с обычными объектами, а с объектами-вьюшками, которые создаются отдельно от данных, на которые они указывают. Конкретно я использую объект cv::Mat библиотеки OpenCV для работы с матрицами, которому можно явно указать адрес, по которому хранятся данные. Аналогия со std::string_view. Буфер нужен мне для хранения сырых данных без заголовка cv::Mat.

#include <string.h>

class RingBuffer
{
public:
  RingBuffer(size_t capacity, size_t elemSize)
    : m_capacity(capacity), m_elemSize(elemSize)
  {
    m_base = magicAlloc(capacity*elemSize);
    m_head = m_base;
  }

  void* seek();

  void put(const void*);

  template<typename T> T element(size_t) const;

  size_t capacity() const {return m_capacity;}

private:
  void*  m_base;        // Указатель на начало памяти
  void*  m_head;        // Указатель на вакантный элемент
  size_t m_capacity;    // количество элементов в буфере (в единицах)
  size_t m_elemSize;    // размер элемента (в байтах)
  size_t m_size {0};    // Текущее число элементов
  size_t m_headIdx {0}; // Индекс вакантного элемента
};

От буфера требуется подкинуть вакантный адрес, по которому должны быть расположены данные очередного cv::Mat. Посколько я храню матрицы одинакового размера, то рассчитать следующий вакантный адрес не составляет труда.

#define MIN(a, b) (((a) < (b)) ? (a) : (b))

void* RingBuffer::seek()
{
  void* prevHead = m_head;
  m_headIdx = (m_headIdx + 1) % m_capacity;
  m_head = (char*)m_base + m_headIdx*m_elemSize;
  m_size = MIN(m_size + 1, m_capacity);
  return prevHead;
}

Второй вариант записи — явное копирование элемента в буфер для записи тривиально копируемых объектов.

void RingBuffer::put(const void* src)
{
  memcpy(m_head, src, m_elemSize);

  m_headIdx = (m_headIdx + 1) % m_capacity;
  m_head = (char*)m_base + m_headIdx*m_elemSize;
  m_size = MIN(m_size + 1, m_capacity);
}

Получить указатель на уже записанную i-й матрицу можно методом element(i).

template<typename T = void*>
T RingBuffer::element(size_t idx) const
{
  idx = (m_headIdx - m_size + idx) % m_capacity;
  return reinterpret_cast<T>((char*)m_base + idx*m_elemSize);
}

Используя этот метод можно создать заголовок cv::Mat({H,W,F}, CV_32F, ring.element(i)). Аналогично можно создать заголовок над всем буфером cv::Mat({M,H,W,F}, CV_32F, ring.element(0)). В обоих случаях массив остаётся непрерывным и никакой перегруппировки элементов не происходит.

Пример программы для записи в буфер матриц, заполненных 0, 1, 2 и так далее и чтения из буфера как поматрично, так и единым тензором:

#include <opencv2/core.hpp>

int main()
{
    const size_t M = 4;
    const size_t H = 16;
    const size_t W = 16;
    const size_t F = 16;
    RingBuffer ring(M, H*W*F);

    auto sum = [](const cv::Mat& m) -> uint64_t {return cv::sum(m)[0];};

    // Запись матриц, заполненных 0, 1, 2, ...
    // Буфер прокручивается больше одного раза таким образом, что 
    // после цикла в буфере должны остаться 4 матрицы, заполненные 3, 4, 5, 6.

    for (cv::Scalar x : {0, 1, 2, 3, 4, 5, 6})
    {
        cv::Mat sample({H,W,F}, CV_8U, x); // Имитация входных данных, прилетающих извне
        ring.put(sample.data);
    }

    // Поэлементное чтение буфера

    for (int i = 0; i < ring.capacity(); ++i)
    {
        cv::Mat /* (view) */ sample({H,W,F}, CV_8U, ring.element(i));
        printf("%d-element sum: %lu\n", i, sum(sample)); // Сумма должна равняться (i + 3)*16*16*16
    }

    // Чтение буфера целиком

    cv::Mat /* (view) */ batch({M,H,W,F}, CV_8U, ring.element(0));
    printf("Total sum: %lu\n", sum(batch)); // Сумма должна равняться (3+4+5+6)*16*16*16

    return 0;
}

Программа выведет на консоль

0-element sum: 12288
1-element sum: 16384
2-element sum: 20480
3-element sum: 24576
Total sum: 73728

Производительность

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

Для этого я написал два теста, имитирующих работу реального буфера, которые выделяют память под буфер и заполняют его элементами. Первый тест (malloc-тест) имитирует работу плоского буфера с двойной вставкой. Он выделяет байт через malloc, затем, в цикле, размещает новый элемент по индексу i и копирует его во вторую часть буфера по индексу [i+N]. Второй тест (ring-тест) имитирует работу магического буфера. Он выделяет байт методом, описанным выше, и размещает новый элемент по индексу i. Элемент отзеркаливается во второй части буфера, поэтому копирования не требуется.

Запуск Valgrind на malloc-тесте показал ожидаемый расход памяти. Запуск на ring-тесте показал нулевой расход. Выяснилось, что Valgrind не отслеживает утечки на системных вызовах mmap/munmap, через которые мы выделяем и освобождаем магическую память. Пришлось добавить в код специальные макросы VALGRIND_MALLOCLIKE_BLOCK и VALGRIND_FREELIKE_BLOCK, помогающие отследить нестандартные аллокации в рантайме. После этого Valgrind стал показывать правильный расход, причем в обоих случаях расход одинаковый. Это логично, так как в обоих тестах мы запрашиваем у системы байт. Однако расход физической памяти на ring-тесте, очевидно, должен быть вдвое меньше. Проверить это можно утилитой pmap, которая раскрывет реальный расход памяти. Как и ожидалось, ring-тест израсходовал вдвое меньше физической памяти (колонка RSS на развёртке ниже).

> pmap -x 3786910
3786910:   ./perf_tests malloc write 1
Address           Kbytes     RSS   Dirty Mode  Mapping
...                  ...     ...     ...  ...  ...
00007fa49559a000   23060   23060   23060 rw---   [ anon ]
...                  ...     ...     ...  ...  ...
---------------- ------- ------- ------- 
total kB           29552   26224   23228

> pmap -x 3786963
3786963:   ./perf_tests ring write 1
Address           Kbytes     RSS   Dirty Mode  Mapping
...                  ...     ...     ...  ...  ...
00007f8846575000   11520   11520    7424 rw-s- ring_buffer_tempfile_VVvNQx (deleted)
...                  ...     ...     ...  ...  ...
---------------- ------- ------- ------- 
total kB           29548   15196    7608

Далее я решил замерить производительность. Для этого я разделил каждый тест на read- и write-случай для чтения из буфера и записи в буфер, соответственно. Поскольку в ring-тесте при записи в буфер мы не делаем дополнительного копирования, то ожидался прирост производительности относительно malloc-теста.

> perf stat --repeat=16 -dd ./perf_tests malloc write 1

 Performance counter stats for 'build/perf_tests malloc write 1' (16 runs):

            573,02 msec task-clock                #    1,001 CPUs utilized            ( +-  0,19% )
                60      context-switches          #  105,017 /sec                     ( +-  0,78% )
                 3      cpu-migrations            #    5,251 /sec                     ( +-  7,89% )
             5 887      page-faults               #   10,304 K/sec                    ( +-  0,01% )
     2 107 860 626      cycles                    #    3,689 GHz                      ( +-  0,21% )  (35,13%)
        67 479 515      stalled-cycles-frontend   #    3,22% frontend cycles idle     ( +-  1,29% )  (35,83%)
     1 615 186 984      stalled-cycles-backend    #   77,05% backend cycles idle      ( +-  1,09% )  (36,53%)
       399 114 333      instructions              #    0,19  insn per cycle         
                                                  #    4,22  stalled cycles per insn  ( +-  0,61% )  (37,23%)
        63 838 490      branches                  #  111,736 M/sec                    ( +-  0,23% )  (37,28%)
         2 191 172      branch-misses             #    3,46% of all branches          ( +-  1,53% )  (37,00%)
       402 000 712      L1-dcache-loads           #  703,616 M/sec                    ( +-  0,11% )  (36,29%)
        94 652 134      L1-dcache-load-misses     #   23,68% of all L1-dcache accesses  ( +-  0,19% )  (35,60%)
   <not supported>      LLC-loads                                                   
   <not supported>      LLC-load-misses                                             
         8 424 538      L1-icache-loads           #   14,745 M/sec                    ( +- 19,23% )  (34,90%)
           151 266      L1-icache-load-misses     #    1,25% of all L1-icache accesses  ( +-  0,68% )  (34,84%)
         1 565 211      dTLB-loads                #    2,740 M/sec                    ( +-  0,16% )  (34,84%)
         1 473 271      dTLB-load-misses          #   93,49% of all dTLB cache accesses  ( +-  0,22% )  (34,85%)
                 0      iTLB-loads                #    0,000 /sec                     (34,84%)
                14      iTLB-load-misses          #  101,82% of all iTLB cache accesses  ( +- 18,73% )  (34,84%)

           0,57261 +- 0,00113 seconds time elapsed  ( +-  0,20% )

> perf stat --repeat=16 -dd ./perf_tests ring write 1

 Performance counter stats for 'build/perf_tests ring write 1' (16 runs):

            281,55 msec task-clock                #    1,000 CPUs utilized            ( +-  0,22% )
                30      context-switches          #  106,896 /sec                     ( +-  1,05% )
                 1      cpu-migrations            #    3,563 /sec                     ( +- 29,89% )
             3 012      page-faults               #   10,732 K/sec                    ( +-  0,02% )
     1 035 848 873      cycles                    #    3,691 GHz                      ( +-  0,35% )  (36,15%)
        35 440 595      stalled-cycles-frontend   #    3,46% frontend cycles idle     ( +-  1,97% )  (36,15%)
       804 606 061      stalled-cycles-backend    #   78,48% backend cycles idle      ( +-  2,05% )  (36,15%)
       258 684 817      instructions              #    0,25  insn per cycle         
                                                  #    2,90  stalled cycles per insn  ( +-  0,99% )  (36,15%)
        46 744 057      branches                  #  166,558 M/sec                    ( +-  1,15% )  (36,12%)
         2 391 308      branch-misses             #    5,12% of all branches          ( +-  3,01% )  (35,47%)
       210 746 186      L1-dcache-loads           #  750,928 M/sec                    ( +-  0,35% )  (35,47%)
        47 895 856      L1-dcache-load-misses     #   22,35% of all L1-dcache accesses  ( +-  0,36% )  (35,48%)
   <not supported>      LLC-loads                                                   
   <not supported>      LLC-load-misses                                             
        14 721 389      L1-icache-loads           #   52,455 M/sec                    ( +- 16,03% )  (35,48%)
            84 158      L1-icache-load-misses     #    0,44% of all L1-icache accesses  ( +- 32,97% )  (35,48%)
           819 820      dTLB-loads                #    2,921 M/sec                    ( +-  0,16% )  (35,47%)
           752 279      dTLB-load-misses          #   92,09% of all dTLB cache accesses  ( +-  0,51% )  (35,47%)
                 0      iTLB-loads                #    0,000 /sec                     (35,47%)
                36      iTLB-load-misses          #  201,40% of all iTLB cache accesses  ( +- 36,24% )  (35,49%)

          0,281539 +- 0,000643 seconds time elapsed  ( +-  0,23% )

Дейстительно, ring-тест на запись (write) отработал в два раза быстрее. В цифрах можно увидеть, что у ring-теста в два раза меньше промахов L1-кэша и промахов кэша страниц TLB. Однако количество неверно предсказанных бранчей, вычисляемых на стороне ядра, практически сопоставимо. Далее это сильно проявится.

Теперь запустим тесты на чтение (read).

> perf stat --repeat=32 -dd ./perf_tests malloc read 2

 Performance counter stats for 'build/perf_tests malloc read 2' (32 runs):

             22,22 msec task-clock                #    0,974 CPUs utilized            ( +-  2,33% )
                 3      context-switches          #  134,278 /sec                     ( +-  4,72% )
                 0      cpu-migrations            #    0,000 /sec                   
               176      page-faults               #    7,878 K/sec                    ( +-  0,20% )
        81 041 308      cycles                    #    3,627 GHz                      ( +-  4,04% )  (2,88%)
           591 486      stalled-cycles-frontend   #    0,86% frontend cycles idle     ( +- 15,76% )  (20,84%)
        56 512 017      stalled-cycles-backend    #   82,54% backend cycles idle      ( +-  4,88% )  (38,83%)
        27 646 990      instructions              #    0,40  insn per cycle         
                                                  #    1,25  stalled cycles per insn  ( +-  1,67% )  (56,83%)
         2 406 873      branches                  #  107,730 M/sec                    ( +-  0,53% )  (74,79%)
            26 423      branch-misses             #    1,12% of all branches          ( +- 11,53% )  (89,92%)
         6 912 481      L1-dcache-loads           #  309,397 M/sec                    ( +-  1,36% )  (79,16%)
            17 070      L1-dcache-load-misses     #    0,24% of all L1-dcache accesses  ( +- 27,37% )  (61,17%)
   <not supported>      LLC-loads                                                   
   <not supported>      LLC-load-misses                                             
         1 134 464      L1-icache-loads           #   50,778 M/sec                    ( +-  4,87% )  (43,17%)
            21 469      L1-icache-load-misses     #    1,71% of all L1-icache accesses  ( +- 39,86% )  (25,21%)
            12 255      dTLB-loads                #  548,524 K/sec                    ( +- 10,03% )  (7,20%)
     <not counted>      dTLB-load-misses                                              (0,00%)
     <not counted>      iTLB-loads                                                    (0,00%)
     <not counted>      iTLB-load-misses                                              (0,00%)

          0,022800 +- 0,000542 seconds time elapsed  ( +-  2,38% )

> perf stat --repeat=32 -dd ./perf_tests ring read 2

 Performance counter stats for 'build/perf_tests ring read 2' (32 runs):

             25,92 msec task-clock                #    0,935 CPUs utilized            ( +-  1,81% )
                 2      context-switches          #   73,493 /sec                     ( +-  6,19% )
                 0      cpu-migrations            #    0,000 /sec                   
               175      page-faults               #    6,431 K/sec                    ( +-  0,21% )
        95 467 226      cycles                    #    3,508 GHz                      ( +-  4,33% )  (9,51%)
         3 438 670      stalled-cycles-frontend   #    4,19% frontend cycles idle     ( +-  4,43% )  (24,94%)
        63 318 352      stalled-cycles-backend    #   77,24% backend cycles idle      ( +-  5,88% )  (40,31%)
        38 501 280      instructions              #    0,47  insn per cycle         
                                                  #    0,63  stalled cycles per insn  ( +-  1,78% )  (55,74%)
         4 173 364      branches                  #  153,356 M/sec                    ( +-  1,32% )  (71,17%)
            90 513      branch-misses             #    2,10% of all branches          ( +- 17,35% )  (77,04%)
         9 137 536      L1-dcache-loads           #  335,772 M/sec                    ( +-  1,86% )  (75,06%)
            31 899      L1-dcache-load-misses     #    0,34% of all L1-dcache accesses  ( +-  6,19% )  (59,69%)
   <not supported>      LLC-loads                                                   
   <not supported>      LLC-load-misses                                             
         5 513 485      L1-icache-loads           #  202,601 M/sec                    ( +-  2,49% )  (44,26%)
            30 218      L1-icache-load-misses     #    0,60% of all L1-icache accesses  ( +-  3,57% )  (28,83%)
            37 339      dTLB-loads                #    1,372 M/sec                    ( +-  9,74% )  (13,44%)
     <not counted>      dTLB-load-misses                                              (0,00%)
     <not counted>      iTLB-loads                                                    (0,00%)
     <not counted>      iTLB-load-misses                                              (0,00%)

          0,027742 +- 0,000489 seconds time elapsed  ( +-  1,76% )

Тут ring-тест от запуска к запуску проседает до полутора раз по сравнению с malloc-тестом. Действительно, по числам видно, что на ring-тест уходит больше инструкций и неверно предсказанных бранчей. С помощью perf record я проверил, что множество непредсказанных ветвлений происходит во многих функциях ядра, связанных с обработкой страниц.

> perf record -e branch-misses ./perf_tests malloc read 1

Samples: 15  of event 'branch-misses', Event count (approx.): 74434
Overhead  Command     Shared Object      Symbol
  17,81%  perf_tests  [kernel.kallsyms]  [k] zap_pte_range.isra.0
  15,59%  perf_tests  [kernel.kallsyms]  [k] rcu_read_unlock_strict
  14,84%  perf_tests  [kernel.kallsyms]  [k] page_remove_rmap
  14,15%  perf_tests  ld-2.31.so         [.] _dl_map_object_from_fd
  13,96%  perf_tests  [kernel.kallsyms]  [k] rmqueue
  12,78%  perf_tests  [kernel.kallsyms]  [k] pmd_page_vaddr
   5,58%  perf_tests  [kernel.kallsyms]  [k] anon_vma_interval_tree_remove
   4,70%  perf_tests  [kernel.kallsyms]  [k] strnlen_user
   0,52%  perf_tests  [kernel.kallsyms]  [k] cpumask_any_but
   0,07%  perf-exec   [kernel.kallsyms]  [k] srso_safe_ret

> perf record -e branch-misses ./perf_tests ring read 1

Samples: 40  of event 'branch-misses', Event count (approx.): 297353
Overhead  Command     Shared Object        Symbol
   7,70%  perf_tests  [kernel.kallsyms]    [k] xas_create
   7,30%  perf_tests  [kernel.kallsyms]    [k] __mod_memcg_lruvec_state
   6,23%  perf_tests  [kernel.kallsyms]    [k] get_page_from_freelist
   5,71%  perf_tests  [kernel.kallsyms]    [k] clear_page_rep
   5,50%  perf_tests  [kernel.kallsyms]    [k] free_unref_page_prepare.part.0
   5,21%  perf_tests  [kernel.kallsyms]    [k] xas_load
   4,74%  perf_tests  [kernel.kallsyms]    [k] get_mem_cgroup_from_mm
   4,48%  perf_tests  [kernel.kallsyms]    [k] xas_init_marks
   4,46%  perf_tests  ld-2.31.so           [.] _dl_relocate_object
   4,32%  perf_tests  [kernel.kallsyms]    [k] __perf_addr_filters_adjust
   4,21%  perf_tests  libstdc++.so.6.0.32  [.] std::locale::_Impl::_Impl
   3,91%  perf_tests  [kernel.kallsyms]    [k] delete_from_page_cache_batch
   3,89%  perf_tests  [kernel.kallsyms]    [k] __alloc_pages
   3,77%  perf_tests  [kernel.kallsyms]    [k] PageHuge
   3,16%  perf_tests  [kernel.kallsyms]    [k] ext4_mpage_readpages
   2,95%  perf_tests  [kernel.kallsyms]    [k] page_remove_rmap
   2,92%  perf_tests  [kernel.kallsyms]    [k] try_charge_memcg
   2,72%  perf_tests  [kernel.kallsyms]    [k] filemap_fault
   2,66%  perf_tests  [kernel.kallsyms]    [k] __mod_zone_page_state
   2,51%  perf_tests  [kernel.kallsyms]    [k] do_set_pte
   2,30%  perf_tests  [kernel.kallsyms]    [k] should_fail_alloc_page
   2,20%  perf_tests  [kernel.kallsyms]    [k] page_counter_try_charge
   2,16%  perf_tests  [kernel.kallsyms]    [k] __add_to_page_cache_locked
   2,04%  perf_tests  [kernel.kallsyms]    [k] xas_find
   1,82%  perf_tests  ld-2.31.so           [.] dl_main
   0,93%  perf_tests  [kernel.kallsyms]    [k] lock_page_memcg
   0,19%  perf_tests  [kernel.kallsyms]    [k] __mod_lruvec_page_state
   0,02%  perf-exec   [kernel.kallsyms]    [k] perf_event_exec

> perf record -e dTLB-load-misses ./perf_tests malloc read 1

Samples: 13  of event 'dTLB-load-misses', Event count (approx.): 1979
Overhead  Command     Shared Object      Symbol
  14,40%  perf_tests  [kernel.kallsyms]  [k] clear_page_rep
  14,20%  perf_tests  [kernel.kallsyms]  [k] asm_exc_page_fault
  13,95%  perf_tests  ld-2.31.so         [.] do_lookup_x
  13,54%  perf_tests  libc-2.31.so       [.] __strlen_avx2
  12,58%  perf_tests  [kernel.kallsyms]  [k] ext4_inode_journal_mode
  11,77%  perf_tests  [kernel.kallsyms]  [k] rcu_do_batch
  10,91%  perf_tests  ld-2.31.so         [.] memmove
   6,16%  perf_tests  ld-2.31.so         [.] _dl_runtime_resolve_xsavec
   2,02%  perf_tests  [kernel.kallsyms]  [k] vma_interval_tree_insert
   0,30%  perf_tests  [kernel.kallsyms]  [k] change_p4d_range
   0,10%  perf_tests  [kernel.kallsyms]  [k] commit_creds
   0,05%  perf_tests  [kernel.kallsyms]  [k] srso_safe_ret

> perf record -e dTLB-load-misses ./perf_tests ring read 1

Samples: 40  of event 'dTLB-load-misses', Event count (approx.): 5118
Overhead  Command     Shared Object      Symbol
  32,45%  perf_tests  [kernel.kallsyms]  [k] clear_page_rep
  11,51%  perf_tests  [kernel.kallsyms]  [k] asm_exc_page_fault
   7,37%  perf_tests  [kernel.kallsyms]  [k] error_entry
   6,92%  perf_tests  [kernel.kallsyms]  [k] ext4_mpage_readpages
   4,20%  perf_tests  ld-2.31.so         [.] check_match
   4,18%  perf_tests  [kernel.kallsyms]  [k] tlb_flush_mmu
   4,08%  perf_tests  ld-2.31.so         [.] _dl_relocate_object
   3,95%  perf_tests  [kernel.kallsyms]  [k] perf_event_mmap
   3,87%  perf_tests  [kernel.kallsyms]  [k] rcu_read_unlock_strict
   3,79%  perf_tests  ld-2.31.so         [.] _dl_load_cache_lookup
   2,75%  perf_tests  [kernel.kallsyms]  [k] memcpy
   2,60%  perf_tests  [kernel.kallsyms]  [k] __handle_mm_fault
   2,25%  perf_tests  [kernel.kallsyms]  [k] xa_load
   2,19%  perf_tests  [kernel.kallsyms]  [k] __mod_lruvec_page_state
   1,60%  perf_tests  [kernel.kallsyms]  [k] mem_cgroup_from_task
   1,50%  perf_tests  [kernel.kallsyms]  [k] find_vma
   1,48%  perf_tests  [kernel.kallsyms]  [k] xas_store
   1,19%  perf_tests  [kernel.kallsyms]  [k] find_lock_entries
   1,19%  perf_tests  [kernel.kallsyms]  [k] zap_pte_range.isra.0
   0,74%  perf_tests  [kernel.kallsyms]  [k] vma_interval_tree_insert
   0,12%  perf_tests  [kernel.kallsyms]  [k] __vma_adjust
   0,04%  perf_tests  [kernel.kallsyms]  [k] arch_rnd.part.0
   0,02%  perf_tests  [kernel.kallsyms]  [k] chacha_permute

Похоже это связано с более сложным управлением MAP_SHARED страницами под капотом ядра. Плюс, с количеством промахов TLB кэша, поскольку необходимо прокручивать в системе в два раза больше виртуальных адресов.

Таблица задержек (наносекунд на 1 мегабайт):

Итог

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

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

• Заводить массив с огромным числом элементов и выделять память под них по требованию: резервирование виртуальной памяти через mmap или VirtualAlloc2 не выделяет физическую память. Вместо этого физическая память выделяется при первом обращении к странице обработчиком page fault;

• Реализовать end-of-page аллокатор для отслеживания ошибок доступа к памяти: такой аллокатор провоцирует access violation при неправильном обращении к памяти, вместо «тихой» перезаписи данных, как в случае с malloc;

• Реализовать аллокатор, не подверженный фрагментации на уровне физической памяти: каждая виртуальная страница сопоставляется со своей физической областью памяти. Поэтому, если освободить какую-либо страницу из середины виртуального пространства, то соответствующая физическая страница будет занята другой виртуальной страницей. Таким образом, фрагментация остается только на уровне виртуального пространства, что не так страшно, потому что бóльшая часть этого пространства пустует;

На момент написания статьи я услышал доклад на конференции C++ Zero Cost Conf 2026 о ещё одном применении магического буфера. В докладе "Трассирую и профилирую — бесплатно" докладчик использовал эту технологию в HFT-проекте для быстрой записи логов в буфер.

В данной статье я показал реализацию магического кольцевого буфера и произвел замеры производительности. Реализация буфера доступна в гитхабе.