プログラマーの理想と現実

第11回 小手先チューニング — ループの高速化

2015.06.10 (2015.06.24更新)

この記事は、『UNIX Magazine』2004年11月号(2004年10月18日発売)に掲載された同名記事の初稿(著者から編集部に提出したもの)を元に、Web掲載用に一部を修正したものです。10年以上前に執筆したものなので、現在のUNIXを取り巻く環境とは色々と異なることがありますが、プログラミングに対する心構えとしては現在でも通用するものと思い、再掲してみることにしました。

・・・・・・・・・・

プログラム開発の現場では、動作速度をもう少し速くしないとまずい、という状況に遭遇することがある。プログラムの全体的な動作が緩慢で利用者から不満が出たということもあるだろうし、一部の処理が実時間的な制約に間に合わないということもあるだろう。特に、組み込みシステムでは、限られた資源で最大の効率を発揮することが求められるため、動作速度に関する制約や要求も厳しくなり、プログラムの高速化は日常的な課題となる。

プログラムを高速化する際、まず最初に考慮すべきは使用しているアルゴリズムの妥当性だ。たとえば、プログラム内でデータのソートを行っている場合、ソートのアルゴリズムとしてバブルソートを使っているのか、クイックソートを使っているのか、というレベルの話だ。[1] 適切なアルゴリズムを採用することで、プログラムは劇的に速くなる。

実際のプログラム開発ではさまざまな条件や制約があり、どのアルゴリズムが最適であるかは一概に理論どおりにはならないのだが、少なくともより良いアルゴリズムを検討し、実験する努力はしておくべきだ。筋の悪いアルゴリズムのままでは、他にいくら策を弄しても良い成果は得られない。

プログラムの高速化でもう一点重要なことは、効果の大きい部分を重点的にチューニングするということだ。一般に、プログラム中のすべての命令が均等に実行されるということはなく、命令の実行頻度は場所により大きな差が生じる。つまり、プログラムのごく一部の命令列が実行時間の大半を占めるという状態が起きている。実行時間の多くを占めている小さい部分を見つけ、そこを重点的に高速化することで、少ない労力で大きな成果が得られる。

たとえば、プログラム内でデータのソートを行っているものの、ソートが占める時間が全体の実行時間の1%でしかない場合、ソートのアルゴリズムを検討して最適なものに変更したとしても、得られる効果は最大で実行時間の1%の短縮でしかない。1%でも速くしたいという場合はもちろん検討の価値はあるが、通常はもっと他に効果的な策があるはずだ。

小手先チューニング

原則として、効果の高い部分のアルゴリズムを良くするという方向が正解ではあるが、正当な方法ではこれ以上速くならず、それでもあと何ミリ秒か削らなければならないというような厳しい状況に出くわすこともある。

プログラム書きとしては、速度だけではなく、可読性や移植性なども含めて総合的に質の良いコードを生産したいとは思うのだが、そんな理想は”動くか動かないか”という現実の前では吹き飛んでしまう。あと何ミリ秒かを削るために、可読性や移植性を捨ててでも速くしなければならない。

このような高速化の最終局面で使えるテクニックがいくつかある。ここでは “小手先チューニング”と呼んでおこう。小手先チューニングはいずれもプログラムの可読性を悪くし、移植性を低下させ、にもかかわらず劇的な効果は望めないというもので、本来は使うべきものではない。しかし最終兵器としては使わざるを得ないこともある。

ループを開く

配列のデータを別の配列にまるごとコピーするという処理は、実際のプログラミングでも良く出てくる。図1は、int型の配列のポインタ2つと要素数を受け取り、内容をコピーして戻る関数 copy1 だ。

void
copy1(int *src, int *dst, int size)
{
   while(size-- > 0)
       *dst++ = *src++;
   return;
}

図1: copy1() — 単純ループ

