How fast is Haskell pattern matching?

Question

We mostly use data to store values, like this:

data Sex = Male | Female data Person = Person {name :: String, age :: Int, sex :: Sex} charlie :: Person charlie = Person "Charlie" 32 Male

And now we have nice functions name age and sex to get data values with.

But, with GADTs and Rank2, we can do something cooler:

{-# LANGUAGE GADTs #-} {-# LANGUAGE Rank2Types #-} data Sex = Male | Female data Data a where Name :: Data String Age :: Data Int Sex :: Data Sex type Person = forall a. Data a -> a charlie :: Person charlie Name = "Charlie" charlie Age = 32 charlie Sex = Male

So, this is pretty darned awesome. It provides us with a gloriously beautiful syntax for defining people, and makes slick use of GADTs.

But is this really any better? How is this represented at runtime? Is pattern-matching actually slower and/or bigger in representation than the data?

lt;dr: How fast is pattern matching compared to data lookup?

I guess YMMV on whether this is a useful use of GADTs. Still, pattern matching is the fastest thing there is: everything else depends on it (with the exception of things like floating point math). As far as "data lookup" (field accessors), you might look at core to see what they are actually doing. — Rein Henrichs
– Rein Henrichs, Commented Oct 7, 2015 at 16:24
Try it and see! But I would predict about an order of magnitude slowdown compared to using data. But that is more due to the overhead of calling an unknown function than due to pattern matching. The function version is also not quite the same because if the fields are more complicated expressions than just 32, they will be re-evaluated each time. (Or you or the compiler floats it out of the function into a closure, and then you just reinvented storing data as data, with extra overhead to access it.) — Reid Barton
– Reid Barton, Commented Oct 7, 2015 at 16:35
An issue with the (->) representation is that updating fields leaks space and lookup gets slower after each update. — András Kovács
– András Kovács, Commented Oct 7, 2015 at 16:39

Thomas M. DuBuisson · Accepted Answer · 2015-10-07 21:36:48Z

If you compile your code with -ddump-asm you can see the pattern match is a series of comparisons and jumps with the data embedded in the instructions (load an address for the string, load a constant for the number 32, etc).

A container, such as a Map or HashMap, will be slower due to the indirection but hopefully it is obvious that a statically named variable is faster than traversing a (potentially dynamic) tree structure.

Collectives™ on Stack Overflow

How fast is Haskell pattern matching?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related