C言語でカッコよく見えたコードが走らせたら遅かった話

これは「やっちまった」話です

私は株式会社 ACCESS の三原と申します。ACCESS Advent Calendar 2016 の11日目をお読みいただき感謝申し上げます。

これは「やっちまった」話です。

一言で言えば「C++の仮想関数で遅くなるパターンをわざわざCでやってしまった」話です。

それを聞いて「ダメだなぁ」と笑える方はお読みになる必要はありません(あ、末尾にある明日の筆者の紹介だけはお読みいただけませんか)。ピンとこない方は、ダメな話におつきあい願えませんか。

先輩が残したキレイなコードが遅い

弊社で実装した、ある言語のインタプリタのメンテナンスを引き継ぎました。たとえインタプリタでも、言語処理系を1つ丸々作るのは気が遠くなる作業です。完動するまで実装なされた先輩を今でも尊敬しています。

でも、上手の手から水が漏れることもございます。

元々実装なされた先輩が離れてから、ある顧客から、インタプリタが遅いという指摘を受けました。弊社は組込みプログラミングの会社ですから、顧客というのはエンドユーザではなく電子機器開発メーカです。メーカは入念な調査を行い、インタプリタのメインループではなく字句解析部分が遅いと証拠をつかんでいました。

その遅い箇所は次のような構造をしていました。(製品そのままではありません。模擬コードです)

/*
 * 次の文字に対する処理を実行する関数の
 * インタフェースを定義。
 */
typedef int (*handle_character_proc)(int next_character, ...);

/*
 * 次の文字に対する処理を実行する関数を
 * 関数ポインタで保持。
 */
static handle_character_proc *state_proc;

/*
 * 次の処理を行う関数を設定する。
 */
static void
SetStateProc(handle_character_proc next_proc)
{
  handle_character_proc = next_proc;
}


/*
 * 初期状態を設定する。
 * すなわち、
 * 最初の関数ポインタを設定する。
 */
static int
SetInitialStateProc(int next_character)
{
  ... /* 前段は略 */
  /*
   * 始めの文字に応じて、関数ポインタを設定。
   */
  switch (next_character) {
  case '?':
    SetStateProc(HandleCharacter1);
    break;
  case '=':
    SetStateProc(HandleCharacter2);
    break;
  /*
   * 関数ポインタを設定するcase文は
   * 処理する文字の数だけ続きます。
   */
  }
  ... /* 後段は略 */
}

static int
HandleCharacter1(int next_character, ...)
{
  ... /* 文字に対する処理を行って。 */
  switch (next_character) {
  ...
  /*
   * 次の関数ポインタを設定して状態遷移。
   */
  case '=':
    SetStateProc(HandleCharacter5);
    break;
  ...
  }
}

/*
 * 関数ポインタを呼び出すのが文字に対する処理。
 */
int
ScanChar(int next_character, ...)
{
  int ret;

  ...
  ret = (*handle_character_proc)(next_character, ...);
  ...
}

このコード、さすが先輩、キレイだなあ、と思って見ていたのですが……

考えてみれば当たり前です

考えてみれば、上のコードが遅いのは当たり前なんです。

• 1文字処理するたびに関数呼び出しのプロローグとエピローグ
• Cコンパイラの最適化もCPUの投機実行も無効化される

関数呼び出しは、自動変数の退避と復帰、等々、環境を作るためのプロローグとエピローグのコストがかかります。

関数呼び出しのコストは、関数が行う処理が十分大きければ、メンテナンスコストとの兼ね合いで許容されます。

しかし上のコードはインタプリタの字句解析機で、1文字処理するたびに関数呼び出しを行っています。内部の処理が小さく、プログラムは関数呼び出しのプロローグとエピローグばかり実行する結果となってしまいます。

こんなときのためのCコンパイラの最適化、とおっしゃる方もいらっしゃるかもしれませんが、このコードは最適化が効かないんです。

関数ポインタの値はプログラム中に頻繁に書き換えられ、法則性がありません。ですからCコンパイラは関数呼び出しに前提を置くことができず、正直に関数ポインタを読み込んでジャンプするコードを生成せざるをえません。

さらにCPUの投機実行も無効化されます。関数ポインタの値は事前に分からないので、ありそうなジャンプ先をとりあえず実行しようとしても「ありそうなジャンプ先」が見つからないのです。

C++プログラマなら、仮想関数の呼び出しが遅いのをいかに静的呼び出しに置換するかテクニックを駆使したことがおありだと思います。上のコードは、C言語なのに、仮想関数を作ってしまったわけです。

stupid で泥臭い解決策

上のコードは、見栄えがどうであれ、早急に速くする必要がありました。そこで、全部ベタにswitch文で書きなおしました。switch文は、CPUの分岐予測は効きませんが、とりあえず関数呼び出しはなくなります。

すると処理時間が約半分になりました。元コードは処理の半分が関数呼び出しのプロローグとエピローグだったわけです。

「教訓」という名の苦い思い出

苦い思いをして1つ学んだのは、関数ポインタによる処理の分岐はカッコいいけれども遅いということです。

分岐の枝が膨大な場合にif文やswitch文より構造が明確になる利点があります。でも、その代わりに実行時間でコストを払うことを顧客からの苦言とともに学びました。

カッコいいプログラミングをしてはいけない、という結論に性急に飛びつくのはやめます。一般的には速いプログラムは構文的にも美しいですから。

明日の ACCESS Advent Calendar 2016 は @DaisukeKondo さんです。どうぞお楽しみに。