LINUX.ORG.RU

сборка мусора - зацените идейку


1

0

Доброго!

Как я понял, поколенческая сборка мусора требует некоторых дополнительных действий при каждом создании или изменении ссылки, чтобы отследить ссылки старого объекта на молодой. Почему бы тогда не обобщить понятие «поколения» на понятие «область хранения» и не позволить пользователю явно управлять областями? Например, ввести глобальную (поточную) переменную «текущая область хранения» и всё выделение по умолчанию вести в этой области. Или добавить параметр в конструктор (хотя это требует переделки языка). Области могут быть упорядочены в иерархию и тогда нужно будет отслеживать только ссылки «старших» на «младших» по иерархии. Или они могут составлять произвольный граф и тогда нужно отслеживать все ссылки. Причём, можно отслеживать ссылки как тонко (на уровне объектов), так и грубо (на уровне областей). Например, мы знаем, что область A ссылается на область B. Тогда, чтобы собрать мусор в области B, нам нужно искать корни также в области А. Самое главное, если на область B вообще никто не ссылается, то мы можем одним махом убить все объекты в области B.

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

★★★★★

Ответ на: комментарий от den73

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

Booster ★★
()
Ответ на: комментарий от Booster

> А если из области много других и рекурсивных вызовов?
Тогда нам не повезло.

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


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

den73 ★★★★★
() автор топика
Ответ на: комментарий от den73

В принципе интересно. По идее можно полностью заменить GC этой штукой.

Booster ★★
()
Ответ на: комментарий от den73

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

Booster ★★
()
Ответ на: комментарий от Booster

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

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

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

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

den73 ★★★★★
() автор топика
Ответ на: комментарий от den73

Блин, опять очепятка. Не «мы можем запустить сборку мусора», а «мы можем запретить сборку мусора» в нити реального времени.

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

den73 ★★★★★
() автор топика
Ответ на: комментарий от den73

Ещё немного поразмыслил как можно организовать сборку мусора на основе данной идеи. А что если отказаться от gc, сделав всё на основе смартпоинтеров и областей видимости? В каждой области видимости хранить массив указателей на объекты, которые принадлежат данной области. В самих объектах будет счётчик ссылок областей. Когда объект создался, то он принадлежит данной области, значит заносим указатель на данный объект в массив указателей области и ставим ссылку в объекте в 1. Если кто-то из другой области ссылается на этот объект, то также заносим указатель на него в массив той другой области и увеличиваем ссылку в объекте. В итоге никаких проблем с циклическими ссылками. Так же есть экономия, если на объект из одной области ссылается много ссылок, то указатель в массиве всё равно один, так как объект принадлежит сразу всей области, а не каждой ссылке на него.

Booster ★★
()
Ответ на: комментарий от Booster

Так, я не понял, нужно два массива? Один «кто ссылается на нас» и второй - «на кого ссылаемся мы»?

den73 ★★★★★
() автор топика
Ответ на: комментарий от den73

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

Booster ★★
()
Ответ на: комментарий от Booster

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

Ну всё равно непонятно. Вот у нас объект б в области Б ссылается на объект а в области А. Добавляем ещё одну ссылку из области Б на объект а. Как мы узнаем, что не нужно увеличивать счётчик ссылок на объекте а?

den73 ★★★★★
() автор топика
Ответ на: комментарий от den73

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

Booster ★★
()
Ответ на: комментарий от Booster

Да ну, по-моему, чистый GC ничем не хуже. Главное, что если у нас области независимы, то мы можем делать GC в одной области и в то же время другая область будет работать в риалтайме. Этакий получится змей-горыныч,у которого головы спят поочерёдно.

den73 ★★★★★
() автор топика
Ответ на: комментарий от den73

А как в твоей идее быть с циклическими ссылками? К примеру у нас есть локальное дерево и где-то сбоку ссылка из внешнего объекта. То есть локальное дерево переплелось с основным. Как тут быть? Запускать обход дерева?

Booster ★★
()
Ответ на: комментарий от Booster

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

den73 ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.