12.02 Основы Программирования

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

Мы вспомнили, что есть аллокаторы, мы обсудили уже, какие они бывают, три разных. И там много логики в malloc, а тем более в какой-нибудь планировочной логике у нас что-то там выделяется, но всё равно не сложно. А стековый аллокатор очень хороший, просто добавим туда неудобную, лишнюю логику. И поэтому, когда у нас уже стековый аллокатор реализован аппаратно, есть какой-то регистр, [неясный фрагмент] а соответственно у нас есть аппаратная [возможная ошибка распознавания: радиаторская кровавая карта], мы можем ей пользоваться. Значит, есть языковые расширения, не совсем как в русских языках, это расширение для того, чтобы на каких-то машинах с какого-нибудь языка я всегда мог ими воспользоваться. Ну вот, я зашел, я в процедуру заезжаю, я хочу больше места на стеке, [возможная ошибка распознавания: молоко на стеках], потому что он сам всё почищает, когда мы будем выходить оттуда, это происходит автоматически. Соответственно, при ручном выделении и освобождении [неясный фрагмент].

Переходя к технической части, висячие указатели (dangling pointers) — это ситуация, когда указатель указывает на свои данные, а там уже не его данные. Это на самом деле undefined behavior, то есть абсолютно некорректная ситуация. Чтение оттуда, даже просто чтение, опасно, потому что эта страница памяти может уже [неясный фрагмент] быть не замаплена [возможная ошибка распознавания: замаханный], то есть может быть вообще неизвестно что [неясный фрагмент].

Есть ИММУ [возможная ошибка распознавания: имеется в виду единица управления памятью или схожий механизм], которая нужна в случае, если у нас сложная логика. [неясный фрагмент] Если вы до момента, когда в области высокопроизводительных вычислений вы просто вдруг выбиваете переменную [возможная ошибка распознавания], то это приводит, ну, даже если это локальная переменная, [неясный фрагмент]. Во-первых, [неясный фрагмент] ненужный, неиспользуемый [неясный фрагмент]. Во-вторых, лучше один раз написать лишнее в том самом случае, когда это поможет отловить ошибку [неясный фрагмент]. [неясный фрагмент] программа, для этого нужно с памятью работать [возможная ошибка распознавания]. Будет очень сложно, потому что достаточно сложно [неясный фрагмент], которая приводит к ошибке.

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

Светлая идея заключается в том, что управление должно быть прозрачным и помогать избегать типичных ошибок, связанных с неаккуратной моделью владения ресурсами. Проблемы возникают тогда, когда появляется некорректно используемый указатель, когда нет понимания, кто является хозяином ресурса, когда возникает путаница и каждый не освобождает то, что добыл, либо когда у объекта оказывается два хозяина («два господина»), и каждый пытается решить проблемы дизайна и повышения владения по-своему. В архитектуре всегда нужно аккуратно исследовать вопрос владения ресурсом: кто главный, кому передается владение, поскольку у объекта должен быть один хозяин, который все почистит.

Существует и разделяемое владение, но с ним значительно сложнее работать. Обычно за ресурс отвечает кто-то один, и он может передавать владение — это работает хорошо. Когда же владение разделяется одновременно несколькими сущностями, возникают проблемы висящих указателей либо многократно освобождаемой памяти, так как каждый считал себя главным и пытался выполнить освобождение. Если мы хотим избавиться от явного удаления, то сам деаллокатор [...]

Если избавиться от явного удаления, то сам аллокатор — мы об этом говорим в контексте аллокаторов, которыми мы занимаемся — имеет две части: как выделять и как освобождать. И это освобождение оно решает какую-нибудь проблему, потому что существуют две проблемы. Первая проблема, которую мы всегда обсуждаем в аллокаторах — это какая задача?

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

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

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

Далее рассматривается аллокатор, который умеет работать назад, если у нас есть гарантия обращения. Линейный аллокатор на самом деле используется, например, в виде пула, когда мы знаем, что в этом куске программы будем очень-очень много отводить память, поэтому выделяем её последовательно и не удаляем по отдельности. Зачастую выделяется целый массив, то есть мы создаём пул и как-то активно используем память, вообще забывая про освобождение. Если памяти пул-ка [возможная ошибка распознавания: пула] и мы знаем, что нам её хватит... Она не динамическая, то есть она линейная, она не «жаркая» [возможная ошибка распознавания: сжатая / шагающая]. Возникает вопрос: «Сколько я этим могу? Сколько я этим [неясный фрагмент]? Достаточно ли 1000 элементов? Это 1000 умножить на $N$ элементов. Окей». Мы выделили его, внутри него только аллоцируем, потом целиком освободили. В общем, линейный — это самый-самый примитивный аллокатор, но он используется, он бывает, как мы знаем из системного программирования, то есть когда нам надо предсказать [поведение] и необязательно делать [сложные операции освобождения], потому что [всё выделили] и всё разом освободили.

