compilation of pattern-matching?

[Lennart Augustsson]

The only way to see the impact of very low level things like which way
branches go is to generate assembly code and the make simple
controlled changes of that.
But even doing that is very dodgy since you are subject to the whims
of cache misses etc.

As far as branching goes, conditional branches that are in loops and
that almost always go the same way are free on all modern processors.
The branch predictor will learn quickly which way the the branch goes
and prefetch along the right path.

  -- Lennart

On Tue, Mar 24, 2009 at 11:30 AM, Claus Reinke <claus.reinke at talk21.com> wrote:
> [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
>
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>
>