Improving Random

classic Classic list List threaded Threaded
26 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Improving Random

Dominic Steinitz-2

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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
Twitter: @idontgetoutmuch





_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Carter Schonwald
Hey Dominic ,

There’s still a huge pile of release engineering I’ll do on top of the pull request change set, but I genuinely appreciate these patches!

Thanks again! 
-Carter 

On Tue, May 26, 2020 at 6:00 AM <[hidden email]> wrote:

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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
Twitter: @idontgetoutmuch




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

David Feuer
In reply to this post by Dominic Steinitz-2
Could you explain the reasoning behind the deprecations?

On Tue, May 26, 2020, 6:00 AM <[hidden email]> wrote:

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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
Twitter: @idontgetoutmuch




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Zemyla
And can you explain how to take an existing RNG and write it in this new format?

On Tue, May 26, 2020, 15:54 David Feuer <[hidden email]> wrote:
Could you explain the reasoning behind the deprecations?

On Tue, May 26, 2020, 6:00 AM <[hidden email]> wrote:

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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
Twitter: @idontgetoutmuch




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Carter Schonwald
Zemyla! 

Yeah, absolutely agree that their pr has the wrong shape for monad random, which is why I’m confused by dominics pronouncement :), though its a great contrib.

It should be (ignoring m being applicative vs monad)
(For context, their design is roughly  ... MonadRandom m s g | m,g -> s ?  I’m typing on a phone so i might be restating it wrong ... :) )


The *better* choice is 
Class PRNG g =>  MonadRandom m g | m-> g where ... 

And then their example instance  should be something like 

Newtype MWCT  m a = ... newtype wrapper around StateT m a threading an MWC indexed by the state token of the underlying PrimMonad
(Or newtype MWCT s m a = .... stateT thing)

Instance (PrimMonad m) => MonadRandom  (MWCT m) (MCWGen (PrimState m)) where ... 

Or something along those lines.  It absolutely shouldn’t be in the style of being on any PrimMonad, but part of a stack that provides that instance.  

This is ignoring the freeze/thaw stuff which really is just “record and restore RNG state”, and i think is  an artifact of ther design choice in their PR. Which has a lot of great stuff I’m reviewing and poking at.


Nothing is set in stone about deprecation and migration story, cause improving everything and making sure everyone has a zero pain/ or at least tolerable upgrade path is step zero.  (And making sure good stable interfaces persists is key! )

I hope everyone is having a safe and healthy start to their summers, 

and I’m sorry for any confusions Dominics email about his collab Pr announcement has created.  But cest lie vie! Though sharing excitement about a great Pr is great! 

Stay well!
-Carter 

On Tue, May 26, 2020 at 6:48 PM Zemyla <[hidden email]> wrote:
And can you explain how to take an existing RNG and write it in this new format?

On Tue, May 26, 2020, 15:54 David Feuer <[hidden email]> wrote:
Could you explain the reasoning behind the deprecations?

On Tue, May 26, 2020, 6:00 AM <[hidden email]> wrote:

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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
Twitter: @idontgetoutmuch




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Dominic Steinitz-2
In reply to this post by Zemyla
Hi Zemyla,

It’s fully documented in the haddocks which I have temporarily put here: https://htmlpreview.github.io/?https://raw.githubusercontent.com/idontgetoutmuch/random/haddock-preview/doc/index.html. There was a link to them in the announcement but maybe I should have highlighted it a bit more.

Specifically suppose you love permuted congruential generators then

data PCGen = PCGen !Word64 !Word64

stepGen :: PCGen -> (Word32, PCGen)
stepGen (PCGen state inc) = let
  newState = state * 6364136223846793005 + (inc .|. 1)
  xorShifted = fromIntegral (((state `shiftR` 18) `xor` state) `shiftR` 27) :: Word32
  rot = fromIntegral (state `shiftR` 59) :: Word32
  out = (xorShifted `shiftR` (fromIntegral rot)) .|. (xorShifted `shiftL` fromIntegral ((-rot) .&. 31))
  in (out, PCGen newState inc)

instance RandomGen PCGen where
  genWord32 = stepGen
  split _ = error "PCG is not splittable”

And if you prefer a monadic style interface:

> (/ 1000) $ sum $ runStateGen_ (PCGen 17 29) $ \g -> replicateM 1000 $ uniformRM (0.0, 1.0) g

0.508595082944005

HTH - let me know if you have any other questions.

Dominic Steinitz
Twitter: @idontgetoutmuch

On 26 May 2020, at 23:47, Zemyla <[hidden email]> wrote:

And can you explain how to take an existing RNG and write it in this new format?



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Alexey Kuleshevich
In reply to this post by Carter Schonwald
Hey Zemyla,

> And can you explain how to take an existing RNG and write it in this new format?

This question is a bit vague, so I'll try to elaborate on all aspects of new format. New interface supports both stateful and pure RNGs, so I assume you are asking how to use them with the new format, rather than how to create instances, because the latter is only important for maintainers of PRNG libraries and a user will never need to create any instances. If you are still curious about how to write them there is example for stateful mwc-random, which can be found in the generated haddock and in the beginning of this thread, as Dominic pointed out. For pure RNGs I included links to repositories that contain adjusted RandomGen instances below in this email.

As far as pure RNGs, such as the default splitmix and tf-random, etc. Any of them can be used with monadic interface by the means of any `MonadState`. There is a newtype wrapper `StateGen` that allows us to use new monadic interface without any runtime overhead and any other work on the user's part. Let's look at some examples of why this monadic interface is extremely powerful.

We can write our code in this monadic style once:

-- | Generate a random alpha string with random length up to a specified value.
randomStringN :: MonadRandom g s m => Int -> g s -> m (Int, String)
randomStringN upperBound gen = do
  n <- uniformRM (0, upperBound) gen
  xs <- replicateM n $ uniformRM ('a', 'z') gen
  pure (n, xs)

And then we can use such function with any of the available PRNG in Haskell. There are some helper functions that allow using pure RNGs that have RandomGen instance with this monadic style, like `runStateGen`

>>> runStateGen (mkStdGen 217) (randomStringN 10)
((6,"ihhtwd"),StdGen {unStdGen = SMGen 16329862649850020527 15251669095119325999})

which is equivalent to:

>>> runState (randomStringN 10 StateGenM) (mkStdGen 217)
((6,"ihhtwd"),StdGen {unStdGen = SMGen 16329862649850020527 15251669095119325999})

There is also IOGen, that is a wrapper around IORef, which can be used in places where `StateT` can't be used, such as in presence of `bracket` for example:

>>> gen <- thawGen (IOGen (mkStdGen 217))
>>> randomStringN 10 gen
(6,"ihhtwd")

It is just as easily can be used with mwc-random or pcg-random packages in IO:

>>> import System.Random.MWC as MWC
>>> gen <- MWC.createSystemRandom
>>> randomStringN 10 gen
(7,"gfcfodz")

and of course in ST:

>>> import Control.Monad.ST
>>> seed <- MWC.save =<< MWC.createSystemRandom
>>> runST $ thawGen seed >>= randomStringN 10
(9,"wuzudihnd")

It is important to note, that we didn't have to define any new monads or transformers, which saves us from a need to create thousands of different instances and force a user to use yet another monad. All of our machinery from Haskell ecosystem will work perfectly fine with this new interface.


With regards to Carter's remark:
> Yeah, absolutely agree that their pr has the wrong shape for monad random

It is possible to drop state token `s`, but we would have to loose `Frozen` type and ability to use functions like `thawGen`, `freezeGen` and consequently `runGenM` which  make `MonadRandom` even so more useful. That being said, if that is a deal breaker, I can submit a PR that removes this functionality.


Here is also an answer to David's question:

> Could you explain the reasoning behind the deprecations?

`next` and `genRange` are the actual  reason behind the slowness of `random` all these years. It is not feasible to convert an arbitrary `Int` sub range (which is what `next`+`genRange` give us) to another arbitrary subrange of another type efficiently. All prior versions of random go through `Integer` to generate ranges for almost all types, precisely because of this problem. The great part about this problem is that the poor quality `StdGen` in `random-1.1` is the only pure RNG in Haskell that relies in this property of having unusual min and max value in `genRange`. Most of RNGs out there produce pseudo random numbers in a n-bit range, where n is usually 32 or 64 bits. Once you have that property available it is possible to utilize it to get really fast generation of random numbers of any type in any range. Therefore this is the reason for addition of `genWord32`, `genWord64` ... and deprecation of `next` and `genRange`. Nice thing the approach we took is that it makes it backwards compatible, in other words any instance that only defined `next` and `genRange` will still work, albeit slower than it could if it were to implement either `genWord32` or `genWord64`.

In case you are curious, I've went through all packages that implement `RandomGen` instance and none of them will miss these two functions, here is a list of some of the repos with branches that contain fixed instances:

Alexey.

PS. I didn't realize I my last email was not posted to libraries because my email was not registered, so I resent it again.



‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, May 27, 2020 5:13 AM, Carter Schonwald <[hidden email]> wrote:

Zemyla! 

Yeah, absolutely agree that their pr has the wrong shape for monad random, which is why I’m confused by dominics pronouncement :), though its a great contrib.

It should be (ignoring m being applicative vs monad)
(For context, their design is roughly  ... MonadRandom m s g | m,g -> s ?  I’m typing on a phone so i might be restating it wrong ... :) )


The *better* choice is 
Class PRNG g =>  MonadRandom m g | m-> g where ... 

And then their example instance  should be something like 

Newtype MWCT  m a = ... newtype wrapper around StateT m a threading an MWC indexed by the state token of the underlying PrimMonad
(Or newtype MWCT s m a = .... stateT thing)

Instance (PrimMonad m) => MonadRandom  (MWCT m) (MCWGen (PrimState m)) where ... 

Or something along those lines.  It absolutely shouldn’t be in the style of being on any PrimMonad, but part of a stack that provides that instance.  

This is ignoring the freeze/thaw stuff which really is just “record and restore RNG state”, and i think is  an artifact of ther design choice in their PR. Which has a lot of great stuff I’m reviewing and poking at.


Nothing is set in stone about deprecation and migration story, cause improving everything and making sure everyone has a zero pain/ or at least tolerable upgrade path is step zero.  (And making sure good stable interfaces persists is key! )

I hope everyone is having a safe and healthy start to their summers, 

and I’m sorry for any confusions Dominics email about his collab Pr announcement has created.  But cest lie vie! Though sharing excitement about a great Pr is great! 

Stay well!
-Carter 

On Tue, May 26, 2020 at 6:48 PM Zemyla <[hidden email]> wrote:
And can you explain how to take an existing RNG and write it in this new format?

On Tue, May 26, 2020, 15:54 David Feuer <[hidden email]> wrote:
Could you explain the reasoning behind the deprecations?

On Tue, May 26, 2020, 6:00 AM <[hidden email]> wrote:

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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
Twitter: @idontgetoutmuch




_______________________________________________
Libraries mailing list
_______________________________________________
Libraries mailing list
_______________________________________________
Libraries mailing list


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Richard Eisenberg-5


On May 27, 2020, at 9:23 AM, Alexey Kuleshevich <[hidden email]> wrote:

> Could you explain the reasoning behind the deprecations?

My sense from the answer to this question is that *defining* a RandomGen instance in terms of next/genRange is deprecated, but *using* these functions isn't. Is that correct?

Richard

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

David Feuer
It sounds to me like they're totally deprecated. Presumably, almost no one uses them directly anyway, outside the package.

On Wed, May 27, 2020, 4:51 AM Richard Eisenberg <[hidden email]> wrote:


On May 27, 2020, at 9:23 AM, Alexey Kuleshevich <[hidden email]> wrote:

> Could you explain the reasoning behind the deprecations?

My sense from the answer to this question is that *defining* a RandomGen instance in terms of next/genRange is deprecated, but *using* these functions isn't. Is that correct?

Richard
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Alexey Kuleshevich
In reply to this post by Richard Eisenberg-5
Hey Richard,



`next` and `genRange` were never used directly anyways. They were only useful for defining `Random` instances, so they do not serve any purpose whatsoever after new version is released.

Alexey
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, May 27, 2020 11:51 AM, Richard Eisenberg <[hidden email]> wrote:



On May 27, 2020, at 9:23 AM, Alexey Kuleshevich <[hidden email]> wrote:

> Could you explain the reasoning behind the deprecations?

My sense from the answer to this question is that *defining* a RandomGen instance in terms of next/genRange is deprecated, but *using* these functions isn't. Is that correct?

Richard


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Alexey Khudyakov
In reply to this post by Carter Schonwald
On 27.05.2020 05:13, Carter Schonwald wrote:

> Zemyla!
>
> Yeah, absolutely agree that their pr has the wrong shape for monad
> random, which is why I’m confused by dominics pronouncement :), though
> its a great contrib.
>
> It should be (ignoring m being applicative vs monad)
> (For context, their design is roughly  ... MonadRandom m s g | m,g -> s
> ?  I’m typing on a phone so i might be restating it wrong ... :) )
>
>
> The *better* choice is
> Class PRNG g =>  MonadRandom m g | m-> g where ...
>
> And then their example instance  should be something like
>
> Newtype MWCT  m a = ... newtype wrapper around StateT m a threading an
> MWC indexed by the state token of the underlying PrimMonad
> (Or newtype MWCT s m a = .... stateT thing)
>
> Instance (PrimMonad m) => MonadRandom  (MWCT m) (MCWGen (PrimState m))
> where ...
>
> Or something along those lines.  It absolutely shouldn’t be in the style
> of being on any PrimMonad, but part of a stack that provides that instance.
>
One couldn't use StateT to thread state token for two reasont. First
StateT from transformer since it allows to thread values of kind * and
IO's state token is #.

State transformer threading state token on top of some other monad
_will_ cause problems if it's placed on top of list monad causing
unwanted buffer sharing and possibly loss of referential transparency


> This is ignoring the freeze/thaw stuff which really is just “record and
> restore RNG state”, and i think is  an artifact of ther design choice in
> their PR. Which has a lot of great stuff I’m reviewing and poking at.
>
Frozen/thaw (or immutable/mutable) distinction is inevitable once one
starts working with in place mutation. In order to get snapshot of PRNG
state at some particular point it have to be copied.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Dominic Steinitz-2
In reply to this post by Carter Schonwald
Hi Carter,

With respect to migration, most people will need to make no changes. We have built all the packages in hackage against the proposed new version (1.2) and there have been very few breakages and, where there have been, the fix is very simple. For example, for `buffon-machines` the patch is just

-import System.Random
+import System.Random hiding (uniform)

So most people will have zero pain and we have PRs prepared for those few packages that are impacted.

I think Alexey has already answered the question on deprecation.

Dominic Steinitz
Twitter: @idontgetoutmuch


On 27 May 2020, at 03:13, Carter Schonwald <[hidden email]> wrote:

Zemyla! 


...


Nothing is set in stone about deprecation and migration story, cause improving everything and making sure everyone has a zero pain/ or at least tolerable upgrade path is step zero.  (And making sure good stable interfaces persists is key! )



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Markert, Leonhard
Zemyla, Richard and Carter: thanks for your questions! The proposal is large, and though we've tried to document things thoroughly (see links at the end of the email), the motivation behind and consequences of some decisions are not obvious.

I don't want this proposal to stall. If you have follow-up questions, please ask them! If your questions have been answered by one of the detailed replies in this thread, would you mind saying so?


On Wed, May 27, 2020 at 1:24 PM <[hidden email]> wrote:
Hi Carter,

With respect to migration, most people will need to make no changes. We have built all the packages in hackage against the proposed new version (1.2) and there have been very few breakages and, where there have been, the fix is very simple. For example, for `buffon-machines` the patch is just

-import System.Random
+import System.Random hiding (uniform)

So most people will have zero pain and we have PRs prepared for those few packages that are impacted.

I think Alexey has already answered the question on deprecation.

Dominic Steinitz
Twitter: @idontgetoutmuch


On 27 May 2020, at 03:13, Carter Schonwald <[hidden email]> wrote:

Zemyla! 


...


Nothing is set in stone about deprecation and migration story, cause improving everything and making sure everyone has a zero pain/ or at least tolerable upgrade path is step zero.  (And making sure good stable interfaces persists is key! )


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Dominic Steinitz-2
In reply to this post by Dominic Steinitz-2
We shouldn’t lost sight of what a big improvement this is; in some cases it is more than x1000 better!

| 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|
(Times in milliseconds per 100,000 generations)

On 29 May 2020, at 13:00, [hidden email] wrote:

Zemyla, Richard and Carter: thanks for your questions! The proposal is
large, and though we've tried to document things thoroughly (see links at
the end of the email), the motivation behind and consequences of some
decisions are not obvious.

I don't want this proposal to stall. If you have follow-up questions,
please ask them! If your questions have been answered by one of the
detailed replies in this thread, would you mind saying so?

Haddocks:
https://htmlpreview.github.io/?https://raw.githubusercontent.com/idontgetoutmuch/random/haddock-preview/doc/index.html
Motivation and design:
https://github.com/idontgetoutmuch/random/blob/v1.2-release-notes/RELEASE-NOTES-v1.2.md
Benchmarks:
https://github.com/idontgetoutmuch/random/blob/v1.2-proposal/CHANGELOG.md#benchmarks


Dominic Steinitz
Twitter: @idontgetoutmuch



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

RE: Improving Random

Haskell - Libraries mailing list
In reply to this post by Dominic Steinitz-2

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 <[hidden email]> On Behalf Of [hidden email]
Sent: 26 May 2020 11:00
To: libraries <[hidden email]>
Cc: Alexey Kuleshevich <[hidden email]>
Subject: Improving Random

 

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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

Twitter: @idontgetoutmuch

 

 

 

 


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Markert, Leonhard
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 as its default PRNG.