Также числятся ресурсы для завершения процесса. Декадата [возможная ошибка распознавания: стековая структура или декремент] — это и есть линейный алгоритм. Что бы там внутри процесса ни происходило, операционка дала ему стоп. Он еще чуть-чуть просил, а потом все целиком у процесса освободилось. Это математически та же самая информация. Ясно? Близко, да?

Итак, самый базовый автоматический [способ выделения памяти], который мы интуитивно прозрачно используем и сами того не замечаем, — это локальные переменные, обратный стек [возможная ошибка распознавания: стека вызовов]. Он автоматически сам чистит то, что не нужно. Классная вещь, пользуйтесь.

Для той эпохи очень приятный язык. Там просто [неясный фрагмент] сказал две другие вещи. Для того чтобы понять красоту [неясный фрагмент] механизма, [неясный фрагмент] частоты и мегабайта оперативной памяти, ну мы дождались тех времен, уже в 80-х. И второе, что развивает людей, почему нужно было всем этим заниматься — потому что в дизайне языка изначально была модель использования рекурсии [возможная ошибка распознавания: эксперимента] и очень большого количества динамических аллокаций, малых объектов и т.д. Просто надо было сделать автоматический аллокатор какой-то, [неясный фрагмент], который будет по ходу выполнения программы что-то подчищать. И он, считайте, что он входит в термин garbage collection [возможная ошибка распознавания: «дампич» — «мусор»].

Термин «мусор» (garbage) исторически восходит к понятию «дампич» (dumpich). Мусором называется объект, который не будет использоваться в дальнейшей работе программы. Суть сбора мусора заключается в том, что в определенный момент, когда требуется память или когда у процессора появляется свободное время, система ищет все объекты, которые точно больше не будут использоваться, и освобождает занимаемые ими участки памяти. Идея эта проста и прозрачна.

Рассмотрим гипотетический язык программирования, где есть механизм динамического выделения памяти в куче — аналог malloc или new. Куча — это область памяти, позволяющая размещать произвольные объекты в произвольном порядке. Пусть у нас есть простая программа с выделением объекта. Возникает вопрос: является ли объект мусором в определенной строке программы (например, в третьей и ниже)?

В ходе обсуждения со студентами рассматривается вопрос о том, будет ли переменная использоваться дальше. Студент отмечает, что значение может не использоваться напрямую для вычислений, но указатель на него передается в качестве аргумента функции, сохраняется в регистре или на стеке. Поскольку речь идет об аллокации объектов в куче, у нас есть указатель, указывающий куда-то в кучу. Мы используем адрес (неважно где — в регистре или на стеке), чтобы обратиться к памяти. Будет ли эта переменная точно использоваться? Ответ зависит от логики программы и от того, удастся ли доказать условие выполнения ветвления (например, с помощью распространения констант — constant propagation). Если компилятор сможет доказать, что условие в ветвлении (например, if (платформа Windows)) всегда истинно, то он сможет доказать, что определенный ветвящийся код является мертвым кодом (dead code), и удалить его. Однако конструктор объекта может иметь побочный эффект (например, печатать что-то на экран), поэтому полностью убирать создание объекта нельзя. В общем случае точно ответить на вопрос, будет ли объект использоваться в дальнейшем, нельзя.

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

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

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

Наша задача — научиться определять объекты, на которые больше нет ссылок. Во-первых, нам надо уметь знать про ссылки: есть ли она, куда указывает, на какой объект. Ибо объект должен иметь первый принцип памяти, должен сказать истинный доступ. Что сделаем в данном случае с памятью? Положим еще один принцип памяти, где будет указано количество ссылок на объект. Когда мы выделяем блок памяти, мы пишем системную информацию и отдаем пользователю текст.

