Устройство виртуальной памяти процесса

Без понимания принципов устройства виртуальной памяти процесса вполне можно разрабатывать прикладное ПО. Однако, понимание этих принципов будет полезно любому software инженеру. А в случаях низкоуровневой работы с памятью такие знания становятся необходимостью. В данном посте я поверхностно раскрою данную тему, а в последующих сделаю углубление в отдельные темы о том, как работает память внутри программного обеспечения.

Для начала давайте разберемся, что такое виртуальная память, зачем она нужна и почему мы не можем обращаться к реальной памяти напрямую.
На заре развития компьютеры исполняли лишь одну программу за раз. И даже первые операционные системы были однозадачными. Запущенная программа спокойно могла распоряжаться всеми доступными ресурсами, в том числе и оперативной памятью.
Предоставить такой программе доступ к реальной памяти не вызывало особых проблем.
Сегодня же подобными привилегиями могут похвастаться лишь программы исполняемые на голом железе, такие как ядра операционных систем и прошивки микроконтроллеров.

Если же мы имеем дело с программой исполняющейся под одной из современных операционных систем, таких как Linux, Windows, MacOS, FreeBSD и некоторых других, то мы оказываемся в многозадачной среде, в которой исполняются несколько программ параллельно.
В таких условиях при использовании реальной памяти появляется ряд проблем. Одна из них - это эффективное ограничение доступа к областям памяти принадлежащих другим процессам. Менее очевидная для разработчиков работавших только с высокоуровневыми языками проблема - мы не можем гарантировать, что исполняемый код нашей программы будет всегда загружен в оперативную память по одним и тем же адресам, что сильно затрудняет вызовы функций/методов нашей программы.
Наличие же виртуальной памяти, помимо решения вышеуказанных проблем позволяет делать еще несколько полезных трюков, вроде сброса неиспользуемой в данный момент памяти в файл/раздел подкачки или архивирование ее в ZRAM, а так же отображение виртуальной памяти в устройства отличные от оперативный памяти.

Как же это работает?
Каждому процессу в системе предоставляется виртуальное адресное пространство, как будто он обладает максимально возможной памятью для данной аппаратной архитектуры. О том, какие максимумы для памяти доступны на различных архитектурах я расскажу в одном из следующих постов. А вот с виртуальными адресами разберемся прямо сейчас.
Когда процесс обращается к памяти по своему виртуальному адресу, контроллер памяти сопоставляет ему реальный адрес по специальным таблицам, составленным операционной системой.
Если такое сопоставление успешно, то программа получает в свое распоряжение конкретный блок реальной памяти.
Если же виртуальный адрес не сопоставлен реальному, то программа падает с segmentation fault.
Еще один возможный сценарий, когда виртуальный адрес сопоставлен с чем либо за пределами оперативной памяти, например с файлом подкачки, в этом случае управление передается операционной системе, которая загружает нужные данные в оперативную память и обновляет таблицу виртуальных адресов, после чего операция повторяется и программа получает доступ к требуемой памяти.

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

Страничная организация памяти

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

Для начала посмотрим, как это работает.
Для каждого процесса ОС заводит несколько таблиц для хранения информации о страницах памяти. В одной таблице могут хранится только таблицы одинакового размера, а количество записей ограничено. Помимо реального адреса начала страницы, в каждой записи таблицы хранятся права доступа к данной странице, похожие на права файлов в unix - чтение, запись, выполнение, с той разницей, что ограничение на чтение обычно не имеет смысла и вместо него используется ограничение на доступ только из ядра ОС.
Несколько таблиц объединяются в каталоги, а каталоги могут объединяться в каталоги более высокого уровня. В современных 64-битных архитектурах может использоваться до 4 уровней вложенности.
Виртуальный адрес в такой модели состоит из двух частей: старшие биты указывают на индекс каталога/таблицы, а младшие - смещение в странице.

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

Области виртуальной памяти

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

