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

63

Предполагается, что в таких языках, как C, программист вставляет вызовы бесплатно. Почему компилятор не делает это автоматически? Люди делают это в разумные сроки (игнорируя ошибки), поэтому это не невозможно.

РЕДАКТИРОВАТЬ: Для дальнейшего использования, вот еще одна дискуссия, которая имеет интересный пример.

Милтон Сильва
источник
125
И именно поэтому, дети, мы учим вас теории вычислимости. ;)
Рафаэль
7
Это не проблема вычислимости, так как люди не могут решить во всех случаях. Это проблема полноты; операторы освобождения содержат информацию, которая в случае удаления не может быть полностью восстановлена ​​анализом, если этот анализ не содержит информацию о среде развертывания и ожидаемой операции, которую не содержит исходный код на языке Си.
Nat
41
Нет, это проблема вычислимости. Это неразрешимое , следует ли освобождаться данный кусок памяти. Для фиксированной программы нет ввода пользователя или других внешних помех.
Андрей Бауэр
1
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат . Все комментарии, которые конкретно не касаются вопроса и того, как его можно улучшить, будут удалены сразу же.
Рафаэль
2
@BorisTreukhov, пожалуйста, отнесите это в чат. Нет, я не думаю, что Андрей говорит, что анализ побега "невозможен" (хотя определить, что именно это означает в этом контексте, немного неясно для меня). Совершенно точный анализ побега является неразрешимым. Для всех: пожалуйста, отнесите это в чат . Пожалуйста, оставляйте здесь только комментарии, направленные на улучшение вопроса - другие обсуждения и комментарии должны быть размещены в чате.
DW

Ответы:

81

Потому что неясно, будет ли программа снова использовать память. Это означает, что ни один алгоритм не может правильно определить, когда вызывать free()во всех случаях, что означает, что любой компилятор, который пытался это сделать, обязательно генерировал бы некоторые программы с утечками памяти и / или некоторые программы, которые продолжали использовать освобожденную память. Даже если вы обеспечите, чтобы ваш компилятор никогда не делал второй, и позволили программисту вставлять вызовы для free()исправления этих ошибок, знать, когда вызывать free()этот компилятор, будет даже сложнее, чем знать, когда вызывать free()при использовании компилятора, который не пытался помогать.

Дэвид Ричерби
источник
12
У нас есть вопрос, который касается способности людей решать неразрешимые проблемы . Я не могу дать вам пример программы, которая была бы скомпилирована неправильно, потому что это зависит от того, какой алгоритм использует компилятор. Но любой алгоритм выдаст неверный вывод для бесконечно большого количества разных программ.
Дэвид Ричерби
1
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Жиль "ТАК - перестань быть злым"
2
Ребята, возьмите это в чат . Все, что не имеет прямого отношения к самому ответу и как его можно улучшить, будет удалено.
Рафаэль
2
Многие вещи, которые компиляторы делают счастливо, вообще неразрешимы; мы бы никуда не попали в мир компиляторов, если бы всегда уступали теореме Райс.
Тихон Джелвис
3
Это не имеет значения. Если это неразрешимо для всех компиляторов, это неразрешимо и для всех людей. Все же мы ожидаем, что люди вставят free()правильно.
Пол Дрейпер
53

Как справедливо заметил Дэвид Ричерби, проблема в целом неразрешима. Жизнеспособность объекта является глобальным свойством программы и может в целом зависеть от входных данных для программы.

Даже точная динамическая сборка мусора - неразрешимая проблема! Все реальные сборщики мусора используют достижимость как консервативное приближение к тому, понадобится ли выделенный объект в будущем. Это хорошее приближение, но, тем не менее, это приближение.

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

Реализации, основанные на подсчете ссылок, очень близки к «освобождению компилятора», так что трудно заметить разницу. LLVM «ы автоматический подсчет ссылок (используется в Objective-C и Swift ) является известным примером.

Вывод области и сборка мусора во время компиляции - текущие активные области исследования. Оказывается, намного проще в декларативных языках, таких как ML и Mercury , где вы не можете изменить объект после его создания.

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

  1. По пониманию программы и проблемы. Например, люди могут помещать объекты с одинаковым временем жизни в один и тот же объект размещения. Компиляторы и сборщики мусора должны сделать это, но у людей есть более точная информация.
  2. Выборочно используя нелокальное ведение бухгалтерского учета (например, подсчет ссылок) или другие специальные методы распределения (например, зоны) только при необходимости. Опять же, человек может знать это, когда компилятор должен сделать вывод.
  3. Плохо. Все знают о реальных развернутых программах, которые в конце концов имеют медленную утечку. Или, если они этого не делают, иногда программы и внутренние API-интерфейсы необходимо реструктурировать в соответствии с временем жизни памяти, уменьшая возможность повторного использования и модульность.
