Does VC8 optimize Tail Recursion?

　末尾再帰というものがある。ある関数が、最後に自分自身を呼び出すように書かれている場合、もし分岐があるならば、それぞれの分岐の最後に、自分自身を呼び出すように書かれている場合、それをTail Recursion（末尾再帰）という。下に例を示す。

void print_hello(int const n) { if ( n == 0 ) { return ; } else { std::cout << "hello" << std::endl ; return print_hello(n - 1) ; } } double power( double const x, int const n ) { if ( n == 0 ) { return 1.0 ; } else { return x * power(x, n - 1) ; } }

　print_hello関数は、引数に与えられた数だけ、helloと出力する関数である。power関数は、xのn乗を計算する関数である。しかし、このように再帰的に記述するのは、C++らしくない。我々C++プログラマは、副作用がたっぷり詰まった、forやwhile文のループを好むものだ。なぜならば、たとえばMS-Windows X86の場合、関数を呼ぶというのは、それだけでスタックを消費するのだ。今の時代にC++を書く、根性のあるプログラマは、皆CPUのサイクル数や、数バイトのメモリ消費を気にするパフォーマンスの信奉者である。再帰のオーバーヘッドなど許されるはずがない。 　しかし、ちょっと待って欲しい。次のような単純な変換を施すだけで、この糞みたいなオーバーヘッドを持つ関数は、単なるループに変わる。

void print_hello(int n) { LOOP : if ( n == 0 ) { return ; } else { std::cout << "hello" << std::endl ; --n ; goto LOOP ; } } double power( double x, int n ) { double tmp(x) ; LOOP : if ( n == 0 ) { return tmp ; } else { tmp *= x ; --n ; goto LOOP ; } }

　すばらしい。実に単純な変形だ。コンパイラにできないはずがない。 　実際、主要なコンパイラは、末尾再帰を最適化できる。この末尾再帰という考え方は、副作用を忌み嫌う関数型言語の信者にとって、崇拝の対象である。特にLISP教徒は、再帰がなければまともにループを書くことができない。LISPの方言のひとつ、Schemeなどは、 「Thou shalt not waste stack by tail recursion. if thou defy god's will, thy are evil beast, slow belly, and pagan.」 「処理系は末尾再帰にてスタックの消費をしてはならぬ。もし我が意に沿わざれば、汝は悪しき獣、懶惰の腹、異教徒なり」 　とまで、規格書の中で明言している。まあ、私にとって、Schemeが異教徒なのだが。 　さて、関数型言語は異教徒ではあるかというと、最近のC++の動向を見るにつけ、そうもいえなくなっている。しかし、どの程度できるのだろうか。さっそく確かめてみよう。 　確かめるからには、何か実用的なコードにしなければならない。バイナリサーチなどどうだろう。あれは、スタックを消費せずに、ループでも実装できる。あれを再帰で書いて、コンパイラが最適化できるか確かめてみよう。 　まず、典型的なC++教徒の書くバイナリサーチを書いてみる。

template < typename Iterator, typename T > bool binary_search( Iterator first, Iterator last, T const & value ) { typename std::iterator_traits<Iterator>::difference_type n = std::distance(first, last) ; Iterator mid ; for ( ; n != 0 ; n = n / 2 ) { mid = first ; std::advance(mid, n / 2) ; if ( *mid < value ) { first = ++mid ; } else { last = ++mid ;} } return bool( *first == value ) ; }

　これはどうみても、典型的なC++のバイナリサーチだ。さて、早速再帰で書いてみよう。特に難しくはない。

namespace detail { template < typename Iterator, typename T > bool binary_search(Iterator first, Iterator last, T const & value , typename std::iterator_traits<Iterator>::difference_type const n) { if ( n == 0 ) { return bool( *first == value ) ; } Iterator mid(first) ; std::advance(mid, n / 2 ) ; if ( *mid < value ) { return binary_search(++mid, last, value, n / 2) ; } else { return binary_search(first, ++mid, value, n / 2) ; } } } // namespace detail template < typename Iterator, typename T > bool binary_search( Iterator first, Iterator last, T const & value ) { return detail::binary_search(first, last, value, std::distance(first, last) ) ; }

　私はまだ、C++への信心と修行が足りないし、ましてや異教徒の操る再帰は得意ではないが、こんなものだろう。さっそくこれを、VC8 SP1でコンパイルしてみる。VC8の最適化のほどを見せてもらおう。五千円だして買っただけの価値はあるのだろうか（学生というのはいい身分だ） 　まず、これがC++版のbinary_searchだ。これを次のように呼ぶと。

binary_search<int *, int>(&v[0], &v[1000], 12700) ;

00401120 |> 99 /CDQ 00401121 |. 2BC2 |SUB EAX,EDX 00401123 |. D1F8 |SAR EAX,1 00401125 |. 813C81 9C310000 |CMP DWORD PTR DS:[ECX+EAX*4],319C 0040112C |. 7D 04 |JGE SHORT test.00401132 0040112E |. 8D4C81 04 |LEA ECX,DWORD PTR DS:[ECX+EAX*4+4] 00401132 |> 85C0 |TEST EAX,EAX 00401134 |.^75 EA \JNZ SHORT 00401120

　前後を省略するが、これがループである。binary_search関数は、呼び出したところでインライン展開された。ループ版のbinary_searchはこのようになる。再帰版のbinary_searchも、このようになることが理想だ。さて、どうなるだろう。早速比較しよう。

00401370 /$ 85C0 TEST EAX,EAX 00401372 |. 74 16 JE SHORT 0040138A 00401374 |. 56 PUSH ESI 00401375 |. 8B37 MOV ESI,DWORD PTR DS:[EDI] 00401377 |> 99 /CDQ 00401378 |. 2BC2 |SUB EAX,EDX 0040137A |. D1F8 |SAR EAX,1 0040137C |. 393481 |CMP DWORD PTR DS:[ECX+EAX*4],ESI 0040137F |. 7D 04 |JGE SHORT 00401385 00401381 |. 8D4C81 04 |LEA ECX,DWORD PTR DS:[ECX+EAX*4+4] 00401385 |> 85C0 |TEST EAX,EAX 00401387 |.^75 EE \JNZ SHORT 00401377 00401389 |. 5E POP ESI 0040138A |> 8B01 MOV EAX,DWORD PTR DS:[ECX] 0040138C |. 3B07 CMP EAX,DWORD PTR DS:[EDI] 0040138E |. 0F94C0 SETE AL 00401391 \. C3 RETN

　これが、再帰版のbinary_search関数である。呼び出したところにインライン展開はされなかったものの、再帰ではなくなっている。思うに、binary_search関数自体はインライン展開されているのだろう。detail::binary_search関数は、末尾再帰が最適化されて、ループに直されるものの、そのトップレベルの関数自体がインライン展開されることはないのだろう。これには何か、理由があると思われる。 　さて、肝心のインストラクションコードはどうだろうか。00401377番地から始まるループを見て欲しい。すばらしい出来だ。関数自体がインライン展開されないので、0x319C(12700)は即値ではなくなっているものの、なんとレジスタである。そのほかはすべて、ループ版と同じだ。再起によるオーバーヘッドはなくなった。単なるループとまったく同じである。もちろん関数呼び出しにかかるコストはあるが、それは一回だけで、無料同然に安い。5千円の価値はあるといえよう。 　 　しかし、ここまで分かりやすい結果になるとは思わなかった。 　因云、VC8のイテレータは、デフォルトで範囲外チェックを行う。コンピュータがネットワークにつながることが当たり前になった今の時代、パフォーマンスよりもセキュリティの方が重要だと叫ばれている。セキュリティの確保にかかるコストは無料ではない。ヘビーなパイプラインを持つCPUにとって、条件分岐は禁忌だ。さて、VC8の、セキュアなイテレータは、どの程度パフォーマンスに影響を及ぼすのか。 　先ほどの関数に、セキュアなイテレータを通してみると、恐ろしく長いコードが生成された。範囲外をチェックするコードは、恐ろしく頻出するので、インライン展開しないほうが良いと判断されたのか、関数になっている。山のようなpushとpopがある。汎用レジスタが、全然足りていないのだ。うーむ、セキュリティは無料ではないとはいえ、これはすこし、セキュアなイテレータの使用をためらってしまう。 　恐らくは、大半の場合は、セキュアなイテレータを使うべきなのだ。それは分かっている。当然だ。しかし、この生成されるコードは……、いや、これは私が古いからなのだ。まったく。この業界は、どうかしている。経験に裏打ちされた熟練の技というものは存在しない。10年前、いや5年前の常識だって通用しないのだ。むしろ、そういう古い知識は、新しい技術習得の邪魔になる。やんぬるかな