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

第12回 小手先チューニング -- 条件分岐の高速化

2015.07.08

本稿では、『UNIX Magazine』に掲載された『プログラマーの理想と現実』の連載記事を、一部修正の上再掲してきました。本誌の連載は前回の第11回で終了していますが、実際にはあと一回分、掲載されなかった原稿があるのです。今回は、本誌に掲載されなかった幻の最終回を掲載することにします。

これまでの記事と同様、執筆したのは10年以上前であり、現在の環境とは色々と異なることもありますが、プログラミングに対する心構えとしては現在でも通用するものがあると思います。

・・・・・・・・・・

プログラムの論理構造や根本的なアルゴリズムはそのままで、ソースコードの表現をちょっとだけ工夫して実行速度を稼ぐ。私はこれを 小手先チューニング と呼んでいる。組み込みシステムなど、リソースに制約がある環境において、もう少し速くならないとすべてが水の泡というような切羽詰まった状況で使う最終兵器だ。

前回はループを速くする手法と、レジスタの使い方を調整する手法を紹介した。今回は条件分岐に高速化の余地があるかどうか見てみよう。

if文とswitch文の違い

C言語では、条件分岐にif文とswitch文が利用できる。if文では、条件式を評価した結果に応じて真の場合と偽の場合の文を選択的に実行できる。switch 文では、整数変数の値に応じて対応した文を選択的に実行できる。条件判断の仕組みは異なるが、if文は二者択一でswitch文は多者択一と言える。

二者択一の処理を考えた場合、if文とswitch文では次のように等価な処理が記述できる。

if (条件式 C) {               switch (条件式 C) {
      文 T                       case 1:
}                                     文 T
else {                                break;
      文 F                       default:
}                                     文 F
                                      break;
                                 }

上記は、条件式 C が評価されると整数値になり、真の場合は値1となることを想定している。[1] gccを含む多くのコンパイラで、両者はまったく同じオブジェクトコードにコンパイルされる。図1と図2に示す比較用の小さな関数を、i386用のgcc 2.95.3を使って最適化レベル3でコンパイルした結果のアセンブラコードを図3と図4に示す。if文を用いた関数 choice2_if と、switch文を用いた関数 choice2_sw では、生成されるアセンブラコードはまったく同じである。switch文の構造が二者択一と解釈できる場合、コンパイラは内部的にif文と同じ処理を行っていると考えて良いだろう。

int choice2_if(int x, int y)
{
   if(x == 1)
       y += 5;
   else
       y += 7;
   return y + 3;
}

図1:if文による二者択一 – choice2_if 関数

int choice2_sw(int x, int y)
{
   switch(x == 1) {
   case 1:
       y += 5;
       break;
   default:
       y += 7;
       break;
   }
   return y + 3;
}

図2:switch文による二者択一 – choice2_sw 関数

choice2_if:
       pushl %ebp
       movl %esp,%ebp
       movl 12(%ebp),%eax
       cmpl $1,8(%ebp)
       jne .L8
       addl $5,%eax
       jmp .L9
.L8:
       addl $7,%eax
.L9:
       addl $3,%eax
       leave
       ret

図3: choice2_if 関数のアセンブラコード

choice2_sw:
       pushl %ebp
       movl %esp,%ebp
       movl 12(%ebp),%eax
       cmpl $1,8(%ebp)
       jne .L13
       addl $5,%eax
       jmp .L11
.L13:
       addl $7,%eax
.L11:
       addl $3,%eax
       leave
       ret

図4: choice2_sw 関数のアセンブラコード

多者択一

多者択一は、switch文を使えば簡単に記述できるが、if文を複数組み合わせて実現することもできる。簡単な例として、整数変数 x の値が1から4のそれぞれに応じて異なった処理をおこなう四者択一のケースを考えてみよう。if文を使った関数 choice4_if を図5に、switch文を使った関数 choice4_sw を図6に示す。

int choice4_if(int x, int y)
{
   if(x == 1)
       y += 5;
   else
   if(x == 2)
       y += 6;
   else
   if(x == 3)
       y += 9;
   else
   if(x == 4)
       y += 7;
   return y + 3;
}

図5:if文による四者択一 – choice4_if 関数

int choice4_sw(int x, int y)
{
   switch(x) {
   case 1:
       y += 5;
       break;
   case 2:
       y += 6;
       break;
   case 3:
       y += 9;
       break;
   case 4:
       y += 7;
       break;
   }
   return y + 3;
}

図6:switch文による四者択一 – choice4_sw 関数

一般に、choice4_ifchoice4_sw をコンパイルして得られるオブジェクトコードは同じにはならない。両者はロジックとしては等価で、実行の結果は同じになるが、ソースコードに込められた意図は異なる。choice4_if の方は、x が1であるか、2であるか、3であるか、と順に調べる。choice4_sw の方は、x の値によって直接的に処理を選ぶ。つまり、x の値に対する期待度が異なる。

