[GHC] #9786: Make quot/rem/div/mod with known divisors fast
#9786: Make quot/rem/div/mod with known divisors fast -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.12.1 Component: Compiler | Version: 7.9 Keywords: | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Unknown | Type of failure: Runtime Blocked By: | performance bug Related Tickets: | Test Case: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- GHC (with NCG) currently optimizes `Int` division by powers of two, but not by other known divisors. The Intel Optimization Manual section 9.2.4 describes a general technique for replacing division by known, sufficiently small, divisors with multiplication. LLVM appears to go further in some fashion. There's no reason we can't do something similar. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9786 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9786: Make quot/rem/div/mod with known divisors fast -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.12.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): It looks like https://gmplib.org/~tege/divcnst-pldi94.pdf is a good source for the algorithms involved. There are algorithms there both for what Haskell calls `quot` and what it calls `div`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9786#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9786: Make quot/rem/div/mod with known divisors fast -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: 7.12.1 Component: Compiler | Version: 7.9 Resolution: | Keywords: Operating System: | Architecture: Unknown/Multiple Unknown/Multiple | Difficulty: Unknown Type of failure: Runtime | Blocked By: performance bug | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): The more I think about it, the more likely it seems that we should `NOINLINE` `divMod` and `quotRem` until very, very late, or maybe never inline them. There are two reasons for this: 1. We would prefer to snag them unmodified when we recognize known divisors. 2. As described in #9617, it would be very nice to use CSE to merge `div` with `mod` and `quot` with `rem` automatically. The major complication, of course, is that in the case of an ''unknown'' divisor that is used multiple times, we'd like to avoid repeating the sign test. I still have no clear sense of how to resolve the tension between these desires. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9786#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC