Необходимость уложить сборку мусора в 10мс накладывает принципиальные ограничения на количество объектов в куче.

ничего подобного, просто надо проводить очистку в несколько этапов.

http://www.google.ru/search?hl=ru&newwindow=1&client=firefox&hs=7R9&rls=org.m...

(den73)

> ...пока они не поменялись ролями. И когда они меняются, то новый мастер остается с невыполненными операциями

Они должны меняться только при пустом журнале.
Я придумал другой вариант. Существует два процесса, W - рабочий, M - моделирующий. Процесс M ничего не вычисляет, но мы дублируем в нём все действия по выделению памяти, созданию и модификацию ссылок между объектами. Эта информация передаётся из W в M через поток (stream) S1. Процесс M имеет идентичную процессу W карту памяти, но всё происходит в нём с некоторым отставанием, а строки и числа могут быть забиты мусором. Однако, состояние ссылок процесса M (включая адреса памяти) идентично состоянию процесса W в каком-то моменте прошлого. Если объект стал мусором, то он навсегда остаётся мусором, поэтому, если в M объект определён как мусор, то он заведомо является мусором и в W. Сборка мусора (не знаю, как называется та сборка, которая находит мусор и удаляет его, а живые объекты не трогает) запускается только во процессе W. Результаты этого процесса, т.е., действия «удалить объект Х» и «переместить объект Х из адреса А в А1» регистрируются и пишутся в поток (stream) S1. W читает S2 в свободное от работы время и выполняет соответсвующие действия. При этом, в W вообще нет самого длинного этапа работы - сканирования корней, который составляет, как я понял, основную долю задержки во всех алгоритмах сборки мусора. Поэтому, кванты времени, выделяемые в W, могут быть очень малы. В момент, когда в M происходят атомарные этапы сборки мусора, W продолжает работу, а поток S1 в это время накапливается в буфере.

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

Нам понадобится двухкратный объём памяти плюс объём буферов, способный вместить данные о выделении памяти за время сборки мусора плюс резерв на то, что M выявляет мусор с некоторой задержкой по отношению к W. Также понадобятся ресурсы на обслуживание потоков S1 и S2.


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

очепятка! Результаты этого процесса, т.е., действия «удалить объект Х» и «переместить объект Х из адреса А в А1» регистрируются и пишутся в поток (stream) S2 (а не S1).

И ещё одна опечатка - сборка мусора запускается только в процессе M. Если кто-нибудь что-нибудь понял, то напишите, если нет - тоже напишите :-)

>> ...пока они не поменялись ролями. И когда они меняются, то новый мастер остается с невыполненными операциями

Они должны меняться только при пустом журнале.

Тогда зачем вообще журнал?

Результаты этого процесса, т.е., действия «удалить объект Х» и «переместить объект Х из адреса А в А1» регистрируются и пишутся в поток (stream) S1. W читает S2 в свободное от работы время и выполняет соответсвующие действия.

То есть ты хочешь вынести сборку мусора в другой процесс. Это не прокатывает по двум простым причинам: 1) во время сборки мусора в M работа в W продолжается, и результаты сборки мусора в M становятся неприменимы (между записью в S2 и чтением S2 неизбежна какая-то пауза); 2) думаю, ты не сможешь вкрячить результаты сборки мусора в процессе M в процесс W.

Нам понадобится двухкратный объём памяти плюс объём буферов

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

Сcылка, данная анонимусом - по-моему, они не сделали ничего существенного

Ссылка анонимуса - это обзор техник, используемых для сборки мусора в около-RT-задачах, по состоянию лет на 15 назад. Она необходима хотя бы для понимания основ и терминологии.

(den73)

> Тогда зачем вообще журнал?
Без него В/В будет происходить дважды (если ведомый процесс будет честно вызывать ф-ии В/В) или же нельзя будет синхронизировать процессы (т.к. ведомому процессу будет неоткуда узнать результат функций В/В).