choice4_if では、x が1の場合は1回の比較だけで結果を出したいが、x が4の場合は4回比較をおこなっても構わないという意図が暗黙のうちに含まれている。choice4_sw では、どのような x の値でも平等に扱いたいという意図がやはり暗黙のうちに含まれている。コンパイラは、その意図を的確に汲んでオブジェクトコードを生成する。

実際に実験してみよう。ループを回って choice4_ifchoice4_sw を 1億回呼び出すプログラムを作り、i386用のgcc 2.95.3を使って最適化レベル3 でコンパイルし、1 GHzのPentium IIIプロセッサを搭載するPC で実行してみた。OS はNetBSD 1.6.1である。x の値を1~5と変化させ、関数の繰り返し実行にかかる時間を計測する。[2] 結果は表1のようになった。choice4_if では、x が1から4と変化するにしたがい、徐々に実行時間が増えている。対して、choice4_sw では x が2のケースが例外的に速いものの、1, 3, 4ではほぼ同じ時間がかかっている。

変数 x の値
  1 2 3 4 5
choice4_if 1.54 1.69 1.82 2.07 2.00
choice4_sw 1.92 1.53 1.92 1.91 1.94

単位:秒

表1: choice4_ifchoice4_sw の実行時間

switch文では、複数のcaseラベルをなるべく平等に扱おうとする。実験に用いた choice4_sw のようなプログラムでは、整数値1~4を二分探索のように比較するオブジェクトコードが生成される。まず x と2を比較し、等しい場合、2より小さい場合、2より大きい場合と分岐するようなコードになる。[3]

そのため、x が2の時が例外的に速くなっているが、すべてのcaseラベルを平等に扱おうとする意図は見て取れる。

テーブルジャンプ

choice4_sw は四者択一であったが、選択肢がもっと多くなるとどうなるであろうか。二分探索は、選択肢数 n に対して log(n) のオーダで比較の回数が増えてゆく。n が多くなっても、二分探索的なオブジェクトコードが生成されるのであろうか。

選択肢数を8とした八者択一の関数 choice8_sw (図7)で調べてみよう。choice8_sw をi386用のgcc 2.95.3を使って最適化レベル3でコンパイルした時のアセンブラコードは、図8のようになる。このコードは、テーブルジャンプを実装したものになっている。ラベルL58以降に x の値に対する飛び先アドレスを格納するテーブルが用意され、ラベルL58の直前にあるjmp命令で、x の値に応じたテーブルエントリに格納されたアドレスにジャンプする。

int choice8_sw(int x, int y)
{
   switch(y) {
   case 1:
       y += 5;
        break;
   case 2:
       y += 6;
       break;
   case 3:
       y += 9;
       break;
   case 4:
       y += 7;
       break;
   case 5:
       y += 2;
       break;
   case 6:
       y += 4;
       break;
   case 7:
       y += 8;
       break;
   case 8:
       y += 1;
       break;
   }
   return y + 3;
}

図7:switch文による八者択一 – choice8_sw 関数

choide8_sw:
       pushl %ebp
       movl %esp,%ebp
       movl 12(%ebp),%eax
       leal -1(%eax),%edx
       cmpl $7,%edx
       ja .L49
       jmp *.L58(,%edx,4)
.L58:
       .long .L50
       .long .L51
       .long .L52
       .long .L53
       .long .L54
       .long .L55
       .long .L56
       .long .L57
.L50:
       addl $5,%eax
       jmp .L49
.L51:
       addl $6,%eax
       jmp .L49
...
.L56:
       addl $8,%eax
       jmp .L49
.L57:
       incl %eax
.L49:
       addl $3,%eax
       leave
       ret

図8: choice8_sw 関数のアセンブラコード(抜粋)

テーブルジャンプでは、選択肢数に応じて比較命令や分岐命令を繰り返すことがなく、一定の時間ですべての選択肢に均等に分岐できる。switch文の意味を考えると、妥当な実現方法と言えるだろう。欠点は、テーブルを引くためにメモリを一度アクセスしなければならないため、若干ではあるが実行時間が遅くなることである。i386用のgcc 2.95.3では、選択肢数が8の場合には二分探索的に比較と分岐を繰り返すより、テーブルジャンプの方が有利と判断しているようだ。

テーブルアクセスによるペナルティがどの程度あるのか、実際に実行して確認してみよう。x を1から5まで変化させ、1億回ループを回した時の実行時間を表2に示す。

変数 x の値
  1 2 3 4 5
choice8_sw 1.72 1.72 1.72 1.72 1.72

