Почему компиляторы Haskell не способствуют детерминированному управлению памятью?

Question

Имея богатую информацию о типах, почему среды выполнения Haskell не могут избежать очистки GC? Должна быть возможность выяснить все случаи использования и вставить соответствующие вызовы для alloc / release в скомпилированный код, верно? Это позволит избежать накладных расходов во время выполнения GC.

Answer 1

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

Стоит обратить внимание на работу Мартина Хофманна и его команды по проекту «Гарантии мобильных ресурсов», который сделал выделение памяти типа (de / re) основной темой. Однако то, что заставляет их работать, - это то, чего Хаскелл не имеет в своей системе типов - линейность. Если вы знаете, что входные данные функции секрет из остальной части вычислений, вы можете перераспределить память, которую они занимают. Материал MRG особенно хорош, потому что он управляет реалистичным обменным курсом между освобождением для одного типа и распределением для другого, что превращается в старомодное старомодное манипулирование указателями под чисто функциональным внешним видом. Фактически, множество прекрасных алгоритмов скупой мутации (например, обратного обращения указателя, построения перезаписывающего хвостового указателя и т. Д.) Могут выглядеть чисто функциональными (и проверяться на наличие неприятных ошибок) с помощью этих методов.

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

TL; DR Есть хорошие типизированные подходы к анализу использования, которые сокращают GC, но у Haskell сейчас неправильная информация о типах, чтобы быть особенно полезной для этой цели.

Answer 2

Управление памятью на региональном уровне - это то, что программисты на C и C ++ часто заканчивают программированием вручную: выделяют кусок памяти («регион», «арена» и т. Д.), Выделяют в нем отдельные данные, используют их и в конце концов освободите весь блок, когда вы знаете, что больше не нужны никакие отдельные данные. Работа Тофте, Айкена и других, проведенная в 90-х годах (в том числе и ваша, с нашими соответствующими коллегами), показала, что можно автоматически определять точки распределения и освобождения регионов («логический вывод региона») таким образом, чтобы гарантируйте, что блоки никогда не будут освобождены слишком рано и, на практике, достаточно рано, чтобы избежать удержания слишком большого количества памяти надолго после того, как потребовались последние данные в ней. Например, ML Kit для регионов - это полный стандартный компилятор ML, основанный на выводе региона. В окончательной версии он объединен с внутрирегиональной сборкой мусора: если статический вывод показывает, что существует долгоживущий регион, используйте сборку мусора внутри него. Вы получаете свой торт и едите его тоже: у вас есть сборка мусора для долгоживущих данных, но большая часть данных управляется как стек, хотя обычно она заканчивается в куче.

Answer 3

Рассмотрим следующий псевдокод:

func a = if some_computation a
    then a
    else 0

Чтобы узнать, является ли a мусором после вызова func a, компилятор должен иметь возможность узнать результат some_computation a.Если бы он мог сделать это в общем случае (который требует решения проблемы остановки), то вообще не было бы необходимости генерировать код для этой функции, не говоря уже о сборщике мусора.Информация о типе недостаточна.

Answer 4

Нелегко определить время жизни объекта с ленивой оценкой. Компилятор JHC имеет (имел?) Управление областью памяти, которое пытается освободить память путем освобождения, когда время жизни истекло.

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

Answer 5

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