寻找最佳的64位模拟PRNG

2018年8月更新：Xoroshiro128+PractRand失败非常严重。自从这篇文章发表以来，它的作者已经用xoshiro256**取代了它。它具有基本相同的性能，但具有更好的统计特性。Xoshiro256**现在是我首选的PRNG。

我经常使用伪随机数生成器(PRNG)。它们是许多算法和过程中必不可少的组成部分。

蒙特卡罗模拟，其中PRNG用于计算难以或不可能解析解决的问题的数值估计。

蒙特卡罗树搜索人工智能，其中大量的博弈随机进行，以寻找最优的走法。这是最后一项的具体应用。

遗传算法，其中PRNG创建初始种群，然后指导所选解决方案的突变和育种。

密码学，其中加密安全的PRNG(CSPRNG)产生的输出对于知道特定秘密的收件人是可预测的，但对其他任何人都是不可预测的。这篇文章只涉及普通的PRNG。

对于前三个“模拟”用途，有两个主要因素驱动PRNG的选择。这些因素可能彼此不一致：

PRNG应该非常快。应用程序应该花时间运行实际的算法，而不是生成随机数。

PRNG产出应具有稳健的统计质量。位应该看起来是独立的，并且输出应该紧密遵循所需的分布。低质量的输出会对使用它的算法产生负面影响。同样重要的还有如何使用它，但本文将只关注生成位。

在其他情况下，例如在密码学或在线赌博中，另一个重要特性是观察者无法从其输出中了解到关于PRNG内部状态的任何有意义的信息。对于我关心的三个模拟案例，这不是问题。只有速度和质量属性才重要。

根据编程语言的不同，各种标准库中的PRNG可能质量不佳。它们比需要的速度慢，或者质量比要求的差。在某些情况下，例如C中的rand()，没有指定算法，除了琐碎的示例之外，您不能依赖它。在其他情况下，算法和行为是指定的，但是您可以很容易地做得更好。

我更喜欢BYOPRNG：带上您自己的伪随机NumberGenerator。您可以在任何地方获得可靠的、相同的输出。此外，在C和C++的情况下-如果你做得正确的话-通过将PRNG嵌入到你的项目中，它将被内联和展开，使得它比缓慢地调用动态库要高效得多。

一个快速的PRNG将会很小，这使得它成为一个很好的候选前嵌入组件，比如说，头库。这就只剩下一个重要的问题了，“PRNG能不能小而有高质量的产出？”在21世纪，这个问题的答案是肯定的“是的！”

在过去的几年里，我主要去的地方是xorShift*。函数的主体是6行C，它的整个状态是一个64位整数，直接播种。然而，这里有许多选择，包括XorShift的其他变体。我怎么知道哪一个是最好的呢？唯一知道的方法是测试它，因此我的64位PRNG枪战：

当然，还有其他类似的枪战，但它们都遗漏了一些我想衡量的东西。我还想在一个非常接近我自己如何使用这些PRNG的环境中进行测试。

在详细介绍基准测试和每个生成器之前，下面是结果。这些测试在运行Linux4.9.0的i7-6700(Skylake)上运行。

速度(MB/s)故障弱GCC-6.3.0 clang-3.8.1---baseline X X 15000 13100 Bowfish cbc16 0 1 169 Blowfish cbc4 0 5725 676 Bowfish ctr16 1 3 187 184 Blowfish ctr4 1 5890 1000mt64 1 7 1700 1970pcg64 0 4 4150 3290rc4 0 5366 185spcg64 0 8 5140 4960xoroshiro128+0 8100 7720xor。

明显的赢家是xoroshiro128+，它的函数体只有7行C代码，显然是最快的，而且输出没有观察到统计故障。然而，这并不是故事的全部。与Xoroshiro128+相比，其他PRNG中的一对具有使它们更适合的优势。在下面的讨论中，我将详细介绍这些内容。

之所以选择GCC和嘎嘎这两个版本，是因为这是Debian9“伸展”中可用的最新版本。如果您想尝试不同的版本，自己构建和运行基准测试很容易。

在速度基准中，初始化PRNG，设置1秒报警(1)，然后PRNG以尽可能快的速度一遍又一遍地填充64位未签名编码器的大型易失性缓冲区，直到报警着火。写入的内存量以PRNG的速度衡量。

基线“PRNG”将零写入缓冲区。这代表了PRNG不能超过的绝对速度限制。

将缓冲区设置为易失性的目的是迫使编译器真正地“消耗”整个输出，否则编译器就会耍一些卑鄙的伎俩，让程序尽可能少地做工作。处理这个问题的另一种方法是编写(2)Buffer，但是我当然不想在基准测试中引入不必要的I/O。

在Linux上，SIGALRM在两次运行之间的一致性令人印象深刻，这意味着它非常适合这个基准测试。为了解决任何进程调度的缺陷，基准运行了8次，并且只保留了最快的时间。