во время сборки мусора в M работа в W продолжается, и результаты сборки мусора в M становятся неприменимы (между записью в S2 и чтением S2 неизбежна какая-то пауза

Да, похоже, тут не всё гладко, но мне кажется, что можно выкрутиться. Какие могут быть варианты?
1. Объект X в W стал мусором в момент t0. Пусть M дочитал S1 до t0, потом запустил сборку мусора. Объект X остался мусором в W (по определению мусора), значит, W не трогал этот объект. Значит, если M пишет в S2 free(X), то всё нормально.
2. Происходит перемещение X в порядке дефрагментации живых объектов.
Это проявляется в перемещении самого объекта X и перемещении всех указателей на него. Здесь действительно есть неприятность, потому команда memmove приходит в W в момент t1>t0, а за это время W мог наплодить новых ссылок на X. И если делать всё «в лоб», то новые ссылки начнут указывать в туман. Однако, в Metronome применён для дефрагментации объектов forwarding pointer. В этом случае, дефрагментация, по сути, сводится к копированию объекта. Потому что мы сначала принимаем решение дефрагментировать объект X и создаём для него копию Y. Потом мы делаем X.forwarding_pointer=&Y. При следующей сборке мусора мы заменяем все указатели на X в куче указателями на Y. После этого X становится мусором. Остаётся лишь правильно разделить эту работу между W и M. И вроде бы это понятно, как сделать: M выявляет, что объект подлежит дефрагментации, отправлят команду W. W создаёт копию и меняет forwarding_pointer. Остальное делает M. При этом, переговоры между M и W о дефрагментации проходят за несколько циклов чтения/записи S1 и S2.

(den73)

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

> Если я правильно понял, то узкое место всех сборок мусора - это сканирование корней, которое должно происходить при остановленном процессе.

Точнее, его считали одним из узких мест 15+ лет назад, с специальными оговорками для RT :)

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

Нет. Скорее, оно пропорционально размеру стека и области глобальных переменных.

>> во время сборки мусора в M работа в W продолжается, и результаты сборки мусора в M становятся неприменимы (между записью в S2 и чтением S2 неизбежна какая-то пауза

Да, похоже, тут не всё гладко, но мне кажется, что можно выкрутиться.

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

действительно есть неприятность, потому команда memmove приходит в W в момент t1>t0, а за это время W мог наплодить новых ссылок на X. И если делать всё «в лоб», то новые ссылки начнут указывать в туман. Однако, в Metronome применён для дефрагментации объектов forwarding pointer. В этом случае, дефрагментация, по сути, сводится к копированию объекта. Потому что мы сначала принимаем решение дефрагментировать объект X и создаём для него копию Y. Потом мы делаем X.forwarding_pointer=&Y. При следующей сборке мусора мы заменяем все указатели на X в куче указателями на Y. После этого X становится мусором. Остаётся лишь правильно разделить эту работу между W и M

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

Ты придумываешь эти схемы, похожие на внебрачных детей Манилова и Руби Гольдберг, чтобы уйти от решения задачи «сделать специальный сборщик мусора»? Но предложение о forwarding pointer равносильно тому, что ты его напишешь (да и обмен состояниями сборки мусора в W и M - это уже влезание очень глубоко в сборщик).

(den73)

> Ты лучше придумай, как именно ты будешь добывать информацию о том, в каком состоянии находится память M, и как будешь применять эту информацию к W.

Как это технически сделать - тут нет ничего принципиально сложного. Состояние памяти - можно представить как последовательность вызовов «выделить память», «создать ссылку с поля на объект», «освободить память». Нужно перекрыть в языке именно эти примитивы и сериализовать их вместе с параметрами и возвращаемыми значениями. Передавать объекты между процессами не нужно. Конечно, для того, чтобы сделать такой журнал, нужно иметь полный доступ к исходникам реализации. Похоже, тут нужно ещё одно уточнение/изменение. Судя по всему, процесс M не может вычислять даже адреса, в которые нужно переместить память при дефрагментации, он может лишь выявлять мусор и передавать в W информацию типа «объект по адресу A - мусор» и «объект по адресу A1 фрагментирован, его нужно куда-то переместить». Хотя всё же часть этой работы можно переложить на M, если выделить часть страниц памяти процессу M и запретить процессу W ими пользоваться, пока процесс M этого явно не разрешит. Тогда эти страницы используются процессом M для того, чтобы планировать дефрагментацию. M назначает каждому перемещаемому объекту новый адрес, потом передаёт эти адреса процессу W. После того, как процесс W выполнил все перемещения, оставшееся свободное место на странице поступает в распоряжение W.

чтобы уйти от решения задачи «сделать специальный сборщик мусора»?

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

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

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

(den73)

По правде говоря, мне наиболее интересен вообще не подход с автоматической сборкой мусора, а добавление в язык неких деклараций. Например, таких: «функция F принимает параметр P и уничтожает его». В этом случае, у каждого вызова должно быть либо в статике доказано, что на этот параметр нет иных ссылок, либо необходимо создать соответствующий guard. Или «функция F возвращает свежевыделенное значение, на которое нет иных ссылок». Такая декларация иногда проверяема (по всем путям исполнения не должно создаваться иных ссылок, и должна быть в каждом пути ровно одна операция выделения памяти). Там, куда возвращается результат F, должно быть изучено, нужен ли дальше этот результат. Если в статике становится известно, что результат не нужен, то его можно сразу освободить. К сожалению, здесь есть простые контрпримеры, в которых эта техника не будет работать. Например, граф перекрёстных ссылок между набором функций при возможности горячей замены кода является таким (практически важным) контрпримером.

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

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

валидность которых неочевидна (вся эпопея с журналом).

Здесь всё нормально. Для устойчивой работы RT программы должен быть запас быстродействия и процесс в обязательном порядке достаточное время проводит в ожидании внешнего события (спит). Для устойчивой работы достаточно, чтобы доля простоя в рамках кванта времени была больше некоей константы альфа>0. Ведомый процесс в моей первой модели никогда не ждёт внешнего события, пока журнал внешних событий непуст. Поэтому, он работает, как минимум в 1/(1-альфа) раз быстрее ведущего и можно гарантировать, что за фиксированное время он исчерпает журнал внешних событий. Таким образом, можно гарантировать, что ведущий и ведомый процессы будут переключаться достаточно часто. Нужно ещё сделать такой запас памяти, чтобы можно было прожить без сборки мусора в течение времени между переключениями. Т.е., тут достаточно просто вычислить необходимые резервы, если известны характеристики такого же «одинокого» процесса и характеристики порождения мусора этим процессом. По-моему, придраться здесь не к чему и всё будет работать чётко, как часы, хотя и намного медленнее, но медленнее в фиксированное число раз.

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

Нда, чёто много букв вышло. Извините :-)

