【C++】std::random_deviceは遅い？乱数生成器の速度を比較してみた

C++において，乱数といえば<random>ヘッダを使用して乱数生成をするのが一般的です．

乱数は，「真の乱数」と「疑似乱数」に分類されます．

「真の乱数」は真のランダムな数のため，乱数としての信頼性は高く，再現性はありません．

一方で，「疑似乱数」は再現性のある乱数列であり，厳密に乱数ではありません．しかし，ほとんどの場合実質的に乱数として扱えます．

疑似乱数にはさまざまなアルゴリズムが存在しますが，真の乱数ではなく疑似乱数を使用する主な利点は，「高速性」，「再現性」，「省メモリ」です．

この記事では，C++における乱数生成の”速度”に関して着目しています．

いくつかの疑似乱数生成アルゴリズムと真の乱数生成を比較して，実際にどの程度高速なのかを検証してみました．

>> Optimized C++ ―最適化、高速化のためのプログラミングテクニック

検証内容

検証する乱数生成器は，std::rand()と<random>ヘッダに存在するアルゴリズムであり，下記のものです．

動作環境は，

• Debian on Docker
• GCCバージョン：g++ (Debian 8.3.0-6) 8.3.0
• CPU：AMD Ryzen Threadripper 2950X

速度比較結果

Google Benchmarkを利用して速度検証を行っています．

最適化なし

まずは最適化なし（-O0オプション）で検証しました．

真の乱数生成器（std::random_device）の計算時間は1188 nsです．

疑似乱数生成はranlux24とranlux48を除き，概ね10から20 nsの間です．

疑似乱数と比較して，真の乱数は約100倍程度遅いことが分かりました．真の乱数が低速であることは当然ですが，100倍という数値は結構な差がありますね．

また，疑似乱数アルゴリズム間の比較では，ranlux24とranlux48が明らかに低速でした．

std::rand()は高速ですが，そもそも非推奨ですのであまり意味がない結果です．

最適化あり

次に最適化あり（-O2オプション）の場合を比較しました．

最適化を行うと，いくつかの乱数生成で経過時間が0.0 nsとなり計測できないほどの極めて微小な時間となりました．

真の乱数生成（random_device）は最適化による高速化の恩恵を受けておらず，依然として低速な結果となりました．ハードウェア情報から生成しているため，最適化がないのは納得できます．

まとめ

このことから，一般的によく使用されている疑似乱数生成器であるメルセンヌ・ツイスタ（mt19937とmt19937_64）やその他の高速なアルゴリズム（minstd_rand0, mnistd_rand, knuth_b）を使用すると良いと思います．

注意点として，疑似乱数生成は極めて高速ですが，シード値の生成はrandom_deviceを使用しており，この部分が低速になります．シード値生成を頻繁に行わないことを意識する必要があります．

検証コード

Google Benchmarkを用いて検証を行いました．使用したコード下記のものです．

#include <benchmark/benchmark.h>

#include <cstdlib>
#include <random>

static void rand(benchmark::State& state)
{
    for (auto _ : state)
    {
        std::rand();
    }
}
BENCHMARK(rand);

static void random_device(benchmark::State& state)
{
    std::random_device rng;
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(random_device);

static void minstd_rand0(benchmark::State& state)
{
    std::random_device seed;
    std::minstd_rand0 rng(seed());
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(minstd_rand0);

static void minstd_rand(benchmark::State& state)
{
    std::random_device seed;
    std::minstd_rand rng(seed());
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(minstd_rand);

static void ranlux24_base(benchmark::State& state)
{
    std::random_device seed;
    std::ranlux24_base rng(seed());
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(ranlux24_base);

static void ranlux48_base(benchmark::State& state)
{
    std::random_device seed;
    std::ranlux48_base rng(seed());
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(ranlux48_base);

static void ranlux24(benchmark::State& state)
{
    std::random_device seed;
    std::ranlux24 rng(seed());
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(ranlux24);

static void ranlux48(benchmark::State& state)
{
    std::random_device seed;
    std::ranlux48 rng(seed());
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(ranlux48);

static void knuth_b(benchmark::State& state)
{
    std::random_device seed;
    std::knuth_b rng(seed());
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(knuth_b);

static void mt19937(benchmark::State& state)
{
    std::random_device seed;
    std::mt19937 rng(seed());
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(mt19937);

static void mt19937_64(benchmark::State& state)
{
    std::random_device seed;
    std::mt19937_64 rng(seed());
    for (auto _ : state)
    {
        rng();
    }
}
BENCHMARK(mt19937_64);

BENCHMARK_MAIN();