Записки программиста

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

Важно! В комментариях многие выразили, по всей видимости, небезосновательные сомнения относительно некоторых моментов, озвученных ниже. Короче, фигню я написал и следовало бы называть заметку «Как могла бы работать сборка мусора в неком функциональном языке программирования». Учитывайте это при чтении.

Поскольку данные в Haskell никогда не изменятся, это означает, что любые данные могут ссылаться лишь на данные, созданные ранее. Таким образом, все данные в Haskell образуют ориентированный ациклический граф. Отсутствие циклов — это очень, очень хорошо. Например, мы могли бы использовать для сборки мусора обычные счетчики ссылок.

Более того, неизменяемость данных позволяет реализовать эффективную сборку мусора по поколениям. Например, в GHC все новые данные помещаются в специальный участок памяти размером 512 Кб. Этот участок называется «ясли» («nursery»).

Когда «ясли» заполняются, запускается малая сборка мусора (minor garbage collection). На этом этапе в «яслях» отыскиваются и перемещаются в основную область памяти данные, которые до сих пор используются приложением. После этого вся память в «яслях» вновь начинает заполняться с самого начала. Получается интересная ситуация. Чем больше данных перестает существовать, тем быстрее работает сборщик мусора!

И даже после переноса данных в основную область памяти отсутствие циклических ссылок продолжает играть нам на руку. Например, нет нужды поддерживать дополнительные структуры данных на случай, если старые данные вдруг начнут ссылаться на более молодые, потому что в Haskell это просто невозможно. Кроме того, я не уверен, что есть большая необходимость запоминать, какие данные к какому поколению относятся. Ведь вместо этого при обходе графа данных можно просто ограничивать глубину поиска или число просматриваемых вершин.

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

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

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

Как обычно, я призываю вас не стесняться писать комментарии. Вполне может быть, что я в чем-то неправ. В этом случае вы ведь непременно поправите меня, правда?

Метки: Haskell, Алгоритмы, Разработка, Функциональное программирование.