Что это за области?
Я предполагаю, что большинство моих читателей хотя бы что-то слышали о таких понятиях как стек и куча. Это как раз 2 примера таких областей, однако ими дело не ограничивается.
Прежде чем мы разберемся, какие области бывают и для чего они предназначены, стоит прояснить несколько важных моментов:
Во-первых, все эти области являются всего лишь абстракциями. Это значит, что большинство из этих областей по сути не являются обязательными, но ими оперируют большинство языков программирования на уровне компиляторов и стандартных библиотек. Однако никто не мешает нам на самом низком уровне распоряжаться памятью так, как мы сочтем нужным. Хотя и здесь есть нюансы, например ОС может навязывать нам свои правила.
Во-вторых, не лишним будет знать, что виртуальная память обычно разделена на 2 пространства - пользовательское и пространство ядра. Пространство ядра как правило располагается в верхней половине адресов и недоступно из режима пользователя, в котором выполняются наши программы. Такое разделение очень важно для выполнения системных вызовов, о которых мы поговорим в будущих постах.
В третьих, некоторые области могут быть на деле разбросаны по адресному пространству, а так же присутствовать в нескольких экземплярах. То, что стек обычно рисуют сверху - не более чем грубое упрощение, таким упрощениям я посвящу следующий пост.

Перечислим часто встречающиеся области с описанием для чего они нужны:

stack - используется для локальных переменных функций, а так же для мета информации о вызовах, такой как адрес возврата. Каждый поток имеет свой собственный стек. Размер стека не изменяется в процессе выполнения и определяется ОС для главного потока и разработчиком для дочерних. Получил свое название в честь одноименной структуры данных, так как по сути представлен стеком кадров (stack frames), каждый из которых содержит информацию запущенной в текущей момент функции.

heap (куча) - используется для динамической памяти, которая выделяется и освобождается в runtime по мере надобности. Опять же, куча названа так по имени структуры данных, которая использовалась в первых аллокаторах (алгоритмах выделяющих и освобождающих память, а так же нарезающих страницы на куски).

text - здесь расположен машинный код программы. Указатели на функции ведут в эту область памяти. Сюда запрещена запись, но разрешено выполнение.

data - область для static и глобальных переменных инициализированных на старте программы. Начальное состояние загружается из файла с программой (elf/exe/mach o).

rodata - область для констант, похожа на предыдущую с той разницей, что сюда запрещена запись.

bss - область для неинициализированных static и глобальных переменных. От data отличается тем, что в файле с программой описывается лишь размер данных. В зависимости от ОС на старте программы может быть заполнена нулями или мусором.

env - область в которую ОС записывает переменные окружения и аргументы командной строки.

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

Вот несколько таких нюансов:
- В Windows область text расположена по более старшим адресам, чем stack.
- Stack не растет вниз, размер стека не меняется.
- В программе может быть больше одного стека.
- Heap (куча) не растет вверх.
- В таких языках как JavaScript или Python разработчику доступна только куча.
- Есть языки с JIT компиляцией, у которых под капотом используются области с одновременно разрешенными записью и исполнением.

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

Как работает stack?

Область памяти stack очень интересна по своей природе. Хотя абсолютно все области памяти являются абстракциями, stack единственная из них, которая пронизывает слой абстракций вплоть до аппаратного уровня на практически любой архитектуре.

В основе работы стека лежит регистр специального назначения называемый stack pointer (sp), который хранит в себе адрес указывающий на вершину стека. Так же в большинстве ассемблеров можно встретить такие операции как push и pop. Если упрощать, то можно сказать, что push кладет свой аргумент на вершину стека, а pop извлекает вершину стека в свой аргумент.

Но что эти операции делают на самом деле?
Операция push на самом деле выполняет 2 действия. Сначала она уменьшает значение в регистре sp на размер машинного слова (8 байт на 64 битных архитектурах). Затем она перемещает данные из регистра указанного в ее аргументе по адресу полученному в результате предыдущей операции.
Операция pop делает все наоборот. Помещает данные из памяти по адресу хранящемуся в sp в регистр указанный в ее аргументе, а затем увеличивает значение sp на размер машинного слова.

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

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

Ну и раз уж заговорили о многозадачности. Операции со стеком не задумывались для работы в многопоточной среде, поэтому для каждого потока в программе создается свой собственный стек. Память под стек выделяется в момент создания потока, а освобождается когда поток завершает свою работу.
Сколько выделить памяти решает тот, кто запускает поток, для главного потока - ОС, для дочерних - программа. Единственное ограничение тут - стек должен занимать целое число страниц.
Ниже этой памяти ОС размечает 1 дополнительную страницу, которая не отображается на реальную память, а служит защитником стека (stack guard), при попытке записи в данную страницу вместо ошибки segmentation fault происходит более понятная ошибка stack overflow.

Немного холиварной лирики в ленту касательно языков.

Я вижу как много указали Java в комментах под опросом выше. Упоминали и другие языки, но именно Java оказалось очень много, что не мудрено. Если думать с позиции заколачивания кэша, то Python, JavaScript (или скорее TypeScript) и Java - беспроигрышный выбор, с которым всегда найдешь работу.

Почему основной список языков в опросе именно такой? Это те языки, которыми я владею уверенно, как минимум на достаточном уровне чтоб написать на них что-то осмысленное.

Конечно у каждого наверняка есть свой язык любимчик. Для меня Rust - one love 🫀+🧠. Но я хочу взглянуть на языки немного с другой стороны. С позиции парадокса Блаба. Исходя из того, как они развивают программистский кругозор и прокачивают мозг.
С одной стороны можно просто изучить как можно больше языков, но без использования знания выветриваются. Я уже не думаю на php или Go, хотя когда-то зарабатывал на них деньги. Я вообще не помню QBasic и Pascal, хотя начинал с них. Я по фану въехал в Brainfuck, но дальше фана он не применим. Мне интересны семейства Prolog и APL, вот только кому они нужны на практике.
И если вы спросите меня про 3 языка, которые проапгрейдили мое мышление, то я отвечу - C, Haskell, Rust.

C - до предела простой. В нем минимум абстракций, нужна абстракция - напиши ее сам. Он заставляет думать о том, как все работает под капотом, не погружаясь при этом в дебри ассемблера.

Haskell - заставляет мыслить совершенно по другому. Мыслить в категории потока данных проходящих через последовательность вычислений (что по сути и делает любая программа). Он взрывает мозг, когда ты втыкаешь отладку через unsafePerformIO $ print и получаешь не то что ожидал. Но потом ты в это въезжаешь и ты уже никогда не будешь мыслить как прежде. Правда мне теперь всегда не хватает HKT в других языках, каждый раз, как я ухожу в метапрограммирование на типах.

Rust - еще один переворот сознания. Хоть и многословное, но красивое сочетание zero-cost абстракций из мира плюсов с изяществом ML языков. Первый месяц ты борешься с компилятором с мыслями "какого черта оно не компилируется?" А потом приходит понимание, которое навсегда меняет твой подход к написанию кода на любом языке. Да и читаешь ты код уже по другому. Начинаешь видеть проблемы там где они есть, но раньше ты их не видел. И сетуешь, почему нельзя было кинуть хотя бы warning на ту дичь, что написал коллега джун.
Плюсовики, вы видите тут UB?
void foo(const int &x, int &y) {
bar(x, ++y);
}
А так: foo(a, a)? А Rust не даст такое скомпилировать, в этом и прелесть.

Stack Frames или сказ о вызовах функций используя стек

Есть много способов, как организовать вызовы функций, да так, чтоб мы могли передавать в функцию аргументы, изолировать в ней локальные переменные, а так же уметь возвращаться назад, желательно с результатом.
Некоторые динамические языки, вроде JavaScript, php или Python, могут даже позволить себе роскошь хранить локальные переменные на куче (в случае исполнения интерпретатором такая роскошь вынужденная).
Но чаще всего компиляторы организуют вызовы и хранение локальных переменных используя кадры стека (stack frames).

Stack frame - это такая абстракция компилятора, которая позволяет разделить части стека принадлежащие разным функциям.
В ее основе лежит еще один регистр специального назначения называемый base pointer (bp). У него 2 назначения: во-первых быть базовым адресом, относительно которого можно обращаться к локальным переменным, во-вторых хранить в себе состояние stack pointer (sp), которое было до вызова и восстанавливать его при возврате из функции.

Есть и операции в ассемблере для манипуляции с кадрами стека - call и ret.
Операция call сохраняет свой адрес инструкции на стеке и делает переход по адресу из своего аргумента. То есть ее можно заменить на последовательность push %ip и jmp arg, где arg - аргумент call, а ip - еще один регистр специального назначения instruction pointer, указывающий на адрес текущей операции.
Операция ret делает все наоборот, переходит по адресу на стеке и восстанавливает регистр ip. То есть ее можно развернуть в последовательность jmp %sp и pop %ip.

