プログラムの実行時間の多くはループ処理と言われていて、

このループ処理を如何に短くすることがプログラムの高速化に繋がると言えます。

ループ処理というのは、

for(;;){

}

while(){

}

で表されますが、

アセンブリで言うと、判定処理とジャンプ命令で表現することができ、

このジャンプ命令がパイプライン上のストールを発生させて速度の遅延が発生します 。

 

そこで今回はループアンローリングという手法について紹介したいと思います。

日本語ではループ展開ともいいます。

for(i=0;i<5;i++){

sum  = sum * i;

}

という処理があった場合、ループを展開すると

sum = sum + i;

sum = sum + (i+1);

sum = sum + (i+2);

sum = sum + (i+3);

sum = sum + (i+4);

と書くことで判定処理はジャンプ命令がなくなるため高速化が期待できます。(理論上)

もちろん、この程度では速くなるとは限らず、遅くなることもありえますので注意が必要です。

 

実際に速くなる例を見せたいと思います。
<pre>for (i = 0; i &lt; loop; i++)
{
for (j = 0; j &lt; loop; j++)
{
sum += i * j;
}
}
</pre>
このループを5段のループ展開すると
<pre>for (i = 0; i &lt; loop; i++)
{
for (j = 0; j &lt; loop / 5; j++)
{
sum += i * j;
sum += i * (j + 1);
sum += i * (j + 2);
sum += i * (j + 3);
sum += i * (j + 4);
}
}
</pre>
&nbsp;

更に10段で展開すると
<pre>for (i = 0; i &lt; loop; i++)
{
for (j = 0; j &lt; loop / 10; j++)
{
sum += i * j;
sum += i * (j + 1);
sum += i * (j + 2);
sum += i * (j + 3);
sum += i * (j + 4);
sum += i * (j + 5);
sum += i * (j + 6);
sum += i * (j + 7);
sum += i * (j + 8);
sum += i * (j + 9);
}
}
</pre>
となります。

これを実際に実行すると(変数:loopは50000)

<img class=”alignnone size-medium wp-image-2209″ src=”https://www.aag.co.jp/wp-content/uploads/2016/08/2016-08-07-300×198.png” alt=”処理結果” width=”300″ height=”198″ />

確かに1秒以上速くなっていることが確認できました。

5段と10段の差があまりないのは

ループ展開をしたのが2重目のループのみだからだと思われます。

&nbsp;

このようにループの回数が多くなるほど

ループアンローリングによる高速化の期待は高くなります。

&nbsp;

しかし、今回行ったループ回数ような10万、100万回のループは科学技術計算の分野では

よくある回数ではあるのですが、

弊社のシステム事業のメインであるWEBでの開発ではこのレベルのループ回数は珍しく

このようなループ回数のループは今まで出会ったことがないです。

&nbsp;

もちろん、使えそうな機会に出くわしても

ソースの可読性や保守性なども考えないといけないので、

独断で使うのは控えた方がいいと思います。

もし、業務で勝手にループアンローリングを使ってきたら怒りますね。

&nbsp;

まぁこう言った意味で、

実践では使いにくい高速化手法ですね。