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
