[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 thefold-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 smallhere (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 leftfirstand 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
PMorder.hs
Description: Binary data
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
