ループアンローリングが面白かった

チューニング技法入門という資料を読んでいた 。

この手の最適化は大体処理系がやってくれる場合が多くて見えにくい。 いろんな手法の最適化テクニックが紹介してあったのだけど、特にループアンローリングっていう最適化が面白かったので、そのメモ。

これを実際に試したコードをgithubにも上げてるので(こっちはGoで書いてますが)、良かったら参考にしてください

github.com

ループアンローリングの概要

以下、普通のloop処理。

for i = 0; i < 1000; i++ {
    something(i);
}

このfor文のアセンブリは以下のようになる (godboltから生成)

  movl $0, -4(%rbp)        # loop内の変数iを0に初期化
  jmp .L3                     
.L4:
  movl -4(%rbp), %eax
  movl %eax, %edi           # iを関数somethingの引数に
  call something
  addl $1, -4(%rbp)         # block内の処理を終えてiをincrement
.L3:
  cmpl $3, -4(%rbp)        # iとnを比較
  jle .L4

この際、loopの度に

• iとnの比較
• iのincrement

を行っていることがわかる( for文なので至極当たり前のことなんだけど)

この、「1回loop回す度にこれら2つの処理をいちいち実行すんのめんどくね？」ってのがループアンローリングの動機だと理解してる

じゃあどうするか

じゃあどうするか。 ループアンローリングでは、以下のようにループを展開することで、ループの度の処理を減らす。

for(int i = 0; i < 1000; i = i +10) {
         something(i);
         something(i+1);
         something(i+2);
         something(i+3);
         something(i+4);
         something(i+5);
         something(i+6);
         something(i+7);
         something(i+8);
         something(i+9);
}

この例だと、上記の繰り返しに伴う2つの処理は1/10の回数に減らせることがわかる。 なるほど...頭いい...。

どれくらい早くなるの？

雑な計測だけど、ここに一応メモしてある