ARMアセンブリの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の命令can shift or even rotate their inputs on the flyでは、別々の左シフト命令を使用するのは無駄です。明らかにin Thumb mode, only 32bit thumb instructions can use the barrel shifter。

ループが実際に呼び出す関数であれば、ループからのインラインスニペットではなく、標準ABIに従わないことに注意してください。唯一の呼び出し元がasmであなたによっても書かれているなら、それは問題ありません。あなたのループ内で4つのレジスタをPRNGステートにすることができれば、ポインタを渡すか、ロード/ストアする必要はありません。

いつものように、compiler outputはしばしば良い出発点である：

// 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; 
} 

内部ループは次のとおりです。最初のカップルの命令は別々のDEPの一部であるので、XOR演算の順序が変更されている方法を

## 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  @, 

お知らせ鎖。これは、スーパスカラインオーダーARMコアの場合、またはシフトされたオペランドを持つeorが1より大きいレイテンシを持つ場合に役立ちます。また、t^= t>>8; w^=t;の代わりにw^=t; w^= t>>8を実行しますが、特に有利な場合はIDKを選択します。

2をアンロールすると、すべてのmov命令が取り除かれ、結果ごとに入力がシフトされたeor命令が4回だけ実行されます。 -funroll-loopsでgccが展開されているように見えるので、コードを実行するのは難しいです。

---

xorshift+ is apparently pretty good quality非常に高速です。

これは、AArch64のショートコードと32ビットARMのショート/効率的なコードにコンパイルされます。しかし、ちょうどxorshiftよりもずっと多くのコード。私のgodboltコンパイラエクスプローラのリンクを参照してください。