为什么 mt19937 的 STD 实现有两倍大小作为升压版本?

Why do STD implementations of mt19937 have double sizeof as boost version?

提问人:NoSenseEtAl 提问时间:8/26/2020 最后编辑:NoSenseEtAl 更新时间:8/27/2020 访问量:597

问:

我有这个简单的C++程序,输出意外:

#include<random>
#include<iostream>
#include "boost/random/mersenne_twister.hpp"
#include "boost/random/uniform_int_distribution.hpp"

int main(){
    std::cout << sizeof(std::mt19937) << std::endl;
    std::cout << sizeof(std::mt19937_64) << std::endl;
    std::cout << sizeof(boost::random::mt19937) << std::endl;
    std::cout << sizeof(boost::random::mt19937_64) << std::endl;
}

叮当声和 GCC 输出

5000

2504

2504

2504

我发现有趣的是,mt19937(32 位)的标准实现大小约为升压版本的 2 倍,而 64 位则完美匹配。

由于 MT 占用了大量空间,因此差异不小。

同样奇怪的是,严格指定算法的实现会具有如此不同的大小,我们不是在谈论 std::string,实现者可能会选择不同的 SSO 缓冲区大小......

我最好的猜测是 boost 要么有一个错误,要么它实现了一些略有不同的 mt19937 版本,但维基百科是这样说的,这表明 boost 可能是对的:

相对较大的状态缓冲区,为 2.5 KiB,

编辑:Boost 和 std 版本似乎都满足第 1000 个生成值4123659995的要求,因此 boost 中似乎没有错误。

C++ 随机 升压 STD MT19937

评论

0赞 eerorika 8/26/2020
实现是什么样的?
0赞 NoSenseEtAl 8/27/2020
@eerorika丑陋:)它使用某种缓冲区,该缓冲区在许多事情上都是模板化的......github.com/llvm/llvm-project/blob/master/libcxx/include/random 搜索 624(即 mt19973 中的幻数)显然不确定我是否链接了与 godbolt 中的代码相同的代码。
0赞 François Andrieux 8/27/2020
@NoSenseEtAl 和 对于 std::mersenne_twister_engine 的特定专业化,两者都需要 s,这是您看到的模板。你会想看看。std::mt19937std::mt19937_64typedefstd::mersenne_twister_engine

答:

4赞 eerorika 8/27/2020 #1

这是标准定义:

mersenne_twister_engine<
    uint_fast32_t, // element of the buffer
    32,
    624,           // size of the buffer
    397, 31,
    0x9908b0df, 11,
    0xffffffff, 7,
    0x9d2c5680, 15,
    0xefc60000, 18, 1812433253>

问题在于 GNU 在 64 位系统上选择了 64 位类型(这是一个好选择还是坏选择是单独的讨论)。因此,如果缓冲区包含 32 位整数,则缓冲区的大小是预期的两倍。std::uint_fast32_t

这是 Boost 的定义:

mersenne_twister_engine<
    uint32_t,
    32,
    624,
    397, 31,
    0x9908b0df, 11,
    0xffffffff, 7,
    0x9d2c5680, 15,
    0xefc60000, 18, 1812433253>

这是相同的,除了使用固定宽度的元素,该元素在所有系统上始终相同。


您可以直接与元素一起使用来解决此问题。使用此别名比使用固定别名更可取,因为所有系统都需要支持此别名。std::mersenne_twister_enginestd::uint_least32_t

评论

0赞 NoSenseEtAl 8/27/2020
我看到了这个 typedef ,但我希望uint_fast32_t是 4 号......愚蠢的我:)
0赞 NoSenseEtAl 8/27/2020
老实说,这是一个错误,但如果打开,我认为它会被忽略......
0赞 eerorika 8/27/2020
@NoSenseEtAl我同意,这可以被认为是标准的缺陷。另一方面,委员会的观点可能只是GNU / Linux做出了一个愚蠢的选择。他们可能会同意,但由于向后兼容性而无法更改。
1赞 Mgetz 8/27/2020
@NoSenseEtAl取决于平台。它们是为像 Alpha AXP 这样的平台设计的,其中“快速”类型实际上是本地词,其他一切都很慢,因为它需要多个指令。Raymond Chen的博客
1赞 eerorika 8/27/2020
@NoSenseEtAl 请参阅该建议后面的句子。皮特·贝克尔(Pete Becker)在上面的评论中也(基本上)更详细地重复了一遍。