G++ С++ 11 оценка эффективности constexpr

g++ (4.7.2) и аналогичные версии, похоже, неожиданно оценивают constexpr во время компиляции. На моих машинах на самом деле намного быстрее, чем скомпилированная программа во время выполнения.

Есть ли разумное объяснение этого поведения? Применяются ли какие-либо методы оптимизации применимо во время компиляции, которое может быть выполнено быстрее, чем фактический скомпилированный код? Если да, то какой?

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

#include <iostream>

constexpr int mc91(int n)
 {

     return (n > 100)? n-10 : mc91(mc91(n+11));

 }

constexpr double foo(double n)
{
   return (n>2)? (0.9999)*((unsigned int)(foo(n-1)+foo(n-2))%100):1;
}

constexpr unsigned ack( unsigned m, unsigned n )
{
    return m == 0
        ? n + 1
        : n == 0
        ? ack( m - 1, 1 )
        : ack( m - 1, ack( m, n - 1 ) );
}

constexpr unsigned slow91(int n) {
   return mc91(mc91(foo(n))%100);
}

int main(void)
{
   constexpr unsigned int compiletime_ack=ack(3,14);
   constexpr int compiletime_91=slow91(49);
   static_assert( compiletime_ack == 131069, "Must be evaluated at compile-time" );
   static_assert( compiletime_91  == 91,     "Must be evaluated at compile-time" );
   std::cout << compiletime_ack << std::endl;
   std::cout << compiletime_91  << std::endl;
   std::cout << ack(3,14) << std::endl;
   std::cout << slow91(49) << std::endl;
   return 0;
}

compiletime:

time g++ constexpr.cpp -std=c++11 -fconstexpr-depth=10000000 -O3 

real    0m0.645s
user    0m0.600s
sys     0m0.032s

во время выполнения:

time ./a.out 

131069
91
131069
91

real    0m43.708s
user    0m43.567s
sys     0m0.008s

Здесь mc91 является обычным mac carthy f91 (как можно найти в wikipedia), а foo - это просто бесполезная функция, возвращающая реальные значения от 1 до 100 с сложностью выполнения Flash.

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

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

Ответы

Ответ 1

Во время компиляции избыточные (идентичные) вызовы constexpr могут быть memoized, в то время как рекурсивное поведение во время выполнения не предоставляет этого.

Если вы меняете каждую рекурсивную функцию, например...

constexpr unsigned slow91(int n) {
   return mc91(mc91(foo(n))%100);
}

... в форму, которая не является constexpr, но делает помнит прошлые вычисления во время выполнения:

std::unordered_map< int, boost::optional<unsigned> > results4;
//     parameter(s) ^^^           result ^^^^^^^^

unsigned slow91(int n) {
     boost::optional<unsigned> &ret = results4[n];
     if ( !ret )
     {
         ret = mc91(mc91(foo(n))%100);
     }
     return *ret;
}

Вы получите менее удивительные результаты.

compiletime:

time g++ test.cpp -std=c++11 -O3

real    0m1.708s
user    0m1.496s
sys     0m0.176s

во время выполнения:

time ./a.out

131069
91
131069
91

real    0m0.097s
user    0m0.064s
sys     0m0.032s

Ответ 2

запоминание

Это очень интересное "открытие", но ответ, вероятно, более прост, чем вы думаете.

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

f(x)   = g(x)
g(x)   = x + h(x,x)
h(x,y) = x + y

так как каждое значение известно во время компиляции, компилятор может переписать вышеприведенное значение в эквивалент ниже:

f(x) = x + x + x

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

Если вы знаете, что g(5) = 15 зачем подсчитывать его снова? вместо этого просто заменяйте g(5) на 15 каждый раз, когда это необходимо. Это возможно, так как функция, объявленная как constexpr, не имеет побочных эффектов.

Runtime

В runtime это не происходит (поскольку мы не сказали, что код ведет себя таким образом). Маленькому парню, проходящему через ваш код, нужно будет перейти от f до g в h, а затем вернуться обратно к g из h, прежде чем он перейдет от g до f, пока он сохраняет возвращаемое значение каждой функции и перенос ее на следующую.

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

Но в примере OPs это действительно рассчитанное время компиляции?

Да, и тем, кто не верит, что компилятор действительно вычислит это и поместил его как константы в готовый двоичный файл, я поставлю соответствующие инструкции по сборке из кода OPs ниже (вывод g++ -S -Wall -pedantic -fconstexpr-depth=1000000 -std=c++11)

main:
.LFB1200:
  .cfi_startproc
  pushq %rbp
  .cfi_def_cfa_offset 16
  .cfi_offset 6, -16
  movq  %rsp, %rbp
  .cfi_def_cfa_register 6
  subq  $16, %rsp
  movl  $131069, -4(%rbp)
  movl  $91, -8(%rbp)
  movl  $131069, %esi               # one of the values from constexpr
  movl  $_ZSt4cout, %edi
  call  _ZNSolsEj
  movl  $_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_, %esi
  movq  %rax, %rdi
  call  _ZNSolsEPFRSoS_E
  movl  $91, %esi                   # the other value from our constexpr
  movl  $_ZSt4cout, %edi
  call  _ZNSolsEi
  movl  $_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_, %esi
  movq  %rax, %rdi

  # ...
  # a lot of jumping is taking place down here
  # see the full output at http://codepad.org/Q8D7c41y