c++ - 关于 C++ 上的随机数生成 dSFMT 性能

Question

我正在尝试找到最有效的方法来为我正在处理的 MC 模拟生成随机数。我已经阅读了很多关于 double Mersenne Twister 算法的文章，我想在继续之前了解一些基本知识。

我编译并运行了官方 dSFMT 文件提供的测试，这是我系统的最佳结果:

C:\TDM-GCC-64\C++ Tests\dSFMT>test-sse2-M19937 -s
consumed time for generating 100000000 randoms.
ST BLOCK [0, 1) AVE: 115ms.
ST BLOCK (0, 1] AVE: 108ms.
ST BLOCK (0, 1) AVE: 106ms.
ST BLOCK [1, 2) AVE:  77ms.
ST SEQ [0, 1) 1 AVE: 174ms.
ST SEQ [0, 1) 2 AVE: 207ms.
total = 500014655.815776
ST SEQ (0, 1] 1 AVE: 173ms.
ST SEQ (0, 1] 2 AVE: 205ms.
total = 500035344.184224
ST SEQ (0, 1) 1 AVE: 209ms.
ST SEQ (0, 1) 2 AVE: 247ms.
total = 500014655.815776
ST SEQ [1, 2) 1 AVE: 173ms.
ST SEQ [1, 2) 2 AVE: 204ms.
total = 1500064655.815183

我的问题是:

1. 为什么生成 [1,2) 比 [0,1) 快？
2. 为什么 block 生成比顺序生成更快？分配一个大数组并删除和重写它不应该更慢吗？
3. 如果我需要生成 1e12 个数字，最好的策略是什么？如果分块进行，最佳数组大小是多少？

Answer 1

库中的数字是从 [1,2) 区间生成的。其他范围表示为在此区间之上的函数。

“基本”区间 [1,2) 生成器:

inline static double dsfmt_genrand_close1_open2(dsfmt_t *dsfmt) {
    double r;
    double *psfmt64 = &dsfmt->status[0].d[0];

    if (dsfmt->idx >= DSFMT_N64) {
        dsfmt_gen_rand_all(dsfmt);
        dsfmt->idx = 0;
    }
    r = psfmt64[dsfmt->idx++];
    return r;
}

区间 [0, 1]:

inline static double dsfmt_genrand_close_open(dsfmt_t *dsfmt) {
    return dsfmt_genrand_close1_open2(dsfmt) - 1.0;
}

block 生成可以更快，原因有很多，包括缓存局部性、更少的函数调用、循环展开等。在实践中， block 操作通常比单个操作组合起来更快。

在这种特殊情况下， block 生成也更快，因为数字是成对生成的(W128_T 类型):

union W128_T {
    __m128i si;
    __m128d sd;
    uint64_t u[2];
    uint32_t u32[4];
    double d[2];
};

block 版本利用此属性，并将两个数字从 W128_T 复制到结果数组中。顺序版本仅使用第一个数字并丢弃第二个。

至于你的第三个问题，使用 block 生成，因为它被证明在你的计算机上更快。你每 100 毫秒有 1e8 个数字，所以对于 1e12 你需要大约二十分钟。如果您觉得合适，那么只需使用 NUM_RANDS block 大小，对于任何合理的 block 大小应该没有太大差异。否则，请考虑在多个线程中从独立生成器生成数字。