You could imagine a pragma to say which branch is likely. f p1 = e1 f p2 = {-# LIKELY #-} e2 f p3 = e3
Is there some way to propagate pragmas through core transformations? -- Lennart On Wed, Mar 25, 2009 at 9:18 AM, Simon Peyton-Jones <simo...@microsoft.com> wrote: > 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-boun...@haskell.org > [mailto:glasgow-haskell-users- > | boun...@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 > > _______________________________________________ > Glasgow-haskell-users mailing list > Glasgow-haskell-users@haskell.org > http://www.haskell.org/mailman/listinfo/glasgow-haskell-users > _______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users