アンティーク・アセンブラ~Antique Assembler

第4回 "case" の事情

この記事を読むのに必要な時間:およそ 5 分

低レイヤーから見たswitch

switch相当の機能実現に関する説明は以上で終わりですが,折角アセンブラのような低レイヤーからの視点で見ているわけですから,上位のソースコードからだけでは見えてこないトピックについて,幾つか触れてみようと思います。

データ量を減らすには

先述した switch実現例では,制御遷移先配列の格納の際には,制御遷移先のアドレス情報(32ビット=4バイト)をまるまる格納していました。

しかし,通常のプログラムで考えた場合,分岐命令の位置から分岐先までは高々数十バイト~数百バイト程度,つまり16ビット=2バイトもあれば十分表現できる範囲にあります。このような状況で32bitのアドレスを丸々格納するのは,同一市内の友人に葉書を投函する際の宛先を,わざわざ国名から書き始めるような冗長さがあります。

※)
ひょっとしたら,8ビット=1バイトでも十分かもしれません。

たとえば,制御遷移処理をリスト7のように実装したとします。

リスト8 データ量を減らす制御遷移処理

    leal    addr_table, %ebx
    subl    $2, %eax
    movl    $0, %ecx
    # 16 ビット幅の転送なので,転送先レジスタ指定は
    # 32 ビット幅の ecx ではなく,16 ビット幅の cx。
    # インデックスの倍数も 4 ではなく 2。
    movw    (%ebx, %eax, 2), %cx
    # アドレス値としての switch_jmp を加算するので
    # 即値を示す $ を使用
    addl    $switch_jmp, %ecx
switch_jmp:
    # ecx の値が指すアドレスへ制御遷移
    jmp     *%ecx

上記実装での制御遷移先アドレスの算出では,制御遷移先配列から取り出した値と,switch_jmpのアドレスを加算しています。そのため制御遷移先配列に格納する値はswitch_jmpからの相対的な値,つまり switch_jmpとの差分だけを格納すれば良いことになりますから,両者が十分近い値であれば各要素の格納は16ビット=2バイト程度で済みます。

リスト9 アドレス差分による制御遷移先配列

addr_table:
    .word  switch_case_2  - switch_jmp
    .word  switch_default - switch_jmp
    .word  switch_default - switch_jmp
    .word  switch_case_5  - switch_jmp
    .word  switch_default - switch_jmp
    .word  switch_default - switch_jmp
    .word  switch_case_8  - switch_jmp

実行される命令数の増加=性能低下をある程度許容してでも,必要とされる総メモリ量の抑止を実現したいような場合であれば,制御遷移先配列の格納に必要な領域のサイズを低減させるための,このような実装方式も選択肢の1つになるでしょう。

レジスタecxに対する事前の"movl $0"は,直前の(関係ない)処理で設定されている(かもしれない)ゴミデータが,加算の際に上位の16ビット部分に影響を及ぼすのを防ぐためのものです。

ここでは愚直に即値でクリアしていますが,命令実行効率やプログラムサイズの短縮等を考慮した場合,⁠レジスタ0クリアの最適化」1つ取っても話のネタには事欠きませんので,興味のある方は調べてみるのも面白いでしょう。

制御遷移先は「既知」

初心者がswitch構文を使用する場合の代表的な間違いに:

変数を使ったcase列挙によるコンパイルエラー

というものがあるのではないでしょうか。

プログラミングに慣れるに従い:

switch構文のcaseには,変数を指定してはならない

というルールを理解するわけですが,アセンブラレベルでのswitchの実現方式を理解した今であれば:

コンパイル時点で,制御遷移先配列を格納=値の範囲を確定する必要があるため,実行時にならないと値が確定できない変数値は,caseでの列挙には使用できない

という理屈で理解できるようになっていることでしょう。

switchのコスト

先述したswitchの実現例を見て:

case列挙の下限値~上限値の範囲判定が必要なので,if/elseを使用したものよりもswitchは余計な処理をしているのでは?

と思われるかも知れません。

必要な条件判定が2つ程度であるなら,その考えは正しいと言えます。

また,たとえば0~255の間に分散する値に応じて処理を切り替える必要がある場合,四角四面にswitchを使って実装するなら,4バイト×256=1Kバイトもの制御遷移先情報を格納する必要があります(32ビット環境で制御遷移先アドレスを丸々格納する場合⁠⁠。

さらに上限値と下限値の開きが大きい場合,たとえば0~1024の間で値が分散する状況で制御遷移先情報を丸々格納するのは,とてもではありませんが現実的ではありません。

このようなケースでCコンパイラが生成するアセンブラコードは

  1. case で列挙されている値を大小で2つのグループに分割
  2. 中間値で大小判定
  3. どちらかのグループで一致が検出されるまで,分割~判定の手順を繰り返す
  4. 一致するcase値が判明したなら,該当する処理に制御遷移
  5. 一致するcase値が無いことが判明した場合は default 処理に制御遷移

といった二分探索(binary search)的な実行や,二分探索で値域を絞り込んでから制御遷移先配列を使用したswitch処理と組み合わせる,といったハイブリッドなものになるかもしれません。

コンパイラの最適化が上手くハマれば,下手に人手で書いたプログラムよりも適切なものになるとは思いますが,そもそもの「値判定に要するコスト(= 処理量)はcaseの数に関わりなく一定」という期待からは随分と異なる結果となります。

以上のように,常にswitchがif/elseの連続に対して常に優位であるわけではありません。

しかし,アセンブラレベルでのswitch実現方式を理解した今なら,実行時の性能オーバヘッドや,制御遷移先配列を格納するためのメモリ領域量といったものを勘案し,状況に応じて適切な選択を行うことが可能になっているのではないでしょうか。

著者プロフィール

藤原克則(ふじわらかつのり)

Mercurial三昧の日々が嵩じて, いつの間にやら『入門Mercurial Linux/Windows対応』を上梓。凝り性なのが災いして,年がら年中アップアップな一介の実装屋。最近は仕事の縁が元で,OpenSolarisに入れ込む毎日。