8

I am wondering how Haskell pattern matching is resolved internally and how this impacts performance. Say we have a function that is expensive to compute so we precompute the first and / or more frequently used values and pattern match on the corresponding input before making the actual computation itself:

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

We could precompute a lot of these cases, thousands if we wanted, but do we? I'm assuming that it takes time for Haskell to actually find the pattern that matches the input, so maybe it is actually quicker to compute the, say, 1000th value instead of making a 1000 pattern matches?

Petras Purlys
  • 1,093
  • 6
  • 18
  • Pattern matches are *concetually* done by iterating over the list, but a compiler is free to optimize it (and given there is a certain structure in the numbers, most will). – Willem Van Onsem Feb 01 '18 at 22:03
  • 1
    Another option is to use memoization to "precompute" (rather, compute on the first use only). [data-memocombinators](https://hackage.haskell.org/package/data-memocombinators-0.5.1/docs/Data-MemoCombinators.html) has a combinator [`arrayRange`](https://hackage.haskell.org/package/data-memocombinators-0.5.1/docs/Data-MemoCombinators.html#v:arrayRange) which will memoize a certain range of inputs into a flat array with constant time lookup, which is basically what you are doing manually here. – luqui Feb 01 '18 at 23:26
  • Related: [*Haskell GHC: what is the time complexity of a pattern match with N constructors?*](https://stackoverflow.com/q/9027384/2751851) – duplode Feb 02 '18 at 00:25

1 Answers1

15

I made a simple test in the form:

f 0 = 4
f 1 = 5
...

And compiled with ghc -O2 -ddump-asm -c. I observe key ASM of:

What appears to be implementations for each top level equation:

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

What appears to be a jump table referencing the above implementations:

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

What appears to be a pair of range guards followed by a 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

So do I think this will be slow for 1000 entries? No, if they are contiguous I bet GHC will generate a jump table just like I'm seeing here. Another interesting test would be if they aren't contiguous.

Thomas M. DuBuisson
  • 64,245
  • 7
  • 109
  • 166
  • 3
    The code `createSwitchPlan` starting at https://github.com/ghc/ghc/blob/master/compiler/cmm/CmmSwitch.hs#L324 makes all these decisions, using jump tables for the continguous sections of a sparse pattern match. – Joachim Breitner Feb 02 '18 at 15:32
  • Why are there two conditional jumps? Would it be better to have (at most) one subtraction and then one conditional jump? – dfeuer Feb 02 '18 at 20:20
  • @dfeuer Can you explain how you would check `x < 0` and `x > 24` with a single compare? – Thomas M. DuBuisson Feb 02 '18 at 20:41
  • Er... Let me check my arithmetic. – dfeuer Feb 02 '18 at 21:13
  • 1
    `(fromIntegral x :: Word) < 24`, however you say that in assembly, should do the trick, I believe. – dfeuer Feb 02 '18 at 21:17
  • The (reasonable) assumption here is that even signed values will often have contiguous defined cases in the range `(0,n]` and we can optimize for that using `jb` instead of a pair of other jumps. I see ghc does compile your comparison reasonably too, that is branching on the above compiles to `cmpq $24,7(%rbx) ; jb target_branch ; ...else branch...`. Hey, sounds like you have a contribution to make the GHC's NCG! – Thomas M. DuBuisson Feb 02 '18 at 21:45