Performance of pattern matching in GHC

Question

I'm writing an "append" function for a data type I've created (which basically deals with "streams"). However, this data type has 12 different constructors, dealing with different types of "stream", for example, infinite, null, fixed length, variable length, already appended etc.

There logic between the input types and output types is a bit complex but not incredibly so.

I've considered two approaches:

1. Match against broad categories (perhaps by wrapping in a simpler proxy type) and then match inside those matches OR
2. Just pattern match against 144 cases (12*12). I could perhaps reduce this to 100 with wildcard matches for particular combinations but that's about it.

I know the second approach is more ugly and difficult to maintain, but disregarding that, will GHC find the second approach easier to optimise? If it can do the second approach with a simple jump table (or perhaps two jump tables) I suspect it will be faster. But if it's doing a linear check it will be far slower.

Does GHC optimise pattern matches (even very big ones) into constant time jump tables?

Answer 1

Yes, GHC optimizes such pattern matches. The first seven (I think) constructors get optimizes especially well, via pointer tagging. I believe the rest will be handled by a jump table. But 144 cases sounds hard to maintain, and you'll have to watch for code size. Do you really need all those cases?

Answer 2

It's not too hard to write a small Haskell script that writes a huge case-block and a small benchmark for it. For example:

module Main (main) where

mapping = zip ['!'..'z'] (reverse ['!'..'z'])

test_code =
  [
    "module Main where",
    "",
    "tester :: String -> String",
    "tester cs = do",
    "  c <- cs",
    "  case transform c of",
    "    Just c' -> [c']",
    "    Nothing -> [c ]",
    "",
    "input = concat [ [' '..'z'] | x <- [1..10000] ]",
    "",
    "main = print $ length $ tester $ input",
    ""
  ]

code1 =
  test_code ++
  [
    "transform :: Char -> Maybe Char",
    "transform c = lookup c " ++ show mapping
  ]

code2 =
  test_code ++
  [
    "transform :: Char -> Maybe Char",
    "transform c =",
    "  case c of"
  ] ++
  map (\(k, v) -> "    " ++ show k ++ " -> Just " ++ show v) mapping ++
  [
    "    _ -> Nothing"
  ]

main = do
  writeFile "Test1.hs" (unlines code1)
  writeFile "Test2.hs" (unlines code2)

If you run this code, it generates two small Haskell source files: Test1.hs and Test2.hs. The former uses Prelude.lookup to map characters to characters. The latter uses a giant case-block. Both files contain code to apply the mapping to a large list of data and print out the size of the result. (This way avoids I/O, which would otherwise be the dominating factor.) On my system, Test1 takes a few seconds to run, whereas Test2 is pretty much instant.

The over-interested reader may like to try extending this to use Data.Map.lookup and compare the speed.

This proves that pattern-matching is far faster than an O(n) traversal of a list of key/value mappings... which isn't what you asked. But feel free to brew up your own benchmarks. You could try auto-generating a nested-case verses a flat-case and timing the result. My guess is that you won't see much difference, but feel free to try it.