SIGALRM处理程序设置一个告诉生成器停止的易失性全局变量。PRNG调用被展开8次，以避免警报检查严重影响基准。您可以通过在代码中将Unroll更改为1(即“do‘tunroll”)来亲自查看效果。展开超过8次对我的测试没有明显的影响。

由于PRNG是内联的，这种展开使无基准成为现实，并在结果中显示出来。使用Volatile作为缓冲区有助于抵消这种影响并重新计算结果。这是一个模糊的问题，实际上没有任何方法可以避免它，但我也将在下面讨论这个问题。

为了测量每个PRNG的统计质量-主要是作为健全性检查-原始二进制输出通过DieHard 3.31.1运行：

这种统计分析没有时序特征，结果在任何地方都应该是相同的。您只需重新调整单元，即可使用不同版本的DieHard或不同的分析工具进行测试。

没有多少信息可以从这部分枪战中收集到，但大部分都证实了所有这些PRNG都可以很好地用于模拟目的。疲软的结果并不是非常重要，只对打破关系有用。即使是真正的RNG也会得到一些WEAK结果。例如，在我的测试中，x86RDRAND指令(没有包含在实际的枪战中)得到了7个弱结果。

失败的结果更重要，但一次失败并不意味着什么。没有故障的PRNG应该优先于其他相等的有故障的PRNG。

诚然，“64位PRNG”的定义相当模糊。我的高性能目标都是64位平台，所以最高的PRNG吞吐量将构建在64位操作上(如果不是更广的话)。最初的计划是专注于从64位操作构建的PRNG。

好奇心让我不知所措，所以我加入了一些不使用任何64位操作的PRNG。我只想看看它们是怎么堆积起来的。

我编写Blowfish实现的原因之一是评估其性能和统计质量，因此我很自然地将其包括在基准测试中。它只使用32位加法和32位XOR。它有一个64位的块大小，所以它自然会产生一个64位的整数。在基准测试中，有两个不同的属性组合成四个变量：轮数和块模式。

河豚通常使用16发子弹。这使得它比非加密PRNG慢得多，但给了它一个安全裕度。我不在乎安全边际，所以我加了一个4轮变种。不出所料，它的速度大约快了四倍。

我测试的另一个功能是块模式：密码块链接(CBC)与计数器(CTR)模式。在CBC模式下，它将零加密为明文。这仅仅意味着它在加密其最后一次输出。密文是PRNG的输出。

在CTR模式下，PRNG正在加密一个64位计数器。它比16轮的CBC快11%，比4轮的快23%，原因很简单，部分原因是在基准测试中展开生成循环。

在CBC模式下，每个输出都依赖于前一个输出，但在CTR模式下，所有块都是独立的。在前一次输出完成之前，可以开始下一次输出的工作。X86体系结构使用无序执行来实现许多性能收益：指令的执行顺序可能与它们在程序中出现的顺序不同，尽管它们的可观察效果通常必须正确排序。打破指令之间的依赖关系允许完全执行无序执行。它还在指令调度中给予编译器更大的自由度，尽管不能将易失性访问彼此重新排序(因此可以帮助重新循环基准)。

从统计上看，4轮密码并不比16轮密码差多少。尽管Xoroshiro128+在不牺牲质量的情况下仍然比Xoroshiro128+快9倍以上，但出于模拟目的，4轮密码已经完全足够了。

另一方面，CTR模式在4轮(Dab_Fultree2)和16轮(Dab_Fultree)变体中都有一个故障。至少对于Blowfish来说，有没有什么东西让CTR模式比CBCmode更不适合作为PRNG呢？

最后，Blowfish速度太慢，太复杂，不能作为模拟PRNG。这完全是意料之中的，但看看它是如何堆叠起来的，这是很有趣的。

从来没有人因为选择梅森·特维斯特而被解雇。这是模拟的经典选择，至今仍被推荐使用。然而，Mersenne Twister最好的日子已经过去了。我测试了64位变体MT19937-64，有四个问题：

它有一个很大的状态：2500字节。与Xoroshiro128+的16字节相比。

奇怪的是，我用Clang实现的速度比用GCC快16%。因为梅森·特维斯特并不是认真的参选，所以我没有花时间去挖掘其中的原因。

“置换一致生成器”(PCG)背后有一些非常有趣的历史，特别是它的论文有些不同寻常，因为篇幅过长(58页)和非正式风格而有争议。它与XorShift和Xoroshiro128+竞争激烈。我真的很想看看它是如何堆积起来的。

PCG实际上只是一个线性同余发生器(LCG)，它不输出最低的比特(质量太差)，并且有一个置换步骤来弥补LCG的其他弱点。我在我的基准测试中包含了两个变体：官方PCG和带有简单排列步骤的“简化”PCG(SPCG)。SPCG只是论文中介绍的第一个PCG(34页！)。

Uint32_t spcg32(uint64_t s[1]){uint64_t m=0x9b60933458e17d7d；uint64_t a=0xd737232eeccdf7ed；*s=*s*m+a；int shift=29-(*s>；>；61)；return*s>；>；Shift；}。

