compilation of pattern-matching?

[Claus Reinke]

| 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.  

It is a programming habit from my early functional programming
days, probably pre-Haskell, certainly from before I started using
GHC. It just so happens that I've only recently started to get 
interested in performance-critical code again, so I'm only now 
finding out that the old habit doesn't fit for GHC (among other
recent surprises with GHC optimizations, as you've noticed;-).

I don't currently have sufficient data to support a feature request
myself (benchmarking on my laptop is not a fun game unless the 
effects are fairly clear-cut - too much noise in the timing details), 
though #849 seemed to have more extreme numbers. I was just 
hoping that the "sorting" of case branches was an accident that 
could be switched off easily, as I can't see any benefit in it. If
that wouldn't be easy, there are bigger fish to catch elsewhere,
so I'm not suggesting to spend much time on this now. 

>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?

Strange. I don't think it is my idea (older implementations
used to work that way, and iirc, it also matches what Prolog
systems used to do), and I didn't think it was anything but 
straightforward to avoid case transformations unless there
is a clear benefit, so I doubt there is a useful paper in there
(also, I can't afford to plan that far ahead atm). 

What is the benefit of changing the ordering (not just joining 
paths to avoid redundant tests, but actually modifying the 
order of tests, to sort by their order in the data type 
declaration)? Is there any documentation of these case 
transformations that I could look up?

Claus