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

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

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

В области computer vision, где я работаю, приходится иметь дело с большими матрицами, вес которых исчисляется сотнями килобайт или даже мегабайтами. Моя задача — хранить в буфере историю последних M поступивших матриц размерности H \times W \times F, например (48, 12 \times 20 \times 256). Новые матрицы потоком поступают в буфер с определенной периодичностью. С той же периодичностью уходят старые матрицы, сохраняя свежесть всей серии. Эта серия в любой момент времени, который заранее неизвестен, должна быть подана единым тензором (M \times H \times W \times F) на вход рекуррентной нейросетке, которая будет искать временны́е закономерности в этой серии. Для неё важно не нарушать порядок следования элементов, который соответствует времени вставки элемента в буфер. Очевидно, что любые манипуляции с матрицами такого размера обойдутся дорого, как по памяти, так и по вычислительным ресурсам, и нужно искать способы сокращать расходы на любые манипуляции с буфером.

Как правило, кольцевой буфер реализуется одним из двух способов. Либо на базе списков, вроде 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‑чипом на физические. Схема расположения физических адресов при этом не обязана совпадать с расположением адресов виртуальных. Я представил, что, по такой схеме можно выделить два виртуальных блока по N байт, следующих друг за другом, которые будут транслироваться на общий физический блок. Это означает, что любые манипуляции с памятью первого виртуального блока автоматически отразятся на втором и наоборот. С точки зрения указателя, который может гулять по интервалу [0; 2N], от начала первого блока до конца второго, перепрыгнув на позицию N, мы автоматически попадем в начало физического блока: то есть выполнится условие buf[i] == buf[i+N], где i ∈ [0; N-1]. Таким образом, можно вставлять новые элементы по индексу 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. Создать анонимный файл объёма N — кусочек будущей оперативной памяти, не имеющей привязки к диску. Физическая память на этом этапе не выделяется;

  2. Застолбить виртуальную подложку (base) объёма 2N — ещё не привязанную к физической памяти область виртуальной памяти для хранения двух будущих виртуальных блоков. Очередность выполнения шагов 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 секцию объёма N — область памяти, привязанную к файлу подкачки, а не к файлу с диска. Это аналог линуксового анонимного файла;

  2. Застолбить виртуальную подложку (base) объёма 2N — ещё не привязанную к физической памяти область виртуальной памяти для хранения двух будущих виртуальных блоков. Очередность выполнения шагов 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‑тест) имитирует работу плоского буфера с двойной вставкой. Он выделяет 2N байт через malloc, затем, в цикле, размещает новый элемент по индексу i и копирует его во вторую часть буфера по индексу [i+N]. Второй тест (ring‑тест) имитирует работу магического буфера. Он выделяет 2N байт методом, описанным выше, и размещает новый элемент по индексу i. Элемент отзеркаливается во второй части буфера, поэтому копирования не требуется.

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

pmap ‑x
> 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 (write)
> 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 (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 (branch‑misses)
> 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 (dTLB‑load‑misses)
> 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 мегабайт):

malloc‑read

ring‑read

malloc‑write

ring‑write

AMD Ryzen 5 1600 Six‑Core Processor, Ubuntu 24, 6 ядер, 8192 RAM

26

31

201⋅10³

101⋅10³

AMD Ryzen 5 1600 Six‑Core Processor, Windows 10, 6 ядер, 8192 RAM

67

22

400⋅10³

43⋅10³

12th Gen Intel® Core™ i5-12400F, Ubuntu 24, 6 ядер, 8192 RAM

11

14

76⋅10³

31⋅10³

12th Gen Intel® Core™ i5-12400F, Windows 10, 6 ядер, 8192 RAM

252

62

216⋅10³

7⋅10³

Итог

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

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

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

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

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

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

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