Давайте посмотрим на примере такой функции:

int func(int a, int b) {
    int c = a + b;
    return c;
}

Она может быть скомпилирована в следующий ассемблер:
func:
; сохраняем bp на стек
pushq %rbp
; обновляем bp значением sp
movq %rsp, %rbp
; сохраняем аргументы на стек
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
; складываем
movl -4(%rbp), %eax
addl -8(%rbp), %eax
movl %eax, -12(%rbp)
; возвращаем результат
movl -12(%rbp), %eax
; восстанавливаем bp
popq %rbp
; возвращаемся в место вызова
retq

Теперь ее можно будет вызвать с аргументами 1 и 2 вот так:
movl $1, %edi
movl $2, %esi
callq func

Суффикс l у операции и префикс e у регистра в x86 говорит об операции со значением размером 32 бита, суффикс q и префикс r - 64 бита, а без суффикса и префикса - 16 бит.
Метка func будет заменена на адрес следующей за ней инструкции при линковке.

Использование кадров стека позволяет производить вложенные вызовы, глубина которых ограничена только размером стека. Так же, благодаря кадрам стека мы можем произвольно обращаться к локальным переменным не ограничиваясь лишь тем, что лежит на вершине стека.

Но есть в такой модели и ограничение - компилятор должен знать размер stack frame для каждой функции, а значит размер всех ее локальных переменных, включая аргументы.

Встречаются и расширения данной модели, позволяющие обойти это ограничение, но они не так эффективны.

Как запустить 10 программ на 1 ядре CPU?

Сейчас, когда современные CPU запросто имеют 64 ядра, ядра умеют обрабатывать 2, а то и 4 и 8 потоков параллельно, а также есть материнские платы под несколько CPU, становится все сложнее представить, что не так давно были в норме однозадачные ОС.

Первые многоядерные CPU появились лишь в начале 2000х. Немногим ранее появились решения с несколькими CPU, но лишь в серверном сегменте. А десктопы могли лишь порадоваться технологии SMT, названой маркетологами Intel гипертредингом.

При всем при этом уже в 1969 году появляется ОС Unix поддерживающая многозадачность.
Бум многозадачных ОС приходится на 90е. Его породили OS/2, MacOS, Windows (которая на тот момент являлась графической оболочкой над однозадачной MS DOS) и первые дистрибутивы Linux в лице Slackware и Debian.

Проблему многозадачности первыми решили программисты, а не производители железа. Многозадачность эмитирует параллельность, для этого есть 2 основных способа:

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

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

Многоядерные CPU были вынужденной мерой. С каждым годом мы все ближе к физическому пределу производительности на ядро.
Многоядерные и многопроцессорные системы сильно усложнили планировщики. Хотя они и принесли истинную параллельность, количество одновременных задач все равно больше количества ядер. Планировщик должен по возможности загружать все ядра работой.
Кроме того, истинная параллельность усложнила и синхронизацию общих данных, которые нужны нескольким задачам. Проблема гонок данных стала более значимой, приводя к сложно отлаживаемым ошибкам. А взаимные блокировки - самая частая на сегодня причина зависания программ.

Switch Context или ода о том, что больше не всегда лучше

Вы сталкивались с таким, что вычисления распараллеленые на 32 потока работают медленнее чем те же вычисления, но на 8 потоках?
Давайте разберемся, почему так происходит.

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

Одной из самых дорогих операций в работе планировщика является переключение контекста (switch context). Контекстом в терминах планировщика является полное состояние исполняющегося потока, куда входят все регистры общего назначения и множество специальных регистров. Планировщик ОС сохраняет значения регистров в оперативную память, затем изменяет регистр CR3, хранящий физический адрес каталога страниц виртуальной памяти, что позволяет перейти в виртуальное адресное пространство другого процесса. Последним шагом восстанавливается контекст потока, который будет запущен и осуществляется переход на инструкцию на которой он был остановлен.

