Умный сборщик мусора для разделения поддиапазонов массивов?

Ответ 1

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

Как работает GC?

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

Примечания. Я использовал информацию о типе и информацию о макете с тем же значением.

Пример:

Imagine we have some object layouts:
====================================
A: { int, object, double, object }
B: { object, object }
C: { int }


Memory Data:
============
Now we need to describe what is in memory.
The following list is composed of memory positions,
and the data contained in each position.
There are 2 kinds of notation I will use:
  - Address: ROOT[ list-of-root-references ]
  - Address: type-identifier { object-data }
     Note that each object can span multiple memory
     positions from the first one.
     e.g. 90: B { 0, 0 } -- this reads as
       "stored at address 90: type-identifier of B followed by raw data { 0, 0 }"
  - A reference is represented by a number,
    that point to the memory address of the pointed object.

 1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 }    There is a self-reference here!
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 }                 Note that 0 is a null reference!

   The GC need to know the layout of each object.
   Otherwise it wouldn't be abled to tell
   what knid of information is stored in each memory position.

Running the GC:
===============
Garbage collecting steps, to clean the memory described above:
Step 1: Get ROOT references: 2, 3, 9 and mark as 'in-use'
Step 2: Get references from 2, 3 and 9: 3, 6, 7. Note that 0 is a null reference!
Step 3: Get references from 3, 6 and 7: 6, 7, 8, and mark them.
Step 4: Get references from 6, 7, 8, and mark them: only 8!
Step 5: Get references from 8... it has none! We are finished with marking objects.
Step 6: Delete unmarked objects.


      This shows what happened in each step with each object stored in the memory.

Step ->  1  2  3  4  5
Memory                    
20       x           
30       x  x        
40                   DELETE
50                   DELETE
60          x  x     
70          x  x     
80             x  x  
90       x           

То, что я описал, является очень простым алгоритмом GC.

Взгляните на трехцветную маркировку... это действительно потрясающе! Вот как делаются настоящие современные GC.

Сбор мусора (информатика) - описывает некоторые современные методологии GC.

Но... где хранится информация о размещении макета?

Этот вопрос важен, поскольку он влияет как на GC, так и на runtime. Чтобы выполнить быстрое литье типов, информация о типе должна быть размещена вблизи ссылки, или рядом с выделенной памятью. Мы могли бы думать, чтобы хранить информацию о типе в каталоге выделенных блоков памяти, но тогда... type-casts понадобится для доступа к каталогу, как и новый оператор и GC, когда это необходимо удалить объект.

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

Пример:

To represent the memory data I will introduce the following notation:
 - Address: { object-data } -- this time object type is not at the begining!
 - A reference is represented by a type-identifier and an address-number,
   that point to the memory address of the pointed object,
   in the following format: type/number...
   e.g. A/20 -- this reads as: "at address 20, there is an object of type A"
Note that: 0/0 is a null reference,
      but it still requires space to store the type.

The memory would look like this:
 1: ROOT[ B/90, A/20, B/30 ]
20: { 1236, B/30, 0.5, C/60 }
30: { C/60, A/70 }
40: { 1237 }
50: { 1238, A/20, 0.8, A/50 }
60: { 1234 }
70: { 1234, 0/0, 0.7, C/80 }
80: { 1235 }
90: { 0/0, 0/0 }

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

Пример:

The memory looks like the first sample:
 *This is the same notation used at the begining of this answer.
 1: ROOT[ 90, 20, 30 ]
20: A { 1236, 30, 0.5, 60 }
30: B { 60, 70 }
40: C { 1237 }
50: A { 1238, 20, 0.8, 50 }
60: C { 1234 }
70: A { 1234, 0, 0.7, 80 }
80: C { 1235 }
90: B { 0, 0 }

До сих пор так приятно... но теперь мне нужна разделяемая память.

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

Представьте массив с разделяемой памятью:

Пример:

 I'll introduce a new notation for arrays:
    type-identifier < array-length >

 1: ROOT[ 20, 31 ] -- pointer 31 is invalid, destination has no type-identifier.
20: INT<5>  -- info about layout of the next memory data (spans by 10 memory units)
30:  2
31:  3 -- should have type-identifier, because someone
32:  5              is pointing here!! Invalid memory!!
33:  7
34: 11

Мы можем по-прежнему пытаться размещать информацию о макете рядом с указателем, вместо. Теперь доступен массив разделяемой памяти:

Пример:

 1: ROOT[ INT<5>/30, INT<2>/31 ]
30:  2
31:  3
32:  5
33:  7
34: 11

Помните, что этот aproach заставляет нас повторять всю информацию о макете везде... но смысл здесь в том, чтобы использовать меньше памяти, не так ли??? Но чтобы разделить память, нам нужно больше памяти для хранения макетов-данных/указателей. Нет пончиков для нас. = (

Есть только одна надежда: позволяет деградировать возможности выполнения!

ЭТО МОЙ ОТВЕТ - Как я думаю, это может быть возможно = >

Как использовать каталог распределения памяти для хранения информации о типе?

Это можно сделать, но тогда динамическое кастинг будет страдать, а также GC будет страдать. Помните, что я сказал, что GC необходимо получить доступ к каталогу памяти, просто для удаления объектов... ну, теперь ему нужно будет получить доступ к каталогу каждый раз, когда он найдет ссылку, не просто удалить. О, МОЙ БОГ!! Мы собираемся убить производительность GC с этим, а также производительность исполнения. Слишком высокая стоимость, я думаю!

< = ЭТО МОЙ ОТВЕТ

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

Нет легкого, умного решения, в поле зрения.

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

Другие ссылки:

http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)

http://www.memorymanagement.org/glossary/t.html

http://www.cs.purdue.edu/homes/sbarakat/cs456/gc-2.pdf

Трехкрасовое инкрементальное обновление GC: нужно ли дважды сканировать каждый стек?

Ответ 2

Язык D поддерживает массивы с таким же поведением GC. Посмотрите http://www.dsource.org/projects/dcollections/wiki/ArrayArticle#WhosResponsible для получения дополнительной информации.

Ответ 3

Кто-нибудь знает пример реализации языка, у которого есть сборщик мусора, подобный этому?

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

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

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

Я фактически написал виртуальную машину (HLVM), которая позволяет избежать заголовков с использованием ссылок на квадратные слова, т.е. метаданные переносятся со ссылкой а не в объекте, на который он указывает. Из исследования подсчета ссылок мы знаем, что подавляющее большинство объектов имеют счетчик ссылок на один, поэтому потенциальное дублирование заголовков для каждой ссылки действительно дешевле, чем вы могли себе представить. Отсутствие заголовка означает, что внутреннее представление массива HLVM является C-совместимым, поэтому интероперабельность намного проще и быстрее. Аналогично, срез может быть ссылкой в ​​середину массива. Соответствующий алгоритм GC, такой как область метки, мог бы затем освободить части блока памяти, выделенного кучей, которые больше недоступны и не используются повторно, сохраняя доступные дольки.

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

Ответ 4

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

Ответ 5

Я думаю, что все реализации ассоциативного массива (PERL, PHP, javascript..) должны быть выполнены таким образом. Вы называете это "сбор мусора", но это означает, что определенные предметы должны быть сначала удалены (удалены, удалены) для сборщика мусора, чтобы знать, что они не используются. Таким образом, это обычное удаление/удаление/удаление, что, безусловно, отражается не только в ассоциативном массиве, но также и в структуре данных, используемой конкретной реализацией языка. В противном случае память может быть исчерпана почти пустым массивом...