compilation of pattern-matching?

[Lennart Augustsson]

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
<simonpj at 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-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
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>