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