copy1 は、配列の要素をコピーするのに要素の数だけループを回る。この実装はもちろん間違っていないが、高速化の余地はある。ループごとに4要素コピーするようにし、ループを回る回数を減らしたものが図2に示す関数 copy2 だ。

void
copy2(int *src, int *dst, int size)
{
   while(size >= 4) {
       dst[0] = src[0];
       dst[1] = src[1];
       dst[2] = src[2];
       dst[3] = src[3];
       dst += 4;
       src += 4;
       size -= 4;
   }
   while(size-- > 0)
       *dst++ = *src++;
   return;
}

図2: copy2() — 4要素ループ

copy2 は、プログラムの意味としては copy1 と等価である。このように、ループ内で行う処理を複数回まとめて記述し、ループを回る回数を減らすことを ループを開く (loop unrolling)と言い、小手先チューニングの基本的な技法である。

実際にメモリの内容をコピーする回数が変わるわけではないのに、ループを開くと速くなるのはなぜだろうか。それは、近年のプロセッサには 分岐が遅い という避けがたい性質があるからだ。近年のプロセッサはパイプライン化が進み、命令列を途切れなく実行できる時に高性能を発揮するようにできている。分岐命令によりパイプラインに供給する命令列が途切れると、パイプラインの中身を捨てたり、再度埋めたりするために余計な時間がかかるため、実行速度が遅くなる。このように、パイプラインが順調に動かなくなる現象を パイプラインのストール と言う。

手元の計算機で copy1copy2 を実行した結果を示そう。配列の要素は100,000個とし、コピー関数を10,000回呼び出すプログラムを作成し、その実行にかかった時間を計測したものだ。コンパイルにはgcc 2.95.2を用い、最適化レベル3を適用した。

関数 計算機A 計算機B
copy1 36.26秒 14.03秒
copy2 25.95秒 14.04秒

計算機Aは1GHzのPentiumIIIプロセッサを搭載したPCでNetBSD 1.6.1が走っているもの、計算機Bは400MHzのUltraSPARCプロセッサを搭載したSun Ultra10 でSolaris8 が走っているものだ。計算機A (PentiumIII)の結果に注目して欲しい。copy2 の方が断然速くなっており、コピー関数の呼び出し一回あたりに換算すると1.03ミリ秒になる。この成果は、切羽詰まった時に試してみるには十分なものだ。

パイプラインを流す

さて、上の実験では、計算機A (PentiumIII)では良い成果が得られたものの、計算機B (UltraSPARC)ではまったく効果が見られなかった。その理由を考えてみよう。

       ...
.LL11:
       ld      [%o0], %g2
       add     %o2, -4, %o2
       st      %g2, [%o1]
       ld      [%o0+4], %g3
       cmp     %o2, 3
       st      %g3, [%o1+4]
       ld      [%o0+8], %g2
       st      %g2, [%o1+8]
       ld      [%o0+12], %g3
       st      %g3, [%o1+12]
       add     %o1, 16, %o1
       bg      .LL11
       add     %o0, 16, %o0
       ...

図3: copy2 アセンブラコード — 4要素ループ部分

図3は、copy2 をUltraSPARC用にコンパイルした際に生成されるアセンブラリストから、4要素単位のループに相当する部分を抜き出したものである。

src ポインタがo0レジスタに、dst ポインタがo1レジスタに割り付けられ、g2レジスタとg3レジスタがコピーするデータを一時保持するために使われている。最初と2度目の要素のコピーでは、src ポインタから読み出すld(ロード)命令と dst ポインタに書き込むst(ストア)命令の間に別の命令が挟まれているが、3番目以降の要素のコピーでは、ld命令の直後にst命令が配置されており、余計な命令は挟まれていない。つまり、データを一時保持するレジスタg2またはg3は、ロードの直後にストアのためにアクセスされることになる。

このように、同一のレジスタへのロードとストアが命令列で並んでしまうと、パイプラインの構造によっては、パイプラインストールを起こすことがある。UltraSPARCプロセッサでも図3のようなプログラムではパイプラインストールを起こしてしまうため、最大の性能で動作することができない。

