Да, gc амортизируется постоянным временем. Предположим, у вас есть алгоритм, который работает в течение времени с пиковым рабочим набором размера k . Теперь обратите внимание, что вы можете выделить не более O ( n ) слов во время выполнения программы, и что временные затраты на копирование сборщика мусора равны O ( k ) (т. Е. Стоимость gc пропорциональна общей сумме количество живых данных). Таким образом, если вы запускаете gc не более O ( n / k ) раз, то общая стоимость времени выполнения ограничена O ( n )NКO ( n )O ( k )O ( н / к )O ( n ), что означает, что амортизированная стоимость gc постоянна. Таким образом, если у вас есть коллектор в стиле Чейни, где каждое полупространство имеет размер , то легко увидеть, что полная коллекция не может быть вызвана более одного раза каждые n / k шагов, поскольку выделение k слов требует O ( k ) время, и рабочий набор никогда не превышает размер k , что дает вам желаемую границу. Это оправдывает игнорирование проблем gc.2 кн / кКO ( k )К
Однако один случай, когда наличие или отсутствие gc не является игнорируемым, - это при записи структур данных без блокировки. Многие современные структуры данных без блокировок намеренно пропускают память и полагаются на gc для корректности. Это связано с тем, что на высоком уровне они работают так, чтобы копировать некоторые данные, вносить в них изменения и пытаться атомарно обновить их с помощью инструкции CAS и выполнять это в цикле до тех пор, пока CAS не преуспеет. Добавление детерминированного освобождения к этим алгоритмам делает их намного более сложными, и поэтому люди часто не беспокоятся (особенно потому, что они часто нацелены на Java-подобные среды).
РЕДАКТИРОВАТЬ: Если вы хотите не амортизированные границы, сборщик Чейни не будет делать это - он сканирует весь живой набор каждый раз, когда он вызывается. Ключевым словом для Google является «сборщик мусора в реальном времени», и Djikstra et al. и Стил дал первые в реальном времени коллекторно-меточные машины, а Бейкер - первый компакт-диск в реальном времени.
@article {dijkstra1978fly,
title = {{Сборка мусора на лету: совместная работа}},
author = {Dijkstra, EW and Lamport, L. and Martin, AJ and Scholten, CS and Steffens, EFM},
journal = {Сообщения ACM},
объем = {21},
число = {11},
страницы = {966--975},
= {ISSN 0001-0782},
год = {1978},
издатель = {} ACM
}
@article {steele1975multiprocessing,
title = {{Многопроцессорная компактифицирующая сборка мусора}},
author = {Стил-младший, GL},
journal = {Сообщения ACM},
объем = {18},
число = {9},
страницы = {495--508},
= {ISSN 0001-0782},
год = {1975},
издатель = {} ACM
}
@article {baker1978list,
title = {{Обработка списка в реальном времени на последовательном компьютере}},
author = {Baker Jr, HG},
journal = {Сообщения ACM},
объем = {21},
число = {4},
страницы = {280--294},
= {ISSN 0001-0782},
год = {1978},
издатель = {} ACM
}
List.map
в OCaml на самом деле является квадратичной сложностью, потому что глубина стека является линейной, и стека обходят каждый раз, когда питомник эвакуируется. То же самое касается основных кусков, встречающихся с большими массивами указателей.Полная ссылка на сборку мусора:
Бен Цорн проделал определенную работу по измерению фактических затрат на различные алгоритмы сбора мусора, хотя в более поздней статье приведено гораздо более полное сравнение:
Для более подробной информации смотрите:
источник