What are the advantages of using uniform_int_distribution vs a modulus operation?

Question

According to following results, generating uniform random integers between two numbers using % operation is almost 3 times faster than using std::uniform_int_distribution: Is there any good reason to use std::uniform_int_distribution?

Code:

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
#include <random>

#include <cstdio>
#include <cstdlib>

using namespace std;

#define N 100000000

int main()
{

clock_t tic,toc;

for(int trials=0; trials<3; trials++)
{
    cout<<"trial: "<<trials<<endl;

    // uniform_int_distribution
    {
        int res = 0;
        mt19937 gen(1);
        uniform_int_distribution<int> dist(0,999);

        tic = clock();
        for(int i=0; i<N; i++)
        {
            int r = dist(gen);
            res += r;
            res %= 1000;
        }
        toc = clock();
        cout << "uniform_int_distribution: "<<(float)(toc-tic)/CLOCKS_PER_SEC << endl;
        cout<<res<<" "<<endl;

    }

    // simple modulus operation
    {
        int res = 0;
        mt19937 gen(1);

        tic = clock();
        for(int i=0; i<N; i++)
        {
            int r = gen()%1000;
            res += r;
            res %= 1000;
        }
        toc = clock();
        cout << "simple modulus operation: "<<(float)(toc-tic)/CLOCKS_PER_SEC << endl;
        cout<<res<<" "<<endl;

    }

    cout<<endl;
}

}

Output:

trial: 0
uniform_int_distribution: 2.90289
538 
simple modulus operation: 1.0232
575 

trial: 1
uniform_int_distribution: 2.86416
538 
simple modulus operation: 1.01866
575 

trial: 2
uniform_int_distribution: 2.94309
538 
simple modulus operation: 1.01809
575

`std::uniform_int_distribution` is able to generate a uniform distribution between any integer interval, while `%` cannot. — Lingxi, Sep 30 '15 at 07:55
It's quite easy to write fast code if you don't have to do it right. — T.C., Sep 30 '15 at 07:55
https://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful — T.C., Sep 30 '15 at 08:04
Aside: I would try it without the `res %= 1000;` line. I can imagine a couple ways it would screw up your test. — , Sep 30 '15 at 11:31

score 43 · Accepted Answer · edited Sep 30 '15 at 10:33

43

You will get statistical bias when you use modulo (%) to map the range of e.g. rand() to another interval.

E.g suppose rand() maps uniformly (without bias) to [0, 32767] and you want to map to [0,4] doing rand() % 5. Then the values 0, 1, and 2 will on average be produced 6554 out of 32768 times, but the values 3 and 4 only 6553 times (so that 3 * 6554 + 2 * 6553 = 32768).

The bias is small (0.01%) but depending on your application that could prove fatal. Watch Stephan T. Lavavej's talk "rand() considered harmful" for more details.

edited Sep 30 '15 at 10:33

Angew is no longer proud of SO

167,307
17
350
455

answered Sep 30 '15 at 08:01

TemplateRex

69,038
19
164
304

2

To be fair, a corollary is that if the modulus is a constant power of two, then `%` rsp. `&` may be much faster than `uniform_int_distribution`, and no bias is introduced on the usual implementations. – Arne Vogel Sep 30 '15 at 12:18
1

@ArneVogel true, but only if RAND_MAX is also a power of 2. This value is implementation dependent. It's guaranteed that this value is at least 32767. For portable code and general interfaces, just use `uniform_int_distribution`. – TemplateRex Sep 30 '15 at 12:27
@ArneVogel That looks like a QOI issue, no? But, if you have a random number with X bits of entropy that is Y bits wide with the entropy spread uniformly, if you extract the lower Z bits, you end up with X * Z/Y bits of entropy. If you instead munge all Y bits into your result (a simple shift-xor system), your output can still have up to X bits of entropy (assuming X <= Z). – Yakk - Adam Nevraumont Sep 30 '15 at 13:39
1

@Yakk if your random number generator returns one of M numbers, 100% randomly, and you need one of N numbers, then unless M is divisible by N _any_ operation that accepts _each_ of the M original numbers and maps it to one of N numbers will be biased. You need to calculate M' which is a multiple of N, map any of those M' numbers to one of the N numbers, and if another number is picked then reject it and pick another one (or use more complicated methods). – gnasher729 Sep 30 '15 at 14:11
3

@gnasher729 If you walk outside on a clear day at noon with no cloud cover, the sky is blue. There is no way for the sky to be a pale pink with green stripes. (In short, what are you talking about? Your syntax looks like you are responding to my comment, but you are at best talking about something tangential to what I'm talking about, and doing so as if you are disagreeing with me? I was addressing ArneVogel's implied position that `%` might be a good idea if the source random data range and the modulus are both a power of two. That is what the `@arnevogel` means. Look at Arne's comment) – Yakk - Adam Nevraumont Sep 30 '15 at 14:17
@Yakk: It's not QoI because `uniform_int_distribution` doesn't know the output range at compile time. Of course it's possible to make a version where the range is given as template parameters, but there's none in the standard. Or the compiler may optimize well if the calls are inline and it's a local object. There isn't much entropy in a PRNG such as `mt19937` used in the question, but the standard guarantees uniform distribution over the range of its `result_type`, and that is enough here, for the *usual implementations* with binary integer types. If not -> GIGO principle – Arne Vogel Sep 30 '15 at 14:50
@ArneVogel Well, if the range is a power of 2, the uniform int distribution can use raw `%` or `&`, detected at run time. Detecting that is cheap (once per distribution creation), the branch (or other dispatch) might have modest cost (highly predictable, so few branch failures). Are you worried about that branch prediction cost, or figure people won't optimize for that case? ... And no, discarding most of the bits of a random value to get a smaller range is not a GIGO issue. That is a GPGO (Garbage Processing Garbage Out) issue. – Yakk - Adam Nevraumont Sep 30 '15 at 15:05
@Yakk: The branch may not be expensive, but IIRC the throughput of `AND` on recent Intel Cores (e.g.) is 3, which means an average of 3 instructions per clock. Compared to that, any branching is *relatively* expensive. I understand your discomfort with discarding bits but `mt19937` is supposed to work hard to ensure uniform output, and any distribution function that maps a larger to a smaller int range has necessarily collisions due to the pigeonhole principle, though mostly less obvious than for `%`. Since the MT is not crypto-safe anyway, I'd choose the former for this specific PRNG. – Arne Vogel Sep 30 '15 at 19:23
@ArneVogel There are several non-power-of-two PRNGs in the standard (IIRC, the two `minstd_rand`s and `knuth_b`). GCC's `default_random_engine` uses one of them (`minstd_rand0`). – T.C. Oct 02 '15 at 01:56

What are the advantages of using uniform_int_distribution vs a modulus operation?

1 Answers1

Linked