9
\$\begingroup\$

I use this document as a basis for my mini-library:

Motivation

The std::rand friends are discouraged in C++14, so we want:

  • A direct replacement to the std::rand friends. Despite of the security issues, std::rand is considered both handy and useful as a global uniform random number generator.

  • To expose the most widely-used combo in C++11 <random> without pushing the users to learn the whole design. Smoothing the learning curve can usually optimize the acceptance.that using rdtsc

Design Decisions

std::rand is a self-contained interface, so its replacement should be independent as well. In addition, I expect the interface to correctly expose the functionalities of <random> and lead to more robust and secure programs. The proposed replacement is

  • Distribution based. RNG must be used with a distribution; std::rand is a wrong design.

  • Randomly seeded before used. Improper seeding like rand(time(0)) may result in vulnerabilities.

  • Per-thread engine. Minimal interface should minimize astonishment, [with respect to] thread-safety and performance.

  • Manually seedable. User can observe repeatability in a given thread, which is a typical demand for debugging.

  • Type-safe. No integral promotion, no loss of distribution property during down-casting. For a given invocation, the inputs and the result have the same type.

Questions:

  • Do I follow the spec well? Primarily worried about 32-bit vs 64-bit issues.

  • How can I do the ugly enable_if better?

  • How can I do the ugly macros better?

  • Good way to seed? Neither rdtsc or std::random_device are very portable.

#include <cstdint>
#include <iostream>
#include <random>
#include <type_traits>

/* rdtsc
 *
 * The instruction measures the total pseudo-cycles since the processor
 * was powered on. Given the high frequency of today's machines, it's
 * extremely unlikely that two processors will return the same value
 * even if they booted at the same time and are clocked at the same
 * speed.
 */

// GCC macros (Clang also supports these)
// https://gcc.gnu.org/onlinedocs/gcc/Machine-Constraints.html
#if defined(__i386__)
    std::uint_fast32_t rdtsc(void)
    {
        std::uint_fast32_t tick;
        __asm__ __volatile__("rdtsc":"=a"(tick));
        return tick;
    }

    #define RTDSC_ENTROPY rdtsc()    
#elif defined(__x86_64__)
    std::uint_fast64_t rdtsc(void)
    {
        unsigned int tickl, tickh;
        __asm__ __volatile__("rdtsc":"=a"(tickl),"=d"(tickh));
        return ((std::uint_fast64_t)tickh << 32)|tickl;
    }

    #define RTDSC_ENTROPY rdtsc()
// MSVC (Visual C++)
#elif defined(_WIN64)
    #include <intrin.h>

    // returns 64-bit unsigned integer
    #define RTDSC_ENTROPY __rdtsc()
#endif

namespace better_rand
{

namespace detail
{
    /*
     * std::default_random_engine may default to a weak PRNG. In MSVC, it's
     * std::mt19937. In libstdc++ and libc++, it's std::minstd_rand0.
     *
     * Comparison (http://www.boost.org/doc/libs/1_59_0/doc/html/boost_random/performance.html)
     * shows that std::mt19937_64 potentially performs slower     
     */
    using random_engine = std::mt19937;

    // We only use a 64-bit seed with std::mt19937_64
    template <typename Engine = random_engine>
    typename std::enable_if<
        std::is_same<Engine, std::mt19937_64>::value,
        random_engine::result_type 
    >::type
    seed()
    {
        #if defined(RTDSC_ENTROPY)
            return RTDSC_ENTROPY;
        #else
            // std::random_device's result_type is unsigned int
            std::random_device rd;
            std::uint_fast64_t value = rd();
            value = (value << 32) | rd();
            return value;
        #endif
    }

    // 32-bit engine, 32-bit seed
    template <typename Engine = random_engine>
    typename std::enable_if<
        !std::is_same<Engine, std::mt19937_64>::value,
        random_engine::result_type 
    >::type
    seed()
    {
        #if defined(RTDSC_ENTROPY)
            return RTDSC_ENTROPY;
        #else
            // std::random_device's result_type is unsigned int
            return std::random_device(){};
        #endif
    }    

    // Global generator
    random_engine& prng()
    {
        thread_local static detail::random_engine re{detail::seed()};
        return re;
    }

    template <typename IntType>
    IntType randint(IntType a, IntType b)
    {
        // does not entirely satisfy 26.5.1.1/1(e).
        static_assert(std::is_integral<IntType>(), "not an integral");

        using distribution_type = std::uniform_int_distribution<IntType>;
        using param_type = typename distribution_type::param_type;

        thread_local static distribution_type d;
        return d(detail::prng(), param_type(a, b));
    }

    void reseed()
    {
        detail::prng().seed(detail::seed());
    }

    void reseed(detail::random_engine::result_type value)
    {
        detail::prng().seed(value);
    }
}

// Public API
using detail::randint;
using detail::reseed;

}

int main()
{
    using namespace better_rand;

    for (int i = 0; i < 10; ++i)
        std::cout << randint(1, 10) << " ";
    std::cout << "\n";

    reseed(0);
    // Should output 6 6 8 9 7 9 6 9 5 7
    for (int i = 0; i < 10; ++i)
        std::cout << randint(1, 10) << " ";
    std::cout << "\n";

    reseed();
    for (int i = 0; i < 10; ++i)
        std::cout << randint(1, 10) << " ";    
    std::cout << "\n";
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Are you referring to open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4316.html ? \$\endgroup\$
    – Martin R
    Sep 8, 2015 at 6:20
  • 1
    \$\begingroup\$ rdtsc is not portable at all (only Intel x86/x86_64 chips have it, not even Itanium). std::random_device is mandated by the standard, and even on implementations that don't provide cryto-grade random_device, they're probably better than picking from a monotonous source. \$\endgroup\$
    – Mat
    Sep 8, 2015 at 18:24

2 Answers 2

5
\$\begingroup\$

It's not clear to me why we need to downgrade from std::random_device to a timestamp-based seed on Intel platforms. If we have good reason to distrust a particular library's implementation, then submit a patch mixing timestamp into the randomness, rather than ignoring the platform's randomness.

C++17 was standardised after this code was written; it provides if constexpr to simplify the two versions of seed():

template <typename Engine = random_engine>
auto seed()
{
    std::random_device rd;
    if constexpr (std::is_same_v<Engine, std::mt19937_64>) {
        std::uint_fast64_t value = rd();
        value = (value << 32) | rd();
        return value;
    } else {
        return rd();
    }
}

The implementation here still embeds an assumption that std::random_device::max is 2³². A more portable version adapts to the actual sizes of the random device and engine, perhaps like this:

template <typename Engine = random_engine>
auto seed()
{
    using result_type = typename Engine::result_type;
    std::random_device rd;
    result_type result = 0;
    auto const step = rd.max() / 2 + 1;
    auto const start = std::numeric_limits<result_type>::max();
    for (auto needed = start;  needed;  needed = needed / 2 / step) {
        result = result * 2 * step | rd();
    }
    return result;
}

Here, needed keeps track of how much more needs to be generated, and step represents how much is added from the device in each iteration (divided by 2, to make it an exact power).


With C++20 Concepts, we can replace the static_assert in randint() with a constraint:

template <std::integral IntType>
IntType randint(IntType a, IntType b)
{

The thread-local engines could be problematic in some applications. It's important that the user be aware that reseed() applies only to the calling thread's instance, and does not affect any other.


Given that many calls would like to use the same distribution, it would be nice to have an interface that returns a combination of generator and distribution, that can be used as a source of numbers drawn (with replacement) from a single population. That seems like a useful enhancement.

\$\endgroup\$
3
\$\begingroup\$

Some things to think about: different PRNG algorithms have different trade-offs. The MT19937 algorithm is very fast, but it has a huge internal state (19937 bits to be exact, which is how it got its name). While this is a trivial amount of memory on desktop and server class CPUs, consider that on devices with less (cache) memory, this can be a significant drawback.

And related to the internal state, ideally you should use a seed sequence of at least 19937 bits to seed the std::mt19937 engine.

Finally, why have two versions of seed(), one specifically for std::mt19937, one for any other engine? That does not make sense at all.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.