compilation of pattern-matching?

Claus Reinke claus.reinke at
Wed Mar 25 21:38:55 EDT 2009

>I don't find ordering of patterns appealing, I find it scary! I order
>my patterns according to the semantics I desire, and then additionally
>by what looks pretty. I'd like it if whatever cleverness GHC can work
>is used rather than requiring me to think. If the order of patterns is
>to become important, it has to be with an explicit "look, I know
>something you don't" pragma rather than by default.

No need to be scared! As I mentioned, Haskell already specifies
pattern match order left-to-right, top-to-bottom, so the declarative
semantics wouldn't change one bit. I'm just suggesting to use the
existing specification, in order to make the generated branching
code somewhat more predictable. 

We don't know yet whether this would make a worthwhile difference,
but if it would, then being able to express performance constraints
without affecting the declarative semantics might seem more important 
than aesthetical considerations. Not to mention that the alternative
would be to spoil your pretty code with pragmas!-)

>As an example, I suspect that the "hot-path" on most list pattern
>matches is in the (:) case. I don't want to ever teach a user that (:)
>comes before [] because ... long spiel about branch prediction ...

It is the other way round: without branch prediction, the order
of tests did matter, branch prediction hardware can figure out
many things without help, thereby making the order of tests in
the code less important - but that can be defeated.

As long as you're sure your students don't need to care about 
performance, there is no need for you to teach them about it. 
But if their ByteStrings aren't as fast as they need to be, they 
will very much want to know why (the example in #849 was 
from ByteString). Unless they just give up.

>Controlling branch prediction will only ever be a niche activity, 
>so the defaults should reflect that.

My impression is that branch prediction hardware is (usually)
designed for users with full control over generated code (eg,
the Intel compiler manuals seem to advise loop unrolling to
match and complement the branch prediction hardware exactly). 

If you don't have that kind of control, and generate code as if
there were no hardware-level optimizations, the resulting
mismatch will manifest in hard-to-predict variations in 
performance, making it difficult to see how much or why
speed is lost. No fun.


More information about the Glasgow-haskell-users mailing list