This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
I have implemented my proposal D0205 to allow seeding random number
engines directly with `std::random_device` as in
std::random_device device {};
std::mt19937 engine {device}; // note: device passed by-reference
std::cout << "Here is a very random number: " << engine() << "\n";
for libstdc++. The paper will be officially submitted to ISO tomorrow
and hopefully be discussed in Jacksonville and ideally accepted for
C++17. Attached is my patch against libstdc++ SVN revision 233225 and a
quick note how to use it. You can find the current version of any of
these as well as the final D0205R1 of the paper on my website, too.
http://klammler.eu/data/computer-science/iso-c++/p0205/
I would be very grateful for a review of my patch. This is my first
experience with writing standard library code. By the way, I don't
know how to make the ABI compatibility check pass again, even though
I've read the [ABI Policy and
Guidelines](https://gcc.gnu.org/onlinedocs/libstdc++/manual/abi.html).
I didn't include a copyright notice in the files because I didn't want
to say that something is by the FSF without being asked to do so. I
will be happy to fix this once asked for.
Do you have any interest in incorporating this patch into libstdc++? Is
there a process for merging experimental features that are not
officially standard yet?
Thank you for considering.
--
OpenPGP:
Public Key: http://openpgp.klammler.eu
Fingerprint: 2732 DA32 C8D0 EEEC A081 BE9D CF6C 5166 F393 A9C0
<!-- -*- coding:utf-8; mode:markdown; -*- -->
# Allow Seeding Random Number Engines With `std::random_device`
This patch is work-in-progress to implement D0205 for `libstdc++`, the C++
standard library that comes with GCC.
## Overview
The patch is currently based on the GCC trunk revision 233225. The SVN sources
of GCC can be checked out via the following URL.
svn://gcc.gnu.org/svn/gcc
The current version of this patch can be found at the following URL.
http://klammler.eu/data/computer-science/iso-c++/p0205/libstdc++/
## Usage
With the patch applied, `libstdc++`' `std::random_device` meets the
requirements of *seed generator* and can be used to seed `libstdc++`' *random
number engines*. See the file
libstdc++-v3/testsuite/26_numerics/random/random_device/generate/header-only/seed_generator.cc
for an example.
In order to see the changes made by the patch, C++ files that want to make use
of them must `#define _GLIBCXX_USE_P0205` before `#include`ing the `<random>`
header. There macro must be defined to either of the following values.
- `#define _GLIBCXX_USE_P0205 'I'`
provides a header-only implementation that does not require re-building
`libstdc++`. It adds all functionality but misses all optimizations.
- `#define _GLIBCXX_USE_P0205 'L'`
provides an optimized implementation but requires re-building the
`libstdc++` library.
## Known Issues
- This patch breaks `make check` for the ABI compliance and I don't know how
to fix it.
- The optimization deployed for iterators of type `std::uint32_t *` should
also be enabled for any other iterators of type `IterT` where
`std::iterator_traits<IterT>::value_type` is `std::uint32_t` and
`std::iterator_traits<IterT>::iterator_category` is
`std::contiguous_iterator_tag`, except that the latter does not exist yet.
Apparently, it is possible to do the optimization at least for standard
library iterators because `std::copy` et al do it too but I don't know how
to enable it.
Index: config/abi/pre/gnu.ver
===================================================================
--- config/abi/pre/gnu.ver (revision 233225)
+++ config/abi/pre/gnu.ver (working copy)
@@ -1564,6 +1564,7 @@
_ZNSt13random_device7_M_finiEv;
_ZNSt13random_device7_M_initERKSs;
_ZNSt13random_device9_M_getvalEv;
+ _ZNSt13random_device14_M_fill_bufferEPvm; # FIXME: Where to add this?
# std::this_thread::__sleep_for
_ZNSt11this_thread11__sleep_for*;
Index: include/bits/random.h
===================================================================
--- include/bits/random.h (revision 233225)
+++ include/bits/random.h (working copy)
@@ -31,8 +31,9 @@
#ifndef _RANDOM_H
#define _RANDOM_H 1
-#include <vector>
-#include <bits/uniform_int_dist.h>
+#include <iterator> // std::distance
+#include <vector> // std::vector
+#include <bits/uniform_int_dist.h> // std::uniform_int_distribution
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -1615,12 +1616,56 @@
#endif
}
+#ifdef _GLIBCXX_USE_P0205
+ template <typename _RandIterT>
+ void
+ generate(const _RandIterT __f, const _RandIterT __l)
+ {
+# if _GLIBCXX_USE_P0205 == 'I'
+ auto __dist32 = uniform_int_distribution<uint_least32_t> {};
+ for (auto __it = __f; __it != __l; ++__it)
+ *__it = __dist32(*this);
+# elif _GLIBCXX_USE_P0205 == 'L'
+ _M_generate(__f, __l);
+# else
+# error "Please #define _GLIBCXX_USE_P0205 to 'I' (header-only) or 'L' (library)"
+# endif
+ }
+#endif // defined _GLIBCXX_USE_P0205
+
// No copy functions.
random_device(const random_device&) = delete;
void operator=(const random_device&) = delete;
-
+
private:
+ void
+ _M_generate(uint32_t * __f, uint32_t * __l)
+ {
+ // TODO: Once we have contiguous iterators, they should be handled by
+ // this function, too.
+ _M_fill_buffer(__f, sizeof(uint32_t) * (__l - __f));
+ }
+
+ template <typename _FwdIterT>
+ void
+ _M_generate(_FwdIterT __f, _FwdIterT __l)
+ {
+ uint_least32_t __buff[32] alignas(result_type);
+ constexpr auto __word_sz = sizeof(__buff[0]);
+ constexpr auto __buff_sz = sizeof(__buff) / __word_sz;
+ auto __togo = distance(__f, __l);
+ while (__togo > 0)
+ {
+ constexpr auto __mask32 = static_cast<uint_least32_t>(0xffffffffUL);
+ const auto __chunk = (__togo < __buff_sz) ? __togo : __buff_sz;
+ _M_fill_buffer(__buff, __chunk * __word_sz);
+ for (auto __i = size_t {}; __i < __chunk; ++__i)
+ *__f++ = __mask32 & __buff[__i];
+ __togo -= __chunk;
+ }
+ }
+
void _M_init(const std::string& __token);
void _M_init_pretr1(const std::string& __token);
void _M_fini();
@@ -1628,6 +1673,8 @@
result_type _M_getval();
result_type _M_getval_pretr1();
+ void _M_fill_buffer(void * __p, size_t __n);
+
union
{
void* _M_file;
Index: src/c++11/random.cc
===================================================================
--- src/c++11/random.cc (revision 233225)
+++ src/c++11/random.cc (working copy)
@@ -38,6 +38,10 @@
# include <unistd.h>
#endif
+#if (defined __i386__ || defined __x86_64__) && defined _GLIBCXX_X86_RDRAND
+# define _GLIBCXX_HAVE_X86_RDRAND 1
+#endif
+
namespace std _GLIBCXX_VISIBILITY(default)
{
namespace
@@ -58,7 +62,8 @@
return __ret;
}
-#if (defined __i386__ || defined __x86_64__) && defined _GLIBCXX_X86_RDRAND
+#if _GLIBCXX_HAVE_X86_RDRAND
+
unsigned int
__attribute__ ((target("rdrnd")))
__x86_rdrand(void)
@@ -72,9 +77,56 @@
return val;
}
-#endif
- }
+
+ void
+ fill_buffer_x86_rdrand(void * p, size_t n)
+ {
+ using word_type = random_device::result_type;
+ constexpr auto word_size = sizeof(word_type);
+ static_assert(sizeof(__x86_rdrand()) >= word_size, "");
+ auto dest = static_cast<word_type *>(p);
+ while (n >= word_size)
+ {
+ *dest++ = __x86_rdrand();
+ n -= word_size;
+ }
+ }
+#endif // _GLIBCXX_HAVE_X86_RDRAND
+
+#ifdef _GLIBCXX_HAVE_UNISTD_H
+
+ void
+ fill_buffer_unistd_read(void * p, size_t n, int fd)
+ {
+ while (n > 0)
+ {
+ const auto count = read(fd, p, n);
+ if (count > 0)
+ {
+ n -= count;
+ p = static_cast<char *>(p) + count;
+ }
+ else if (count == 0 || errno != EINTR)
+ {
+ __throw_runtime_error(__N("random_device: read"));
+ }
+ }
+ }
+
+#else // !_GLIBCXX_HAVE_UNISTD_H
+
+ void
+ fill_buffer_stdlib_fread(void * p, size_t n, FILE * fh)
+ {
+ if (fread(p, n, 1, fh) != 1)
+ __throw_runtime_error(__N("random_device: fread"));
+ }
+
+#endif // !_GLIBCXX_HAVE_UNISTD_H
+
+ } // namespace /* anonymous */
+
void
random_device::_M_init(const std::string& token)
{
@@ -82,7 +134,7 @@
if (token == "default")
{
-#if (defined __i386__ || defined __x86_64__) && defined _GLIBCXX_X86_RDRAND
+#ifdef _GLIBCXX_HAVE_X86_RDRAND
unsigned int eax, ebx, ecx, edx;
// Check availability of cpuid and, for now at least, also the
// CPU signature for Intel's
@@ -125,34 +177,26 @@
random_device::result_type
random_device::_M_getval()
{
-#if (defined __i386__ || defined __x86_64__) && defined _GLIBCXX_X86_RDRAND
- if (!_M_file)
- return __x86_rdrand();
+ result_type ret;
+ _M_fill_buffer(&ret, sizeof(ret));
+ return ret;
+ }
+
+ void
+ random_device::_M_fill_buffer(void * p, size_t n)
+ {
+#ifdef _GLIBCXX_HAVE_X86_RDRAND
+ if (_M_file == nullptr)
+ return fill_buffer_x86_rdrand(p, n);
#endif
-
- result_type __ret;
- void* p = &__ret;
- size_t n = sizeof(result_type);
+ const auto fh = static_cast<FILE *>(_M_file);
#ifdef _GLIBCXX_HAVE_UNISTD_H
- do
- {
- const int e = read(fileno(static_cast<FILE*>(_M_file)), p, n);
- if (e > 0)
- {
- n -= e;
- p = static_cast<char*>(p) + e;
- }
- else if (e != -1 || errno != EINTR)
- __throw_runtime_error(__N("random_device could not be read"));
- }
- while (n > 0);
+ const auto fd = fileno(fh);
+ return fill_buffer_unistd_read(p, n, fd);
#else
- const size_t e = std::fread(p, n, 1, static_cast<FILE*>(_M_file));
- if (e != 1)
- __throw_runtime_error(__N("random_device could not be read"));
+ return fill_buffer_stdlib_fread(p, n, fh);
#endif
-
- return __ret;
+ __throw_runtime_error(__N("random_device the impossible has happened"));
}
random_device::result_type
Index: testsuite/26_numerics/random/pr60037-neg.cc
===================================================================
--- testsuite/26_numerics/random/pr60037-neg.cc (revision 233225)
+++ testsuite/26_numerics/random/pr60037-neg.cc (working copy)
@@ -10,6 +10,6 @@
auto x = std::generate_canonical<std::size_t,
std::numeric_limits<std::size_t>::digits>(urng);
-// { dg-error "static assertion failed: template argument not a floating point type" "" { target *-*-* } 160 }
+// { dg-error "static assertion failed: template argument not a floating point type" "" { target *-*-* } 161 }
// { dg-error "static assertion failed: template argument not a floating point type" "" { target *-*-* } 3314 }
Index: testsuite/26_numerics/random/random_device/generate/header-only/seed_generator.cc
===================================================================
--- testsuite/26_numerics/random/random_device/generate/header-only/seed_generator.cc (nonexistent)
+++ testsuite/26_numerics/random/random_device/generate/header-only/seed_generator.cc (working copy)
@@ -0,0 +1,39 @@
+// { dg-do run }
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+
+// 26.4.6 class random_device [rand.device]
+// P0205 std::random_device::generate
+
+#define _GLIBCXX_USE_P0205 'I'
+
+#include <random>
+
+namespace /* anonymous */
+{
+
+ void
+ test01()
+ {
+ std::random_device device {};
+ std::mt19937 engine {device};
+ }
+
+ void
+ test02()
+ {
+ std::random_device device {};
+ std::mt19937 engine {};
+ engine.seed(device);
+ }
+
+} // namespace /* anonymous */
+
+
+int
+main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/26_numerics/random/random_device/generate/header-only/uniformity.cc
===================================================================
--- testsuite/26_numerics/random/random_device/generate/header-only/uniformity.cc (nonexistent)
+++ testsuite/26_numerics/random/random_device/generate/header-only/uniformity.cc (working copy)
@@ -0,0 +1,49 @@
+// { dg-do run }
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+
+// 26.4.6 class random_device [rand.device]
+// P0205 std::random_device::generate
+
+#define _GLIBCXX_USE_P0205 'I'
+
+#include <random>
+
+#include <cstddef> // std::size_t
+#include <cstdint> // std::uint32_t
+#include <testsuite_random.h> // __gnu_test::testDiscreteDist
+#include <vector> // std::vector
+
+
+namespace /* anonymous */
+{
+
+ void
+ test01()
+ {
+ using namespace __gnu_test;
+ constexpr auto n = 32;
+ constexpr auto m = 7;
+ constexpr auto k = 10;
+ auto values = std::vector<std::uint32_t>(1UL << k);
+ std::random_device device {};
+ device.generate(values.data(), values.data() + values.size());
+ auto idx = std::size_t {};
+ const auto stream = [&idx, &values](){
+ return (values.at(idx++) >> (n - m));
+ };
+ const auto pdf = [](const std::size_t i){
+ return uniform_int_pdf(i, 0, (1 << m) - 1);
+ };
+ testDiscreteDist< (1UL << m), (1UL << k) >(stream, pdf);
+ }
+
+} // namespace /* anonymous */
+
+
+int
+main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/26_numerics/random/random_device/generate/library/optimizations.cc
===================================================================
--- testsuite/26_numerics/random/random_device/generate/library/optimizations.cc (nonexistent)
+++ testsuite/26_numerics/random/random_device/generate/library/optimizations.cc (working copy)
@@ -0,0 +1,104 @@
+// { dg-do run }
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+
+// 26.4.6 class random_device [rand.device]
+// P0205 std::random_device::generate
+
+#define _GLIBCXX_USE_P0205 'L'
+
+#include <random>
+
+#include <algorithm> // std::all_of
+#include <array> // std::array
+#include <cstddef> // std::size_t
+#include <cstdint> // std::uint_least{32,64}_t
+#include <deque> // std::deque
+#include <utility> // std::begin, std::end
+#include <vector> // std::vector
+
+#include <testsuite_hooks.h> // VERIFY
+#include <testsuite_random.h> // __gnu_test::testDiscreteDist
+
+
+namespace /* anonymous */
+{
+
+ template <typename C>
+ void
+ test_generic(C& c)
+ {
+ bool test __attribute__((unused)) = true;
+ std::random_device device {};
+ const auto first = std::begin(c);
+ const auto last = std::end(c);
+ device.generate(last, last);
+ device.generate(first, last);
+ if (first == last)
+ return;
+ // Verify that the high-order bits are all zero.
+ constexpr auto lowmask = (static_cast<std::uint_least64_t>(1) << 32) - 1;
+ constexpr auto highmask = ~lowmask;
+ VERIFY(std::all_of(first, last, [](std::uint_least64_t x){ return (x & highmask) == 0; }));
+ // Verify that the low-order bits are uniformly distributed.
+ auto current = first;
+ const auto stream = [first, last, ¤t](){
+ if (current == last)
+ current = first;
+ return *current++;
+ };
+ const auto pdf = [](const std::size_t i){
+ // We cannot use uniform_int_pdf here because it would overflow.
+ return (i > lowmask) ? 0.0 : 1.0 / lowmask;
+ };
+ __gnu_test::testDiscreteDist(stream, pdf);
+ }
+
+ void
+ test_c_array()
+ {
+ std::uint_least32_t xxxii[100 + __LINE__];
+ std::uint_least64_t lxiv[100 + __LINE__];
+ test_generic(xxxii);
+ test_generic(lxiv);
+ }
+
+ void
+ test_std_array()
+ {
+ auto xxxii = std::array<std::uint_least32_t, 100 + __LINE__> {{}};
+ auto lxiv = std::array<std::uint_least64_t, 100 + __LINE__> {{}};
+ test_generic(xxxii);
+ test_generic(lxiv);
+ }
+
+ void
+ test_std_vector()
+ {
+ auto xxxii = std::vector<std::uint_least32_t>(100 + __LINE__);
+ auto lxiv = std::vector<std::uint_least64_t>(100 + __LINE__);
+ test_generic(xxxii);
+ test_generic(lxiv);
+ }
+
+ void
+ test_std_deque()
+ {
+ auto xxxii = std::deque<std::uint_least32_t>(100 + __LINE__);
+ auto lxiv = std::deque<std::uint_least64_t>(100 + __LINE__);
+ test_generic(xxxii);
+ test_generic(lxiv);
+ }
+
+} // namespace /* anonymous */
+
+
+int
+main(int argc, char * * argv)
+{
+ test_c_array();
+ test_std_array();
+ test_std_vector();
+ test_std_deque();
+ return 0;
+}
Index: testsuite/26_numerics/random/random_device/generate/library/seed_generator.cc
===================================================================
--- testsuite/26_numerics/random/random_device/generate/library/seed_generator.cc (nonexistent)
+++ testsuite/26_numerics/random/random_device/generate/library/seed_generator.cc (working copy)
@@ -0,0 +1,39 @@
+// { dg-do run }
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+
+// 26.4.6 class random_device [rand.device]
+// P0205 std::random_device::generate
+
+#define _GLIBCXX_USE_P0205 'L'
+
+#include <random>
+
+namespace /* anonymous */
+{
+
+ void
+ test01()
+ {
+ std::random_device device {};
+ std::mt19937 engine {device};
+ }
+
+ void
+ test02()
+ {
+ std::random_device device {};
+ std::mt19937 engine {};
+ engine.seed(device);
+ }
+
+} // namespace /* anonymous */
+
+
+int
+main()
+{
+ test01();
+ test02();
+ return 0;
+}
Index: testsuite/26_numerics/random/random_device/generate/library/uniformity.cc
===================================================================
--- testsuite/26_numerics/random/random_device/generate/library/uniformity.cc (nonexistent)
+++ testsuite/26_numerics/random/random_device/generate/library/uniformity.cc (working copy)
@@ -0,0 +1,49 @@
+// { dg-do run }
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+
+// 26.4.6 class random_device [rand.device]
+// P0205 std::random_device::generate
+
+#define _GLIBCXX_USE_P0205 'L'
+
+#include <random>
+
+#include <cstddef> // std::size_t
+#include <cstdint> // std::uint32_t
+#include <testsuite_random.h> // __gnu_test::testDiscreteDist
+#include <vector> // std::vector
+
+
+namespace /* anonymous */
+{
+
+ void
+ test01()
+ {
+ using namespace __gnu_test;
+ constexpr auto n = 32;
+ constexpr auto m = 7;
+ constexpr auto k = 10;
+ auto values = std::vector<std::uint32_t>(1UL << k);
+ std::random_device device {};
+ device.generate(values.data(), values.data() + values.size());
+ auto idx = std::size_t {};
+ const auto stream = [&idx, &values](){
+ return (values.at(idx++) >> (n - m));
+ };
+ const auto pdf = [](const std::size_t i){
+ return uniform_int_pdf(i, 0, (1 << m) - 1);
+ };
+ testDiscreteDist< (1UL << m), (1UL << k) >(stream, pdf);
+ }
+
+} // namespace /* anonymous */
+
+
+int
+main()
+{
+ test01();
+ return 0;
+}
Index: testsuite/26_numerics/random/random_device/operators/call.cc
===================================================================
--- testsuite/26_numerics/random/random_device/operators/call.cc (nonexistent)
+++ testsuite/26_numerics/random/random_device/operators/call.cc (working copy)
@@ -0,0 +1,67 @@
+// { dg-do run }
+// { dg-options "-std=gnu++11" }
+// { dg-require-cstdint "" }
+
+// 26.4.6 class random_device [rand.device]
+
+#include <random>
+
+#include <cstddef> // std::size_t
+#include <testsuite_random.h> // __gnu_test::testDiscreteDist
+
+
+namespace /* anonymous */
+{
+
+ // This test takes the output values from a `std::random_device` and applies
+ // an affine transformation to them such that we expect to get a uniform
+ // integer distribution. We then use `testDiscreteDist` to check this
+ // distribution.
+ //
+ // Given that the histogram of the actual result values should look like
+ // this,
+ //
+ // ##################################################
+ // ##################################################
+ // +------------------------------------------------+
+ // min max
+ //
+ // we expect the following histogram for the transformation.
+ //
+ // #########################
+ // #########################
+ // #########################
+ // #########################
+ // +---------+-----------------------+-------------->
+ // 0 offset offset + spread
+ //
+ void
+ test01()
+ {
+ using namespace __gnu_test;
+ constexpr auto min = std::random_device::min();
+ constexpr auto max = std::random_device::max();
+ constexpr auto offset = std::size_t {20};
+ constexpr auto spread = std::size_t {70};
+ std::random_device device {};
+ const auto transformation = [&device](){
+ const auto v = device();
+ const auto r = static_cast<double>(v - min) / (1.0 + max - min);
+ return static_cast<std::size_t>(offset + r * spread);
+ };
+ const auto expectation = [](const std::size_t i){
+ return uniform_int_pdf(i, offset, offset + spread);
+ };
+ if (false)
+ testDiscreteDist(transformation, expectation);
+ }
+
+} // namespace /* anonymous */
+
+
+int
+main()
+{
+ test01();
+ return 0;
+}
Attachment:
signature.asc
Description: PGP signature
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |