Improving Random
Alexey Kuleshevich
alexey at kuleshevi.ch
Tue Jun 2 19:02:33 UTC 2020
With all due respect, Carter, you've been taking your time for last six years. There is no need to blame the World, if you don't have enough time or desire to put work into the library just give up the maintainership to someone who is willing to at least do a proper PR review and make a release. I can produce at least a dozen comments of you saying over the years that you will have a release ready in "two weeks". Dominic, whom you have kicked out from the list of maintainers has done more productive work for `random` in the last few months than you have done in the last few years.
If you see problems in the current work that we've done, please say what it is on the PR we've submitted https://github.com/haskell/random/pull/62 and we can work together on getting it taken care of.
It's been over 20 days since we submitted the proposal and there was no concrete feedback from you, except "there are some nice ideas".
> under ideal circumstances rng algorithms can have hard to see issues
There is no implementation of RNG submitted in the current proposal, instead a well adopted implementation of splitmix is being used.
We've put a tremendous amount of work into getting the improved version of `random`, only because you failed to do it yourself. You were even not willing to collaborate with us when we invited you back in Febreuary and now you are saying that what we came up with is wrong and you are going to take your time with it.
Alexey.
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Tuesday, June 2, 2020 9:32 PM, Carter Schonwald <carter.schonwald at gmail.com> wrote:
> It’s worth also mentioning that my previous 1.2 wip stuff was using splitmix as the suggested default Splittable too.
>
> The proposal has a number of nice ideas. And a number of things that I’m reflecting on how to tweak or align with my own thoughts because I think it’s wrong but I’m not 100% on what approach is best yet. Just that the current one proposed or that random currently has is not !
>
> I’m taking my time with this because even under ideal circumstances rng algorithms can have hard to see issues, and all the weirdness going on in the world right now doesn’t lend itself to speedy clear thinking so I’m being doubly careful to figure out how to communicate and factor this work.
>
> On Mon, Jun 1, 2020 at 7:26 AM Markert, Leonhard <leonhard.markert at tweag.io> wrote:
>
>> 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
>>
>> _______________________________________________
>> 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/20200602/85bb2339/attachment-0001.html>
More information about the Libraries
mailing list