На первый взгляд может показаться, что switch context очень простая операция, но на деле она имеет ряд побочных эффектов.
Первой особенностью является тот факт, что процессор кэширует отображение виртуальных адресов в физические в TLB (Буфере ассоциативной трансляции), а при изменении регистра CR3 данный буфер сбрасывается. Современные планировщики учитывают данную особенность и не меняют CR3 в случае если переключаемые потоки принадлежат одному процессу.
Второй особенностью является тот факт, что инструкции и данные потока могут быть вытеснены из процессорного кэша к моменту восстановления. Частично это решается минимизацией перемещения потока между ядрами.
И последней особенностью становится тот факт, что память необходимая потоку может быть вытеснена в подкачку, что значительно замедлит обращение к такой памяти.

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

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

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

Но он уже на подходе, очень скоро опубликую материал о процессорном кэше.

Кроме того я был занят написанием статьи на хабр, которая вышла сегодня:
https://habr.com/ru/articles/768484/
Буду признателен, если почитаете и накидаете мне плюсиков🫶

Оперативная память - она быстрая или не очень?
Почему проход по массиву выполняется быстрее чем проход по связному списку, если и то и другое имеет сложность O(n)?
Почему dynamic dispatch медленнее чем static dispatch?

Настало время поговорить про процессорный кэш.

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

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

Во-первых кэш разделен на уровни, на очень старых CPU их было 2, на большинстве современных - 3, в редких топовых решениях встречается 4 уровня.
L1 самый маленький из них и самый быстрый. Кроме того он разделен на 2 части с разным назначением L1d под данные и L1i под инструкции. Это позволяет не вытеснять инструкции когда происходят промахи по данным. Когда процессору нужны данные из памяти он в первую очередь ищет их в L1, и лишь в случае промаха (данных в кэше не оказалось) смотрит в следующий уровень.
L2 имеет побольше памяти, он оказывается немного медленнее из-за отсутствия разделения инструкций и данных. L1 и L2 как правило свои на каждое ядро.
L3 и L4 (при наличии) самые большие и как правило общие на все ядра. С одной стороны это создает издержки на синхронизацию конкурентного доступа, с другой улучшает производительность многопоточных приложений с общими данными.
Если данных не оказалось ни на одном из уровней, то они подгружаются из ОЗУ. При этом они проходят уровни кэша в обратном порядке, сохраняясь там.

Второй особенностью кэша является представление данных в виде кэш линий. Кэшу необходимо хранить адрес тех данных, что он кэширует. Хранить адрес для каждого запрошенного байта не рационально. Поэтому кэш подгружает сразу блок памяти и хранит лишь его начальный адрес. На большинстве платформ такой блок равен 64 байтам, но встречается и 128 байт.
Загрузив 1 байт из памяти закешируется не только он, но и байты по соседству, соответствующие той же кэш линии.

Кроме того каждая кэш линия работает только с определенными адресами, которые в пределах уровня принадлежат только ей. Такой подход позволяет находить данные в кэше за O(1), зная адрес мы знаем номер его кэш линии. При этом данные по соседству не вытесняют друг друга, а так же можно хранить только часть адреса, освободив часть бит под состояние.

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

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

Разница между static dispatch и dynamic dispatch тоже из-за кэша. В первом случае адрес вызываемой функции находится прямо в коде, если и будет промах кэша, то только 1. Во втором случае из указателя на стеке или куче мы идем в таблицу виртуальных функций в rodata и лишь в ней находим адрес вызываемой функции.

В комментариях под предыдущим постом @ogsegu попросил рассказать про false sharing и true sharing. Тема эта очень важная в контексте производительности многопоточных приложений, однако о ней многие забывают. Кроме того непосредственно связанная с работой процессорного кэша. Так что ловите пост об этом.

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

Для начала разберемся, что такое sharing вообще.
В многопоточных программах часто встречается ситуация, когда один и тот же объект в памяти используется из нескольких потоков. Такой объект можно назвать общим (shared).
Пока потоки только читают общий объект, работа с ним будет достаточно простой. Однако, если хотя бы 1 из потоков захочет изменять объект, то понадобится синхронизация, иначе произойдет гонка данных (data race). Про гонки данных и как их избегать будет следующий пост.
А пока назовем ситуацию с общим доступом к объекту из нескольких потоков true sharing, так как такое разделение доступа к памяти делается намеренно и осознано.

Рассмотрим другую ситуацию. У нас будет 2 или более потоков, каждый из которых работает со своим собственным объектом в памяти. Так как у нас нет общих объектов, нам не требуется их синхронизация, а следовательно мы ожидаем, что наши потоки не будут тратить на нее время.
Но что если наши объекты будут расположены в памяти очень близко, настолько, что потенциально могут оказаться на одной кэш линии? Как мы помним L1 и L2 кэши у каждого ядра свои. Мы получим ситуацию, когда в L1 и L2 разных ядер окажется кэш линия кэширующая один и тот же блок памяти. И если хотя бы один из потоков начнет изменять свой объект, то соответствующие кэш линии других ядер будут вынуждены синхронизировать это изменение. Такая ситуация называется false sharing и она может ухудшить производительность наших потоков, а следовательно ее стоит избегать.

Посмотрим на false sharing на примере небольшой C++ программы:
#include <array>
#include <iostream>
#include <thread>

int main() {
std::array<int, 2> arr{1, 1};
int &v0 = arr[0];
int &v1 = arr[1];
std::thread t0([&]() { ++v0; });
std::thread t1([&]() { ++v1; });
t0.join();
t1.join();
std::cout << "0: " << arr[0] << ", 1: " << arr[1] << std::endl;
return 0;
}
Данная программа абсолютно корректна, в ней нет гонок данных. Дочерние потоки работают каждый со своим собственным объектом (int'ом), а главный читает эти объекты после завершения дочерних потоков.
Однако тот факт, что эти объекты расположены в памяти последовательно (массив это гарантирует), сильно увеличивает вероятность, что они попадут на одну кэш линию и мы получим false sharing.

На пробу сделал лонгрид в telegraph где подробно разобрал тему "Гонки данных и как с ними бороться".
Расскажите в комментариях, как вам такой формат.

Ловите очередную статью. В ней поговорим про динамическую память и про то как ей управлять. Затронем частые ошибки связанные с управлением памятью.
Заметную часть статьи я посвятил устройству аллокаторов и сборщиков мусора.

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

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

Если формат видео зайдет, то буду думать о создании youtube канала.

В статье про динамическую память упоминается такая идиома как RAII, давайте разберемся что это и зачем нужно.
RAII расшифровывается как Resource Acquisition Is Initialization или по-русски - получение ресурса есть инициализация. Идея данной идиомы заключается в передаче владения и управления некоторым ресурсом (выделенной динамической памятью, открытым файлом/устройством/сокетом, блокировкой мьютекса и т.д.) некоторому связанному объекту при его инициализации, а объект должен будет освободить данный ресурс при своем удалении.

Данная идиома значительно упрощает управление ресурсами, во многих случаях предотвращая проблему их утечек. Давайте посмотрим на простой пример:

auto ptr = new int;
// что-то делаем с выделенной памятью
delete ptr;

Помимо того, что программист может просто забыть написать delete, или случайно написать его дважды, может произойти еще более страшная вещь, выполнение кода может вообще не дойти до данного оператора из-за раннего return или брошенного исключения.
Немного исправим код:

auto ptr = std::make_unique<int>();
// что-то делаем с выделенной памятью

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

Данная идиома является основным способом управления ресурсами в языке Rust и предпочтительным способом в языке C++. Идиома может быть использована в любом языке, в котором есть полноценные деструкторы - функции/методы вызываемые компилятором в конце жизни объекта.
Однако деструкторы есть далеко не во всех языках, а в языках со сборкой мусора они практически невозможны. Предлагаемые в некоторых из них в качестве альтернативы финализаторы здесь не помогут, их вызывает GC перед удалением объекта, а сам GC работает в плохо предсказуемые моменты времени, что делает непредсказуемым время освобождения ресурса (для памяти пойдет, а вот с файлами и блокировками мьютекса могут быть проблемы).

Однако некоторые языки все же предлагают некоторые альтернативы:
- Менеджеры контекста и оператор with в Python
- Интерфейс IDisposable и оператор using в C#
- Интерфейс AutoCloseable и оператор try (...) {} в Java
- Оператор defer в Go и в Zig

Вместо послесловия, страшный сон хаскелиста:

main :: IO ()
main = do
  fileData <- readFile "file.txt"
  writeFile "file.txt" $ map toUpper fileData