haskellpattern-matchingcomplexity-theoryghc

Haskell GHC: what is the time complexity of a pattern match with N constructors?

Let's say we have the following Haskell:

data T = T0 | T1 | T2 | ... | TN

toInt :: T -> Int
toInt t = case t of
  T0 -> 0
  T1 -> 1
  T2 -> 2
  ...
  TN -> N

What algorithm is used to perform the pattern match here? I see two options:

(1) Linear search, something like

if      (t.tag == T0) { ... }
else if (t.tag == T1) { ... }
else ...

(2) Binary search, which would be sensible in this specific task: searching for t.tag in the set {TO...T1023}. However, where pattern matching in general has many other capabilities and generalizations, this may not be used.

Compiling with GHC, what algorithm is used, and what is the time complexity in terms of N, for pattern matching on t in toInt?

Solution

  • A jump table is used, making the pattern-match a constant time operation.

    Unfortunately I'm unable to find an up-to-date citation for this, although this page mentions the implementation of Cmm-level switch statements as jump tables, and this old tagging design document uses a case on a Bool as an example, producing a jump table.