[GHC] #9120: Cache intermediate powers
#9120: Cache intermediate powers ------------------------------------+------------------------------------- Reporter: basvandijk | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Keywords: | Operating System: Unknown/Multiple Architecture: Unknown/Multiple | Type of failure: None/Unknown Difficulty: Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | ------------------------------------+------------------------------------- `GHC.Float` caches powers of 2 and 10. The arrays of powers are currently constructed using: {{{ expts :: Array Int Integer expts = array (minExpt,maxExpt) [(n,2^n) | n <- [minExpt .. maxExpt]] }}} Unfortunately, the intermediate powers in the `2^n` computation are not stored back in the array, only the result is. I propose to use the following scheme that does store the intermediate powers: {{{ -- | Exponentiation with a cache for the most common numbers. expt :: Integer -> Int -> Integer expt _ e | e < 0 = error "Negative exponent" expt 2 e | e <= maxExpt2 = expts2 ! e | otherwise = expts2 ! maxExpt2 * 2^(e-maxExpt2) expt 10 e | e <= maxExpt10 = expts10 ! e | otherwise = expts10 ! maxExpt10 * 10^(e-maxExpt10) expt base e = base^e maxExpt2 :: Int maxExpt2 = 1100 maxExpt10 :: Int maxExpt10 = 324 expts2 :: Array Int Integer expts2 = expts 2 maxExpt2 expts2 expts10 :: Array Int Integer expts10 = expts 10 maxExpt10 expts10 expts :: Integer -> Int -> Array Int Integer -> Array Int Integer expts base hi arr = listArray (0, hi) $ 1 : base : go 2 where go :: Int -> [Integer] go !ix = xx : base*xx : go (ix+2) where xx = x * x x = arr ! half half = ix `unsafeShiftR` 1 }}} I will attach a patch. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9120 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9120: Cache intermediate powers -------------------------------------+------------------------------------ Reporter: basvandijk | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: None/Unknown | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (by simonpj): And perhaps some performance measurements that show it's a win? S -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9120#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9120: Cache intermediate powers -------------------------------------+------------------------------------ Reporter: basvandijk | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: None/Unknown | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (by basvandijk):
And perhaps some performance measurements that show it's a win?
My GHC build is currently failing. Once it compiles I will try producing some benchmarks. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9120#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9120: Cache intermediate powers -------------------------------------+------------------------------------ Reporter: basvandijk | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: None/Unknown | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (by meteficha): I have no idea what is the purpose of this code, but why not the following? {{{#!haskell expt 2 e | e <= maxExpt2 = expts2 ! e | otherwise = expts2 ! maxExpt2 * expt 2 (e-maxExpt2) expt 10 e | e <= maxExpt10 = expts10 ! e | otherwise = expts10 ! maxExpt10 * expt 10 (e-maxExpt10) }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9120#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9120: Cache intermediate powers -------------------------------------+------------------------------------ Reporter: basvandijk | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Unknown/Multiple Type of failure: None/Unknown | Difficulty: Unknown Test Case: | Blocked By: Blocking: | Related Tickets: -------------------------------------+------------------------------------ Comment (by basvandijk):
I have no idea what is the purpose of this code, but why not the following? ...
Won't that have linear complexity instead of logarithmic? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9120#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9120: Cache intermediate powers -------------------------------------+------------------------------------- Reporter: basvandijk | Owner: ekmett Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: Core | Keywords: Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Runtime | performance bug | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by thomie): * type: bug => feature request -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9120#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9120: Cache intermediate powers -------------------------------------+------------------------------------- Reporter: basvandijk | Owner: ekmett Type: feature | Status: new request | Milestone: Priority: normal | Version: 7.8.2 Component: Core | Keywords: Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: Type of failure: Runtime | performance bug | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by ekmett): This seems pretty straight forward and the code looks correct to me. The main cost being borne right now is that rather than being `O(n)` to compute the array it is `O(n log n)`. With `n` bounded above by `1100`, and it only hitting you while you force these constants the first time it'll be hard to find a benchmark materially affected, as they 'warm up' more or less instantly. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9120#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9120: Cache intermediate powers -------------------------------------+------------------------------------- Reporter: basvandijk | Owner: (none) Type: feature request | Status: patch Priority: normal | Milestone: Component: Core Libraries | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: new => patch -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9120#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC