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

Question

Я слышал, что в общих чертах упоминается, что такие вещи существуют, но детали редко обсуждаются. Какие твои любимые? Что мешает?

Answer 1

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

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

Answer 2

Я предполагаю, что вы имеете в виду параллельные структуры данных. Если это так, многие алгоритмы без блокировки требуют сборки мусора (или отложенного / безопасного восстановления памяти). И самый простой пример - классический стек без блокировки: [поиск в Википедии по "проблеме АБА" - сайт запрещает мне публиковать ссылку] (ABA и безопасное восстановление памяти являются тесно связанными проблемами, если вы решите последнее, чем вы решите первое тоже) Разве невозможно реализовать их без GC? Нет, это не невозможно. Тем не менее, это определенно сложнее. Одним из решений является реализация ограниченной формы GC. Например, строго потокобезопасный подсчет ссылок: http://www.1024cores.net/home/lock-free-algorithms/object-life-time-management/differential-reference-counting Другое решение состоит в том, чтобы разработать алгоритм вокруг требования, чтобы он просто не требовал GC. Например, для некоторых очередей производителей-потребителей без блокировки (наиболее заметна очередь M & S) требуется GC. А вот простой эффективный алгоритм очереди, специально разработанный для требований GC: http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue

Answer 3

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

Все, что генерирует много временных данных / переменных, является большой проблемой (то есть трудной, технически невозможной) без некоторыхсортировка мусора.Например, представьте веб-сервер с поддержкой php или asp.net, в котором движок скриптов php / c # не имеет сборки мусора.Каждый веб-запрос от браузера создает много временных данных на веб-сервере, и если в сценарии на сервере произошла небольшая утечка памяти, весь веб-сервер заканчивается ужасной смертью ...

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

Также LINQ в C # создает много временных объектов.Было бы краской, чтобы использовать его без сбора мусора.

Answer 4

var v = FunctionThatAllocatesMemory2(FunctionThatAllocatesMemory1());

Без GC невозможно освободить память, возвращаемую FunctionThatAllocatesMemory1().