Комментарии (25)


  1. Mingun
    07.10.2026 20:04

    Уже была на Хабре похожая статья пять лет назад. Там тоже есть ссылка на GitHub и вроде даже thread-safety заявлено (не проверял, мельком увидел в статье, пока освещал ее в памяти).


    1. matkov Автор
      07.10.2026 20:04

      Да, это перевод статьи https://lo.calho.st/posts/black-magic-buffer/, ссылка на которую приведена в тексте.

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


  1. dbpatch
    07.10.2026 20:04

    Озвученная проблема:
    а) нужно иметь писателя и иметь читателя(лей) для потоковых данных, приближенных к realtime
    б) нужно максимально быстро переиспользовать уже прочитанную / обработанную память
    в) нужно обеспечить непрерывность в памяти нескольких подряд идущих элементов размером в несколько килобайт или мегабайт

    Теперь вопрос - а что мешает просто зарезервировать через mmap() (но не выделить) диапазон адресов размером в несколько терабайт (для современных 64-х битных архитектур с 48 реальными адресуемыми битами верхний предел около 128 терабайт, в реальности чуть менее). Физическая память будет выделяться (commit) при записи. Уже обработанную память - просто освобождать через madvise(MADV_DONTNEED). Быстрее в этом мире ничего нет, т.к. malloc()/free()/new/delete это просто обертки над mmap() с его commit on demand

    80TB это примерно 80млн чанков размером по 1MB. А при достижении "верхнего предела" можно просто взять паузу и сделать remap() активной часть буфера в начало.

    Не просто так конечно - там уже нужно будет две последовательно очень большие области, скажем по 40TB. И если наш читающий хвост переехал из первой области во вторую (т.е. первая стала полностью не нужна), то мы быстро первую отмпаливаем целиком, вторую ставим на место первой через mremap(), и еще раз делаем заново mmap() второй области с MAP_FIXED.

    Linux довольно консервативен в части использования диапазонов адресов - все что не первый и не последний терабайт из адресуемых 128TB userspace - это система практически не задействует сама (heap растет снизу вверх, стек и mmap()ы без указания адреса - сверху вниз).


    1. vanxant
      07.10.2026 20:04

      от ASLR сюрпризов не будет?


      1. dbpatch
        07.10.2026 20:04

        Насколько я знаю нет, там все достаточно предсказуемо в linux, при уровне 2. Обещают правда совсем полную рандомизацию, но пока это лишь в теории.
        Большим сюрпризом там скорее магическое число 89TB, которое есть суть PIE base 0x555555554000, но оно лишь дополняет правило: не первый терабайт и не последний 128й, а да, и 89-й тоже трогать нельзя :)


    1. matkov Автор
      07.10.2026 20:04

      а что мешает просто зарезервировать через mmap()

      Да ничего не мешает. Предложение дельное. Тема для отдельного исследования с выявлением плюсов и минусов такого подхода.

      Буду признателен, если поделитесь примером реализации, если имеется.

      скажем по 40TB

      Это вы хватанули … Буфер же не один в процессе, другим тоже должно хватать. К тому же не забывайте про динамического линковщика, который может прилинковать библиотеку в середину адресного пространства. Терабайта-два должно хватить.

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

      В любом случае заинтересовали, буду углубляться.


      1. dbpatch
        07.10.2026 20:04

        40TB это я рубанул "от души" :) Но скорее с целью показать пределы масштабируемости. Считается же что 64 бит это прям очень много (18.4 экзабайт), а в реальности намного скромнее, 48 бит в общем случае, или 52/56 бит в особо крутых серверных материнках.

        Но основная идея да, заключается в том, что с 64 битами адреса и возможностью манипуляций с mmap(MAP_FIXED) многие старые парадигмы управления памятью из 16-, 31-, 32- битных миров из 70-х годов как минимум могут быть пересмотрены. К примеру можно играть в арены (region memory aka memory pools), с заданными циклами жизни, и не заниматься мелкодробным free() / delete - т.е. вместо malloc() / new выделять память, просто последовательно сдвигая HWM в заранее отмпаленном регионе, прям как в Java, и лишь в конце жизненного цикла (внешнего вызова, сессии, процесса) - просто удалять этот регион целиком. Внешние ресурсы (хендлы) - собирать в linked list и удалять вместе с регионом. Про деструкторы и вовсе забыть. Идея кстати не нова, вовсю используется в APR / apache httpd и PostreSQL, образцах long-running стабильности. В виде плюшки заодно и от memory reuse с undefined behavior проблем избавиться.

        Реализацией пока не поделюсь, это отдельный исследовательский проект, думаю в следующем году выложить в github/MIT. Правда вопросами кольцевых буферов в аспекте непрерывной группы чанков я не озадачивался, пока не было необходимости. Пока там в части кольцевых буферов пока лишь аналог LMAX Disruptor для сверхскоростной межпроцессной IPC на lockfree алгоритмах. Для меня самого было удивительным, что даже в offset pointer на самом деле уже и не особо надо, если для всех изолированных процессов заранее замапить буфер в строго определенный адрес - так все процессы будут иметь единую сквозную адресацию.

        И т.д. :)


  1. LinkToOS
    07.10.2026 20:04

    В 2026 году, кольцевой буфер все еще не реализован на уровне библиотек, как стандартная функция С++, отлаженная и документированная? Или такая функция отдельно не нужна, и встроена в функции более высокого уровня для работы с данными, в библиотеках для обработки данных?


    1. Sixshaman
      07.10.2026 20:04

      Не реализован. Вместо него стандарт предписывает использовать std::deque на основе связных списков.


    1. matkov Автор
      07.10.2026 20:04

      В 2015 было предложение добавить ring adaptor в стандартную библиотеку https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0059r0.pdf. Видимо предложение отклонили, раз адаптор так и не появился.

      Или такая функция отдельно не нужна, и встроена в функции более высокого уровня для работы с данными, в библиотеках для обработки данных?

      Ближайшая к std реализация — это Boost.Circular Buffer. Других проверенных реализаций я не встречал.


      1. LinkToOS
        07.10.2026 20:04

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


  1. AlexSky
    07.10.2026 20:04

    Прочитал заголовок и сразу понял, о чем пойдет речь. Сам к такой идее пару лет назад пришел, только потом обнаружил, что так уже делали.


  1. vanxant
    07.10.2026 20:04

    40 лет назад для такого в С++ придумали шаблоны, а затем и STL. Именно чтобы можно было сделать свой контейнер для тензоров в кольцевом буфере, у которого указатель на данные первого индекса будет вычисляться как (head_offset + i) % capacity. И чтобы всё это подставлялось и оптимизировалось во время компиляции, без виртуальных функций и т.д. Потому что кому-то хватит обычного буфера, кому-то кольцевого, а у кого-то разреженные матрицы на основе списка списков. Но увы:)


    1. matkov Автор
      07.10.2026 20:04

      40 лет назад для такого в С++ придумали шаблоны, а затем и STL

      Не улавливаю. Как это связано с темой закольцовки памяти? Если вы говорите про удобный АПИ для доступа к буферу — вопросов нет. Можно разработать свой контейнер для кольцевой структуры данных, а-ля STL. Можно взять готовый std::vector и написать ему свой аллокатор. Главное в том, что у них будет под капотом.

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

      указатель на данные первого индекса будет вычисляться как (head_offset + i) % capacity

      Да, реализация через std::vector со швом. Есть в статье.

      без виртуальных функций

      Виртуальные функции в тексте нигде не фигурируют.


      1. vanxant
        07.10.2026 20:04

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


        1. aamonster
          07.10.2026 20:04

          Никакие темплейты вам не обеспечат возврат указателя на массив (автору нужен именно физический массив, а не нечто с operator[]), если вы этот массив не сформируете. Они просто уберут бойлерплейт.

          Единственное что – можно за счёт темплейтов сделать платформенно-зависимый кусок маленьким.


          1. vanxant
            07.10.2026 20:04

            Если что, я 20 лет назад примерно так и делал - прикручивал свои кастомные контейнеры к тогдашнему OpenCV. Не ко всему, разумеется, только к десятку нужных функций. Первый operator[] перегружен, дальше уже обычный многомерный массив в стиле С.


        1. matkov Автор
          07.10.2026 20:04

          Речь о том, что это должна поддерживать ваша числодробительная библиотека

          А если не поддерживает? Это зависит от железа, либо проц поддерживает modulo addressing, либо нет. Процы общего назначения не поддерживают. Оптимизации компилятора это вторичное. И уж точно компилятор не будет ничего подставлять на этапе компиляции, если только у него нету оракула, который предсказывает, когда и по какому адресу мне понадобятся данные в рантайме)

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


          1. vanxant
            07.10.2026 20:04

            А если не поддерживает?

            Тогда ой:) И это в первую очередь от самой библиотеки зависит. Я понимаю, зачем нужна линейность внутри кадра, там и кеши и SIMD и т.д., но где и как хранить разные кадры, пусть даже и соседние - это уже не дело библиотеки. Но увы.


  1. nv13
    07.10.2026 20:04

    То есть неудобство с границей плоского буфера вы заменили использованием кучи системных вызовов? И посчитали наносекунды.. а может тогда dma использовать для перемещения 2 блоков в выходной массив?


    1. matkov Автор
      07.10.2026 20:04

      Каким образом можно это сделать на процессорах общего назначения?


      1. nv13
        07.10.2026 20:04

        А разве нельзя? Какие то вроде драйверы есть любительские - я давно ничего такого не программировал


    1. Mingun
      07.10.2026 20:04

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


      1. nv13
        07.10.2026 20:04

        Да, ошибался, не дочитал) Всё равно не очень понимаю смысл использования mmap - у вас же всё равно нет сплошной физической памяти, при доступе будет постоянная трансляция страниц. Что мешает просто реализовать самому адресную арифметику по модулю - где надо? Если задача быстро сделать снапшот того, что уже в памяти, то самое эффективное это memcpy, пусть и в 2 этапа - перевычислить адреса это копейки по сравнению с доступом через отображение в память, что ваши тесты и подтверждают. Ну на С это напишите - всё равно же mmap хотите использовать

        Я один раз видел, к чему приводят идеи "сделать красиво")) На достаточно дохлой машине надо было считывать файл и блоками передавать его по сети. Формат - заголовок сколько то байт и массив short пара килобайт. Программа на c++ состояла из десятка классов, не помещающихся на пару экранов каждый - сначала открывался и парсился файл, потом создавался объект с объектом заголовком и объектом массивом, потом он сериализовался и побайтно засовывался в сокет. Выглядело это очень академично, но.. ну нельзя же так, если задачей является поток данных порядка 10 МБ сек))


        1. Mingun
          07.10.2026 20:04

          нет сплошной физической памяти, при доступе будет постоянная трансляция страниц.

          Ну так ее и так, и так нет. Трансляции есть что при традиционном подходе, что в этом.

          Что мешает просто реализовать самому адресную арифметику по модулю - где надо?

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

          • или скопировать практически весь буфер (кроме первого элемента) в память за концом хранилища (это если там свободно)

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

          • или поддерживать хранилище в двукратном размере, работать в его первой половине, а когда надо отдать непрерывный кусок, то хвост вылезает во вторую половину. Для буфера на N элементов в худшем случае логическое начало на последнем рабочем элементе (индекс N-1) и вам нужна N-1 копия в хвосте. То есть хранилище должно быть размера 2*N-1. В этом хвосте можно

            • или наполнять его по требованию (когда попросят непрерывный кусок памяти из буфера, разумеется, помять можно только одолжить, а не отдать во владение)

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

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