Haskell的穷举模式匹配性能

Question

Haskell的穷举模式匹配性能

8

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

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

我们可以预先计算很多这样的情况，如果需要的话可以计算数千个，但我们是否需要呢？我认为Haskell实际上需要一些时间来找到匹配输入的模式，因此可能比进行1000次模式匹配更快地计算出第1000个值。

- Petras Purlys

模式匹配概念上是通过迭代列表来完成的，但编译器可以自由优化它（并且鉴于数字中存在一定的结构，大多数编译器都会这样做）。 - Willem Van Onsem

1

另一个选择是使用记忆化来“预计算”（或者说仅在第一次使用时计算）。data-memocombinators有一个组合器arrayRange，它将某个输入范围的值存储到一个平坦数组中，并且具有常数时间查找，这基本上就是您在此手动执行的操作。 - luqui

相关：Haskell GHC：具有N个构造函数的模式匹配的时间复杂度是多少？ - duplode

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas M. DuBuisson · Accepted Answer

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

f 0 = 4
f 1 = 5
...

使用 ghc -O2 -ddump-asm -c 进行编译。我观察到了关键的汇编代码:

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

_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
        ...

一对范围守卫和调度器跟随其后:

_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 会生成一个跳转表，就像我在这里看到的一样。另一个有趣的测试是它们是否不连续。