[GHC] #14437: Optimise remainders by powers of two
#14437: Optimise remainders by powers of two -------------------------------------+------------------------------------- Reporter: Bodigrim | Owner: (none) Type: feature | Status: new request | Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- Current GHC optimises quotients, but not remainders by powers of two. For instance, even `even :: Word -> Bool` requires division: {{{#!hs evenWord :: Word -> Bool evenWord = even }}} results in CMM, containing {{{#!c if (I64[R1 + 7] % 2 != 0) goto c2sK; else goto c2sQ; }}} My proposal is to optimise `MO_{S,U}_Rem` by powers of two in `CmmOpt.cmmMachOpFoldM`, similar to existing cases for `MO_{S,U}_Quot`. Something like this may do: {{{#!hs MO_U_Rem rep | Just _ <- exactLog2 n -> Just (cmmMachOpFold dflags (MO_And rep) [x, CmmLit (CmmInt (n - 1) rep)]) MO_S_Rem rep | Just p <- exactLog2 n -> Just (cmmMachOpFold dflags (MO_Sub rep) [x, cmmMachOpFold dflags (MO_Shl rep) [cmmMachOpFold dflags (MO_S_Quot rep) [x, y], CmmLit (CmmInt p rep)]]) }}} Function `even` is used by default definition of `stimes` (`Data.Semigroup.Internal.stimesDefault`). If `<>` is cheap, division may become a bottleneck. It is also used by `GHC.Real.^`. Here is a simple benchmark: {{{#!hs v :: Int v = maximum [ x ^ (6 :: Word) | x <- [1..100000000 :: Int] ] }}} It takes 4.5 seconds on my PC before the patch above (`-O2`) and only 2.2 seconds after. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14437 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14437: Optimise remainders by powers of two -------------------------------------+------------------------------------- Reporter: Bodigrim | Owner: Bodigrim 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): Phab:D4180 Wiki Page: | -------------------------------------+------------------------------------- Changes (by Bodigrim): * owner: (none) => Bodigrim * differential: => Phab:D4180 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14437#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14437: Optimise remainders by powers of two -------------------------------------+------------------------------------- Reporter: Bodigrim | Owner: Bodigrim Type: feature request | Status: patch 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): Phab:D4180 Wiki Page: | -------------------------------------+------------------------------------- Changes (by Bodigrim): * status: new => patch -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14437#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14437: Optimise remainders by powers of two
-------------------------------------+-------------------------------------
Reporter: Bodigrim | Owner: Bodigrim
Type: feature request | Status: patch
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): Phab:D4180
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Ben Gamari
#14437: Optimise remainders by powers of two -------------------------------------+------------------------------------- Reporter: Bodigrim | Owner: Bodigrim Type: feature request | Status: closed Priority: normal | Milestone: 8.4.1 Component: Compiler | Version: 8.2.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Phab:D4180 Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: patch => closed * resolution: => fixed * milestone: => 8.4.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14437#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC