Будет ли компилятор C / C ++ оптимизировать код путем повторного использования недавно вычисленного результата функции?

Question

Предположим, у меня есть функция double F(double x), и давайте предположим, что в этом примере вызовы F стоят дорого.

Предположим, я пишу функцию f, которая вычисляет квадратный корень из F:

double f(double x){
   return sqrt(F(x));
}

и в третьей функции sum Я вычисляю сумму f и F:

double sum(double x){
   return F(x) + f(x);
}

Поскольку я хочу минимизировать вызовы на F, приведенный выше код неэффективен по сравнению, например, с

double sum_2(double x){
   double y = F(x);
   return y + sqrt(y);
}

Но так как я ленивый, или глупый, или хочу сделать свой код максимально понятным, я выбрал первое определение.

Будет ли компилятор C / C ++ оптимизировать мой код в любом случае, понимая, что значение F(x) можно использовать повторно для вычисления f(x), как это делается в sum_2?

Большое спасибо.

Answer 1

Будет ли компилятор C / C ++ оптимизировать мой код в любом случае, понимая, что значение F (x) можно повторно использовать для вычисления f (x), как это делается в sum_2?

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

Вполне вероятно, что компилятор встроит функцию f() в функцию sum(), что даст ему возможность распознать, что есть два вызова F(x), способствующие одинаковому результату. В этом случае, если F() не имеет побочных эффектов, тогда возможно, что компилятор отправит только один вызов F(), повторно используя результат.

Определенные реализации могут иметь расширения, которые могут использоваться, чтобы помочь компилятору прийти к такому выводу. Однако, если такое расширение не будет применено к проблеме, вряд ли компилятор выдаст код, который выполняет только один вызов F() и повторно использует результат.

Answer 2

То, что вы описываете, называется памятка , форма (обычно) кэширования во время выполнения. Хотя это возможно реализовать в компиляторах, чаще всего не выполняется в компиляторах C.

C ++ имеет умный обходной путь для этого, используя STL, подробности в этом сообщении в блоге несколько лет назад; есть также немного более свежий SO-ответ здесь . Стоит отметить, что при таком подходе компилятор не «умно» делает вывод, что несколько идентичных результатов функции будут использованы повторно, но эффект в значительной степени тот же.

Некоторые языки, такие как Haskell, имеют встроенную поддержку для запоминания во время компиляции, но архитектура компилятора довольно сильно отличается от Clang или GCC / G ++.

Answer 3

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

for (int i=0; i < strlen(str); i++)

Без оптимизации этого сложность этого цикла составляет не менее O (n ² ), но после оптимизации это может быть O (n).

Подсказки, которые могут взять gcc, clang и многие другие: __attribute__((pure)) и __attribute__((const)), которые описаны здесь . Например, GNU strlen объявлен как чистая функция.

GCC может обнаруживать чистые функции и предлагать программисту, какие функции должны быть женаты в чистом виде. Фактически, это происходит автоматически для следующего упрощенного примера:

unsigned my_strlen(const char* str) 
{
    int i=0;
    while (str[i])
       ++i;
    return i;
} 

unsigned word_len(const char *str)
{
    for (unsigned i=0 ; i < my_strlen(str); ++i) {
        if (str[i] == ' ')
           return i;
    }
    return my_strlen(str);
}

Вы можете посмотреть результат компиляции для gcc с -O3 -fno-inline. Он вызывает my_strlen(str) только один раз за всю функцию word_len. Clang 7.0.0, похоже, не выполняет эту оптимизацию.

word_len:
        mov     rcx, rdi
        call    my_strlen ; <-- this is the only call (outside any loop)
        test    eax, eax
        je      .L7
        xor     edx, edx
        cmp     BYTE PTR [rcx], 32
        lea     rdi, [rdi+1]
        jne     .L11
        jmp     .L19
.L12:
        add     rdi, 1
        cmp     BYTE PTR [rdi-1], 32
        je      .L9
.L11:
        add     edx, 1
        cmp     eax, edx
        jne     .L12
.L7:
        ret
.L19:
        xor     edx, edx
.L9:
        mov     eax, edx
        ret