Вот это то, как устроены Swift, Objective-C, Python и многое другое. Это reference counting (подсчет ссылок), он бывает автоматический (automatic reference counting) или ручной (manual reference counting), но главная идея — счетчик ссылок. Здорово, если есть языковая проверка, как в Питоне. То есть, когда вы присваиваете одну переменную в другую, вот здесь мы увеличиваем счетчик, ну и соответственно меняются переменные адреса. Это вот обычный Питон пытается сделать. Ну там не обязательно переменные именованные, это просто любое значение, которое в Питоне создается. Вот написали в скобочках значения, создали объект. Если мы писали строка за строкой в скобочках, то это бы уже создало размещение для первой строки, размещение для второй строки. И как это было в скобочках? Кортеж был, притом.

Reference counting основывается на том, что мы должны узнать, что произошло с ссылкой. Если у нас появилась вторая ссылка на объект, нам в этот момент надо обязательно увеличить счетчик. Банально, если мы выделяем какой-то аргумент, мы выделили этот кусок памяти, потом создали копию, присвоили переменной a, и потом вызвали функцию, где используется b, и b больше не используется, но у нас должны увеличиться ссылки. То есть на первой строке мы создали объект, на второй строке мы его скопировали, на третьей, на самом деле, мы, скорее всего, еще скопировали b как аргумент функции. У нас может быть в тот момент три указателя на эту область памяти. А потом, когда мы выходим из области видимости z, у нас один из этих указателей исчезает, так как мы вышли из z, здесь мы ставим индикатор, что b больше не используем, соответственно, мы убираем z, и там происходит минус один. На конце блока для b тоже будет минус один, а вот самое базовое присвоение останется, будет только счетчик уменьшен.

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

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

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

Чтобы избежать подобных проблем, необходимо менять последовательность действий. Сначала следует корректно увеличить отметку счетчика (сказать, что появилась еще одна ссылка), и только потом заполучить её на кадре стека как конкретное число. То есть нужно обязательно увеличить захват — правильно проинициализировать указатель в момент захвата. Если этого не сделать, ресурсов может не хватить или возникнет повреждение данных. К этому вопросу мы вернемся дальше, так как с этим связаны и другие архитектурные особенности.

И еще, конечно, есть вот такая прелесть. Можно ли получить такую структуру данных, в которой ссылки как-нибудь так расположены? Например, можно ли написать, когда это случится? Когда ссылки образовывают цикл, когда они делаются: одно ссылочное, другое — это сюда, это сюда, это сюда. Массив указателей, может быть? Массив указателей и что с массивом указателей? Ну в плане у нас получается массив будет указатель на первый элемент, а в элементах будет лежать указатель на... А зачем? Нет, можно. А зачем это вы сможете, да? Типа массив, типа вот звездочка, внутри которой выходят сюда ямки. Вот, то есть можно это выносить.

В целом, в жизни бывают такие специфические структуры данных: нам надо буфер на зацикленную очередь просто вставлять и читать сначала континуум. Бывает иерархическая структура сложная, ну там у вас список состоит из узлов, а деревьев, это там, а вам надо ссылку на начало документа. Представьте модель данных любой серьезной системы, да включая текстовый документ. Например, символ нужно знать, как мы ссылаемся на какой-нибудь тег, [возможная ошибка распознавания: а теги ссылаются] на основной документ, потому что они описаны внутри документа, и там какая-нибудь идет внутренняя структура так или иначе получить. То есть любая серьезная [неясный фрагмент] вот такой, ну как следствие, помните, что баз данных без ссылок никак не будет с этими структурами данных. Парсинг. Может быть на этот вопрос вы сможете ответить: что ему мешает? Ладно, пойду к последнему моменту.

Что мешает счетчику ссылок работать с этими структурами данных? Что там, если мы захотим вот здесь сказать, что эта ссылка больше не нужна, но у него счетчик равен единице, и они когда не умеют... Если мы скажем, что он больше не нужен, то все равно остается входящая ссылка на то, когда мы уменьшаем. То есть, если мы смогли замкнуть туда [цикл], мы никогда не сможем ее очистить. И есть такая проблема, с этим надо уметь работать. В принципе, можно так. Может быть, надо рассказать про слабые указатели, но да ладно, об этом потом. Итак, одна из проблем — это... А где... А! Ладно, хорошо. Вот. Ну и соответственно, анализируя этот репутационный проект [возможная ошибка распознавания], стоят ли там циклические ссылки, требуют доступа. После разработки одного из этих компонентов решения, так только блок, если завести вот простые функции, или компилятор будет при использовании объекта составлять вот эти функции: rc_increment, rc_decrement, что делается в CWT [возможная ошибка распознавания], то все равно будет [неясный фрагмент]. И это надо как-то решать в архитектуре или в бюджетах. Есть эти варианты. Вторая проблема, которая есть еще с осуществлением производительности, она очень серьезная. У...

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

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

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

