compilation of pattern-matching?

[Claus Reinke]

[commented cmm and asm elided - thanks, though! Some examples
 like this would be helpful in the commentary (or are they there and
 I've not yet seen them?)]

|I guess this is a long winded way of saying that the branches are being 
|ordered such that the fall though case is not the one that you put first, 
|which, if I recall correctly, is somewhat bad as the x86 branch predictor 
|guesses a forward branch that hasn't been seen before will fall through.
|
|Perhaps they are being ordered by the constructor tag?

> In Core, case alternatives are stored in an order determined by the
> "data constructor tag" of the thing being matched on - this is
> independent of the order you wrote them in the source code. I believe
> the reason for this is just to reduce the work done by the code
> generator a tiny bit (and it's sometimes handy to know that the
> default case, if any, is always the first alternative).
> 
> I don't know if preserving the order of the alts as written by the
> user would be a significant gain for the code generator. Maybe codegen
> should just output those tests for data alternatives that contain a
> recursive use of the data type first - e.g. the cons constructor for
> lists or the branch constructor for trees?

Ok, so the answer seems to be: yes, GHC ignores my preferences
but modern branch prediction might make this issue less relevant
than it was in the early days?-) The recursive-case-first heuristic
sounds useful, but not all pattern-match recursions fall into the
fold-over-recursive-type category (see attached test). And what 
about different processors, with differing branch-prediction capabilities?

I've attached an attempt at a test program, using Either with various 
options for testing Left first vs Right first on data with varying ratios
of Left vs Right, and varying "predicability". The effect seems small
here (Pentium M760, 2 GHz), not zero (5-8%), but not easily 
predictable, eg the largest effect so far was where I expected 
none at all:

    rml 1000000000 2: 0m47.632s
    rmr 1000000000 2: 0m44.150s

(that should be a rightfirst match with equal mix Left and Right,
so perhaps we need a different test?)

There does seem to be a visible effect of ~5% between leftfirst
and rightfirst in the extreme all-Left/Right cases, though, suggesting 
that the source order should be preserved to give programmers 
control over this, in spite of recent processors. What are the 
results elsewhere?

Claus
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PMorder.hs
Type: application/octet-stream
Size: 1176 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20090324/c152668a/PMorder.obj