Кольцевой буфер (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-чипом на физические. Схема расположения физических адресов при этом не обязана совпадать с расположением адресов виртуальных. Я представил, что, по такой схеме можно выделить два виртуальных блока по 
байт, следующих друг за другом, которые будут транслироваться на общий физический блок. Это означает, что любые манипуляции с памятью первого виртуального блока автоматически отразятся на втором и наоборот. С точки зрения указателя, который может гулять по интервалу ![[0; 2N]](https://habrastorage.org/getpro/habr/upload_files/22e/275/542/22e27554260a4908e23afcf464e7cdd4.svg)
, от начала первого блока до конца второго, перепрыгнув на позицию 
, мы автоматически попадем в начало физического блока: т.е. выполнится условие buf[i] == buf[i+N], где ![i ∈ [0; N-1]](https://habrastorage.org/getpro/habr/upload_files/767/203/320/767203320f60677192478212f2b893ca.svg)
. Таким образом, можно вставлять новые элементы по индексу 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
Создать анонимный файл объёма
— кусочек будущей оперативной памяти, не имеющей привязки к диску. Физическая память на этом этапе не выделяется;Застолбить виртуальную подложку (base) объёма
— ещё не привязанную к физической памяти область виртуальной памяти для хранения двух будущих виртуальных блоков. Очередность выполнения шагов 1 и 2 не играет роли, так как подложка не привязана к анонимному файлу;Разбить подложку на две части, разместив в каждой по виртуальному блоку по адресам
&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КБ.
Создать pagefile-backed секцию объёма
— область памяти, привязанную к файлу подкачки, а не к файлу с диска. Это аналог линуксового анонимного файла;Застолбить виртуальную подложку (base) объёма
— ещё не привязанную к физической памяти область виртуальной памяти для хранения двух будущих виртуальных блоков. Очередность выполнения шагов 1 и 2 не играет роли, так как подложка не привязана к файлу подкачки;Разбить подложку на два виртуальных блока по адресам
&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
> 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-проекте для быстрой записи логов в буфер.
В данной статье я показал реализацию магического кольцевого буфера и произвел замеры производительности. Реализация буфера доступна в гитхабе.
Комментарии (3)
dbpatch
07.10.2026 20:04Озвученная проблема:
а) нужно иметь писателя и иметь читателя(лей) для потоковых данных, приближенных к realtime
б) нужно максимально быстро переиспользовать уже прочитанную / обработанную память
в) нужно обеспечить непрерывность в памяти нескольких подряд идущих элементов размером в несколько килобайт или мегабайт
Теперь вопрос - а что мешает просто зарезервировать через mmap() (но не выделить) диапазон адресов размером в несколько терабайт (для современных 64-х битных архитектур с 48 реальными адресуемыми битами верхний предел около 128 терабайт, в реальности чуть менее). Физическая память будет выделяться (commit) при записи. Уже обработанную память - просто освобождать через madvise(MADV_DONTNEED). Быстрее в этом мире ничего нет, т.к. malloc()/free()/new/delete это просто обертки над mmap() с его commit on demand80TB это примерно 80млн чанков размером по 1MB. А при достижении "верхнего предела" можно просто взять паузу и сделать remap() активной часть буфера в начало.
Не просто так конечно - там уже нужно будет две последовательно очень большие области, скажем по 40TB. И если наш читающий хвост переехал из первой области во вторую (т.е. первая стала полностью не нужна), то мы быстро первую отмпаливаем целиком, вторую ставим на место первой через mremap(), и еще раз делаем заново mmap() второй области с MAP_FIXED.
Linux довольно консервативен в части использования диапазонов адресов - все что не первый и не последний терабайт из адресуемых 128TB userspace - это система практически не задействует сама (heap растет снизу вверх, стек и mmap()ы без указания адреса - сверху вниз).
Mingun
Уже была на Хабре похожая статья пять лет назад. Там тоже есть ссылка на GitHub и вроде даже thread-safety заявлено (не проверял, мельком увидел в статье, пока освещал ее в памяти).
matkov Автор
Да, это перевод статьи https://lo.calho.st/posts/black-magic-buffer/, ссылка на которую приведена в тексте.
У нас немного разные сценарии. Тот мужик записывал в буфер сообщения разной длины и хотел избавиться от проверки, не вылезет ли сообщение за границы буфера. У меня сообщения (матрицы) всегда одинаковой длины. Мне нужно экономить место и операции.