Как реализовать закрытие без gc?

Question

Я разрабатываю язык. Во-первых, я хочу решить, какой код сгенерировать. Язык будет иметь лексические замыкания и основанное на прототипе наследование, подобное javascript. Но я не поклонник gc и стараюсь избегать как можно большего. Итак, вопрос: есть ли элегантный способ реализовать закрытие, не прибегая к тому, чтобы выделить стек стека в кучу и оставить его сборщику мусора?

Мои первые мысли:

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

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

(Edit: Я знаю, что подсчет ссылок является формой сбора мусора, но я использую дс в более общем смысле)

Answer 1

Это было бы лучше вопрос, если вы можете объяснить, что вы пытаетесь избежать, не используя GC. Как я уверен, вы знаете, большинство языков, которые предоставляют лексические замыкания, выделяют их в кучу и позволяют им сохранять ссылки на привязки переменных в записи активации, которая их создала.

Единственная альтернатива этому подходу, о которой я знаю, это то, что gcc использует для вложенных функций: создайте батут для функции и выделите ее в стеке. Но, как написано в руководстве gcc:

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

Короткая версия, у вас есть три основных варианта:

• выделят замыкания на стеке, и не позволяют использовать их после того, как их содержащих выходы функции.
• выделять замыкания на кучу и использовать какую-то сборку мусора.
• сделайте оригинальное исследование, возможно, начиная с региона, который ML, Cyclone и т. Д. Есть.

Answer 2

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

Вы также можете посмотреть на подход C++ 0x (N1968), хотя, как можно было бы ожидать от C++, он состоит в том, чтобы рассчитывать на программиста, чтобы указать, что копируется и на что ссылается, и если вы ошибаетесь, вы просто получить недействительные обращения.

Answer 3

Или просто не делайте GC вообще. Могут быть ситуации, когда лучше просто забыть утечку памяти и позволить процессу очистить после нее, когда это будет сделано.

В зависимости от ваших проблем с GC, вы можете опасаться периодических сборок GC. В этом случае вы можете сделать выборочный GC, когда элемент выпадает из области видимости или изменяется указатель. Я не уверен, насколько это было бы дорого.

@Allen

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

Answer 4

Спецификация C++ 0x определяет lambdas без сбора мусора. Короче говоря, спецификация допускает недетерминированное поведение в тех случаях, когда лямбда-замыкание содержит ссылки, которые более недействительны. Например (псевдо-синтаксис):

(int)=>int create_lambda(int a) 
{ 
    return { (int x) => x + a } 
} 

create_lambda(5)(4) // undefined result 

лямбда в этом примере относится к переменной (a), который выделяется в стеке. Тем не менее, этот стек стека был вставлен и не равен , доступный после возвращения функции. В этом случае он, вероятно, сработает и вернет 9 (при условии семантики разумного компилятора), но гарантировать его невозможно.

Если вы избегаете сбора мусора, то я предполагаю, что вы также допускаете явное распределение кучи и стека и (возможно) указатели. Если это так, то вы можете сделать, как C++, и просто предположите, что разработчики, использующие ваш язык, будут достаточно умны, чтобы выявлять проблемы с lambdas и копировать в кучу явно (точно так же, как если бы вы возвращали значение, синтезированное внутри функция).

Answer 5

Используйте подсчет ссылок и собирать мусор циклов (я на самом деле не так)

Можно создать свой язык, так что нет циклов: если вы можете сделать только новые объекты и не мутировать старые, и если создание объекта не может сделать цикл, то циклы никогда не появятся. Эрланг работает по существу таким образом, хотя на практике он использует GC.

Answer 6

Создать несколько стеков?

Answer 7

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

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

Answer 8

Я прочитал, что последние версии ML использовать GC только экономно

Answer 9

This thread может помочь, хотя некоторые из ответов здесь отражают ответы уже там.

Один плакат делает хорошую точку:

кажется, что вы хотите, вывоз мусора для закрытия «в отсутствие истинного сбора мусора». Обратите внимание, что для реализации cons-ячеек могут использоваться замыкания .Так что ваш вопрос , по-видимому, о сборке мусора «при отсутствии истины сбор мусора» - есть богатая литература. Ограничение проблемы с закрытием на самом деле не меняет ее.

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

Итак, мой вопрос отражает некоторые из других здесь - почему вы не хотите внедрять GC? Простая метка + развертка или стоп + копия занимает около 2-300 строк кода (Scheme), и на самом деле это не так плохо с точки зрения усилий по программированию. С точки зрения замедления ваших программ:

1. Вы можете реализовать более сложный GC, который имеет лучшую производительность.
2. Просто подумайте обо всех программах утечки памяти на вашем языке, от которых не будет страдать.
3. Кодирование с доступной GC является благословением. (Think C#, Java, Python, Perl и т. Д.) Против C++ или C).

Answer 10

Я понимаю, что я очень поздно, но случайно наткнулся на этот вопрос.

Я считаю, что полная поддержка замыканий действительно требует GC, но в некоторых особых случаях распределение стека безопасно. Для определения этих особых случаев требуется анализ эвакуации. Я предлагаю вам взглянуть на BitC language papers, например Closure Implementation in BitC. (Хотя я сомневаюсь, что документы отражают текущие планы.) У дизайнеров BitC была та же проблема, что и вы. Они решили реализовать специальный не-сборщик для компилятора, который отрицает все блокировки, которые могут уйти. Если он включен, это значительно ограничит язык. Однако эта функция еще не реализована.

Я бы посоветовал вам использовать коллекционер - это самый элегантный способ. Вы также должны учитывать, что сборщик сборщиков мусора выделяет память быстрее, чем malloc. Люди BitC действительно ценят производительность, и они по-прежнему считают, что GC отлично подходит даже для большинства частей операционной системы Coyotos. Вы можете migitate минусов простых средств:

• создает лишь минимальное количество мусора
• Пусть управление программистом коллектор
• оптимизирует стек/использование кучи с помощью анализа эвакуации
• использовать инкрементальный или одновременно коллектор
• если как-то можно, разделить кучу как Erlang делает

Многие боятся сборщики мусора becau из-за их опыта работы с Java. Java имеет фантастический коллекционер, но приложения, написанные на Java, имеют проблемы с производительностью из-за огромного количества вывозимого мусора. Кроме того, раздутая среда выполнения и причудливая компиляция JIT на самом деле не являются хорошей идеей для настольных приложений из-за более длительного времени запуска и ответа.

Answer 11

Лучше поздно, чем никогда?

Возможно, это интересно: Differential Execution.

Это малоизвестная контрольная структура, и ее основное использование заключается в программировании пользовательских интерфейсов, в том числе тех, которые могут динамически меняться во время использования. Это значительная альтернатива парадигме Model-View-Controller.

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

Answer 12

Я думаю, если процесс очень короткий, что означает, что он не может использовать много памяти, тогда GC не нужен. Ситуация аналогична беспокойству о переполнении стека. Не гнездайтесь слишком глубоко, и вы не можете переливаться; не запускайте слишком долго, и вам не понадобится GC. Очистка становится вопросом простого восстановления большого региона, который вы предварительно выделили. Даже более длительный процесс можно разделить на более мелкие процессы, у которых есть свои собственные кучи, предварительно выделенные. Например, это хорошо работает с обработчиками событий. Это не работает, если вы пишете компилятор; в этом случае GC, безусловно, не является большим препятствием.

Answer 13

Таким образом, вопрос: существует ли элегантный способ реализовать замыкания, не прибегая к тому, чтобы выделить стек стека в кучу и оставить его сборщику мусора?

GC - единственное решение для общего случая.