Псевдоним
источник
Комментарии не для расширенного обсуждения. Если вы хотите обсудить декларативный или функциональный функционал, сделайте это в чате .
Жиль "ТАК - перестань быть злым"
2
Это, безусловно, лучший ответ на вопрос (на который слишком много ответов даже не обращаются). Вы могли бы добавить ссылку на новаторскую работу Ханса Бёма по созданию вторичного GC : en.wikipedia.org/wiki/Boehm_garbage_collector . Другим интересным моментом является то, что живучесть данных (или полезность в расширенном смысле) может быть определена относительно абстрактной семантики или модели исполнения. Но тема действительно широкая.
Бабу
29

Это проблема неполноты, а не неразрешимости

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

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

Например, предположим, что вы пишете Read-Evaluate-Print-Loop (REPL) : пользователь вводит команду, а ваша программа выполняет ее. Пользователь может выделить / освободить память, введя команды в ваш REPL. Ваш исходный код будет указывать, что REPL должен делать для каждой возможной пользовательской команды, включая освобождение, когда пользователь вводит команду для нее.

Но если в исходном коде C нет явной команды для освобождения, то компилятору потребуется сделать вывод, что он должен выполнить делокацию, когда пользователь вводит соответствующую команду в REPL. Эта команда «освобождает», «освобождает» или что-то еще? Компилятор не может знать, какой командой вы хотите быть. Даже если вы программируете в логике, чтобы искать это командное слово, и REPL находит его, компилятор не может знать, что он должен ответить на него освобождением, если вы явно не указали это в исходном коде.

tl; dr Проблема в том, что исходный код на C не предоставляет компилятору внешние знания. Неразрешимость не является проблемой, потому что она существует независимо от того, является ли этот процесс ручным или автоматическим.

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

В настоящее время ни один из опубликованных ответов не является полностью правильным.

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

  1. Некоторые делают. (Я объясню позже.)

  2. Тривиально, вы можете позвонить free()перед выходом из программы. Но в вашем вопросе подразумевается необходимость звонить free()как можно скорее.

  3. Проблема того, когда вызывать free()в любой C-программе, как только память недоступна, неразрешима, т. Е. Для любого алгоритма, предоставляющего ответ за конечное время, есть случай, который он не охватывает. Это - и многие другие неразрешимости произвольных программ - могут быть доказаны из проблемы останова .

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

  5. Люди (пытаются) написать в подмножестве программ на С, которые могут быть проверены на правильность памяти их алгоритмом (сами).

  6. Некоторые языки достигают # 1, встроив # 5 в компилятор. Они не позволяют программам с произвольным использованием распределения памяти, а скорее разрешимым подмножеством их. Foth и Rust - два примера языков, которые имеют более ограниченное распределение памяти, чем C malloc(), которые могут (1) обнаружить, написана ли программа вне их разрешимого набора (2), автоматически вставлять освобождения.

Пол Дрэйпер
источник
1
Я понимаю, как это делает Rust. Но я никогда не слышал о Форт, который сделал это. Можете ли вы уточнить?
Милтон Сильва
2
@MiltonSilva, Forth - по крайней мере, его самая базовая, оригинальная реализация - имеет только стек, а не кучу. Это делает выделение / освобождение перемещением указателя стека вызовов, задача, которую может легко выполнить компилятор. Forth был сделан, чтобы предназначаться для очень простого аппаратного обеспечения, и иногда нединамическая память - все, что работоспособно. Это, очевидно, нереальное решение для нетривиальных программ.
Пол Дрейпер
10

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

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

