「真実」の中には、賞味期限を越えて生き残るものがあります。これは、リリースノートに何か情報が載っていたとしても、それよりも人から人へと「情報」が広がっていく速度の方が早いからです。実際には、かつて古いといわれていたfunも、現在では高速になっています。
このドキュメントを通じて私たちが行おうとしていることは、かつて真実(あるいは多少誤解があるもの)だったもののうち、もはや古くなって、すでに都市伝説となっているものを、正しく葬り去ることです。
そうです。かつてfunは遅かったです。とても遅かったです。apply/3よりも遅かったです。最初は、funはコンパイラ上のトリックと通常のタプル、apply/3と、大量のアイディアを使って実装されていました。
しかし、これは過去の歴史でしかありません。R6Bリリースからはfunに対して専用のデータ型が与えられ、R7Bリリースではかなりの最適化が行われました。現在の実装においては、funを呼び出すコストは、大雑把に言うと、ローカルの関数を呼び出すコストと、apply/3を使用するコストの中間ぐらいになっています。
リスト内包表記は、かつてはfunを利用して実装されていました。そして、暗黒時代のfunは本当に遅かったということがありました。
現在のコンパイラの実装では、リスト内包表記は通常の再帰関数へとリライトされます。当然、末尾再帰関数を使って最後にreverseをする方がとっても早いのです。本当？それでは次の都市伝説を見ていきましょう。
都市伝説によると、再帰関数はスタック上の不要になったtermを参照し続けてしまうため、ガーベジコレクタはこれらの不要なtermをすべてコピーしなければなりません。一方、末尾再帰関数の場合は、不要になったらすぐに捨てることができる、ということです。
これはR7B以前は本当でした。R7B以降のコンパイラは、もう使用しないtermへの参照を、空のリストで上書きをするようなコードを生成するようになりました。このため、必要以上に長い期間、ガーベジコレクタが不要な値を保持し続けることもなくなりました。
このような最適化の後も、ほとんどの場合で、末尾再帰関数は本体再帰(訳語正しい？)関数よりも高速なままでした。それはなぜでしょうか？
それは、再帰のコール一回ごとに、どれだけのメモリ量のスタックが使用されるのか、ということと関係があります。ほとんどの場合では、末尾再帰呼び出し時ヒープ上に割り当てられるメモリ量よりも、再帰関数呼び出してスタック上に確保されるメモリ量の方が多くなります。より多くのメモリが使用されると、ガーベジコレクタの起動回数は増えますし、スタックをたどる動作が大変になります。
R12B以降のリリースでは、本体再帰呼び出しのほとんどの場合において、スタック上で使用するメモリ量を減らすように最適化するようになりました。そのため、リストを本体再帰して処理する関数を使用する場合と、末尾再帰関数を実行して最後にlists:reverse/1を実行する場合では、同じ量のメモリを使用するようになりました。現在では、lists:map/2, lists:filter/2, リスト内包表記、その他の多くの再帰関数は、末尾再帰を使用した場合と、同じメモリ量で動作するようになっています。
それでは、最終的にどちらが速いと言えるのでしょうか？
それは状況に依存します。Sparc上で動作しているSolarisで、リスト中の要素が極めて多い場合には、本体再帰関数の方が速くなります。x86アーキテクチャでは、末尾再帰のほうが30%ほど高速です。
そのような状況なので、現在ではどちらを選択するかは好みの問題でしかありません。もし最大限の速度が必要ということであれば、どちらの方がすぐれているか測定してみるしかありません。どんな状況においても、末尾再帰のリスト処理の関数の方が確実に最速であるということは、もはや言うことはできません。
Note
もしも末尾再帰関数がtermをまったく作成しないという条件で、かつ、処理の後でリストを反転させる必要がなければ、もちろん末尾再帰関数の方が本体再帰関数よりも高速になります。実例で言えば、リスト中の数値を足していくような関数がこれにあたります。
++演算子には、大げさに言うと、とても悪いうわさが付いて回っています。これはおそらく、以下のようなコードに関するものです。
非推奨:
naive_reverse([H|T]) ->
naive_reverse(T)++[H];
naive_reverse([]) ->
[].
これは、リストを反転させる方法としては、もっとも非効率的な方法です。++演算子は左側のオペランドのコピーを作成し、結果もまたコピーされ、そしてそれもコピーされて・・・と、N^2のオーダーでの非効率が発生するというのがその理由です。
一方以下のようなケースで ++ 演算子を利用するのは問題ありません。
OK:
naive_but_ok_reverse([H|T], Acc) ->
naive_but_ok_reverse(T, [H]++Acc);
naive_but_ok_reverse([], Acc) ->
Acc.
この場合は、リストの要素ごとに1度だけコピーされます。結果を結合するときに、徐々に結果が大きくなっていく側の Acc は ++ 演算子の右側のオペランドであるため、これに含まれたものが何度もコピーされることはありません。
当然、経験のあるErlangプログラマは、実際には以下のように書くでしょう。
推奨:
vanilla_reverse([H|T], Acc) ->
vanilla_reverse(T, [H|Acc]);
vanilla_reverse([], Acc) ->
Acc.
この方法は、上記であげた良い例よりもさらに多少効率的です。というのは、コピーをしないでリストの要素を組み立てていっているからです。(もしくは、コンパイラが [H]++Acc を [H|Acc] へと自動で書き換えるようなことをしなかったため、より効率的でした。)
実際に適切でないやりかたで文字列を操作すると遅くなる可能性はあります。Erlangでは、文字列がどのように使用されているかについて考える必要があります。また、正規表現を使用しようと思ったときに、古くなったregexpモジュールではなくて、新しいreモジュールを使用するなどの配慮をする必要があります。
Detsファイルの修復時間は、ファイルに含まれるレコード数に比例しますが、以前の実装ではとてつもなく時間がかかっていました。その後、大幅に実装が書き換えられたため、性能は改善しています。
BEAMはレジスタベースの仮想マシンです。1024個の仮想レジスタを持ち、関数呼び出しがあった際に、引数を渡すために一時的に値を格納するために使用されています。関数呼び出しを実行する際に残す必要のある変数だけがスタックに保存されます。
BEAMはダイレクトスレデッドコード [1] という方法で高速化されており、命令分岐は非常に高速です。
| [1] | (訳注) インタプリタの最適化の手法の一つ。結果として命令キャッシュのヒット率が上がり、現代的な命令予測をするCPUでの実行効率が高まります。Rubyist Magazineに解説があります。 http://jp.rubyist.net/magazine/?0008-YarvManiacs |
これはかつての実装では正しい話でした。しかし、R6BのBEAMコンパイラからは、ほとんどのケースで、変数が使用されているか、そうではないのか、というのが検知できるようになっています。
Copyright (c) 1991-2009 Ericsson AB