void
copy3(int *src, int *dst, int size)
{
   register int tmp0, tmp1, tmp2, tmp3;

   while(size >= 4) {
       tmp0 = src[0];
       tmp1 = src[1];
       tmp2 = src[2];
       tmp3 = src[3];
       size -= 4;
       dst[0] = tmp0;
       dst[1] = tmp1;
       dst[2] = tmp2;
       dst[3] = tmp3;
       src += 4;
       dst += 4;
   }
   while(size-- > 0)
       *dst++ = *src++;
   return;
}

図4: copy3() — 4要素ループ レジスタ使用

       ...
.LL29:
       ld      [%o4], %o1
       add     %o2, -4, %o2
       ld      [%o4+4], %o0
       cmp     %o2, 3
       ld      [%o4+8], %g2
       ld      [%o4+12], %g3
       st      %o1, [%o3]
       st      %o0, [%o3+4]
       st      %g2, [%o3+8]
       st      %g3, [%o3+12]
       add     %o4, 16, %o4
       bg      .LL29
       add     %o3, 16, %o3
       ...

図5: copy3 アセンブラコード — 4要素ループ部分

図4は、register宣言を伴う中間変数を用いることで、一時保持用のレジスタのアクセスタイミングも制御することを試みた関数 copy3 だ。copy3 の4要素単位のループ部分を抜き出したアセンブラリストを図5 に示した。src ポインタがo4レジスタに、dst レジスタがo3レジスタに割り付けられ、データの一時保持のためにo1, o0, g2, g3の4つのレジスタが使われている。命令のならびとしては、まずロード命令を連続して4つ実行し、その後ストア命令を4つ連続して実行するようになっており、同じレジスタへのロードとストアが並ぶことがなくなっている。

copy2copy3 をUltraSPARCで実行すれば、copy3 の方が速いことが期待できる。先ほどと同様、計算機Aと計算機Bで実行して時間を計ってみよう。

関数 計算機A 計算機B
copy1 36.26秒 14.03秒
copy2 25.95秒 14.04秒
copy3 31.63秒 10.59秒

UltraSPARCを搭載している計算機Aでは、予想通り copy3 の方が copy2 よりも速く、コピー関数の呼び出し一回あたりに換算すると345 マイクロ秒になる。そこそこの効果だ。

対して、PentiumIIIを搭載している計算機Bでは、copy3 の方がかえって copy2 より遅くなっている。Pentium系のプロセッサはCISC型でもともとレジスタが少なく、レジスタの連続的なアクセスによるパイプラインストールが発生しないため、UltraSPARCなどのRISC型プロセッサとは異なった結果となっている。

memcpy() を使う

配列を複製するという観点から、C言語で要素単位の代入を行う関数を書いて実験したが、やっていることとしては、単にメモリブロックの内容をコピーしているだけという見方もできる。C言語ライブラリには memcpy という標準メモリブロックコピー関数が用意されており、システムが用意しているものであるから、それなりにチューニングされている可能性が高い。C言語でコピーのループを書くのではなく、memcpy に任せてしまったらどうなるだろうか。

void
copy4(int *src, int *dst, int size)
{
   memcpy(dst, src, sizeof(int) * size);
   return;
}

図6: copy4()memcpy 任せ

図6のように、memcpy() にすべてを任せる関数 copy4 を作成し、同様に計算機Aと計算機Bで実行して時間を計ってみた。

関数 計算機A 計算機B
copy1 36.26秒 14.03秒
copy2 25.95秒 14.04秒
copy3 31.63秒 10.59秒
copy4 21.45秒 13.35秒

計算機A (PentiumIII)では copy4 が最も高速であるのに対し、計算機B (UltraSPARC)では copy4copy3 より遅い。メモリブロックをコピーするならば常に memcpy が速いと思い込んではいけない。これは、プログラムの高速化を考える上で小手先チューニングがいかに厄介かを示す良い例でもある。