Андре Соуза Лемос
источник
1
Ошибочность принятия предпосылки человеческой ошибочности и все же допущения, что созданные человеком мыслительные машины все еще могут быть непогрешимыми (то есть лучше, чем люди), менее известна, но более интригует. Единственное предположение, из которого может исходить действие, состоит в том, что человеческий разум обладает потенциалом для совершенных вычислений.
Wildcard
1. Я никогда не говорил, что думающие машины могут быть непогрешимыми. Во многих случаях они лучше, чем люди. 2. Ожидание совершенства (даже потенциального) как предпосылки для действий - абсурд.
Андре Соуза Лемос
«Мы можем когда-нибудь, возможно, не слишком далеко, быть заменены искусственным интеллектом на работе». Это, в частности, ерунда. Люди являются источником намерений в системе. Без людей нет цели для системы. «Искусственный интеллект» может быть определен как очевидность интеллектуального решения, принимаемого в настоящее время машинами, на самом деле вызванного интеллектуальными решениями программиста или системного разработчика в прошлом. Если нет технического обслуживания (которое должно быть выполнено человеком), AI (или любая система, оставленная без проверки и полностью автоматическая), выйдет из строя.
Wildcard
У людей, как и у машин, намерение всегда приходит извне .
Андре Соуза Лемос
Совершенно не соответствует действительности. (И также «снаружи» не определяет источник. ) Либо вы заявляете, что намерение как таковое на самом деле не существует, либо вы заявляете, что намерение существует, но не откуда-либо. Возможно, вы верите, что намерение может существовать независимо от цели? В этом случае вы неправильно понимаете слово «намерение». В любом случае, персональная демонстрация вскоре изменит ваше мнение по этому вопросу. Я остановлюсь после этого комментария, поскольку одни только слова не могут привести к пониманию «намерения», поэтому дальнейшее обсуждение здесь бессмысленно.
Wildcard
9

Отсутствие автоматического управления памятью является особенностью языка.

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

Джуни Сирен
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
DW
2
Как это ответ на вопрос (часть CS)?
Рафаэль
6
@Raphael Информатика не означает, что мы должны искать неясные технические ответы. Компиляторы делают много вещей, которые невозможны в общем случае. Если нам нужно автоматическое управление памятью, мы можем реализовать его разными способами. С не делает этого, потому что это не должно делать.
Джуни Сирен
9

Проблема в основном исторический артефакт, а не невозможность реализации.

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

Если вы посмотрите на более современные низкоуровневые языки, такие как C ++ 11 или Rust, вы обнаружите, что они в основном решили проблему, сделав явное владение памятью в типе указателя. В C ++ вы должны использовать unique_ptr<T>вместо обычного T*для хранения памяти, и он unique_ptr<T>гарантирует, что память освобождается, когда объект достигает конца области, в отличие от простого T*. Программист может передавать память от одного unique_ptr<T>к другому, но может быть только один, unique_ptr<T>указывающий на память. Так что всегда понятно, кому принадлежит память и когда ее нужно освободить.

C ++ по причинам обратной совместимости все еще допускает ручное управление памятью старого стиля и, таким образом, создание ошибок или способов обойти защиту unique_ptr<T>. Rust еще более строг в том смысле, что он обеспечивает соблюдение правил владения памятью через ошибки компилятора.

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

Grumbel
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Рафаэль
6

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

Одной из проблем, которая еще не была рассмотрена, является неизбежная задержка сбора мусора. В C, когда программист вызывает free (), эта память сразу же доступна для повторного использования. (По крайней мере, в теории!) Таким образом, программист может освободить свою структуру размером 100 МБ, выделить еще одну структуру размером 100 МБ спустя миллисекунду и ожидать, что общее использование памяти останется прежним.

Это не так с сборкой мусора. Системы сбора мусора имеют некоторую задержку при возврате неиспользуемой памяти в кучу, и это может быть значительным. Если ваша структура размером 100 МБ выходит из области видимости, и спустя миллисекунду ваша программа устанавливает другую структуру размером 100 МБ, вы можете ожидать, что ваша система будет использовать 200 МБ в течение короткого периода времени. Этот «короткий период» может составлять миллисекунды или секунды, в зависимости от системы, но все равно есть задержка.

Если вы работаете на ПК с гигабайтами оперативной памяти и виртуальной памяти, вы, вероятно, никогда этого не заметите. Если вы работаете в системе с более ограниченными ресурсами (например, встроенной системой или телефоном), к этому нужно относиться серьезно. Это не просто теоретически - я лично видел, что это создает проблемы (например, при сбое устройства) при работе в системе WinCE с использованием .NET Compact Framework и разработке на C #.

Грэхем
источник
Теоретически вы можете запустить GC перед каждым выделением.
adrianN
4
@adrianN Но на практике это не делается, потому что это будет ментально. Точка зрения Грэма остается неизменной: GC всегда подвергаются значительным накладным расходам, либо в плане времени выполнения, либо в плане требуемой избыточной памяти. Вы можете настроить этот баланс в крайнюю сторону, но принципиально не можете снять накладные расходы.
Конрад Рудольф
«Задержка», когда освобождается память, является большей проблемой в системе виртуальной памяти, чем в системе с ограниченными ресурсами. В первом случае для программы может быть лучше использовать 100 МБ, чем 200 МБ, даже если в системе доступно 200 МБ , но во втором случае не будет никакого преимущества для запуска GC раньше, чем необходимо, если задержки не будут более приемлемыми в течение некоторого времени. части кода, чем во время других.
суперкат
Я не вижу, как это пытается ответить на вопрос (часть CS).
Рафаэль
1
@ Рафаэль Я объяснил общепризнанную проблему с принципом сбора мусора, который (или должен преподаваться) преподается в CS как один из его основных недостатков. Я даже привел свой личный опыт, когда видел это на практике, чтобы показать, что это не чисто теоретическая проблема. Если вы что-то не поняли по этому поводу, я буду рад поговорить с вами, чтобы улучшить ваши знания по этому вопросу.
Грэм
4

Вопрос предполагает, что освобождение - это то, что программист должен выводить из других частей исходного кода. Это не. «На данный момент в программе ссылка на память FOO больше не является полезной» - это информация, известная только в уме программиста, пока она не закодирована в (на процедурных языках) оператор освобождения.

Это теоретически не отличается от любой другой строки кода. Почему компиляторы не вставляют автоматически «В этой точке программы, проверьте регистр BAR для ввода» или «если вызов функции возвращает ненулевое значение, выйдите из текущей подпрограммы» ? С точки зрения компилятора причина - «неполнота», как показано в этом ответе . Но любая программа страдает от незавершенности, когда программист не рассказал ей все, что он знает.

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

Трэвис Уилсон
источник
4
«На данный момент в программе ссылка на память FOO больше не нужна» - это информация, известная только уму программиста »- это явно неверно. а) Для многих FOO это легко понять, например, локальные переменные с семантикой значений. б) Вы предполагаете, что программист знает это всегда, что явно является чрезмерно оптимистичным предположением; если бы это было правдой, у нас не было бы серьезных ошибок из-за плохой обработки памяти - это программное обеспечение, критичное для безопасности. Что, увы, мы делаем.
Рафаэль
Я просто предполагаю, что язык был разработан для случаев, когда программист знает, что FOO больше не является полезным. Я согласен, ясно, что это обычно не так, и поэтому мы должны иметь статический анализ и / или сбор мусора. Что, ура, мы делаем. Но вопрос ОП заключается в том, когда эти вещи не так ценны, как ручная кодировка?
Трэвис Уилсон
4

Что будет сделано: Существует мусор, и есть компиляторы с помощью подсчета ссылок (Objective-C, Swift). Те, кто выполняет подсчет ссылок, нуждаются в помощи программиста, избегая сильных циклов ссылок.

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

Одна из причин того, что это очень, очень трудно, конечно, что это неразрешимо. В информатике, когда мы говорим о «разрешимости», мы имеем в виду «принятие правильного решения». Конечно, программисты-люди могут легко решить, где освободить память, потому что они не ограничены правильными решениями. И они часто принимают неправильные решения.

gnasher729
источник
Я не вижу здесь вклада.
Бабу
3

Предполагается, что в таких языках, как C, программист вставляет вызовы бесплатно. Почему компилятор не делает это автоматически?

Потому что время жизни блока памяти - это решение программиста, а не компилятора.

Вот и все. Это конструкция C. Компилятор не может знать, каково было намерение выделить блок памяти. Люди могут сделать это, потому что они знают цель каждого блока памяти и когда эта цель достигается, чтобы ее можно было освободить. Это часть дизайна написанной программы.

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

Agent_L
источник
-1

Предполагается, что в таких языках, как C, программист вставляет вызовы бесплатно. Почему компилятор не делает это автоматически?

В Си и многих других языках действительно есть возможность заставить компилятор делать эквивалент этого в тех случаях, когда во время компиляции ясно, когда это должно быть сделано: использование переменных с автоматической продолжительностью (т. Е. Обычных локальных переменных) , Компилятор отвечает за организацию достаточного пространства для таких переменных и за освобождение этого пространства, когда заканчивается их (четко определенное) время жизни.

Поскольку массивы переменной длины являются функцией C, начиная с C99, объекты с автоматической продолжительностью, в принципе, обслуживают практически все функции в C, которые выполняют динамически распределяемые объекты вычислимой продолжительности. На практике, конечно, реализации C могут накладывать значительные практические ограничения на использование VLA - то есть их размер может быть ограничен в результате размещения в стеке - но это соображение реализации, а не соображение проектирования языка.

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

PellMel
источник