haskell - C 与 Haskell 中的朴素斐波那契

Question

请问如何评价g (fib) 完全严格？ ( 我知道这个指数解不是最优的。 我想知道如何使递归 完全严格/如果可能的话/)

Haskell

g :: Int -> Int
g 0 = 0
g 1 = 1
g x = g(x-1) + g(x-2)
main = print $ g 42

这样它的运行速度大约与原始 C 解决方案一样快:

C

#include <stdio.h>

long f(int x)
{
    if (x == 0) return 0;
    if (x == 1) return 1;
    return f(x-1) + f(x-2);
}

int main(void)
{
    printf("%ld\n", f(42));
    return 0;
}

备注 :这个 fibs-recursion 仅用作一个 super 简单的例子。我完全知道，有很多更好的算法。但是肯定有递归算法没有这么简单和更有效的替代方案。

Answer 1

答案是，GHC 使评估本身完全严格(当您通过优化编译给它机会时)。原始代码产生核心

Rec {
Main.$wg [Occ=LoopBreaker] :: GHC.Prim.Int# -> GHC.Prim.Int#
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType L]
Main.$wg =
  \ (ww_s1JE :: GHC.Prim.Int#) ->
    case ww_s1JE of ds_XsI {
      __DEFAULT ->
        case Main.$wg (GHC.Prim.-# ds_XsI 1) of ww1_s1JI { __DEFAULT ->
        case Main.$wg (GHC.Prim.-# ds_XsI 2) of ww2_X1K4 { __DEFAULT ->
        GHC.Prim.+# ww1_s1JI ww2_X1K4
        }
        };
      0 -> 0;
      1 -> 1
    }
end Rec }

如果您了解 GHC 的核心，您就会看到它是完全严格的，并且使用未装箱的原始机器整数。

(不幸的是，gcc 从 C 源代码生成的机器代码显然更快。)

GHC的严格性分析器相当不错，在像这里这样的简单情况下，不涉及多态性，函数也不太复杂，你可以指望它发现它可以使用unboxed Int#对所有值进行拆箱以生成一个worker。 s。

但是，在这种情况下，生成快速代码不仅仅是对机器类型进行操作。 native 代码生成器以及 LLVM 后端生成的程序集基本上是将代码直接转换为程序集，检查参数是 0 还是 1，如果不是则调用该函数两次并添加结果。两者都会产生一些我不明白的进入和退出代码，在我的盒子上， native 代码生成器产生更快的代码。

对于 C 代码， clang -O3以更少的繁琐和使用更多的寄存器产生直接的组装，

.Ltmp8:
    .cfi_offset %r14, -24
    movl        %edi, %ebx
    xorl        %eax, %eax
    testl       %ebx, %ebx
    je          .LBB0_4
# BB#1:
    cmpl        $1, %ebx
    jne         .LBB0_3
# BB#2:
    movl        $1, %eax
    jmp         .LBB0_4
.LBB0_3:
    leal        -1(%rbx), %edi
    callq       recfib
    movq        %rax, %r14
    addl        $-2, %ebx
    movl        %ebx, %edi
    callq       recfib
    addq        %r14, %rax
.LBB0_4:
    popq        %rbx
    popq        %r14
    popq        %rbp
    ret

(由于某种原因，今天在我的系统上的表现比昨天好得多)。由 Haskell 源代码和 C 生成的代码之间的许多性能差异来自后者使用寄存器的情况，前者使用间接寻址，两者的算法核心相同。

没有任何优化的 gcc 使用一些间接寻址产生的结果基本相同，但比 GHC 使用 NCG 或 LLVM 后端产生的要少。与 -O1 , 同上，但间接寻址更少。与 -O2 ，您会得到一个转换，以便程序集不容易映射回源，并使用 -O3 , gcc 产生了相当惊人的

.LFB0:
    .cfi_startproc
    pushq   %r15
    .cfi_def_cfa_offset 16
    .cfi_offset 15, -16
    pushq   %r14
    .cfi_def_cfa_offset 24
    .cfi_offset 14, -24
    pushq   %r13
    .cfi_def_cfa_offset 32
    .cfi_offset 13, -32
    pushq   %r12
    .cfi_def_cfa_offset 40
    .cfi_offset 12, -40
    pushq   %rbp
    .cfi_def_cfa_offset 48
    .cfi_offset 6, -48
    pushq   %rbx
    .cfi_def_cfa_offset 56
    .cfi_offset 3, -56
    subq    $120, %rsp
    .cfi_def_cfa_offset 176
    testl   %edi, %edi
    movl    %edi, 64(%rsp)
    movq    $0, 16(%rsp)
    je      .L2
    cmpl    $1, %edi
    movq    $1, 16(%rsp)
    je      .L2
    movl    %edi, %eax
    movq    $0, 16(%rsp)
    subl    $1, %eax
    movl    %eax, 108(%rsp)
.L3:
    movl    108(%rsp), %eax
    movq    $0, 32(%rsp)
    testl   %eax, %eax
    movl    %eax, 72(%rsp)
    je      .L4
    cmpl    $1, %eax
    movq    $1, 32(%rsp)
    je      .L4
    movl    64(%rsp), %eax
    movq    $0, 32(%rsp)
    subl    $2, %eax
    movl    %eax, 104(%rsp)
.L5:
    movl    104(%rsp), %eax
    movq    $0, 24(%rsp)
    testl   %eax, %eax
    movl    %eax, 76(%rsp)
    je      .L6
    cmpl    $1, %eax
    movq    $1, 24(%rsp)
    je      .L6
    movl    72(%rsp), %eax
    movq    $0, 24(%rsp)
    subl    $2, %eax
    movl    %eax, 92(%rsp)