On Mon, Jun 1, 2020 at 12:55 PM Simon Peyton Jones via Libraries <[hidden email]> 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 <[hidden email]> On Behalf Of [hidden email]
Sent: 26 May 2020 11:00
To: libraries <[hidden email]>
Cc: Alexey Kuleshevich <[hidden email]>
Subject: Improving Random

 

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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

Twitter: @idontgetoutmuch

 

 

 

 

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Carter Schonwald
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 <[hidden email]> 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 as its default PRNG.

On Mon, Jun 1, 2020 at 12:55 PM Simon Peyton Jones via Libraries <[hidden email]> 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 <[hidden email]> On Behalf Of [hidden email]
Sent: 26 May 2020 11:00
To: libraries <[hidden email]>
Cc: Alexey Kuleshevich <[hidden email]>
Subject: Improving Random

 

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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

Twitter: @idontgetoutmuch

 

 

 

 

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Alexey Kuleshevich
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 <[hidden email]> 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 <[hidden email]> 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 as its default PRNG.

On Mon, Jun 1, 2020 at 12:55 PM Simon Peyton Jones via Libraries <[hidden email]> 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 <[hidden email]> On Behalf Of [hidden email]
Sent: 26 May 2020 11:00
To: libraries <[hidden email]>
Cc: Alexey Kuleshevich <[hidden email]>
Subject: Improving Random

 

Hello Libraries,

You may recall that following the blog post by @lehins, a group of us (@curiousleo, @lehins and me) invited participation in February to take this work and apply it to improving the current random library.

Our proximate goals were to fix #25 (filed in 2015) and #51 (filed in 2018). After a lot of discussion and experimentation, we have a proposal that addresses both these issues and also: #26, #44, #53, #55, #58 and #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 and the PR for the proposed new version is here.

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

Twitter: @idontgetoutmuch

 

 

 

 

_______________________________________________
Libraries mailing list
_______________________________________________
Libraries mailing list


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Fumiaki Kinoshita
> Dominic, whom you have kicked out from the list of maintainers

Can I also ask why this happened?

IMO (I believe a lot of people would agree), software development, especially of core libraries should be transparent and healthy, but as far as I can see none of this work is getting into master, and still held back because of reasons Carter hasn't clarified.

This looks quite similar to what we've seen in the vector package a while ago; I noticed that patches I submitted weren't getting into the release for several years, so I posted an issue asking to release a new version including recent fixes. As people point out the problem in the release process, the issue has been locked, and eventually deleted for some reason (https://github.com/haskell/vector/issues/265).

Incidents like these significantly discourage active/potential contributors, and can affect the entire ecosystem. If anything like this happens again, we may want to introduce some kind of audits to lubricate and  sanitise the workflow. The current situation looks rather disappointing to me.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Improving Random

Alexey Kuleshevich
> Can I also ask why this happened?

I don't know why, maybe Carter can shed some light for us why he abused his power and dropped another maintainer of core library without any explanation.
I suspect that he got upset about Dominic saying publicly not to use `random` because it is of poor quality [1], which I can only deduce from Carter's response in [2]
I am not sure if it happened immediately, but the wiki was updated a few months later [3]




> This looks quite similar to what we've seen in the vector package a while ago;

This does look very similar indeed. I participated on the issue #265 and I am very surprised that it was deleted! It was an important ticket that discussed lack of maintainship and poor release process currently practiced in `vector` package.

I do not want to derail this conversation away from `random`, but this seems like a recurring pattern. I believe many will agree with me that this is not an acceptable way of maintaining core packages. I can't think of a better time for CLC to get involved and do something about the problem at hand.

Alexey.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, June 3, 2020 10:03 AM, Fumiaki Kinoshita <[hidden email]> wrote:

> Dominic, whom you have kicked out from the list of maintainers

Can I also ask why this happened?

IMO (I believe a lot of people would agree), software development, especially of core libraries should be transparent and healthy, but as far as I can see none of this work is getting into master, and still held back because of reasons Carter hasn't clarified.

This looks quite similar to what we've seen in the vector package a while ago; I noticed that patches I submitted weren't getting into the release for several years, so I posted an issue asking to release a new version including recent fixes. As people point out the problem in the release process, the issue has been locked, and eventually deleted for some reason (https://github.com/haskell/vector/issues/265).

Incidents like these significantly discourage active/potential contributors, and can affect the entire ecosystem. If anything like this happens again, we may want to introduce some kind of audits to lubricate and  sanitise the workflow. The current situation looks rather disappointing to me.


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
12