(den73)

И вообще, что значит «гигантский оверхед»? Вот какой оверхед есть в природе:

http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=java&lang2=...

http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=python&lang...

Раз этими языками люди пользуются, а не пишут всё на C, доказывает, что люди готовы на 10-кратный оверхед по быстродействию и памяти одновременно ради удобства и надёжности программ. То, что предлагаю я, даёт меньший оверхед, думаю, он будет порядка 3-4.

(den73)

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

Нет. Скорее, оно пропорционально размеру стека и области глобальных >переменных.

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

>> Ты лучше придумай, как именно ты будешь добывать информацию о том, в каком состоянии находится память M, и как будешь применять эту информацию к W.

Как это технически сделать - тут нет ничего принципиально сложного. Состояние памяти - можно представить как последовательность вызовов «выделить память», «создать ссылку с поля на объект», «освободить память». Нужно перекрыть в языке именно эти примитивы и сериализовать их вместе с параметрами и возвращаемыми значениями.

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

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

Какой пункт обзора?

По правде говоря, мне наиболее интересен вообще не подход с автоматической сборкой мусора, а добавление в язык неких деклараций. Например, таких: «функция F принимает параметр P и уничтожает его». В этом случае, у каждого вызова должно быть либо в статике доказано, что на этот параметр нет иных ссылок, либо необходимо создать соответствующий guard.

То есть мы весь тред обсуждаем идею, которая тебе неинтересна? Какая прелесть.

И вообще, что значит «гигантский оверхед»?

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

Раз этими языками люди пользуются, а не пишут всё на C, доказывает, что люди готовы на 10-кратный оверхед по быстродействию и памяти одновременно ради удобства и надёжности программ.

Мне тупо лень объяснять очевидные вещи, поэтому я не буду. Только замечу, что 1) кратность своего оверхеда ты еще не считал (почему ты вдруг решил, что уложишься всего в 10 раз?); 2) профиты двухпроцессной сборки мусора, мягко говоря, неочевидны по сравнению с обычной (а вот профит сборки мусора по сравнению с ручным управлением памятью вполне очевиден).

Я не понял, что именно ты пытаешься сказать.

den73

http://www.jopdesign.com/doc/nbgc.pdf
стр. 5.
[quote]
All writes are recorded in a
mutation log and the garbage collector has to apply the writes from this log after updating
the pointer(s) to the new object copy.
[/quote]
Речь, идёт, правда, не про выделение памяти, а про гораздо более редкую операцию записи.

