手臂装配的PRNG？

Question

我在为ARM大会执行PRNG时遇到了问题。我尝试了一些算法，在工作的同时，在最初的几次随机数迭代之后，最终花费了很长的时间，这可能是因为除法(模)步骤对大数需要很长的时间。我试着得到0到31之间的随机数。我在下面做了一些粗略的工作，用字母代替了特定的寄存器。

开始：

mov t, x            // t = x

// t ^= t << 11
lsl temp, t, #11
eor t, temp

// t ^= t >> 8
lsr temp, t, #8
eor t, temp

// z = w
mov z, w

// x = y
mov x, y

// y = z
mov y, z

// w ^= w >> 19
lsr temp, w, #19
eor w, temp

// w ^= t
eor w, t

// result is the RETURNED RANDOM NUMBER
mov result, w

这就是我试图从维基百科的XORSHIFT页面实现的算法。我只需要这个来返回一个从0到31的随机数，所以在一个10位数的数字上实现除法需要一段时间，而且看起来很过火。如果有人能帮我优化或者指出一个错误，我会很感激的。

编辑:上面的子例程返回随机数，然后我基本上把它除以31 (这里没有给出代码)，并把剩余的作为我的“随机”数从0到31。

Answer 1

ARM指令可以动态地移动甚至旋转它们的输入，所以使用分开的左移位指令是一种浪费.显然是在拇指模式下，只有32位的拇指指令才能使用桶形移位器。。

请注意，如果您的例程是实际调用的函数，而不仅仅是循环中的内联片段，那么它就不遵循标准的ABI。如果唯一的调用者也是由您在asm中编写的，这是很好的。如果您可以将4个寄存器专用于循环中的PRNG状态，则不需要传递指针或加载/存储。

和往常一样，编译器输出通常是一个很好的起点：

// we need a loop to see how many mov instructions are actually needed when keeping state in regs
// Otherwise we just get loads/stores
uint32_t xorshift_loop(uint32_t *output, uint32_t x, uint32_t y, uint32_t z, uint32_t w) {
  for(int i=0 ; i<1000 ; ++i) {
    uint32_t t = x;
    t ^= t << 11;
    t ^= t >> 8;
    x = y; y = z; z = w;
    w ^= w >> 19;
    w ^= t;
    *(++output) = w;
  }
  return w;
}

内环是：

## 32bit ARM gcc 4.8  -O3 -fverbose-asm
## The @comments are from -fverbose-asm, which is more helpful than usual here
.L4:
        eor     r6, r1, r1, lsl #11       @, t, x, x,
        eor     r5, r4, r4, lsr #19       @, w, w, w,
        eors    r5, r5, r6                @, t, w, t
        mov     r1, r2                    @ x, y
        eor     r5, r5, r6, lsr #8        @, w, t, t,
        str     r5, [r0, #4]!     @ w, MEM[base: _42, offset: 4B]  // this is a post-increment store
        cmp     r0, r7    @ ivtmp.20, D.4237
        mov     r2, r3    @ y, z
        mov     r3, r4    @ z, w
        mov     r4, r5    @ w, w
        bne     .L4       @,

注意XOR是如何被重新排序的，所以第一对指令是分开的dep链的一部分。这将有助于超标量有序ARM核，或者如果移动操作数的eor的延迟大于1，它也选择做w^=t; w^= t>>8而不是t^= t>>8; w^=t;，但是如果有什么特别的优势的话。

展开两次就可以去掉所有的mov指令，让每次迭代只执行四个eor指令，每个结果都有移位的输入。看起来gcc用-funroll-loops 8展开，所以代码很难理解。

很明显质量很好为了这么快的东西。

它在AArch64上编译成短代码，在32位ARM上仍然是短/高效的代码。但是，不仅仅是xorshift，还有更多的代码。请参阅上面的“我的霹雳编译器资源管理器”链接。