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@haskell.org [mailto:glasgow-haskell-users- | bounces@haskell.org] On Behalf Of Claus Reinke | Sent: 23 March 2009 23:17 | To: glasgow-haskell-users@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@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users