Можно ли статически предсказать, когда освободить память - только из исходного кода?

Память (и блокировки ресурсов) возвращаются в ОС в детерминированных точках во время выполнения программы. Поток управления программой сам по себе достаточен, чтобы знать, где, без сомнения, данный ресурс может быть освобожден. Точно так же, как человек-программист знает, куда писать, fclose(file)когда программа завершает работу с ним.

GC решают эту проблему, выясняя это непосредственно во время выполнения, когда выполняется поток управления. Но реальным источником правды о потоке управления является источник. Таким образом, теоретически, должно быть возможно определить, куда вставить free()вызовы перед компиляцией, анализируя источник (или AST).

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

Кажется, что можно написать программу, которая может читать исходный код программы и:

1. предсказывать все перестановки потока управления программой - с такой же точностью, как наблюдение за выполнением программы в реальном времени
2. отслеживать все ссылки на выделенные ресурсы
3. для каждой ссылки просмотрите весь последующий поток управления, чтобы найти самую раннюю точку, на которую ссылка никогда не будет разыменована
4. в этот момент вставьте оператор освобождения в этой строке исходного кода

Есть ли что-нибудь, что уже делает это? Я не думаю, что интеллектуальные указатели Rust или C ++ / RAII - это одно и то же.

Возьмите этот (надуманный) пример:

void* resource1;
void* resource2;

while(true){

    int input = getInputFromUser();

    switch(input){
        case 1: resource1 = malloc(500); break;
        case 2: resource2 = resource1; break;
        case 3: useResource(resource1); useResource(resource2); break;
    }
}

Когда следует позвонить бесплатно? перед malloc и назначить resource1мы не можем, потому что это может быть скопировано resource2, перед назначением resource2мы не можем, потому что мы могли получить 2 от пользователя дважды без промежуточной 1.

Единственный способ убедиться в этом - это проверить resource1 и resource2, чтобы увидеть, не равны ли они в случаях 1 и 2, и освободить старое значение, если их нет. По сути, это подсчет ссылок, когда вы знаете, что есть только 2 возможных ссылки.

RAII автоматически не то же самое, но он имеет тот же эффект. Он дает простой ответ на вопрос "как вы узнаете, когда к нему больше нельзя получить доступ?" с помощью области действия, чтобы покрыть область, когда конкретный ресурс используется.

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

Можно написать доказательства о поведении программы, не решая проблему остановки, но только если вы используете какие-то аннотации для ограничения программы. Смотрите также доказательства безопасности (sel4 и т. Д.)

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

Ретроспектива по управлению памятью на региональном уровне - это статья первоначальных авторов ML Kit, в которой рассматриваются ее успехи и неудачи. Окончательный вывод состоит в том, что стратегия является практичной при написании с помощью профилировщика кучи.

(Это хорошая иллюстрация того, почему вы не должны обращаться к проблеме остановки, чтобы найти ответ на практические инженерные вопросы: мы не хотим или не должны решать общий случай для большинства реалистичных программ.)

предсказать все перестановки потока управления программой

Вот в чем проблема. Количество перестановок настолько велико (на практике это бесконечно) для любой нетривиальной программы, что необходимое время и память сделали бы это абсолютно непрактичным.

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

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

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

Однако, когда вы учитываете сторонние DLL, API, фреймворки (и также добавляете потоки), для программистов, использующих программисты, может быть очень трудно (нет, невозможно во всех случаях) правильно определить, какой сущности принадлежит какая память и когда последнее использование это. Наш обычный подозреваемый в языках недостаточно документирует передачу в память владения объектами и массивами, мелкими и глубокими. Если программист не может рассуждать об этом (статически или динамически!), То компилятор, скорее всего, тоже не может. Опять же, это связано с тем, что передачи владения памятью не фиксируются при вызовах методов или интерфейсах и т. Д., Поэтому невозможно статически предсказать, когда или где в коде освободить память.

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

Есть несколько альтернатив (некоторые появляются).

Язык Rust доводит RAII до крайности. Он предоставляет лингвистические конструкции, которые более подробно определяют передачу владения в методах классов и интерфейсов, например, объекты, передаваемые или заимствованные между вызывающим и вызываемым объектами, или объекты с более длительным сроком службы. Это обеспечивает высокий уровень безопасности времени компиляции для управления памятью. Тем не менее, это не простой язык для восприятия, а также не без проблем (например, я не думаю, что дизайн полностью стабилен, некоторые вещи все еще экспериментируют и, таким образом, меняются).

Swift и Objective-C идут еще одним маршрутом, который в основном - автоматический подсчет ссылок. При подсчете ссылок возникают проблемы с циклами, и, например, существуют серьезные проблемы для программистов, особенно с замыканиями.

Если программа не зависит от какого-либо неизвестного ввода, тогда да, это должно быть возможно (с оговоркой, что это может быть сложной задачей и может занять много времени, но это также будет верно для программы). Такие программы будут полностью разрешимы во время компиляции; в терминах C ++ они могут (почти) полностью состоять из constexprs. Простыми примерами будет вычисление первых 100 цифр числа Пи или сортировка известного словаря.

В общем, освобождение памяти эквивалентно проблеме остановки - если вы не можете статически определить, будет ли программа останавливаться (статически), вы также не сможете определить, освободит ли она память (статически).

function foo(int a) {
    void *p = malloc(1);
    ... do something which may, or may not, halt ...
    free(p);
}

https://en.wikipedia.org/wiki/Halting_problem

Тем не менее, Rust очень хороший ... https://doc.rust-lang.org/book/ownership.html