Верно ли что программист не может управлять сборкой мусора

Что такое сборщик мусора в программировании

Чисто и там, где метут, и там, где не мусорят.

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

Ситуация

Когда мы пишем программы, мы обычно действуем по такому принципу:

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

Проблема

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

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

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

Решение — очистка мусора и управление памятью

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

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

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

Особенности ручного управления

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

Ручное управление идеально для систем со слабыми ресурсами и систем реального времени — там, где программа не имеет права тормозить.

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

Особенности автоматического сборщика

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

Вроде хорошо, но нет. Сборщик мусора тоже работает неидеально:

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

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

❌ Если рабочей памяти очень мало, то сборщик будет работать постоянно. Но ему тоже нужна своя память для работы. И может получиться, что сборщик, например, занимает 100 МБ, а освобождает 10 МБ. Может оказаться так, что без сборщика программа будет работать эффективнее.

Автоматические сборщики — добро или зло?

Тут у разработчиков мнения разделяются.

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

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

Что выбрать?

С выбором интересная ситуация.

Если вы пишете приложения для iOS или OSX, вам нельзя использовать сборщики мусора из соображений быстродействия.

Языки типа JavaScript и Ruby собирают мусор сами, вы об этом можете даже никогда не узнать.

В некоторые языки можно подключить сбор мусора, пожертвовав производительностью — например, в Java, C или C++.

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

Источник

Дюк, вынеси мусор! — Часть 1

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

Попробуем в нескольких статьях пройти путь от описания базовых идей, лежащих в основе всех сборщиков мусора, до разбора алгоритмов работы и возможностей тонкой настройки различных сборщиков Java HotSpot VM (вы ведь знаете, что таких сборщиков четыре?). И самое главное, рассмотрим, каким образом эти знания можно использовать на практике.

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

А оно мне надо?

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

Разделяй и властвуй

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

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

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

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

Из поколения в поколение

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

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

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

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

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

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

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

Вам быстро, дешево или качественно?

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

Традиционно, при определении эффективности работы сборщика мусора учитываются следующие факторы:

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

Memento Mori

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

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

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

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

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

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

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

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

Под микроскопом

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

Внутренние инструменты

Что касается внутренних инструментов мониторинга, то здесь мы можем либо попросить JVM выводить информацию о производимых сборках с различным уровнем детализации (в stdout или в лог-файл), либо самостоятельно обращаться к MXBean’ам, возвращающим информацию о состоянии памяти и о выполняемых сборках мусора, и обрабатывать ее как нам вздумается.

В JVM HotSpot доступны следующие опции, управляющие выводом информации о сборках мусора (это основные опции, работающие для всех сборщиков):

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

Внешние инструменты

В природе существует огромное количество инструментов, позволяющих подключиться к процессу Java и в удобном виде получить информацию о состоянии памяти и процессах сборки мусора. Это и входящие в поставку JVM HotSpot утилиты VisualVM (с плагином VisualGC) и Java Mission Control и различные инструменты/плагины для IDE и отдельные программы вроде JProfiler или YourKit и еще много чего.

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

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

В идеале, ваш инструмент должен отображать график использования памяти коматозной программой как-нибудь так:

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

А можно всех посмотреть?

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

Как уже было сказано, описанные выше принципы сборки мусора являются общими для всех сборщиков. Но при этом между сборщиками существуют и заметные различия, проявляющиеся в ответах на следующие вопросы:

Java HotSpot VM предоставляет разработчикам на выбор четыре различных сборщика мусора:

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

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

Concurrent Mark Sweep (CMS) — нацелен на снижение максимальных задержек путем выполнения части работ по сборке мусора параллельно с основными потоками приложения. Подходит для работы с относительно большими объемами данных в памяти.

Garbage-First (G1) — создан для постепенной замены CMS, особенно в серверных приложениях, работающих на многопроцессорных серверах и оперирующих большими объемами данных.

В следующих статьях мы детально рассмотрим каждый из этих сборщиков, стараясь придерживаться общего плана: краткое описание, принципы работы, ситуации STW (это stop the world, если успели забыть), способы настройки, достоинства и недостатки. Получив эти знания, мы посмотрим, что с ними делать в реальной жизни.

Источник

Сборщик мусора на С++

Привет, Хабр! Эту статью я задумал довольно давно. Речь в ней пойдет о простейшем копирующем сборщике мусора на С++. У него довольно много ограничений (часть не мешает, часть можно обойти, если задаться целью написать какую-то серьезную библиотеку, а для кое-чего неплохо было бы заиметь зачаточную поддержку от языка), зато и кода в нем чуть больше 100 строк. Заинтересовавшихся прошу под кат. Там минимум ООП, простейшие шаблоны и жуткие магические ритуалы с указателями.

