Improving Random

Markert, Leonhard leonhard.markert at tweag.io
Mon Jun 1 11:24:52 UTC 2020


Thank you, Simon! I am keen to see the improvements we've been working on
released for others to use.

I just wanted to mention Oleg Grenrus (@phadej) here - the proposed random
v1.2 uses his fast, pure-Haskell SplitMix implementation
<https://hackage.haskell.org/package/splitmix> as its default PRNG.

On Mon, Jun 1, 2020 at 12:55 PM Simon Peyton Jones via Libraries <
libraries at haskell.org> wrote:

> Friends
>
>
>
> Random number generation lies far outside my expertise, but I know it to
> be an area where it’s easy to mess up, either in performance or in
> generating genuinely random numbers.  So I’m delighted that Dominic and his
> colleagues have been working so hard on this.   We all owe them a debt of
> thanks.  Good RNGs are at the beating heart of many other algorithms, but
> are rather un-loved as an object of study in their own right.
>
>
>
> So thank you Dominic, @curiousleo @lehins  -- and indeed Guy Steele and
> colleagues, on whose work this is based.  We don’t often get perf boosts of
> 1000x!
>
>
>
> I hope that that, after suitable scrutiny and refinement if necessary,
> this ends up being accepted.
>
>
>
> Simon
>
>
>
> *From:* Libraries <libraries-bounces at haskell.org> *On Behalf Of *
> dominic at steinitz.org
> *Sent:* 26 May 2020 11:00
> *To:* libraries <libraries at haskell.org>
> *Cc:* Alexey Kuleshevich <alexey at kuleshevi.ch>
> *Subject:* Improving Random
>
>
>
> Hello Libraries,
>
> You may recall that following the blog post
> <https://alexey.kuleshevi.ch/blog/2019/12/21/random-benchmarks/> by
> @lehins, a group of us (@curiousleo, @lehins and me) invited participation
> in February
> <https://mail.haskell.org/pipermail/libraries/2020-February/030261.html>
> to take this work and apply it to improving the current random library.
>
> Our proximate goals were to fix #25
> <https://github.com/haskell/random/issues/25> (filed in 2015) and #51
> <https://github.com/haskell/random/issues/51> (filed in 2018). After a
> lot of discussion and experimentation, we have a proposal that addresses
> both these issues and also: #26
> <https://github.com/haskell/random/issues/26>, #44
> <https://github.com/haskell/random/issues/44>, #53
> <https://github.com/haskell/random/issues/53>, #55
> <https://github.com/haskell/random/issues/55>, #58
> <https://github.com/haskell/random/issues/58> and #59
> <https://github.com/haskell/random/issues/59>.
>
> For backwards compatibility, the proposal retains the old style classes
> and enhances them. Thus in 1.1 we have
>
> class RandomGen g where
>
>     next :: g -> (Int, g)
>
>     genRange :: g -> (Int, Int)
>
>     split :: g -> (g, g)
>
>     {-# MINIMAL next, split #-}
>
> and in 1.2 we have
>
> class RandomGen g where
>
>     next :: g -> (Int, g)
>
>     genWord8 :: g -> (Word8, g)
>
>     genWord16 :: g -> (Word16, g)
>
>     genWord32 :: g -> (Word32, g)
>
>     genWord64 :: g -> (Word64, g)
>
>     genWord32R :: Word32 -> g -> (Word32, g)
>
>     genWord64R :: Word64 -> g -> (Word64, g)
>
>     genShortByteString :: Int
>
>         -> g -> (Data.ByteString.Short.Internal.ShortByteString, g)
>
>     genRange :: g -> (Int, Int)
>
>     split :: g -> (g, g)
>
>     {-# MINIMAL split, (genWord32 | genWord64 | next, genRange) #-}
>
> and next and genRange are deprecated. This interface is what allows the
> significantly faster performance as no longer is everything forced to go
> via Integer.
>
> Several new interfaces are introduced and it is recommended that new
> applications use these and, where feasible, existing applications migrate
> to using them.
>
> The major API addition in this PR is the definition of a new class
> MonadRandom:
>
> -- | 'MonadRandom' is an interface to monadic pseudo-random number generators.
>
> class Monad m => MonadRandom g s m | g m -> s where
>
> {-# MINIMAL freezeGen,thawGen,(uniformWord32|uniformWord64) #-}
>
>
>
>     type Frozen g = (f :: Type) | f -> g
>
>     freezeGen :: g s -> m (Frozen g)
>
>     thawGen :: Frozen g -> m (g s)
>
>
>
>     uniformWord32 :: g s -> m Word32 -- default implementation in terms of uniformWord64
>
>     uniformWord64 :: g s -> m Word64 -- default implementation in terms of uniformWord32
>
>     -- plus methods for other word sizes and for byte strings
>
>     -- all have default implementations so the MINIMAL pragma holds
>
> Conceptually, in MonadRandom g s m, g s is the type of the generator, s
> is the state type, and m the underlying monad. Via the functional
> dependency g m -> s, the state type is determined by the generator and
> monad.
>
> Frozen is the type of the generator's state "at rest". It is defined as
> an injective type family via f -> g, so there is no ambiguity as to which
> g any Frozen g belongs to.
>
> This definition is generic enough to accommodate, for example, the Gen
> type from mwc-random, which itself abstracts over the underlying
> primitive monad and state token. This is the full instance declaration
> (provided here as an example - this instance is not part of random as
> random does not depend on mwc-random):
>
> instance (s ~ PrimState m, PrimMonad m) => MonadRandom MWC.Gen s m where
>
>     type Frozen MWC.Gen = MWC.Seed
>
>     freezeGen = MWC.save
>
>     thawGen = MWC.restore
>
>
>
>     uniformWord8 = MWC.uniform
>
>     uniformWord16 = MWC.uniform
>
>     uniformWord32 = MWC.uniform
>
>     uniformWord64 = MWC.uniform
>
>     uniformShortByteString n g = unsafeSTToPrim (genShortByteStringST n (MWC.uniform g))
>
> Pure random number generators can also be made instances of this class
> providing a uniform interface to both pure and stateful random number
> generators. An instance for the standard number generator StdGen is
> provided.
>
> The Random typeclass has conceptually been split into Uniform and
> UniformRange. The Random typeclass is still included for backwards
> compatibility. Uniform is for types where it is possible to sample from
> the type's entire domain; UniformRange is for types where one can sample
> from a specified range:
>
> class Uniform a where
>
>     uniformM :: MonadRandom g s m => g s -> m a
>
>
>
> class UniformRange a where
>
>     uniformRM :: MonadRandom g s m => (a, a) -> g s -> m a
>
> The proposal is a breaking change but the changes are not very intrusive
> and we have PRs ready for the affected downstream libraries:
>
>    - requires base >= 4.10 (GHC-8.2)
>    - StdGen is no longer an instance of Read
>    - randomIO and randomRIO were extracted from the Random class into
>    separate functions
>
> In addition, there may be import clashes with new functions, e.g. uniform
> and uniformR.
>
> Further explanatory details may be found here
> <https://github.com/idontgetoutmuch/random/blob/v1.2-release-notes/RELEASE-NOTES-v1.2.md#api-changes>
> and the PR for the proposed new version is here
> <https://github.com/haskell/random/pull/61>.
>
> Here are some benchmarks run on a 3.1 GHz Intel Core i7. The full
> benchmarks can be run using e.g. stack bench. The benchmarks are measured
> in milliseconds per 100,000 generations. In some cases, the performance is
> over x1000(!) times better; the minimum performance increase for the types
> listed below is more than x35.
>
> | Name                    | Mean (1.1) | Mean (1.2) | Improvement|
>
> | ----------------------- | ---------- | ---------- | ---------- |
>
> | pure/random/Float       |         30 |       0.03 |        1038|
>
> | pure/random/Double      |         52 |       0.03 |        1672|
>
> | pure/random/Integer     |         43 |       0.33 |         131|
>
> | pure/uniform/Word8      |         14 |       0.03 |         422|
>
> | pure/uniform/Word16     |         13 |       0.03 |         375|
>
> | pure/uniform/Word32     |         21 |       0.03 |         594|
>
> | pure/uniform/Word64     |         42 |       0.03 |        1283|
>
> | pure/uniform/Word       |         44 |       0.03 |        1491|
>
> | pure/uniform/Int8       |         15 |       0.03 |         511|
>
> | pure/uniform/Int16      |         15 |       0.03 |         507|
>
> | pure/uniform/Int32      |         22 |       0.03 |         749|
>
> | pure/uniform/Int64      |         44 |       0.03 |        1405|
>
> | pure/uniform/Int        |         43 |       0.03 |        1512|
>
> | pure/uniform/Char       |         17 |       0.49 |          35|
>
> | pure/uniform/Bool       |         18 |       0.03 |         618|
>
> | pure/uniform/CChar      |         14 |       0.03 |         485|
>
> | pure/uniform/CSChar     |         14 |       0.03 |         455|
>
> | pure/uniform/CUChar     |         13 |       0.03 |         448|
>
> | pure/uniform/CShort     |         14 |       0.03 |         473|
>
> | pure/uniform/CUShort    |         13 |       0.03 |         457|
>
> | pure/uniform/CInt       |         21 |       0.03 |         737|
>
> | pure/uniform/CUInt      |         21 |       0.03 |         742|
>
> | pure/uniform/CLong      |         43 |       0.03 |        1544|
>
> | pure/uniform/CULong     |         42 |       0.03 |        1460|
>
> | pure/uniform/CPtrdiff   |         43 |       0.03 |        1494|
>
> | pure/uniform/CSize      |         43 |       0.03 |        1475|
>
> | pure/uniform/CWchar     |         22 |       0.03 |         785|
>
> | pure/uniform/CSigAtomic |         21 |       0.03 |         749|
>
> | pure/uniform/CLLong     |         43 |       0.03 |        1554|
>
> | pure/uniform/CULLong    |         42 |       0.03 |        1505|
>
> | pure/uniform/CIntPtr    |         43 |       0.03 |        1476|
>
> | pure/uniform/CUIntPtr   |         42 |       0.03 |        1463|
>
> | pure/uniform/CIntMax    |         43 |       0.03 |        1535|
>
> | pure/uniform/CUIntMax   |         42 |       0.03 |        1493|
>
>
>
> Dominic Steinitz
>
> dominic at steinitz.org
>
> http://idontgetoutmuch.org
>
> Twitter: @idontgetoutmuch
>
>
>
>
>
>
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20200601/c9a81d9c/attachment-0001.html>


More information about the Libraries mailing list