Аппаратная сборка мусора

Question

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

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

Это то, что сделал LISP Machines? Было ли какое-либо дальнейшее исследование этой идеи? Это слишком специфично для домена?

Мысли? Возражения? Обсудить.

Answer 1

Из-за Generational Collection я бы сказал, что трассировка и копирование не огромные узкие места для GC.

Что может помочь, так это аппаратные барьеры READ, которые устраняют необходимость в паузах «остановка мира» при сканировании стека и разметке кучи.

Azul Systems сделала это: http://www.azulsystems.com/products/compute_appliance.htm Они выступили с докладом на JavaOne о том, как их аппаратные модификации позволили сделать абсолютно безостановочный сборщик мусора.

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

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

Проблема в том, что это означает, что ЛЮБОЕ время, когда мутатор (причудливое слово для «настоящей программы») устанавливает указатель, он также должен поместить запись в соответствующий запоминаемый набор. Таким образом, у вас есть (небольшие) накладные расходы, даже если вы не GCing. Если вы можете уменьшить это, вы уменьшите как время паузы, необходимое для GCing, так и общую производительность программы.

Answer 2

Да. Посмотрите на соответствующие разделы работы этих 2 статей:

https://research.microsoft.com/en-us/um/people/simonpj/papers/parallel-gc/index.htm http://www.filpizlo.com/papers/pizlo-ismm2007-stopless.pdf

Или на этом:

http://researcher.watson.ibm.com/researcher/files/us-bacon/Bacon12StallFree.pdf

Answer 3

Вы аспирант, звучит как хорошая тема для исследовательского гранта для меня. Изучите дизайн FPGA и компьютерную архитектуру. Существует множество бесплатных разработок процессоров, доступных на http://www.opencores.org/

Сборка мусора может быть реализована как фоновая задача, она уже предназначена для параллельной работы.

Пит

Answer 4

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

Answer 5

Одним из очевидных решений было использование указателей памяти, которые больше, чем ваша доступная оперативная память, например, 34-разрядных указателей на 32-разрядной машине. Или используйте самые верхние 8 бит 32-битной машины, когда у вас только 16 МБ ОЗУ (2 ^ 24). машины Oberon в ETH Zurich использовали такую ​​схему с большим успехом, пока оперативная память не стала слишком дешевой. Это было примерно в 1994 году, поэтому идея довольно старая.

Это дает вам пару битов, в которых вы можете сохранить состояние объекта (например, «это новый объект» и «Я только что коснулся этого объекта»). При выполнении ГХ предпочитайте объекты с надписью «это новое» и избегайте «только что коснулись».

Это может на самом деле увидеть ренессанс, потому что ни у кого нет 2 ^ 64 байтов ОЗУ (= 2 ^ 67 битов; во вселенной около 10 ^ 80 ~ 2 ^ 240 атомов, так что это может быть невозможно много оперативной памяти когда-либо ). Это означает, что вы можете использовать пару бит на современных машинах , если виртуальная машина может указать ОС, как отобразить память.

Answer 6

В старых системах sparc была помечена память (33 бита), которую можно было использовать для маркировки адресов. Не установлено сегодня?

Это пришло из их наследия LISP IIRC.

Один из моих друзей создал GC для поколений, который пометил, немного украдя у примитивов. Работало лучше.

Итак, да, это можно сделать, но больше никто не мешает помечать вещи.

Комментарии runT1mes о GC с аппаратной поддержкой поколений заслуживают прочтения.

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

Answer 7

Я почти уверен, что некоторые прототипы должны существовать. Но разрабатывать и производить аппаратные особенности очень дорого. Потребовалось очень много времени, чтобы реализовать MMU или TLB на аппаратном уровне, что довольно легко реализовать.

GC слишком велик для эффективной реализации на аппаратном уровне.

Answer 8

Несколько великих умов в Массачусетском технологическом институте еще в 80-х годах создали чип SCHEME-79 , который непосредственно интерпретировал диалект схемы, был разработан с DSL LISP, и имели hardware-gc встроенный.

Answer 9

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

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

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

Answer 10

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

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

Посмотрите, что только что появилось ... в другом сообщении ... Просмотр журнала GC Java.