Если попытаться решить проблемы производительности подсчета ссылок, можно изменить подход: делать изменения не сразу при каждом копировании указателя, а отложить их, а потом дружно посчитать суммарное изменение для всего блока — кому сколько надо. Например, мы удалили все локальные ссылки в функции, а потом разом обновили счетчик главного объекта. Мы не будем каждый раз трогать его счетчик при передаче ссылки внутри функции, нам достаточно того, что объект не будет удален во время выполнения этой функции, пока мы удерживаем хотя бы одну ссылку. Если реализовать все эти усовершенствования на уровне типов, мы в итоге придем к тому, что называется tracing garbage collection, то есть к трассирующему сборщику мусора.

Мы приходим к тому, что называется трассирующий сборщик мусора (tracing garbage collector). Если посмотреть на наши структуры данных, мы понимаем, что объекты ссылаются друг на друга, образуя нециклические или циклические структуры, где ссылка указывает на другой объект, позволяя переходить дальше по памяти. Эти стрелочки существуют и мы их видим.

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

Для реализации этого используется метод трехцветной маркировки (tri-color marking). Объекты делятся на три цвета: черные, серые и белые. Черные — это объекты, которые мы проверили, они используются, и на них больше не ссылаются неопробованные объекты (или, как поясняется далее: черные могут быть проверенные, но не используемые, хотя мы не можем доказать, что они не используются). Серые — это те объекты, которые мы доказали, что они используются в дальнейшем (или к которым есть доступ), но пока не доработали, недообошли, недокрасили в черные, чтобы потом освобождать. Белые — это объекты, которые еще не были проверены (непробитые), кандидаты на удаление.

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

Обход начинается с корневого множества (root set) — тех объектов, которые гарантированно используются напрямую (например, локальные переменные в стеке, глобальные переменные). Если множество серых объектов оказывается пустым, то есть у нас больше нет объектов, требующих обработки, процесс завершается.

Когда в программе вызывается одна функция, затем вторая, третья, стек растет вперед, а при возвращении — идет назад. И если очистить те объекты, на которые есть ссылки из стека, то можно поломать корректность программы.

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

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

Рассмотрим подробнее корневое множество (root set). Оно состоит из глобальных переменных и стеков всех потоков, потому что элементы в стеке содержат ссылки, и аргументов вызова, на которые у нас есть ссылки. Начинаем с этого набора — это будет наше серое множество. Эти объекты куда-то ссылаются, а значит, сами объекты должны остаться, но те объекты, на которые они ссылаются, тоже, возможно, должны остаться.

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

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

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

Обход графов и поиск путей тесно связаны с базовыми алгоритмами, такими как обход в глубину и обход в ширину, которые изучаются в рамках специальных курсов, поскольку эти концепции требуют понимания и умения их применять. Когда в процессе работы программы возникает нехватка памяти, в определенный момент программа останавливается, чтобы посмотреть, какие данные оказались лишними. Это явление называется Stop-the-World — термин, описывающий остановку работы программы сборщиком мусора.

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

В качестве примера языка с таким поведением можно привести Python. Python работает по принципу stop-the-world: когда системе нужно что-то почистить, она тормозит работу программы и не обходит граф объектов в параллельном потоке. Программный код выполняет выделение и освобождение памяти, и в определенный момент, когда объем выделений достигает определенного порога, запускается сборщик мусора. Программа на время останавливается, происходит очистка памяти, после чего выполнение кода продолжается. Хотя Python не предназначен для работы в условиях жестких требований реального времени и не имеет сложных фоновых сборщиков мусора с предсказуемой задержкой, такое поведение делает его реализацию проще. Из-за особенностей работы с памятью в любой момент выполнения программы может произойти сборка мусора, остановится основа программы, очистится мусор, и выполнение продолжится дальше.

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

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

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

