Может ли оптимизация хвостового звонка и совместное использование RAII?

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

Это задает вопрос для тех реализаций, которые делают: учитывая, что деструкторы вызываются в конце области автоматической переменной, а не отдельной процедурой сбора мусора, не нарушает ли ограничение TCO, что рекурсивный вызов должен быть последним инструкции в конце функции?

Например: -

#include <iostream>

class test_object {
public:
    test_object() { std::cout << "Constructing...\n"; }
    ~test_object() { std::cout << "Destructing...\n"; }
};

void test_function(int count);

int main()
{
    test_function(999);
}

void test_function(int count)
{
    if (!count) return;
    test_object obj;
    test_function(count - 1);
}

"Constructing..." будет написано 999 раз, а затем "Destructing..." еще 999 раз. В конечном счете, 999 test_object экземпляров будут автоматически распределены до размотки. Но при условии, что реализация имеет TCO, будет существовать 1000 кадров стека или всего лишь 1?

Связано ли деструктор после рекурсивного вызова с требованиями к реализации TCO для дефакто?

Ответ 1

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

Первый и наиболее очевидный случай: если деструктор тривиален, это означает, что это деструктор по умолчанию (сгенерированный компилятором), и все под-объекты тоже имеют тривиальные деструкторы, тогда деструктор фактически не существует (всегда оптимизирован далеко). В этом случае TCO может выполняться как обычно.

Затем деструктор может быть встроен (его код берется и помещается непосредственно в функцию, а не называется как функция). В этом случае это сводится к простому некоторому "очистке" кода после оператора return. Компилятору разрешено переупорядочивать операции, если он может определить, что конечный результат тот же (правило "как-если" ), и он сделает это (в общем), если переупорядочение приведет к лучшему коду, и я бы предположил, что TCO является одним из соображений, применяемых большинством компиляторов (т.е. если он может переупорядочить такие вещи, чтобы код стал подходящим для TCO, тогда он это сделает).

И для остальных случаев, когда компилятор не может быть "достаточно умным", чтобы сделать это сам по себе, он становится ответственностью программиста. Присутствие этого автоматического вызова деструктора делает немного сложнее для программиста увидеть код утихающего TCO после хвостового вызова, но он не имеет никакого значения с точки зрения способности программиста сделать функции кандидата в ТШО. Например:

void nonRAII_recursion(int a) {
  int* arr = new int[a];
  // do some stuff with array "arr"
  delete[] arr;
  nonRAII_recursion(--a);  // tail-call
};

Теперь наивная реализация RAII_recursion может быть:

void RAII_recursion(int a) {
  std::vector<int> arr(a);
  // do some stuff with vector "arr"
  RAII_recursion(--a);  // tail-call
};  // arr gets destroyed here, not good for TCO.

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

void RAII_recursion(int a) {
  {
    std::vector<int> arr(a);
    // do some stuff with vector "arr"
  }; // arr gets destroyed here
  RAII_recursion(--a);  // tail-call
};

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

ДОБАВЛЕННОЕ ПРИМЕЧАНИЕ: Посмотрите на это таким образом, деструктор скрывает некоторый автоматический код очистки. Если вам нужен код очистки (т.е. Нетривиальный деструктор), вам понадобится его, используете ли вы RAII или нет (например, массив C-стиля или что-то еще). И тогда, если вы хотите, чтобы TCO была возможной, необходимо сделать очистку перед выполнением хвостового вызова (с RAIF или без него), и это возможно, тогда возможно, что объекты RAII будут уничтожены перед вызовом хвоста (например, помещая их в дополнительную область).

Ответ 2

Если компилятор выполняет TCO, тогда порядок, в котором вызываются деструкторы, изменяется относительно того, когда он не выполняет TCO.

Если компилятор может доказать, что это переупорядочение не имеет значения (например, если деструктор тривиален), то в соответствии с правилом as-if он может выполнять TCO. Однако в вашем примере компилятор не может доказать это и не будет выполнять TCO.