Блог

Главная - Вопросы по программированию - Локальные переменные и оптимизация конечных вызовов

Локальные переменные и оптимизация конечных вызовов

#c #scope #tail-recursion

#c #область видимости #конечная рекурсия

Вопрос:

Я хочу понять последствия оптимизации конечных вызовов в C . Рассмотрим следующий фрагмент кода:

 #include <iostream>
#include <string>

size_t mystrlen(const char* input, size_t size = 0){
    if(!*input){
        return size;
    }else{
        std::string str(input 1);
        return mystrlen(str.c_str(),size   1);
    }
}

int main(void){
    std::cout << mystrlen("Foo") << std::endl; //3
}

mystrlen это (бесполезная) функция, которая вычисляет длину предоставленной строки C. Рассмотрим ветку else: создается новый std::string экземпляр, и его внутренний буфер используется в качестве входных данных для следующего вызова. Если произойдет оптимизация конечных вызовов, и не будут созданы новые кадры стека, не приведет ли это к ошибке, поскольку локальная переменная str будет уничтожена до следующего вызова?

Комментарии:

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

2. Я предполагаю (основываясь на интуиции и логических выводах), что оптимизация конечных вызовов невозможна, если время жизни объекта, отличного от POD, содержит оператор рекурсивного возврата (т. Е. Он создается до, уничтожается после возврата), потому что для каждой рекурсии существует другой объект. Поэтому для всех этих объектов требуется место… [Если только компилятор не сможет обнаружить, что объект вообще не нужен, как в этом коде ;)]

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

4. Что отличает C от многих других языков, так это его тенденция генерировать объектный код, «не соответствующий исходному коду». Для некоторых это огромное преимущество, для других — огромный недостаток. В вашем случае return оператор не является последним в потоке выполнения. Последний оператор в потоке выполнения — } это следующий. То, что в вашей функции выглядит как конечный вызов, на самом деле таковым не является.

Ответ №1:

Оптимизация конечных вызовов в C подпадает под свободу оптимизации «как если бы», которой обладают компиляторы C .

За исключением компилятора с чрезвычайно подробными знаниями std::string на высоком уровне, то, что вы сделали, заблокирует оптимизацию конечных вызовов, поскольку после завершения рекурсивного вызова необходимо вызвать нетривиальный деструктор.

Ответ №2:

Во-первых, вы хотите избавиться от std::string в этом случае:

 size_t mystrlen(const char* input, size_t size = 0) {
    if(!*input){
        return size;
    } else {
        return mystrlen(input   1, size   1);
    }
}

тогда вы можете видеть, что ваша оптимизация конечных вызовов будет просто:

 size_t mystrlen(const char* input) {
    size_t size = 0;
    while (!*(input   size))   size;
    return size;
}

Комментарии:

1. Я специально использовал std::string экземпляр, так как хотел знать, как локальные (нетривиальные) переменные влияют на результат оптимизации конечных вызовов. Иначе я бы никогда не написал такую функцию 😉

Метки: