Opened 5 years ago

Last modified 2 years ago

#9120 patch feature request

Cache intermediate powers

Reported by: basvandijk Owned by:
Priority: normal Milestone:
Component: Core Libraries Version: 7.8.2
Keywords: Cc: core-libraries-committee@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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.

Attachments (1)

0001-Cache-intermediate-powers.patch (2.5 KB) - added by basvandijk 5 years ago.

Download all attachments as: .zip

Change History (10)

Changed 5 years ago by basvandijk

comment:1 Changed 5 years ago by simonpj

And perhaps some performance measurements that show it's a win?

S

comment:2 Changed 5 years ago 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.

comment:3 Changed 5 years ago by meteficha

I have no idea what is the purpose of this code, but why not the following?

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)

comment:4 Changed 5 years ago 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?

comment:5 Changed 5 years ago by thomie

Cc: core-libraries-committee@… added
Component: CompilerCore Libraries
Owner: set to ekmett
Type of failure: None/UnknownRuntime performance bug

comment:6 Changed 5 years ago by thomie

Type: bugfeature request

comment:7 Changed 5 years ago 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.

comment:8 Changed 4 years ago by thomie

Owner: ekmett deleted

comment:9 Changed 2 years ago by bgamari

Status: newpatch
Note: See TracTickets for help on using tickets.