.L7:
    movl    92(%rsp), %eax
    movq    $0, 40(%rsp)
    testl   %eax, %eax
    movl    %eax, 84(%rsp)
    je      .L8
    cmpl    $1, %eax
    movq    $1, 40(%rsp)
    je      .L8
    movl    76(%rsp), %eax
    movq    $0, 40(%rsp)
    subl    $2, %eax
    movl    %eax, 68(%rsp)
.L9:
    movl    68(%rsp), %eax
    movq    $0, 48(%rsp)
    testl   %eax, %eax
    movl    %eax, 88(%rsp)
    je      .L10
    cmpl    $1, %eax
    movq    $1, 48(%rsp)
    je      .L10
    movl    84(%rsp), %eax
    movq    $0, 48(%rsp)
    subl    $2, %eax
    movl    %eax, 100(%rsp)
.L11:
    movl    100(%rsp), %eax
    movq    $0, 56(%rsp)
    testl   %eax, %eax
    movl    %eax, 96(%rsp)
    je      .L12
    cmpl    $1, %eax
    movq    $1, 56(%rsp)
    je      .L12
    movl    88(%rsp), %eax
    movq    $0, 56(%rsp)
    subl    $2, %eax
    movl    %eax, 80(%rsp)
.L13:
    movl    80(%rsp), %eax
    movq    $0, 8(%rsp)
    testl   %eax, %eax
    movl    %eax, 4(%rsp)
    je      .L14
    cmpl    $1, %eax
    movq    $1, 8(%rsp)
    je      .L14
    movl    96(%rsp), %r15d
    movq    $0, 8(%rsp)
    subl    $2, %r15d
.L15:
    xorl    %r14d, %r14d
    testl   %r15d, %r15d
    movl    %r15d, %r13d
    je      .L16
    cmpl    $1, %r15d
    movb    $1, %r14b
    je      .L16
    movl    4(%rsp), %r12d
    xorb    %r14b, %r14b
    subl    $2, %r12d
    .p2align 4,,10
    .p2align 3
.L17:
    xorl    %ebp, %ebp
    testl   %r12d, %r12d
    movl    %r12d, %ebx
    je      .L18
    cmpl    $1, %r12d
    movb    $1, %bpl
    je      .L18
    xorb    %bpl, %bpl
    jmp     .L20
    .p2align 4,,10
    .p2align 3
.L21:
    cmpl    $1, %ebx
    je      .L58
.L20:
    leal    -1(%rbx), %edi
    call    recfib
    addq    %rax, %rbp
    subl    $2, %ebx
    jne     .L21
.L18:
    addq    %rbp, %r14
    subl    $2, %r13d
    je      .L16
    subl    $2, %r12d
    cmpl    $1, %r13d
    jne     .L17
    addq    $1, %r14
.L16:
    addq    %r14, 8(%rsp)
    subl    $2, 4(%rsp)
    je      .L14
    subl    $2, %r15d
    cmpl    $1, 4(%rsp)
    jne     .L15
    addq    $1, 8(%rsp)
.L14:
    movq    8(%rsp), %rax
    addq    %rax, 56(%rsp)
    subl    $2, 96(%rsp)
    je      .L12
    subl    $2, 80(%rsp)
    cmpl    $1, 96(%rsp)
    jne     .L13
    addq    $1, 56(%rsp)
.L12:
    movq    56(%rsp), %rax
    addq    %rax, 48(%rsp)
    subl    $2, 88(%rsp)
    je      .L10
    subl    $2, 100(%rsp)
    cmpl    $1, 88(%rsp)
    jne     .L11
    addq    $1, 48(%rsp)
.L10:
    movq    48(%rsp), %rax
    addq    %rax, 40(%rsp)
    subl    $2, 84(%rsp)
    je      .L8
    subl    $2, 68(%rsp)
    cmpl    $1, 84(%rsp)
    jne     .L9
    addq    $1, 40(%rsp)
.L8:
    movq    40(%rsp), %rax
    addq    %rax, 24(%rsp)
    subl    $2, 76(%rsp)
    je      .L6
    subl    $2, 92(%rsp)
    cmpl    $1, 76(%rsp)
    jne     .L7
    addq    $1, 24(%rsp)
.L6:
    movq    24(%rsp), %rax
    addq    %rax, 32(%rsp)
    subl    $2, 72(%rsp)
    je      .L4
    subl    $2, 104(%rsp)
    cmpl    $1, 72(%rsp)
    jne     .L5
    addq    $1, 32(%rsp)
.L4:
    movq    32(%rsp), %rax
    addq    %rax, 16(%rsp)
    subl    $2, 64(%rsp)
    je      .L2
    subl    $2, 108(%rsp)
    cmpl    $1, 64(%rsp)
    jne     .L3
    addq    $1, 16(%rsp)
.L2:
    movq    16(%rsp), %rax
    addq    $120, %rsp
    .cfi_remember_state
    .cfi_def_cfa_offset 56
    popq    %rbx
    .cfi_def_cfa_offset 48
    popq    %rbp
    .cfi_def_cfa_offset 40
    popq    %r12
    .cfi_def_cfa_offset 32
    popq    %r13
    .cfi_def_cfa_offset 24
    popq    %r14
    .cfi_def_cfa_offset 16
    popq    %r15
    .cfi_def_cfa_offset 8
    ret
    .p2align 4,,10
    .p2align 3
.L58:
    .cfi_restore_state
    addq    $1, %rbp
    jmp     .L18
    .cfi_endproc

这比任何其他测试都要快得多。 gcc 将算法展开到一个显着的深度，GHC 和 LLVM 都没有，这在这里产生了巨大的差异。