Сборка мусора

[captain cobalt]

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

Это детали реализации данных конкретных технологий. Существуют и другие подходы. Можно выбрать более подходящий.

реализация данного дела довольно сложна, поэтому должна быть не частью ОС, а частью реализации ЯВУ (если таковые будут)

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

Я совершенно не могу себе представить, как можно на Speccy запустить параллельно несколько сборщиков мусора. Ведь каждому понадобится собственная память "под мусор". А памяти и так не хватает. Поэтому - если сборку мусора реализовывать - но на самом низком уровне исполнения. Чтобы все использовали один сборщик мусора.

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

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

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

Опять же - насколько?
Загрузив указатель из памяти в регистры можно потом многократно обращаться к блоку памяти, пока указатель находится в регистрах.

А как происходит при "обычном программировании"? Откуда адреса появляются в регистрах?

плюс трата системных ресурсов на периодическую проверку и сборку этого мусора.

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

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

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

[elf/2]

указатели должны быть типизированы или каждый блок памяти иметь маркер типа или размера блока

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

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

где в асме переменные и области видимости?

[GriV]

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

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

где в асме переменные и области видимости?

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

[Vitamin]

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

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

Я совершенно не могу себе представить, как можно на Speccy запустить параллельно несколько сборщиков мусора. Ведь каждому понадобится собственная память "под мусор". А памяти и так не хватает. Поэтому - если сборку мусора реализовывать - но на самом низком уровне исполнения. Чтобы все использовали один сборщик мусора.
А насколько ресурсоёмкая?

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

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

советую почитать статьи по ускорению работы с памятью для ЯВУ, не поддерживающих сабж

Опять же - насколько?
Загрузив указатель из памяти в регистры можно потом многократно обращаться к блоку памяти, пока указатель находится в регистрах.

А как происходит при "обычном программировании"? Откуда адреса появляются в регистрах?

сравни:
call allocate ;hl-addr
ld (block1),hl
ld de,to
ld bc,len
ldir ;something like this

или

call allocate
ld (block1),hl
ld a,(hl)
inc hl
ld h,(hl)
ld l,a
ld de,to
ld bc,len
ldir

вроде мелочь, а неприятно.

А как происходит без сборки мусора?
Классические алгоритмы управления динамической памятью тоже при каждом выделении перебирают список свободных блоков, выбирая подходящий. Это тоже в плохих ситуациях может оказаться долго.
Ну так ведь речь не о начинающих программистах. Имея дисциплину, можно потом "правильно программировать" и со сборщиком мусора.

сравним еще раз:
без сборщика:
при выделении происходит перебор всех блоков и выбор первого подходящего или наиболее подходящего (две разные стратегии выделения памяти)
при освобождении просто происходит вставка в связный список описателя свободного блока

со сборщиком:
при выделении (см. пред. вариант)
процедура освобождения вызывается только при отсутствии необходимости в выделенном блоке и совпадает с аналогичной процедурой пред. варианта.
НО! затраты (периодические) на просмотр _всего_ списка блоков для поиска кандидатов на удаление. единственное облегчение- просматривается не список блоков, а список указателей на блоки (а хрен редьки, как известно, не слаще %) )

(Бонусный вопрос: какие языки больше дисциплинируют: типизированные или бестиповые?)

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

[captain cobalt]

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

Это не годится для динамических связных структур данных.

Вот, кстати, ещё один аргумент за сборщик мусора - что лучше: в каждой программе иметь (рекурсивные) процедуры для уничтожения связных структур данных, или иметь один сборщик мусора?

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

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

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

Ничего не боюсь!
Одна куча на всю систему.
Со сборщиком мусора.
Кому не надо, не использует его.

советую почитать статьи по ускорению работы с памятью для ЯВУ, не поддерживающих сабж

На какую тему?
Сборщик мусора встаёт поперёк дороги каким-то приёмам оптимизации?

сравни:
call allocate ;hl-addr
ld (block1),hl
ld de,to
ld bc,len
ldir ;something like this

или

call allocate
ld (block1),hl
ld a,(hl)
inc hl
ld h,(hl)
ld l,a
ld de,to
ld bc,len
ldir

вроде мелочь, а неприятно.

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

LD HL,block1
CALL allocate
LD DE,dest
LD BC,len
LDIR

Весьма симпатично.

НО! затраты (периодические) на просмотр _всего_ списка блоков для поиска кандидатов на удаление. единственное облегчение- просматривается не список блоков, а список указателей на блоки (а хрен редьки, как известно, не слаще %) )

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

Существуют также ситуации, при которых со сборщиком мусора будет быстрей. Например, если памяти хватило на всё, то можно не тратить время на освобождение. Образуется мусор, который "на досуге" уберём.

[AlexCrush]

Я считаю что пытаться реализовать автосборку мусора это как учиться производить ракеты, не умея делать автомобили. Начать надо (имхо) с реализации самой простой надстройки над asm'ом - это C. На асме полноценную ось никогда не написать, если и написать то надо много временнЫх ресурсов (люди*годы)... Будут полноценные malloc и free - тогда можно и о большем думать...

[elf/2]

Вообще я так понимаю, что сборщик мусора есть свойство/метод ОСи

неправильно понимаешь вот в windows и linux нет сборщиков мусора, а в Java и .NET которые работают под этими осями есть

[captain cobalt]

Однако, ничто не мешает сделать сборщик мусора свойством оси.

[elf/2]

пара комментариев ко всему треду:
1. для реализации сборки мусора не нужна многозадачная ось или потоки. никто не мешаеть позвать его автоматически в тот момент когда кончилась память (из системной функции new). другой вариант, пользовательская программа может сама время от времени звать сборщика (тогда когда она считает нужным: в момент ожидания пользовательского ввода, после окончания ресурсоемкого куска)
2. сборка мусора никак не связана с виртуальными машинами/байткодом. есть библиотеки для C++ реализующие сборку для некоторых частных случаев

ну и хочется вернуться к главному _КАК_ это можно реализовать на спекке? считаем что у нас есть: АСМ и ОСЬ с хорошим менеджером памяти...
для того чтобы сборка заработала нам надо знать где выделили память, сколько и когда она освободиться. на первые два вопроса нам ответит менеджер памяти. А кто ответит на последний?
все еще предлагаю решить простейшую задачу:
1. программа попросила 200 байт памяти, вызвав системную функцию new/malloc
2. указатель на блок памяти нам вернули (в HL или записали куда-то еще в память)
3. мы этот блок использовали и он нам больше не нужен

как сборщик памяти сможет это понять и вернуть память в систему?

или в терминах captain cobalt в какой момент времени сборщик мусора поймет что данный блок "не является достижимым по цепочкам указателей начиная с глобальных статических указателей"?

[elf/2]

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

Это не годится для динамических связных структур данных.

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