Pentium系のプロセッサは、CISCであるがためにサイクルごとに定期的に命令を実行しなければならない、という制約がない。そのため、1命令で複雑な処理を行う複合的な命令が数多く用意されている。ストリングコピー命令はその良い例で、コピー元、コピー先、バイト数をそれぞれ特定のレジスタに設定した後、ストリングコピー命令を呼び出すと、メモリコピーが完了するまで終了しない。つまり、1命令でメモリのブロックコピーができてしまうのだ。計算機Aでは、C言語ライブラリの memcpy() 関数がストリングコピー命令を使って実装されているため、命令フェッチによるパイプラインストールがほとんど発生しない。事実上、C言語で memcpy() 関数 より高速な処理を記述することは不可能であるため、Pentium系プロセッサでは memcpy() 関数を用いるのが最も速くなる。

RISCであるSPARC系プロセッサには、ストリングコピー命令のような便利なものはなく、memcpy() ライブラリ関数の中で、地道に最適化されたプログラムが実行される。しかし、memcpy() 関数は仕様上バイト単位でコピーできることになっているため、ワードアクセスを行うべきか、バイトアクセスを行うべきかなど、アラインメントのチェックを必要とし、それゆえに分岐も多数必要になる。対して copy3 はコピー元もコピー先もワード境界に合っていることを前提として書かれており、アラインメントのチェックなど余計なことは行っていない。そのため、copy3 が最も速くなると考えて良いだろう。

小手先チューニングの弊害

もし、プログラムに大きい配列をコピーする部分があり、かつその部分が大量に呼び出されるのであれば、ループを開いたりレジスタを使ってパイプラインを流すように書き直すことで、それなりの速度向上が達成できる。しかし、その弊害は少なくない。

まず、プログラムコードが大変わかりにくくなる。配列をコピーするというコードは、普通は誰でも copy1 のように書くだろう。copy2copy3 のようなコードは、パッと見て何をやっているのか、何を意図しているのか汲み取りにくい。

また、コードの移植性にも甚大な影響を与える。copy3 はPentiumなどのCISC系プロセッサではほとんど効果がないため、CISC系では copy2 を使うか memcpy に任せることになる。プロセッサの種類によって copy2 を使うか、copy3 を使うか、あるいは memcpy に任せるかを使い分けるというような細工が必要になる。そして、その細工はやはりパッと見ただけでは何のことやらわからない。

小手先チューニングを行うときは、他人にも意図が伝わるように、十分なコメントを入れておくなどの配慮が必要である。

最後に、今回示した成果は私の手元の環境でたまたまそうなっただけであり、どのような環境や条件でも同様の成果が得られるとは限らない。たとえば、同じSPARC系のプロセッサでも、異なるシリーズのプロセッサは異なるパイプライン構造を持ち、異なる条件でストールする。常に今回と同様の成果が得られるという保証はどこにもないのだ。

小手先チューニングは、あくまでも最後の手段と心得よう。

[1]バブルソートの平均時間計算量は O(n2) であるのに対し、クイックソートの平均時間計算量は O(n log n) で、一般的にはクイックソートの方が高速である。

注釈

  • 初稿に由来する表現の差異、ならびにWeb掲載に伴う修正のため、雑誌掲載の内容とは一部文章等が異なることがあります。
  • 転載許諾を頂いた株式会社KADOKAWAアスキー・メディアワークスブランドカンパニーならびに旧『UNIX Magazine』編集部の皆様に深く御礼を申し上げます。

著者プロフィール

tom

当社設立直後に入社して約30 年、UNIX の移植、日本語化、デバイスドライバ開発、周辺機器ファームウェア開発などに継続的に携わり、現在も現役でUNIX 系OS の移植、改造などの開発業務を行う。社内でもっともプログラムを書いている人の一人。代表取締役社長。

記事一覧Index