#14201: Implement ideas from "Compiling Pattern Matching to Good Decision Trees" -------------------------------------+------------------------------------- Reporter: AndreasK | Owner: AndreasK Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: 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 AndreasK): = There are shortcomings in the current codegen of GHC that eliminate much of the gains to be had here. * Changing the order of pattern matches can lead to more floating of case alternatives to the top level. The associated cost from calling a top level function overshadows potential gains when that happens. This is expensive since: * They have to confirm to the calling convention, so can require register shifting. * They prohibit us from falling through to the alternative. * They split the code in memory usually leading to more cache pressure. There is an ticket about the issue already: #15560 * The algorithm depends on shared pattern matching subtrees being commoned up which doesn't work yet. As a consequence we quite often end up with duplicate code which kills performance. * I had hoped to leave this to CSE but it turns out GHC's CSE is not as good as one would hope in this regard. See https://ghc.haskell.org/trac/ghc/wiki/MoreCSE for some discussion. * We could do an special CSE for just the pattern matching trees. Butduring desugaring we don't work bottom up but top down. We generate functions which take as argument the expression to put into the case alternatives instead of directly generating an AST expression. It wasn't clear how to work with or refactor this to allow commoning up of pattern matching subtrees at the time I last looked at this. * Last and least: The current codelayout is heavily dependent on how we generate `if` statements for Cmm. As consequence performance can vary a lot when changing the order of pattern matches. I did some work on code layout which hopefully will help with this in #15124. Which might change the performance difference between differing pattern match algorithms. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14201#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler