Здравствуйте, geniepro, Вы писали:


N>>Мое мнение — компиляторы пока недостаточно умны для таких задач.

G>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

А асимптотика по времени какая получается?

Здравствуйте, nikov, Вы писали:

G>>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

N>А асимптотика по времени какая получается?

Про LLVM не скажу, но GCC код

int fib(int n)
{
  if(n == 0 || n == 1) return n;
  return fib(n-1) + fib(n-2);
}

превращает в что-то вроде

int fib(int n) {
    int r = 0;
    while (n > 1) {
        r += fib(n-1);
        n -= 2;
    }
    return n + r;
}

Подробности:
http://eigenclass.org/hiki/legitimate-microbenchmarks
http://www.reddit.com/r/programming/comments/61tc0/legitimate_uses_of_microbenchmarks_parameter/c02kcpp

Здравствуйте, nikov, Вы писали:

G>>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

N>А асимптотика по времени какая получается?

Проверил сейчас на http://llvm.org/demo/ -- что-то не очень результаты, раньше код вроде лучше генерировался. Сейчас для факториала такой код на LLVM-ассемблере выдаётся:

int factorial(int X) {
  if (X == 0) return 1;
  return X*factorial(X-1);
}

define i32 @factorial(i32 %X) nounwind readnone {
entry:
    %0 = icmp eq i32 %X, 0        ; <i1> [#uses=1]
    br i1 %0, label %bb2, label %bb1

bb1:        ; preds = %entry
    %1 = add i32 %X, -1        ; <i32> [#uses=2]
    %2 = icmp eq i32 %1, 0        ; <i1> [#uses=1]
    br i1 %2, label %factorial.exit, label %bb1.i

bb1.i:        ; preds = %bb1
    %3 = add i32 %X, -2        ; <i32> [#uses=1]
    %4 = tail call i32 @factorial(i32 %3) nounwind        ; <i32> [#uses=1]
    %5 = mul i32 %4, %1        ; <i32> [#uses=1]
    br label %factorial.exit

factorial.exit:        ; preds = %bb1.i, %bb1
    %6 = phi i32 [ %5, %bb1.i ], [ 1, %bb1 ]        ; <i32> [#uses=1]
    %7 = mul i32 %6, %X        ; <i32> [#uses=1]
    ret i32 %7

bb2:        ; preds = %entry
    ret i32 1
}

Для фибоначчи код выглядит ещё хуже, хотя раньше вроде нормальный такой цикл выдавался...

Здравствуйте, geniepro, Вы писали:

G>>>LLVM умеет переводить наивные алгоритмы Фибоначчи и факториала в хвостовую рекурсию.

N>>А асимптотика по времени какая получается?

G>Проверил сейчас на http://llvm.org/demo/ -- что-то не очень результаты, раньше код вроде лучше генерировался. Сейчас для факториала такой код на LLVM-ассемблере выдаётся:
skip
G>Для фибоначчи код выглядит ещё хуже, хотя раньше вроде нормальный такой цикл выдавался...

Это регрессия, уже есть багрепорт (PR4919). Если написать факториал вручную на ассемблере LLVM и указать соответствующий проход, то получается нормально:

$ cat fac.ll
define i32 @factorial(i32 %n)
{
    %ifzero = icmp eq i32 %n, 0
    br i1 %ifzero, label %Return1, label %Recursion
Return1:
    ret i32 1
Recursion:
    %tmp1 = sub i32 %n, 1
    %tmp2 = call i32 @factorial(i32 %tmp1)
    %result = mul i32 %n, %tmp2
    ret i32 %result
}
$ llvm-as fac.ll -o - | opt -tailcallelim -o - | llvm-dis -o -
; ModuleID = '<stdin>'

define i32 @factorial(i32 %n) {
; <label>:0
  br label %tailrecurse

tailrecurse:                                      ; preds = %Recursion, %0
  %accumulator.tr = phi i32 [ 1, %0 ], [ %result, %Recursion ] ; <i32> [#uses=2]
  %n.tr = phi i32 [ %n, %0 ], [ %tmp1, %Recursion ] ; <i32> [#uses=3]
  %ifzero = icmp eq i32 %n.tr, 0                  ; <i1> [#uses=1]
  br i1 %ifzero, label %Return1, label %Recursion

Return1:                                          ; preds = %tailrecurse
  ret i32 %accumulator.tr

Recursion:                                        ; preds = %tailrecurse
  %tmp1 = sub i32 %n.tr, 1                        ; <i32> [#uses=1]
  %result = mul i32 %n.tr, %accumulator.tr        ; <i32> [#uses=1]
  br label %tailrecurse
}