compilation of pattern-matching?

[Simon Peyton-Jones]

Indeed GHC does not attempt to retain the order of alternatives, although
a) it might be possible to do so by paying more attention in numerous places
b) GHC may do so already, by accident, in certain cases

Observations:

* The issue at stake is a small one: not the *number of tests* but *which tests branch, and which fall through*.

* Simply ordering the equations doesn't really work, because pattern-match compilation will match an entire column at once:
   f (x:xs) True = ...
   f []     True = ...
   f []     False = ...
   f (x:xs) False = ...
Which "order" should the (:)/[] test go in?

* Not only does GHC currently not attempt to retain order, but for a particular order it makes no guarantees about which falls through.  For example, given
        case ... of { A -> e1; C -> e2; B -> e3 }
We might test for A and then
either fall though to e1
or     fall through to the test for C

* When the number of constructors is larger, instead of a linear sequence of tests, GHC may generate a table-jump; or a balanced tree of tests.

* Which plan performs best is tremendously architecture dependent, and may well vary a lot between different chips implementing the same instruction set.  It's a losing battle to fix the strategy in source code.

* More promising might be to say "this is the hot branch".  That information about frequency could in principle be used by the back end to generate better code.  However, I am unsure how
        a) to express this info in source code
        b) retain it throughout optimisation


Claus, if you think this thread is worth capturing, then do write a Commentary page, and I'll check its veracity.

Thanks

Simon


| -----Original Message-----
| From: glasgow-haskell-users-bounces at haskell.org [mailto:glasgow-haskell-users-
| bounces at haskell.org] On Behalf Of Claus Reinke
| Sent: 23 March 2009 23:17
| To: glasgow-haskell-users at haskell.org
| Subject: compilation of pattern-matching?
|
| I just noticed that GHC (6.11.20090320) seems to compile both
|
| f (a:b:c) =
| f (a:[]) =
| f [] =
|
| and
|
| f [] =
| f (a:[]) =
| f (a:b:c) =
|
| to something like (looking at Core, but writing source)
|
| f x = case x of { [] -> ..; (a:t) -> case t of { [] ->..; (b:c) ->..}}
|
| That doesn't seem right to me: if I try to give the patterns in
| the order from frequent to rare, in order to reduce jumps, I
| don't expect GHC to rearrange things. What is the rationale
| for this? And where can I read about GHC's pattern match
| compilation approach in general?
|
| Claus
|
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users at haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users