Многие идеи возникают как следствие результатов аккуратных экспериментов. Например, разные программы имеют разные логические модели работы с памятью: кто-то создает много объектов, а потом всё раздробливает, а кто-то создает долго используемые структуры, а в конце удаляет сразу большой объем. Если проанализировать программу по факторам использования памяти — учитывая размер выделяемых структур и реальное время окончания их использования — появляется несколько интересных статистически обоснованных гипотез.

Например, по-моему, все циклы выполняются либо 20, либо 100 раз, либо бесконечно. Все это значительные абсолютные части. То есть ваш программный стандарт: ваш программный цикл он всегда будет по небольшому чему-то, либо по всему вашему списку — ну там, распечатать список чего-нибудь. Этот цикл будет идти по списку, а бывает какая-нибудь небольшая структура данных, ну что-нибудь по массивчику, размер массива известен. В общем, есть много таких паттернов в управлении памятью, они статистически обосновываются и работают для очень частых вызовов памяти. Если мы их учтем в сборщике мусора, то есть в управлении памятью, то мы можем сделать что-то интересное.

Например, если это старая инфантильная гипотеза (или гипотеза о возрасте объектов), тут есть очень понятный паттерн с высокой «магической смертностью». Суть в том, что вспоминайте ваш код: у вас есть какой-нибудь положенный блок, положенный цикл. Вот тут объявили, вот тут переменная, вот тут адрес, вот тут список, туда-сюда, все в кучу и все. Поработали, вышли из этой области видимости, и вам эти данные уже скорее всего долго не доживут.

Суть в том, что просто тот, кто только что родился, скорее всего сейчас живет в куче. Представляете, сколько? Нам надо всю память... Вот вы кучу выбираете, а там каждый объект, короче, там крутит, крутит, крутит... Ну вот там всё куча, куча и куча, они вот так вот уважительно взаимосвязаны. Очень много сканируют. И можно тех, кто недавно появился, держать в специальной области памяти [возможная ошибка распознавания: в пустыне памяти], без имени даже, просто почему? Потому что большая часть из них реально не нужна дальше. А если они нужны, то мы их берём, переносим в другую область и говорим, что ты будешь жить дальше. Это и есть идея инфантилизма (инфантильная гипотеза), хотя корректно называть это ephemeral GC или generational GC (поколенческая сборка мусора). Но это старый уровень терминов, и исторически это называется идеей инфантилизма.

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

Бывают и другие подходы к управлению памятью. Возможно, управление памятью может строиться не на трейсинге (tracing garbage collection) и не на подсчете ссылок (reference counting), который бывает ручной, а бывает автоматический.

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

Region-based memory management (или арены) — это другой принцип управления памятью, [неясный фрагмент] расстроен как раз в деловом интернете. Давайте посмотрим.

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

Python — это такая мультимедиа [возможная ошибка распознавания: jump], если бы кто-то на коленке в 91-м или 93-м году не дочитал статьи о сборке мусора в Smalltalk, о проблемах в языках и прочего, взял бы язык, похожий на Smalltalk, и сделал как [неясный фрагмент], получился бы Python. Вот он и получился где-то тогда.

Вы уже владеете технологией и понимаете, почему область называется Eden — потому что там рождаются, [неясный фрагмент]. Это специальное пространство, куда попадают вновь созданные объекты в Java. Всё, что Java-машина выделила в памяти, все новые объекты появляются там.

Соответственно, все новые объекты оказываются в Eden. А следующие пространства называются Survivor, то есть выжившие. Лектор отмечает, что название претерпевало изменения с точки зрения политкорректности, но исторически закрепилось именно такое наименование.

Итак, соответственно, взрослые и выжившие [неясный фрагмент].

На выставленной картинке, взятой из статьи, показывается, чем отличается Compaction от Copying. В случае Compaction происходит следующее: определяется, что не нужно, очищается память от всего ненужного (метод sweep), а затем объекты реально перетаскиваются. Поскольку мы знаем, кто ссылается на тот или иной объект, так как мы трассировали эти переходы по графу, мы можем просто вернуться и поменять ссылки у подлинных объектов. Это первая идея.

Вторая идея заключается в создании копии. Мы заранее резервируем пространства s0 и s1, и сначала будем выделять все объекты в s0, а когда станет чисто в s0, всё скопируем в s1. Когда станет чисто в s1, мы, например, можем скопировать обратно в s0. Это уже другой подход к работе с объектами.