Начнем с начала. Что такое сборщик мусора и для чего он нужен?

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

Сборщики мусора бывают двух видов — консервативные и копирующие.

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

Для решения этой проблемы — фрагментации кучи – придуман второй тип сборщиков — копирующий. До поры до времени, его стратегия борьбы с мусором — созерцание. Когда же его становится слишком много, он делает следующее:
1. Копирует все нужные данные в другую область памяти.
2. Меняет все указатели на актуальные.
3. Освобождает всю память, которая уже не используется.

Сразу уточню, что я не смотрел вплотную ни одного алгоритма сборки мусора, ни как работают «взрослые» библиотеки GC для С++. Вероятно, у алгоритма, который я сейчас опишу, есть название, возможно, именное, но в тут я обойдусь без ссылок на источники.

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

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

Во-вторых, сразу после заголовка, и нигде более, должны идти все указатели, которые также относятся к сборщику мусора. Соответственно, в gcData[REF_COUNT] будет хранится их количество. Это одно из ограничений, которое накладывает моя реализация. В gcData[STRUCT_SZ] будет храниться размер структуры в байтах. Назначение указателя я раскрою позднее. Что удобно, размер структуры оказался равен размеру указателя (сейчас 2014, народ!).

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

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

В классе нужно переопределить кучу операторов — разыменования, присваивания, etc, но этим появится смысл заниматься не раньше, чем со мной свяжутся парни из Boost Foundation.

Вспомогательные структуры готовы. Можно перейти к выделению памяти.

Классной фичей такого способа управления ресурсами является именно способ их выделения. Стандартному аллокатору С++ приходится после каждого delete обновлять списки свободных блоков, а после new находить среди блоков подходящий, потом дробить его на два мелких блока, а потом что-то еще, что там делают современные аллокаторы. В случае сборщика мусора, операция delete просто не нужна, так что вся занятая память будет идти одним сплошным блоком. Чтобы создать новый объект, нужно всего лишь увеличить размер этого блока, т. е. сдвинуть один указатель. Простая операция, которая выполняется за O(1). Реально перестало это казаться такой уж замечательной идеей, из-за того, что провоцирует кучу сборок тогда, когда можно было бы просто переиспользовать уже не нужную память, но пока можно остановиться на этом.

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

firstChunk — начало списка, currentChunk — последний созданный блок памяти. сurrentOffset — начало свободного сегмента памяти относительно currentChunk.

Здесь неочевидных моментов уже больше. Разберем 12-ую строчку.
На этом этапе нам удобнее не думать о том, какой именно тип у нового объекта. Мы точно знаем, что у него есть наш gcHeader, и этого пока достаточно.
После того, как мы выделили память для нового объекта, нужно инициализировать его заголовок. Что может означать загадочное присваивание

Для этого снова посмотрим на определение заголовка

Ключевое слово union означает, что и массив gcData и указатель post_gcAddress располагаются по одному адресу. Это полезно для экономии памяти, но проблема в том, что С++ не запоминает, как данные в union использовались в последний раз — как массив, или как ссылка. Помогает такая особенность архитектур процессоров, как необходимость выравнивания данных.

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

Тут — то же самое. Если младший бит равен единице, то эти восемь байт — гарантированно массив из двух int. Можно, например, использовать еще один бит, чтобы указывать сборщику мусора, что-то типа «это ссылка на полиморфный объект, у него есть указатель vtable, не затри его».

Ну и небольшая обертка над функцией, чтобы использование аллокатора не вызывало особой боли.
Тут следует поставить emplace new, чтобы корректно инициализировались объекты с конструкторами. Как видно, класс объекта, который мы хотим создать, должен иметь статическую константу refCount. Её можно вычислять автоматически с помощью внешнего препроцессора. В противном случае, я вижу тут как минимум три способа отстрелить себе ногу.

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

Пора посмотреть на реализацию самой сборки мусора.

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

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

А теперь просто освобождаем ненужную память.

Обратите внимание, delete вызывается только для больших блоков памяти. Таким образом, деструкторы объектов в сборщике мусора никогда не будут вызваны. Это не проблема для классов, у которых деструкторы только освобождают память, но нет возможности, например, автоматически закрывать соединения и файловые дескрипторы. Mark & Sweep-алгоритмы могут помочь с этим, но и писать их сильно сложнее.

Последний штрих — функция gcMove.

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

GC выделяет объекту нужное количество памяти в новой куче (он знает, сколько, из заголовка) и копирует все данные из старой инкарнации в новую. Потом он пишет новый адрес объекта в старый заголовок. Теперь, если на объект указывает несколько ссылок, алгоритм сможет определить, что объект уже один раз перемещался (младший бит, гарантированно, 0) и не станет копировать его лишний раз впоследствии. Осталось перенаправить старый указатель на новую копию объекта.
Теперь, нужно разобраться с указателями, самого объекта. С ними нужно сделать то же самое. Строчка

