compilation of pattern-matching?

[Simon Marlow]

(thanks to Simon PJ for an excellent summary of the issues)

Lennart Augustsson wrote:
> 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?

I just thought I'd mention the way gcc does this:

   if (__builtin_expect__(p, 1)) {
      ... likely case ...
   } else {
      ... unlikely case ...
   }

sadly gcc's back end doesn't alway take advantage of the information very 
well, at least when I've tried it, but I think the design is nice - it 
feels more general than just annotating the "hot code".  Or perhaps it 
feels nicer because an annotation on the hot code would have to be 
propagated back through the branches; and how far back?  What if there are 
multiple branches annotated as "hot"?

Cheers,
	Simon


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