compilation of pattern-matching?
simonpj at microsoft.com
Wed Mar 25 15:39:23 EDT 2009
| >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
| That adds even more unpredictability.
| very long list than the Cons-before-Nil order I wanted), but it is
| very frustrating if I'm not even given the chance because GHC
| sorts the alternatives, not even according to its own interpretation
| of branching performance, but completely arbitrarily!-)
All I'm saying is that GHC has never claimed to offer predictability here. I understand that you find it frustrating, but there it is. You are making a feature request. Good! Then someone needs to design it, and implement it in a way that is robust to the rather radical program optimizations that GHC does. I don't think either is straightforward, and at the moment I am snowed under.
It is possible that such a change might allow you to tune programs better; although I doubt such tuning would be portable. (Your 5% figures are encouraging, but it's one thing to get a 5% gain on one program, and quite another to get a positive figure on every program. I spend a lot of time looking at nofib numbers where some programs respond well to some changed optimization, and others slow down.) I'm also a bit concerned that it would impose a new constraint on the entire compilation chain.
Your idea of simply ordering patterns is certainly appealing from the programming point of view. I don't yet see how to propagate that information through the pattern compilation algorithm, retain the resulting information in the optimizer, and exploit it in a code generator. But it might well be possible. Maybe you can write a Haskell workshop paper about it?
Simon's idea of an annotation that gives some idea of the likelihood of the value of an expression taking a particular form sounds promising for robustness. Something like
Note "80% chance of (:), 20% of " (f x)
But it's not so good when there are multiple interacting parameters to a pattern match.
More information about the Glasgow-haskell-users