получает указатель на первую ссылку в структуре (если она есть, конечно). Помним, что sizeof(gcHeader) == sizeof(void*). В противном случае, это будет занимать на пару строк больше.
Что делать дальше, вопрос уже спорный. Я просто для каждого указателя рекурсивно вызываю функцию gcMove. Такой алгоритм соответствует обходу графа в глубину. Однако, это не лучший выбор.
Киллер-фича копирующих сборщиков мусора для меня — это возможность поддерживать локальность по ссылкам. Если коротко, объекты, которые ссылаются друг на друга, и в памяти тоже должны находиться как можно ближе. Так процессор сможет эффективнее использовать свою кэш-память.

Мой GC такого не умеет. Я выбрал обход в глубину из-за простоты. Желательно перемещать объекты в порядке обхода в ширину. Будет совсем здорово заморочиться и выстраивать объекты в памяти в соответствии со статистикой обращений к ним, как в этом алгоритме, чтобы добиться оптимального количества промахов.

На этом всё. Осталось продемонстрировать работу со сборщиком.

В качестве примера возьму простейшее дерево поиска.

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

Обычное добавление в дерево. Обратите внимание, как используется gcAlloc.

stFind возвращает ссылку на поддерево с нужным ключом, stPrint распечатывает ключи и адреса поддеревьев, stCut обрезает поддерево, в котором хранится искомый ключ.

Как видно работа со структурами для программиста особо не меняется. Что тут происходит:
1. Мы произвольно заполняем дерево поиска.
2. Создаем еще одну стековую ссылку на один из элементов, чтобы проверить, как GC реагирует на множественные ссылки на один объект.
3. Распечатываем дерево, additionalReference и currentOffset.
4. Вхолостую вызываем сборку мусора.
5. Снова распечатываем дерево. Все указатели, которые нужны — поменялись.
6. Обрезаем одно поддерево и снова вызываем сборку мусора. Всё снова работает как надо. Обратите внимание currentOffset уменьшился, а корень дерева вернулся на тот же адрес, по которому находился в первый раз.

Выводы

Итак, в С++ можно использовать Garbage Collector. Причем, вполне себе симпатичный, на мой замыленный взгляд, да еще и с минимальным оверхедом. Попробую перечислить всё, что нужно сделать, чтобы он был действительно удобным и полезным.
Сначала — организационные моменты.

1. Глобальные переменные — это, конечно, совсем не клёво. Нужно всё оформить как человеческий класс и\или аллокатор С++.
2. Заставлять в каждый класс вставлять хедер — почти садизм. Нужно просто давать отнаследоваться от абстрактного класса, у которого должны быть два метода — getSize и getLayout. Последний должен возвращать ссылку на массив, в котором хранятся относительные координаты всех указателей (затея с «все ссылки стоят начале» ну совсем не годится для чего-то серьезного). Этот массив однозначно должен заполняться автоматически, но я пока что не представляю, как это можно реализовать.

Следующий вопрос — автоматическая сборка. Когда выдвинули саму идею GC, никто не подразумевал, что кто-то реально будет постоянно вызывать что-то вроде функции gcCollect, всё должно происходить само по себе. Но С++ — особый случай. Он славится тем, что весь поток выполнения под носом, или, по крайней мере, предсказуем. Своенравный Garbage Collector любого другого языка здесь — это практически идеологическое преступление. Так что, у него должно быть как минимум два режима:

1. Прозрачный.
2. Бросок исключения после исчерпания некой квоты памяти. Тут уже программисту решать — убраться или выделить память форсированно.

И еще один вопрос. Многопоточность. Тут всё плохо. Чтобы начать сборку мусора, нужно приостановить все потоки, чтобы ничего не сломать. В итоге придется написать половину JVM. Самым лучшим решением мне кажется его отсутствие. Для каждого потока можно просто создавать свой выделенный GC, а если понадобится передать что-то другому подпроцессу, то обычные shared_ptr никто не отменял. Без разделяемой памяти жить, как правило, гораздо веселее.

Закончим на печальной ноте. Такой сборщик мусора тотально несовместим ни с одной готовой библиотекой. Их объекты не смогут предоставлять необходимые данные. Несмотря на то, что std::list, std::map и std::set только выиграют, если переписать их специально под GC, переделывать N гигабайт исходников Boost, например, совершенно бесперспективно. Однако, для борьбы с фрагментацией в случае маленьких объектов, мне такая штука кажется очень даже полезной.

Источник