穷举 Haskell 模式匹配的性能

Question

我想知道 Haskell 模式匹配是如何在内部解决的，以及这如何影响性能。假设我们有一个计算成本很高的函数，因此我们在进行实际计算之前预先计算第一个和/或更频繁使用的值和模式匹配对应的输入:

expensiveComputation :: Int -> Int
expensiveComputation 1 = 101
expensiveComputation 2 = 3333333
expensiveComputation 3 = 42
...
expensiveComputation n = the actual function

我们可以预先计算很多这样的案例，如果我们愿意，可以预先计算数千个，但是我们可以吗？我假设 Haskell 需要时间才能真正找到与输入匹配的模式，所以计算第 1000 个值而不是进行 1000 个模式匹配实际上可能更快？

Answer 1

我在表格中做了一个简单的测试:

f 0 = 4
f 1 = 5
...

并用 ghc -O2 -ddump-asm -c 编译.我观察到以下关键 ASM:

每个顶级方程的实现似乎是:

_c2aD:
        movl $28,%ebx    ; N.B. the constant 28 matches my largest value
        jmp *(%rbp)
_c2aC:
        movl $27,%ebx
        jmp *(%rbp)
_c2aB:
        movl $26,%ebx
        jmp *(%rbp)
....

似乎是引用上述实现的跳转表:

_n2aN:
        .quad   _c2af-(_n2aN)+0
        .quad   _c2ag-(_n2aN)+0
        .quad   _c2ah-(_n2aN)+0
        .quad   _c2ai-(_n2aN)+0
        .quad   _c2aj-(_n2aN)+0
        .quad   _c2ak-(_n2aN)+0
        ...

似乎是一对范围守卫，然后是 dispatch :

_c2aE:
        cmpq $25,%r14        ; N.B. the last defined input is 24
        jge _c2ae
_u2aH:
        testq %r14,%r14
        jl _c2ae
_u2aI:
        leaq _n2aN(%rip),%rax
        addq (%rax,%r14,8),%rax
        jmp *%rax

那么我认为这对于 1000 个条目来说会很慢吗？不，如果它们是连续的，我敢打赌 GHC 会生成一个跳转表，就像我在这里看到的那样。另一个有趣的测试是它们是否不连续。