Вычислить число Фибоначчи (рекурсивный подход) во время компиляции (constexpr) в C++11

Question

Я написал программу вычисления числа Фибоначчи в задаче времени компиляции (constexpr), используя методы метапрограммирования шаблонов, поддерживаемые в C++11. Цель этого состоит в том, чтобы вычислить разницу во времени выполнения между подходом метапрограммирования шаблона и старым традиционным подходом.

// Template Metaprograming Approach
template<int  N>
constexpr int fibonacci() {return fibonacci<N-1>() + fibonacci<N-2>(); }
template<>
constexpr int fibonacci<1>() { return 1; }
template<>
constexpr int fibonacci<0>() { return 0; }



// Conventional Approach
 int fibonacci(int N) {
   if ( N == 0 ) return 0;
   else if ( N == 1 ) return 1;
   else
      return (fibonacci(N-1) + fibonacci(N-2));
} 

Я запустил обе программы для N = 40 в моей системе GNU/Linux, измерил время и обнаружил, что это обычное решение (1,15 секунды) примерно в два раза медленнее, чем решение на основе шаблонов (0,55 секунды). Это значительное улучшение, поскольку оба подхода основаны на рекурсии.

Чтобы понять это больше, я скомпилировал программу (флаг -fdump-tree-all) в g++ и обнаружил, что компилятор фактически генерирует 40 различных функций (например, fibonacci<40>, fibonacci<39>...fibonacci<0>).

constexpr int fibonacci() [with int N = 40] () {
  int D.29948, D.29949, D.29950;
  D.29949 = fibonacci<39> ();
  D.29950 = fibonacci<38> ();
  D.29948 = D.29949 + D.29950;
  return D.29948;
}

constexpr int fibonacci() [with int N = 39] () {
  int D.29952, D.29953, D.29954;
  D.29953 = fibonacci<38> ();
  D.29954 = fibonacci<37> ();
  D.29952 = D.29953 + D.29954;
  return D.29952;
}
...
...
...
constexpr int fibonacci() [with int N = 0] () {
  int D.29962;
  D.29962 = 0;
  return D.29962;
}

Я также отладил программу в GDB и обнаружил, что все вышеперечисленные функции выполняются столько же раз, сколько и в обычном рекурсивном подходе. Если обе версии программы выполняют функцию одинаковое количество раз (рекурсивно), то как это достигается методами метапрограммирования шаблонов? Я также хотел бы узнать ваше мнение о том, как и почему подход на основе метапрограммирования шаблонов занимает половину времени по сравнению с другой версией? Можно ли сделать эту программу быстрее текущей?

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

Моя машина GNU/Linux с GCC 4.8.1, и я использовал оптимизацию -o3 для обеих программ.

Answer 1

Попробуй это:

template<size_t N>
struct fibonacci : integral_constant<size_t, fibonacci<N-1>{} + fibonacci<N-2>{}> {};

template<> struct fibonacci<1> : integral_constant<size_t,1> {};
template<> struct fibonacci<0> : integral_constant<size_t,0> {};

С лязгом и -Os, это компилируется примерно за 0,5 с и работает в нулевое время для N=40, Ваш "традиционный" подход компилируется примерно за 0,4 с и работает за 0,8 с. Просто для проверки, результат 102334155 право?

Когда я попробовал свой constexpr Решение компилятор запустил на пару минут, а затем я остановил его, потому что, очевидно, память была заполнена (компьютер начал зависать). Компилятор пытался вычислить конечный результат, и ваша реализация крайне неэффективна для использования во время компиляции.

С этим решением, шаблонные экземпляры в N-2, N-1 повторно используются при создании экземпляров N, Так fibonacci<40> на самом деле во время компиляции известен как значение, и во время выполнения ничего не нужно делать. Это подход динамического программирования, и, конечно, вы можете сделать то же самое во время выполнения, если вы сохраняете все значения в 0 через N-1 перед вычислением в N,

С вашим решением компилятор может оценить fibonacci<N>() во время компиляции, но не обязательно. В вашем случае все или часть вычислений оставляются на время выполнения. В моем случае все вычисления предпринимаются во время компиляции, поэтому никогда не заканчиваются.

Answer 2

Причина в том, что ваше решение во время выполнения не является оптимальным. Для каждого числа FIB функции вызываются несколько раз. Последовательность Фибоначчи имеет перекрывающиеся подзадачи, например, fib(6) звонки fib(4), а также fib(5) также звонки fib(4),

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

Я рекомендую поискать "динамическое программирование Фибоначчи" и попробовать, это должно значительно ускорить процесс.

Answer 3

Добавление -O1 (или выше) к GCC4.8.1 сделает fibonacci<40>() постоянной времени компиляции, и весь код, сгенерированный шаблоном, исчезнет из вашей сборки. Следующий код

int foo()
{
  return fibonacci<40>();
}

приведет к выводу сборки

foo():
    movl    $102334155, %eax
    ret

Это дает лучшую производительность во время выполнения.

Тем не менее, похоже, что вы строите без оптимизации (-O0), поэтому вы получаете что-то немного другое. Выходные данные сборки для каждой из 40 функций Фибоначчи выглядят в основном одинаково (за исключением случаев 0 и 1)

int fibonacci<40>():
    pushq   %rbp
    movq    %rsp, %rbp
    pushq   %rbx
    subq    $8, %rsp
    call    int fibonacci<39>()
    movl    %eax, %ebx
    call    int fibonacci<38>()
    addl    %ebx, %eax
    addq    $8, %rsp
    popq    %rbx
    popq    %rbp
    ret

Это просто, он устанавливает стек, вызывает две другие функции Фибоначчи, добавляет значение, разбирает стек и возвращает. Нет разветвлений и сравнений.

Теперь сравните это со сборкой из обычного подхода

fibonacci(int):
    pushq   %rbp
    pushq   %rbx
    subq    $8, %rsp
    movl    %edi, %ebx
    movl    $0, %eax
    testl   %edi, %edi
    je  .L2
    movb    $1, %al
    cmpl    $1, %edi
    je  .L2
    leal    -1(%rdi), %edi
    call    fibonacci(int)
    movl    %eax, %ebp
    leal    -2(%rbx), %edi
    call    fibonacci(int)
    addl    %ebp, %eax
    .L2:
    addq    $8, %rsp
    popq    %rbx
    popq    %rbp
    ret

Каждый раз, когда вызывается функция, она должна проверить, является ли N 0 или 1, и действовать соответствующим образом. Это сравнение не требуется в версии шаблона, потому что оно встроено в функцию с помощью магии шаблонов. Я предполагаю, что неоптимизированная версия кода шаблона быстрее, потому что вы избегаете этих сравнений и также не будете иметь никаких пропущенных предсказаний ветвления.

Answer 4

Может быть, просто использовать более эффективный алгоритм?

constexpr pair<double, double> helper(size_t n, const pair<double, double>& g)
{
    return n % 2
        ? make_pair(g.second * g.second + g.first * g.first, g.second * g.second + 2 * g.first * g.second)
        : make_pair(2 * g.first * g.second - g.first * g.first, g.second * g.second + g.first * g.first);
}

constexpr pair<double, double> fibonacciRecursive(size_t n)
{
    return n < 2
        ? make_pair<double, double>(n, 1)
        : helper(n, fibonacciRecursive(n / 2));
}

constexpr double fibonacci(size_t n)
{
    return fibonacciRecursive(n).first;
}

Мой код основан на идее, описанной Д. Кнутом в первой части его "Искусства компьютерного программирования". Я не могу вспомнить точное место в этой книге, но я уверен, что алгоритм был описан там.