compilation of pattern-matching?

[Duncan Coutts]

On Wed, 2009-03-25 at 18:01 +0000, Claus Reinke wrote:

> With the hint about branch prediction, I also found this old ticket 
> (which seems to have been waiting for the new backend, and
> indicates rather larger performance differences):
> 
>     Offer control  over branch prediction
>     http://hackage.haskell.org/trac/ghc/ticket/849

Oh, I should have read the whole thread first. I see you found it
already.

Yes, I did find that in the ByteString stream/unstream functions that
essentially arbitrary changes in the logic of branches changed
performance by a factor of two or so. At the time I put it down to basic
block ordering and branch prediction.

A related issue is that we cannot reliably force a call to be
out-of-line (so it doesn't add code to the hot-path) without also
disabling the worker wrapper transform.

> But UNLIKELY only covers the most common case
> (marking alternatives with minimal expected frequency) -
> if clause ordering was respected, relative frequencies of
> alternatives could be specified without pragmas, just by
> ordering pattern-match or conditional clauses according
> to expected frequency.

I think marking expectations (either manually or by profile-directed
feedback) is a more profitable approach. We can end up with nested cases
part way through optimisation that were never there explicitly in the
source, so preserving source order is meaningless there.

For example consider a simple tail recursive loop:

length :: ByteString -> Int
length = go 0
  where
    go !n bs  | null bs    = n
              | otherwise  = go (n+1) (tail bs)

There are no explicit cases here. There is nothing for the programmer to
order. In any case, this is a user-defined function and they don't know
the details of how to optimise this.

After inlining we actually find that there are three cases:

      * the lazy ByteString being Empty
      * it being a non-empty Chunk with 1 byte left it
      * it being a non-empty Chunk with more than 1 byte left

In similar situations it may be profitable to re-nest the cases. But if
we attach likelihoods then that seems more robust than trying to
maintain orderings on cases. In the above example I'd annotate the
definition of tail to indicate that the chunk being length 1 is not
nearly as likely as it not being so. 

Actually in this example the information probably doesn't need to be
given explicitly at all since one branch leads to a recursive call and
the other to a function return. A static model here would be enough, no
hints or profile feedback required.

Duncan