System/Random.hs:43:1: warning: [-Wtabs] #55
Milestone
Comments
Merged
curiousleo
added a commit
to curiousleo/random
that referenced
this issue
May 26, 2020
author Alexey Kuleshevich <[email protected]> 1581472095 +0300 committer Leonhard Markert <[email protected]> 1590493894 +0200 This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== MonadRandom ----------- This patch adds a 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 the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full 'MonadRandom Gen' instance. Four 'MonadRandom' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
curiousleo
added a commit
to curiousleo/random
that referenced
this issue
May 26, 2020
author Alexey Kuleshevich <[email protected]> 1581472095 +0300 committer Leonhard Markert <[email protected]> 1590493894 +0200 This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== MonadRandom ----------- This patch adds a 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 the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full 'MonadRandom Gen' instance. Four 'MonadRandom' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
curiousleo
added a commit
to curiousleo/random
that referenced
this issue
May 26, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== MonadRandom ----------- This patch adds a 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 the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full 'MonadRandom Gen' instance. Four 'MonadRandom' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
lehins
added a commit
to idontgetoutmuch/random
that referenced
this issue
May 27, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== MonadRandom ----------- This patch adds a 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 the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full 'MonadRandom Gen' instance. Four 'MonadRandom' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
lehins
added a commit
to idontgetoutmuch/random
that referenced
this issue
May 27, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== MonadRandom ----------- This patch adds a 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 the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full 'MonadRandom Gen' instance. Four 'MonadRandom' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
lehins
added a commit
to idontgetoutmuch/random
that referenced
this issue
May 27, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== MonadRandom ----------- This patch adds a 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 the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full 'MonadRandom Gen' instance. Four 'MonadRandom' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
Merged
curiousleo
added a commit
to curiousleo/random
that referenced
this issue
Jun 15, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== MonadRandom ----------- This patch adds a 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 the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full 'MonadRandom Gen' instance. Four 'MonadRandom' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
curiousleo
added a commit
to idontgetoutmuch/random
that referenced
this issue
Jun 15, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== MonadRandom ----------- This patch adds a 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 the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full 'MonadRandom Gen' instance. Four 'MonadRandom' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
curiousleo
added a commit
to idontgetoutmuch/random
that referenced
this issue
Jun 22, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== StatefulGen ----------- This patch adds a class 'StatefulGen': -- | 'StatefulGen' is an interface to monadic pseudo-random number generators. class Monad m => StatefulGen g m where uniformWord32 :: g -> m Word32 -- default implementation in terms of uniformWord64 uniformWord64 :: g -> 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 In 'StatefulGen g m', 'g' is the type of the generator and 'm' the underlying monad. Four 'StatefulGen' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. FrozenGen --------- This patch also introduces a class 'FrozenGen': -- | 'FrozenGen' is designed for stateful pseudo-random number generators -- that can be saved as and restored from an immutable data type. class StatefulGen (MutableGen f m) m => FrozenGen f m where type MutableGen f m = (g :: Type) | g -> f freezeGen :: MutableGen f m -> m f thawGen :: f -> m (MutableGen f m) 'f' is the type of the generator's state "at rest" and 'm' the underlying monad. 'MutableGen' is defined as an injective type family via 'g -> f' so for any generator 'g', the type 'f' of its at-rest state is well-defined. Both 'StatefulGen' and 'FrozenGen' are generic enough to accommodate, for example, the 'Gen' type from the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full instances. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
curiousleo
added a commit
to idontgetoutmuch/random
that referenced
this issue
Jun 22, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | 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| API changes =========== StatefulGen ----------- This patch adds a class 'StatefulGen': -- | 'StatefulGen' is an interface to monadic pseudo-random number generators. class Monad m => StatefulGen g m where uniformWord32 :: g -> m Word32 -- default implementation in terms of uniformWord64 uniformWord64 :: g -> 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 In 'StatefulGen g m', 'g' is the type of the generator and 'm' the underlying monad. Four 'StatefulGen' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. FrozenGen --------- This patch also introduces a class 'FrozenGen': -- | 'FrozenGen' is designed for stateful pseudo-random number generators -- that can be saved as and restored from an immutable data type. class StatefulGen (MutableGen f m) m => FrozenGen f m where type MutableGen f m = (g :: Type) | g -> f freezeGen :: MutableGen f m -> m f thawGen :: f -> m (MutableGen f m) 'f' is the type of the generator's state "at rest" and 'm' the underlying monad. 'MutableGen' is defined as an injective type family via 'g -> f' so for any generator 'g', the type 'f' of its at-rest state is well-defined. Both 'StatefulGen' and 'FrozenGen' are generic enough to accommodate, for example, the 'Gen' type from the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full instances. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.10' (GHC-8.2) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
curiousleo
added a commit
to idontgetoutmuch/random
that referenced
this issue
Jun 23, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | Improvement| | ----------------------- | ---------- | ------------ | ---------- | | pure/random/Float | 30 | 0.03 | 1038| | pure/random/Double | 52 | 0.03 | 1672| | pure/random/Integer | 43 | 0.33 | 131| | pure/uniform/Word | 44 | 0.03 | 1491| | pure/uniform/Int | 43 | 0.03 | 1512| | pure/uniform/Char | 17 | 0.49 | 35| | pure/uniform/Bool | 18 | 0.03 | 618| API changes =========== StatefulGen ----------- This patch adds a class 'StatefulGen': -- | 'StatefulGen' is an interface to monadic pseudo-random number generators. class Monad m => StatefulGen g m where uniformWord32 :: g -> m Word32 -- default implementation in terms of uniformWord64 uniformWord64 :: g -> 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 In 'StatefulGen g m', 'g' is the type of the generator and 'm' the underlying monad. Four 'StatefulGen' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. FrozenGen --------- This patch also introduces a class 'FrozenGen': -- | 'FrozenGen' is designed for stateful pseudo-random number generators -- that can be saved as and restored from an immutable data type. class StatefulGen (MutableGen f m) m => FrozenGen f m where type MutableGen f m = (g :: Type) | g -> f freezeGen :: MutableGen f m -> m f thawGen :: f -> m (MutableGen f m) 'f' is the type of the generator's state "at rest" and 'm' the underlying monad. 'MutableGen' is defined as an injective type family via 'g -> f' so for any generator 'g', the type 'f' of its at-rest state is well-defined. Both 'StatefulGen' and 'FrozenGen' are generic enough to accommodate, for example, the 'Gen' type from the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full instances. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.8' (GHC-7.10) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
curiousleo
added a commit
to idontgetoutmuch/random
that referenced
this issue
Jun 23, 2020
This patch is mostly backwards compatible. See "Breaking Changes" below for the full list of backwards incompatible changes. This patch fixes quality and performance issues, addresses additional miscellaneous issues, and introduces a monadic API. Issues addressed ================ Priority issues fixed in this patch: - Title: "The seeds generated by split are not independent" Link: haskell#25 Fixed: changed algorithm to SplitMix, which provides a robust 'split' operation - Title: "Very low throughput" Link: haskell#51 Fixed: see "Performance" below Additional issues addressed in this patch: - Title: "Add Random instances for tuples" Link: haskell#26 Addressed: added 'Uniform' instances for up to 6-tuples - Title: "Add Random instance for Natural" Link: haskell#44 Addressed: added 'UniformRange' instance for 'Natural' - Title: "incorrect distribution of randomR for floating-point numbers" Link: haskell#53 Addressed: see "Regarding floating-point numbers" below - Title: "System/Random.hs:43:1: warning: [-Wtabs]" Link: haskell#55 Fixed: no more tabs - Title: "Why does random for Float and Double produce exactly 24 or 53 bits?" Link: haskell#58 Fixed: see "Regarding floating-point numbers" below - Title: "read :: StdGen fails for strings longer than 6" Link: haskell#59 Addressed: 'StdGen' is no longer an instance of 'Read' Regarding floating-point numbers: with this patch, the relevant instances for 'Float' and 'Double' sample more bits than before but do not sample every possible representable value. The documentation now clearly spells out what this means for users. Quality (issue 25) ================== The algorithm [1] in version 1.1 of this library fails empirical PRNG tests when used to generate "split sequences" as proposed in [3]. SplitMix [2] passes the same tests. This patch changes 'StdGen' to use the SplitMix implementation provided by the splitmix package. Test batteries used: dieharder, TestU1, PractRand. [1]: P. L'Ecuyer, "Efficient and portable combined random number generators". https://doi.org/10.1145/62959.62969 [2]: G. L. Steele, D. Lea, C. H. Flood, "Fast splittable pseudorandom number generators". https://doi.org/10.1145/2714064.2660195 [3]: H. G. Schaathun, "Evaluation of splittable pseudo-random generators". https://doi.org/10.1017/S095679681500012X Performance (issue 51) ====================== The "improvement" column in the following table is a multiplier: the improvement for 'random' for type 'Float' is 1038, so this operation is 1038 times faster with this patch. | Name | Mean (1.1) | Mean (patch) | Improvement| | ----------------------- | ---------- | ------------ | ---------- | | pure/random/Float | 30 | 0.03 | 1038| | pure/random/Double | 52 | 0.03 | 1672| | pure/random/Integer | 43 | 0.33 | 131| | pure/uniform/Word | 44 | 0.03 | 1491| | pure/uniform/Int | 43 | 0.03 | 1512| | pure/uniform/Char | 17 | 0.49 | 35| | pure/uniform/Bool | 18 | 0.03 | 618| API changes =========== StatefulGen ----------- This patch adds a class 'StatefulGen': -- | 'StatefulGen' is an interface to monadic pseudo-random number generators. class Monad m => StatefulGen g m where uniformWord32 :: g -> m Word32 -- default implementation in terms of uniformWord64 uniformWord64 :: g -> 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 In 'StatefulGen g m', 'g' is the type of the generator and 'm' the underlying monad. Four 'StatefulGen' instances ("monadic adapters") are provided for pure generators to enable their use in monadic code. The documentation describes them in detail. FrozenGen --------- This patch also introduces a class 'FrozenGen': -- | 'FrozenGen' is designed for stateful pseudo-random number generators -- that can be saved as and restored from an immutable data type. class StatefulGen (MutableGen f m) m => FrozenGen f m where type MutableGen f m = (g :: Type) | g -> f freezeGen :: MutableGen f m -> m f thawGen :: f -> m (MutableGen f m) 'f' is the type of the generator's state "at rest" and 'm' the underlying monad. 'MutableGen' is defined as an injective type family via 'g -> f' so for any generator 'g', the type 'f' of its at-rest state is well-defined. Both 'StatefulGen' and 'FrozenGen' are generic enough to accommodate, for example, the 'Gen' type from the 'mwc-random' package, which itself abstracts over the underlying primitive monad and state token. The documentation shows the full instances. 'Uniform' and 'UniformRange' ---------------------------- 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. Breaking Changes ================ This patch introduces these breaking changes: * requires 'base >= 4.8' (GHC-7.10) * 'StdGen' is no longer an instance of 'Read' * 'randomIO' and 'randomRIO' where extracted from the 'Random' class into separate functions In addition, there may be import clashes with new functions, e.g. 'uniform' and 'uniformR'. Deprecations ============ This patch introduces 'genWord64', 'genWord32' and similar methods to the 'RandomGen' class. The significantly slower method 'next' and its companion 'genRange' are now deprecated. Co-authored-by: Alexey Kuleshevich <[email protected]> Co-authored-by: idontgetoutmuch <[email protected]> Co-authored-by: Leonhard Markert <[email protected]>
|
All compile time warnings have been taken care of. See #62 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
stack buildwith lts-13.26 warns@nagaflokhu mentioned it also in #50
random/System/Random.hs
Lines 42 to 43 in cfdfe6f
The text was updated successfully, but these errors were encountered: