Opened 6 years ago

Last modified 15 months ago

#2280 new bug

randomR too slow

Reported by: guest Owned by: rrnewton
Priority: normal Milestone:
Component: libraries/random Version: 6.8.2
Keywords: randomR Cc: ghc@…
Operating System: Linux Architecture: x86
Type of failure: Runtime performance bug Difficulty: Unknown
Test Case: Blocked By:
Blocking: Related Tickets: #427

Description

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 =
   do 
      -- 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-0.9.0.5 -ddump-simpl-iterations speedtest/RandomTest.hs
-}
{-
bytestring-0.9.0.1 as shipped with GHC-6.8.2 does not inline Data.ByteString.unfoldrN
-}

Is this related to Ticket 427?

Change History (4)

comment:1 Changed 6 years ago by igloo

  • Difficulty set to Unknown
  • Milestone set to _|_

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 4 years ago by simonmar

  • Type of failure set to Runtime performance bug

comment:3 Changed 3 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 15 months ago by morabbin

Note: See TracTickets for help on using tickets.