Opened 11 years ago

Closed 4 years ago

#2280 closed bug (duplicate)

randomR too slow

Reported by: guest Owned by: ekmett
Priority: normal Milestone:
Component: Core Libraries Version: 6.8.2
Keywords: randomR Cc: ghc@…
Operating System: Linux Architecture: x86
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: #427 Differential Rev(s):
Wiki Page:


randomR is considerably slower than implementing it manually. Maybe I have not re-implemented it precisely, maybe it is just not inlined.

module Main (main) where

import System.Random (RandomGen(..), randomR, )
import qualified Data.ByteString as B

newtype KnuthRandomGen = KnuthRandomGen Int

{-# INLINE knuthFactor #-}
knuthFactor :: Int
knuthFactor = 40692

{-# INLINE knuthModulus #-}
knuthModulus :: Int
knuthModulus = 2^(31::Int)-249

-- we have to split the 32 bit integer in order to avoid overflow on multiplication
knuthSplit :: Int
knuthSplit = succ $ div knuthModulus knuthFactor

knuthSplitRem :: Int
knuthSplitRem = knuthSplit * knuthFactor - knuthModulus

instance RandomGen KnuthRandomGen where
   {-# INLINE next #-}
   next (KnuthRandomGen s) =
      -- efficient computation of @mod (s*knuthFactor) knuthModulus@ without Integer
      let (sHigh, sLow) = divMod s knuthSplit
      in  (s, KnuthRandomGen $ flip mod knuthModulus $
                   knuthSplitRem*sHigh + knuthFactor*sLow)
   {-# INLINE split #-}
   split (KnuthRandomGen s) =
      (KnuthRandomGen (s*s), KnuthRandomGen (13+s))
   {-# INLINE genRange #-}
   genRange _ = (1, pred knuthModulus)

main :: IO ()
main =
      -- for comparison: that's very fast
      putStrLn "constant"
      B.writeFile "random.out" $ fst $
          B.unfoldrN 10000000
             (\g0@(KnuthRandomGen s) -> Just (fromIntegral s, g0))
             (KnuthRandomGen 1)

      -- 3 seconds on my machine
      putStrLn "immediate"
      B.writeFile "random.out" $ fst $
          B.unfoldrN 10000000
             (\g0 -> let (w,g1) = next g0
                     in  Just (fromIntegral (mod w 256), g1))
             (KnuthRandomGen 1)

      -- 10 seconds on my machine
      putStrLn "randomR"
      B.writeFile "random.out" $ fst $
          B.unfoldrN 10000000
             (\g0 -> Just (let (w,g1) = randomR (0,255) g0
                           in  (fromIntegral (w::Int), g1)))
             (KnuthRandomGen 1)

ghc -o dist/build/randomtest -O -Wall -package bytestring- -ddump-simpl-iterations speedtest/RandomTest.hs
bytestring- as shipped with GHC-6.8.2 does not inline Data.ByteString.unfoldrN

Is this related to Ticket 427?

Change History (6)

comment:1 Changed 11 years ago by igloo

difficulty: Unknown
Milestone: _|_

It would be great if someone could take a look at this and #427 and make a concrete proposal for what should be done. The random library is rather unloved at the moment!

comment:2 Changed 10 years ago by simonmar

Type of failure: Runtime performance bug

comment:3 Changed 8 years ago by rrnewton

Owner: set to rrnewton

I agree completely. Random just got a significant interface change (SplittableGen) and I think it deserves an overhaul before the next major release.

comment:4 Changed 7 years ago by morabbin

comment:5 Changed 5 years ago by thoughtpolice

Component: libraries/randomCore Libraries
Owner: changed from rrnewton to ekmett

Moving over to new owning component 'Core Libraries'.

comment:6 Changed 4 years ago by thomie

Resolution: duplicate
Status: newclosed

This bug is now being tracked in the random bug tracker on Github: randomR too slow.

Note: See TracTickets for help on using tickets.