带有模乘和加法的第三行是LCG。位移位是排列。此PCG使用结果的最高有效三位来确定输出哪32位。这是PCG的新奇组成部分。

这两个常量完全是我自己设计的。它是使用Emacs的M-x calc生成的两个64位Prime：264^k r k n k k p p k p。

见鬼，这太简单了，我可以很容易地记住它，并根据需要从头开始编码。要点：这是PCG在某种情况下比Xoroshiro128+更好的一种方式。在紧要关头，我可以使用Emacst生成几个素数，然后根据内存编写其余的代码。如果你参加编码比赛，请注意。

不过，您可能也注意到，尽管PCG使用64位运算，但它只生成32位整数。要正确生成64位的值，我们需要128位的操作，这需要在软件中实现。

取而代之的是，我加倍运行两个PRNG，尽管州大小增加了一倍，但是由于PRNG之间没有交互，所以周期不会变得更长。尽管如此，我们还是得到了一些回报。还记得我说过的无序执行吗？除了最后一步合并他们的结果，因为两个PRG是独立的，加倍不应该完全减半性能，特别是在基准循环展开业务的情况下。

Uint64_t spcg64(uint64_t s[2]){uint64_t m=0x9b60933458e17d7d；uint64_t a0=0xd737232eeccdf7ed；uint64_t a1=0x8b260b70b8e98891；uint64_t p0=s[0]；uint64_t p1=s[1]；s[0]=p。61)；uint64_t HIGH=P0>；>；R0；uint32_t Low=p1>；>；R1；RETURN(HIGH<；<；32)|Low；}。

“全”盈科比“简化”盈科慢了25%(GCC)到50%(砰砰)，但它确实将WEAK结果减半。

在这种64位形式中，两者都比xoroshiro128+慢得多。但是，如果您发现自己一次只需要32位(总是丢弃64位PRNG中的高32位)，32位PCG比使用xoroshiro128+并丢弃一半的输出要快得多。

这是另一个CSPRNG，我很好奇它是如何堆叠起来的。它只使用8位运算，并且每次生成一个字节的64位整数。它是在16轮河豚之后最慢的，通常作为模拟PRNG没有用处。

在这个基准测试中，xoroshiro128+显然是赢家，而且它似乎是可用的最好的64位模拟PRNG。如果您需要快速、高质量的PRNG，只需将以下11行代码放入C或C++程序：

Uint64_t xoroshiro128plus(uint64_t s[2]){uint64_t s0=s[0]；uint64_t s1=s[1]；uint64_t result=s0+s1；s1^=s0；s[0]=((s0<；<；<；9))^s1^(s1<；<；14)；s[。36)|(S1&>；>；28)；返回结果；}

有一个重要的警告：16字节的状态必须是种子良好的。拥有大量零字节将导致糟糕的初始输出，直到生成器将其全部混合。全部为零字节将完全破坏生成器。比方说，如果你要从unix时代开始播种，那么就用16个静态随机字节进行异或运算。

这些生成器是密切相关的，就像我说的，xorShift 64*是我多年来一直使用的。看起来是时候让它退役了。

Uint64_t xorshit64star(uint64_t s[1]){uint64_t x=s[0]；x^=x>；>；12；x^=x<；<；25；x^=x>；>；27；s[0]=x；return x*UINT64_C(0x2545f4914f6cdd1d)；}。

然而，与xoroshiro128+和xorshit128+不同的是，xorshit64*可以容忍弱种子，只要它不是字面上的零。零也会破坏这台发电机。

如果不是Xoroshiro128+，那么XorShift 128+将是基准测试的获胜者，也是我最喜欢的新选择。

Uint64_t xorshift t128plus(uint64_t s[2]){uint64_t x=s[0]；uint64_t y=s[1]；s[0]=y；x^=x<；<；23；s[1]=x^y^(x>；>；17)^(y>；>；26)；return s[1]+y；}。

这很像Xoroshiro128+，包括需要播好种子，但它的速度太慢了，以至于会输掉比赛。没有理由使用xororShift 128+而不是xoroshiro128+。

不过，不同平台之间的情况可能会发生重大变化。这是一架ARM Cortex-A53的枪击画面：

速度(MB/s)GCC-5.4.0 clang-3.8.0--baseline 2560 2400 blowfish cbc16 36.5 45.4 blowfish cbc4 135 173 blowfish ctr16 36.4 45.2 blowfish ctr4 133 168mt64 207 254 pcg64980 712rc4 96.6 44.0spcg64 1021 948xoroshiro128+2560 1570xort128+2560 1520xorShift 64*13601080。

LLVM在这个平台上还不是很成熟，但是有了GCC，xoroshiro128+和xorShift 128+都达到了基线！看来记忆才是瓶颈。

所以不一定要相信我的话。你可以在你自己的环境中进行这场枪战-也许甚至可以扔进更多的PRNG-来找出适合你自己的情况。

对这篇文章有什么评论吗？通过发送电子邮件至~Skeeto/[email protected][邮件列表礼仪]开始我的公共收件箱中的讨论，或查看现有讨论。