[quote]
То есть мы весь тред обсуждаем идею, которая тебе неинтересна? Какая прелесть.
[/quote]
Она не то, чтобы совсем неинтересна. Я ждал, что меня кто-нибудь ткнёт носом в то, что поставленная мной проблема вообще неакутальна, тогда можно было бы забить и на декларативное управление памятью. Однако, я вижу лишь последовательные приближения к недостижимой безконечности,а значит, разработка декларативного управления памятью может иметь смысл.
[quote]
1) кратность своего оверхеда ты еще не считал (почему ты вдруг решил, что уложишься всего в 10 раз?
[/quote]
Даже если это будет 20 раз, у меня есть ощущение, что это - константа, независимая от общего числа объектов, размера стека, количества глобальных переменных, интенсивности мутаций старых объектов. Какова эта константа численно, зависит лишь от того, насколько эффективно удастся реализовать журнал. Поскольку журнал можно представить в виде потока с кольцевым буфером, резонно предположить, что он будет не чрезмерно дорог и те операции, которые будут в него писаться, замедлятся не более чем вдвое. Именно отсюда я и взял свою оценку 3-4 (для первого варианта с двумя потоками). Первая двойка - это замедление журналируемых операций вдвое (в худшем случае журналируются все операции), вторая двойка - это два процесса.
Переключение стоит пренебрежимо мало.
Итого, 4. По памяти оценить сложнее, т.к. это зависит от характеристик процесса в отношении сборки мусора, но тут ясно, что речь идёт лишь о выделении достаточно большого буфера, чтобы журнал в него поместился. Размер буфера определяется природой процесса.
Примерно такая же логика применима и ко второму варианту. Хотя, конечно, я мог упустить какие-то нюансы.
[quote]
профиты двухпроцессной сборки мусора, мягко говоря, неочевидны по сравнению с обычной
[/quote]
Вполне очевидны - отсутствие непредсказуемых пауз для атомарных операций типа пометки объектов. Даже если сборка мусора занимает 10 секунд, можно сделать систему работающей с паузами не более 1мс - хватило бы памяти под буфер.

Кстати, вместо двух процессов в первом варианте можно использовать N процессов, между которыми происходит что-то вроде эстафеты. Это позволяет сохранить быстродействие в том случае, когда сборка мусора занимает слишком большую долю всех затрат CPU (или я заврался?)

>> профиты двухпроцессной сборки мусора, мягко говоря, неочевидны по сравнению с обычной

Вполне очевидны - отсутствие непредсказуемых пауз для атомарных операций типа пометки объектов.

Мде. Нет пауз, говоришь?

den73> переговоры между M и W о дефрагментации проходят за несколько циклов чтения/записи S1 и S2.

И это ты еще не учитываешь, сколько времени изменения из M будут применяться к W.

Даже если сборка мусора занимает 10 секунд, можно сделать систему работающей с паузами не более 1мс - хватило бы памяти под буфер.

...и с оверхедом 1000. Что ж, удачи.

</thread>

> И это ты еще не учитываешь, сколько времени изменения из M будут применяться к W
В этом процессе нет ни одной крупной атомарной операции. Если мы применим в M алгоритм метронома, то максимальная задержка в M будет такая же, как в метрономе, а в W она будет в разы меньше.

и с оверхедом 1000

Ага, а ты, значит, уже оверхед посчитал :)

</thread>

Ну, спасибо и на том, что есть.

>По правде говоря, мне наиболее интересен вообще не подход с автоматической сборкой мусора, а добавление в язык неких деклараций. Например, таких: «функция F принимает параметр P и уничтожает его».

А разве let в лиспе не это делает?

>По правде говоря, мне наиболее интересен вообще не подход с автоматической сборкой мусора, а добавление в язык неких деклараций. Например, таких: «функция F принимает параметр P и уничтожает его».

А разве let в лиспе не это делает?

>По правде говоря, мне наиболее интересен вообще не подход с автоматической сборкой мусора, а добавление в язык неких деклараций. Например, таких: «функция F принимает параметр P и уничтожает его».

А разве let в лиспе не это делает?

Нет, в лиспе вообще нельзя удалить «родной» лисповый объект. Let создаёт локальную переменную, которая указывает на то, что ей передали. По выходе из области видимости перестаёт указывать. Если let был единственной ссылкой на переданное значение, то объект становится мусором и удаляется когда-нибудь в будущем при сборке мусора. В лиспе есть декларация dynamic-extent, которая уже ближе к теме - она, грубо говоря, заявляет о намерении разместить объект на стеке.

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

region inference, например?

TAPL:

Компилятор ML Kit с помощью мощного алгоритма вывода регионов (Gifford, Jouvelot, Lucassen, and Sheldon, 1987; Jouvelot and Gifford, 1991; Talpin and Jouvelot, 1992; Tofte and Talpin, 1994, 1997; Tofte and Birkedal, 1998) заменяет большинство вызовов сборщика мусора (а иногда даже все вызовы) операциями управления памятью в стеке.

> заменяет большинство вызовов сборщика мусора (а иногда даже все вызовы) операциями управления памятью в стеке.

Слово «мощный» в цитате сразу говорит о том, что мы имеем дело с мифом. Два контрпримера, которые говорят, что без сборки мусора не обойтись (вроде ты лисп знаешь)
1. (defun f () ...) (defun g () ...) (defun f () ...)
Код любой версии f, а также код g не могут быть размещены на стеке, если формы последовательно вводятся в подсказке интерпретатора, поскольку неизвестно, какое из этих определений первым станет мусором.
2. переменные интерпретатора *, **, ***, **** - их значения не могут быть размещены на стеке.

Хотя, судя по названию, наверное, это примерно этот самый алгоритм и есть.