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

Question

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?

This question reminded me of Is GHC's auto-derived Eq instance really O(N)? — hvr
– hvr, Commented Jan 27, 2012 at 15:55

ehird · Accepted Answer · 2012-01-27 00:27:55Z

36

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.

edited Jan 27, 2012 at 0:27

answered Jan 27, 2012 at 0:19

ehird

40.9k3 gold badges184 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

dflemstr Over a year ago

This means that the time complexity is O(1) and also Θ(1) in case it wasn't clear.

Thomas Eding Over a year ago

Hey, No fair! I wanted the O(1) to subsume the actual Θ(0).

Peter Wortmann Over a year ago

You could cite the GHC source.

Collectives™ on Stack Overflow

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

1 Answer 1

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Linked

Related