Кольцевой буфер (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
Создать анонимный файл объёма
— кусочек будущей оперативной памяти, не имеющей привязки к диску. Физическая память на этом этапе не выделяется;
Застолбить виртуальную подложку (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‑проекте для быстрой записи логов в буфер.
В данной статье я показал реализацию магического кольцевого буфера и произвел замеры производительности. Реализация буфера доступна в гитхабе.
Комментарии (25)

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()ы без указания адреса - сверху вниз).
vanxant
07.10.2026 20:04от ASLR сюрпризов не будет?

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

matkov Автор
07.10.2026 20:04а что мешает просто зарезервировать через mmap()
Да ничего не мешает. Предложение дельное. Тема для отдельного исследования с выявлением плюсов и минусов такого подхода.
Буду признателен, если поделитесь примером реализации, если имеется.
скажем по 40TB
Это вы хватанули … Буфер же не один в процессе, другим тоже должно хватать. К тому же не забывайте про динамического линковщика, который может прилинковать библиотеку в середину адресного пространства. Терабайта-два должно хватить.
Нюанс с резервированием огромного участка, как мне кажется, нужно всегда учитывать и держать в голове при проектировании и поддержании ПО, так как неизвестно, чем это аукнется в сложных системах.
В любом случае заинтересовали, буду углубляться.

dbpatch
07.10.2026 20:0440TB это я рубанул "от души" :) Но скорее с целью показать пределы масштабируемости. Считается же что 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 на самом деле уже и не особо надо, если для всех изолированных процессов заранее замапить буфер в строго определенный адрес - так все процессы будут иметь единую сквозную адресацию.
И т.д. :)

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

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

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. Других проверенных реализаций я не встречал.

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

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

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

matkov Автор
07.10.2026 20:0440 лет назад для такого в С++ придумали шаблоны, а затем и STL
Не улавливаю. Как это связано с темой закольцовки памяти? Если вы говорите про удобный АПИ для доступа к буферу — вопросов нет. Можно разработать свой контейнер для кольцевой структуры данных, а-ля STL. Можно взять готовый
std::vectorи написать ему свой аллокатор. Главное в том, что у них будет под капотом.В статье я поднимаю капот и вижу под ним проблему хранения данных непрерывно и упорядоченно, и предлагаю механизм её решения. А какими методами взаимодействовать с данными — это уже на усмотрение каждого.
указатель на данные первого индекса будет вычисляться как (head_offset + i) % capacity
Да, реализация через
std::vectorсо швом. Есть в статье.без виртуальных функций
Виртуальные функции в тексте нигде не фигурируют.

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

aamonster
07.10.2026 20:04Никакие темплейты вам не обеспечат возврат указателя на массив (автору нужен именно физический массив, а не нечто с operator[]), если вы этот массив не сформируете. Они просто уберут бойлерплейт.
Единственное что – можно за счёт темплейтов сделать платформенно-зависимый кусок маленьким.

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

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

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

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

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

nv13
07.10.2026 20:04Да, ошибался, не дочитал) Всё равно не очень понимаю смысл использования mmap - у вас же всё равно нет сплошной физической памяти, при доступе будет постоянная трансляция страниц. Что мешает просто реализовать самому адресную арифметику по модулю - где надо? Если задача быстро сделать снапшот того, что уже в памяти, то самое эффективное это memcpy, пусть и в 2 этапа - перевычислить адреса это копейки по сравнению с доступом через отображение в память, что ваши тесты и подтверждают. Ну на С это напишите - всё равно же mmap хотите использовать
Я один раз видел, к чему приводят идеи "сделать красиво")) На достаточно дохлой машине надо было считывать файл и блоками передавать его по сети. Формат - заголовок сколько то байт и массив short пара килобайт. Программа на c++ состояла из десятка классов, не помещающихся на пару экранов каждый - сначала открывался и парсился файл, потом создавался объект с объектом заголовком и объектом массивом, потом он сериализовался и побайтно засовывался в сокет. Выглядело это очень академично, но.. ну нельзя же так, если задачей является поток данных порядка 10 МБ сек))

Mingun
07.10.2026 20:04нет сплошной физической памяти, при доступе будет постоянная трансляция страниц.
Ну так ее и так, и так нет. Трансляции есть что при традиционном подходе, что в этом.
Что мешает просто реализовать самому адресную арифметику по модулю - где надо?
Борятся не с арифметикой (она-то как раз никуда не делась), а с созданием копий в памяти. Циклический буфер имеет границу. Если вы хотите извлечь из него один непрерывный кусок байт (в виртуальной адресном пространстве, с которым все и работает), то вам нужно озаботится, чтобы у вас этот непрерывный кусок был. Например, если у вас в буфере его начало на последнем элементе хранилища (т.е. буфер тут же враппится и хвост продолжается в начале), то вам надо:
или скопировать практически весь буфер (кроме первого элемента) в память за концом хранилища (это если там свободно)
или скопировать все хранилище, куда-то в другое место, сделав так, чтобы логически первый элемент был первым и физически
-
или поддерживать хранилище в двукратном размере, работать в его первой половине, а когда надо отдать непрерывный кусок, то хвост вылезает во вторую половину. Для буфера на
элементов в худшем случае логическое начало на последнем рабочем элементе (индекс
) и вам нужна
копия в хвосте. То есть хранилище должно быть размера
. В этом хвосте можно
или наполнять его по требованию (когда попросят непрерывный кусок памяти из буфера, разумеется, помять можно только одолжить, а не отдать во владение)
или поддерживать в нем копию каждый раз при вставке нового элемента в буфер, чтобы когда непрерывный кусок попросили, он у вас уже был. Полезно, когда просят часто по сравнению со вставками
или сделать так, чтобы ОС это поддерживала автоматически, трансляцией страниц. Полезно, когда и вставляете часто, и непрерывный кусок просят часто. Причем нет каких-то специальных накладных расходов – страницы в любом случае транслируются куда-то в физическую память, только тут эта трансляция еще приносит дополнительную пользу
Mingun
Уже была на Хабре похожая статья пять лет назад. Там тоже есть ссылка на GitHub и вроде даже thread-safety заявлено (не проверял, мельком увидел в статье, пока освещал ее в памяти).
matkov Автор
Да, это перевод статьи https://lo.calho.st/posts/black-magic-buffer/, ссылка на которую приведена в тексте.
У нас немного разные сценарии. Тот мужик записывал в буфер сообщения разной длины и хотел избавиться от проверки, не вылезет ли сообщение за границы буфера. У меня сообщения (матрицы) всегда одинаковой длины. Мне нужно экономить место и операции.