AVX/SSE版本的xorshift128+

Question

我正在尝试制作最快速度、高质量的随机数生成器。阅读了http://xorshift.di.unimi.it/后，发现xorshift128+是一个不错的选择。其C代码如下：

#include <stdint.h>
uint64_t s[ 2 ];

uint64_t next(void) { 
    uint64_t s1 = s[ 0 ];
    const uint64_t s0 = s[ 1 ];
    s[ 0 ] = s0;
    s1 ^= s1 << 23; // a
    return ( s[ 1 ] = ( s1 ^ s0 ^ ( s1 >> 17 ) ^ ( s0 >> 26 ) ) ) + s0; // b, c
}

可惜我不是SSE/AVX专家，但我的CPU支持SSE4.1 / SSE4.2 / AVX / F16C / FMA3 / XOP指令。如果你想加速此代码（假设你要生成数十亿个随机数），你该如何利用这些指令，并在实践中期望速度提升的限制是什么？

- Simd

Answer 1

对于其他可能遇到这个问题的人，我认为以下这段C++代码正确地实现了4个xorshift128plus生成器并行运行，使用了AVX2：

__m256i xorshift128plus_avx2(__m256i &state0, __m256i &state1)
{
    __m256i s1 = state0;
    const __m256i s0 = state1;
    state0 = s0;
    s1 = _mm256_xor_si256(s1, _mm256_slli_epi64(s1, 23));
    state1 = _mm256_xor_si256(_mm256_xor_si256(_mm256_xor_si256(s1, s0),
                                               _mm256_srli_epi64(s1, 18)),
                              _mm256_srli_epi64(s0, 5));
    return _mm256_add_epi64(state1, s0);
}

我使用的标量实现如下：

u64 xorshift128plus(u64 &state0, u64 &state1)
{
    u64 s1 = state0;
    const u64 s0 = state1;
    state0 = s0;
    s1 ^= s1 << 23;                              // a
    state1 = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5); // b, c
    return state1 + s0;
}

这是xorshiftplus论文中相同的内容。请注意，原问题中的右移常量与论文中的不一致。

- o9000

---

如果编译器不知道_mm256_xor是可结合的，你可以使用不同的操作顺序来获得更多指令级并行性。 s1 ^ s0可以与移位同时运行，但我误读了，实际上s1 ^ s0在最内部嵌套中。我发现将大量内嵌的指令写成单个表达式难以阅读，最好为临时变量命名具有描述性的名称以提高可读性。因此，这里的gcc生成了良好的代码。 - Peter Cordes

确实，我指望编译器能够解决这个问题。顺便说一句，那个网站真是个宝藏！已经加入书签了。 - o9000

问题中的常量是维基百科上的内容，并且是论文中某个表格的第一项。我不知道哪些常量是最好的选择，但目前在http://xoroshiro.di.unimi.it/xorshift128plus.c中发布的常量与此匹配，而不是维基百科上的常量。 - Peter Cordes

Answer 2

XorShift确实是一个不错的选择。它非常好、非常快，所需状态很少，我很惊讶为什么使用它的人这么少。它应该成为所有平台上的标准生成器。我8年前自己实现了它，即使那时它也可以生成每秒800MB的随机字节。

你不能使用向量指令来加速生成单个随机数。这些指令中的指令级并行性太小了。

但是你可以轻松地加速生成N个数字，其中N是你的目标指令集的向量大小。只需要并行运行N个生成器。为N个生成器保留状态，并同时生成N个数字。

如果客户端代码要求逐个返回数字，则可以保留N（或更多）数字的缓冲区。如果缓冲区为空，则使用向量指令填充它。如果缓冲区不为空，则只需返回下一个数字。

- usr

---

我认为xorshift本身并不好。然而，这个“plus”版本是我感兴趣的。 - Simd

我真的在寻找一些关于AVX/SSE代码或者有关我的代码可能提速多少的具体信息。 - Simd

你可以使用SSE并行运行两个这样的发生器 - 当然，你需要以不同的种子来初始化它们，否则它们只会为每个生成相同的值。使用_mm_srli_epi64进行右移，使用_mm_xor_si128进行异或，使用_mm_add_epi64进行加法运算。 - Paul R

很遗憾，AVX中没有相应的操作 - 您需要AVX2，它在Haswell及更高版本上可用 - 这将使您能够并行运行4个64位RNG而不是2个。 - Paul R

实际上，AVX1仍然可以为128b实现节省movdqa复制指令。因此，代码会稍微小一些，而且可能会运行得更快，因为xorshift+受益于非破坏性移位操作，这些操作会保留原始值。 - Peter Cordes