OberonCore

Неожиданно обнаружил, что не понимаю важной вещи или во всяком случае мне так кажется.
Я о сборщике мусора. В документации сказано, что уничтожить переменную достаточно присвоив ей значение NIL. Это понятно, это здорово. Тоесть сборщик мусора уничтожает все структуры данных на которые никто не указывает. Но вот я создаю скажем связный список.
NEW (A);
A^.n:=1;
FOR i:=2 TO N DO
NEW(A^.next);
A:=A^.next;
A^.n:=i;
END;

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

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

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

Причем тут сборщик мусора? Вы же сами себе ничего больше не оставляете.

Это понятно, что не оставляю, но мне было интересно, как на это смотрит сборщик мусора. Я еще не отвык, что о очистке памяти надо обязательно воспользоваться чем-то вроде Dispose

Тоисть это по разряду ломки

Ну да ну да. Реликтовые пережитки сознания

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

А я тоже не очень понимаю
Видимо, у меня в голове произошло неправильное смешение понятий GC, и reference counting

Как мне казалось до сих пор:
1) уже при значении i=2, при выполнении A:=A^.next; первый (полученный по NEW (A);) алоцированный объект получает нулевой счетчик ссылок, и кэшируется как-то куда-то в некую "свободную область". И вроде бы - сразу же, не отходя от кассы...
2) при значении i=3, при выполнении NEW(A^.next); этот же, уже "освобожденный", кусочек памяти может совершенно спокойно попасть уже в эту алокацию. И это даже было бы самым логичным: в "свободной области" точно есть кусочек именно нужного размера, может и не один такой, а только помещать новый в самое начало списка "свободных", обычно удобнее.
3) из всего, этого мне совершенно непонятно, что означает фраза:


Направьте на путь истинный, пожалуйста.

GC в ББ так не работает. То, что вы описали - это методика повторного использования (кэширования) объектов, которую иногда бывает целесообразно применять, но делается это обычно явным образом, осознанно, и только для некоторых заранее известных типов объектов. GC же в общем случае не знает, какого размера объект потребуется вашему алгоритму в следующий момент (такого же типа/размера, как A, или другого), равно как и не знает он со 100% достоверностью, что вы не сохранили куда-нибудь ссылочку на тот или иной объект до лучших времён: счётчика ссылок здесь нет. Память под все NEW объекты выделяется заново из имеющегося свободного пространства. Только когда и если свободного места не осталось, производится поиск и удаление ненужных объектов (т.е. тех, на которые нет прямых или косвенных ссылок из глобальных переменных или стека).

Хм... А как производится
В процессе исполнения всегда существует некий пополняемый/удаляемый "стек адресов", в которых находятся ссылки на хип
Если существует, кто им управляет ???
Это прямые ссылки... А косвенные ???

Интересно также понимание преимуществ (или недостатков) именно такой стратегии.
Которое одним вопросом и не сформулируешь....
А без понимания - огромный дискомфорт имеет место быть

Я так понимаю, что надо поискать инфу по теме Сборка мусора?
Тогда можно посмотреть в Кнуте - первый том. Или у Элджера - там даже с программами на С++ есть.

Счётчик ссылок в общем случае неприменим, т.к. не работает в случае с циклическими ссылками (два объекта держат друга друга - никому больше не нужны, но друг друга держат ).

По поводу алгоритма ищем на слова "Mark & Sweep". Алгоритм классический ещё со времён появления Лиспа. Сначала проходим от корней (от глобальных указателей и указателей стека), помечая все пройденные. Затем проходим по списку выделенных блоков памяти, ища те, которые не помечены на предыдущей фазе - они, значит, недоступны, их удаляем.

В Явах/Шарпах навороченные модификации (с поколениями, алгоритм "поезд" и т.п. По поводу поколений есть в книге Рихтера про .NET). Оно себя не оправдывает.

Маркировка производится временной установкой младшего бита у указателя. Адреса глобальных переменных известны, список загруженных модулей есть в модуле Kernel (modList: Module). Для каждого составного типа известно, по каким смещениям в нём находятся указатели, так что косвенные ссылки обойти тоже не проблема.

Исходники GC - см. Kernel.Collect и используемые им процедуры. Процедура выделения памяти под объект - Kernel.NewRec (вызывается, когда в исходнике встречается NEW(ptr)).


http://en.wikipedia.org/wiki/Garbage_co ... er_science)#Naive_mark-and-sweep

Цитата:
Маркировка производится временной установкой младшего бита у указателя.


Только не у указателя, а у блока памяти. Блок памяти открывается тегом типа, вот у этого тега и взводится бит. (Поэтому много потоков пущать просто так нельзя. Если в одном запустился сборщик, он временно портит память).

В реализации возможны вариации, а суть в следующем:

язык устроен так, что компилятор при компиляции имеет полную информацию -- и потому может как-то ее зафиксировать для использования во время исполнения -- о структуре ссылок, которая будет иметь место при выполнении:

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

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

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

Указанный тут порядок (сначал...потом...) -- смысловой.
Реально возможны варианты (типа сбор в список свободных и разотмечание занятых за один сплошной проход по памяти -- "sweep").
Как возможны варианты реализации разметки.

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

Если не заниматься оверквотингом, то общее БОЛЬШОЕ СПАСИБО, коллеги
Прежде всего, за указку на буквари - внимательно ознакомился (на что и потребовалось некое время)

Возможно, это не тот Рихтер, который у меня сегодня есть (Создание эффективных WIN32-приложений с учетом специфики 64-разрядной версии Windows).
Не нашел пока у себя такого.
Илья, если можно, уточните ссылку, пожалуйста

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

Упомянутая книга:

Дж. Рихтер Программирование на платформе Microsoft .NET Framework. "Русская редакция" - 2003.

Вспомнил, есть ещё одна:

Richard Jones, Rafael Lins. Garbage Collection. Algorithms for Authomatic Memory Management. "John Willey & Sons" - 1996.

Можно обращаться в личку.

По поводу недетерминированности и зависимости времени сборки от количества объектов - да, всё верно. С этим борются введением поколений (получая другие проблемы), но лучше просто не разводить свинарник из мелких объектов Это возможно (не разводить) только в Обероне, т.к. в Java - .NET на любой чих идёт выделение через new - ООП, массивы, строки...

Кстати, если заинтересуетесь рантаймоописаниями Рихтера, то полезно вживую всё это посмотреть на ядре ББ. По документации - http://oberoncore.ru/wiki/blackbox/kernel

Заинтересуетесь
Спасибо, Илья - прочитал (Рихтера). Реинкорнация объектов - это шедевр, просто нет слов.
Одни мысли, и все не цензурные.

Напоминает технологию стэлз: как можно заставить летать даже чемодан, с помощью супер-современных технологий.
Заставить-то можно. И даже можно всех убедить, что его никто не видит.
До встречи с ламповой С-70 (читай - до ранее упомянутых задач очереди динамических объектов).

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