単位:秒

表2: choice8_sw の実行時間

x が1から5のいずれの場合も、1.72秒と極めて均等に分岐できていることがわかる。直列的に比較と分岐をおこなう choice4_if の実行時間(表1)と比べると、x が1の場合、つまり一回の比較で済むケースよりは遅いものの、x が2以上の場合、二回以上の比較をおこなう場合は同等かより高速に分岐できていることがわかる。

二分探索的に比較と分岐をおこなう choice4_sw との比較では、例外的に速かった x が2のケースを除いて、choice8_sw の方が高速に分岐できている。これは、選択肢数が4の場合はテーブルジャンプではなく二分探索的比較 を使う というgcc 2.95.3の判断が、少なくとも今回の条件では最善ではなかったことを意味している。[4]

離散的なcaseラベル

choice8_sw では、x の値が1~8と狭く連続する範囲で分岐をおこなっていたため、ジャンプテーブルは8エントリで済んだ。では、x の値が広く離散的であった場合はどうなるであろうか。たとえば、x の値が1, 100, 1000 のいずれかで分岐するswitch文をテーブルジャンプで実現すると、1000エントリのジャンプテーブルを用意しなければならない。そのうち、有効な3個を除く997個のエントリはdefaultラベルにジャンプするように設定されることになる。1エントリに4バイト使うと仮定すると、ジャンプテーブルだけで40 KBを消費してしまう。これは現実的ではない。

図9に示す関数 choice8_sw_d は、x を離散的な値に直した八者択一の関数である。これをgcc 2.95.3で同様にコンパイルした時のアセンブラコード(抜粋)を図10に示す。もはやテーブルジャンプは使われておらず、二分探索的な比較と分岐をおこなうコードになっている。

int choice8_sw_d(int x, int y)
{
   switch(x) {
   case 2:
       y += 5;
       break;
   case 34:
       y += 6;
       break;
   case 56:
       y += 9;
       break;
   case 78:
       y += 7;
       break;
   case 90:
       y += 2;
       break;
   case 123:
       y += 4;
       break;
   case 456:
       y += 8;
       break;
   case 789:
       y += 1;
       break;
   }
   return y + 3;
}

図9:離散的な八者択一 – choice8_sw_d 関数

choice8_sw_d:
       pushl %ebp
       movl %esp,%ebp
       movl 8(%ebp),%edx
       movl 12(%ebp),%eax
       cmpl $78,%edx
       je .L65
       jg .L72
       cmpl $34,%edx
       je .L63
       jg .L73
       cmpl $2,%edx
       je .L62
       jmp .L61
.L73:
       cmpl $56,%edx
       je .L64
       jmp .L61
.L72:
       cmpl $123,%edx
       je .L67
       jg .L74
       cmpl $90,%edx
...
.L68:
       addl $8,%eax
       jmp .L61
.L69:
       incl %eax
.L61:
       addl $3,%eax
       leave
       ret

図10: choice8_sw_d 関数のアセンブラコード(抜粋)

テーブルジャンプでは、すべてのcaseラベルに一定時間で分岐できるが、二分探索的な比較と分岐をおこなう場合は、caseラベルの数 n に対して概ね log(n) に比例して分岐の時間が増える。つまり、caseラベルの値が離散的であるかどうかにより、switch文の分岐時間の特性が変わることになる。

☆☆☆

近年のプロセッサは大変高速で、またパイプラインにとって大問題であった分岐命令についても、分岐予測や投機的実行など、さまざまなハードウェア的対策が取られているため、if文やswitch文の性質について細かく気にしながらプログラムを書く必要性が低いことは確かである。しかし、組み込みシステムなどでは、そういった値の張るハードウェア機能を搭載していないプロセッサを使うことも多く、if文やswitch文の性質に考慮しながらプログラムを書くことで、最後の数マイクロ秒を稼げる可能性もある。覚えておいて損はないだろう。

[1]これはgccの場合は成り立つが、他のコンパイラでは成り立たないこともある。このようなコードは移植性に重大な影響を与える。今回は例としてあえて示したが、普通はこのようなコードを書いてはならない。
[2]x が5のケースは、if文の連鎖、switch文のラベルに一致しなかった場合の実行時間を表わす。参考のために示した。
[3]等しい・小さい・大きいの3つに分岐するので、厳密には二分探索ではなく三分探索のような感じになる。
[4]もちろん、実験環境が変われば結果も変わるため、gcc 2.95.3の判断が 誤っている ということにはならない。

注釈

  • 転載許諾を頂いた株式会社KADOKAWAアスキー・メディアワークスブランドカンパニーならびに旧『UNIX Magazine』編集部の皆様に深く御礼を申し上げます。

著者プロフィール

tom

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

記事一覧Index