#14644: Improve cmm/assembly for pattern matches with two constants. -------------------------------------+------------------------------------- Reporter: AndreasK | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 (CodeGen) | Keywords: Codegen, CMM, Resolution: | Patterns, Pattern Matching Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by svenpanne): I am not sure if things are that easy: To do these kind of switches in a really good way, one would need a probability distribution how often the individual cases actually happen. If we e.g. assume that all Ints happen equally often in the example above, it would be best to check for <1 and >7 first, so we would get roughly 1.5 comparisons on average. Depending on the number of registers available, you can even get away with 1 subtraction and 1 unsigned comparison for this range check, a classic C hack (ab)using wrap-around for unsigned ints. If we have some hints, e.g. raising a pattern matching exception, we could do better, e.g. assume 0% probability for this case. If we have more detailed (estimated) probabilities, we could do a Huffman-like decision tree. This is where profile-guided optimization shines. Additional things to consider: Performance in tight loops is often vastly different, because branch prediction/caching will most likely kick in visibly. Correctly predicted branches will cost you almost nothing, while unknown/incorrectly predicted branches will be much more costly. In the absence of more information from their branch predictor, quite a few processors assume that backward branches are taken and forward branches are assumed to be not taken. So code layout has a non-trivial performance impact. Instruction counts are quite misleading nowadays... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14644#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler