64ビット変数を使用したC ++での末尾再帰-パート1

今回は、C ++で反復関数と再帰関数を比較することにしたときに遭遇した問題を1つ紹介します。 再帰と反復の間にはいくつかの違いがあります：それらはこの記事で詳しく説明されています 。 Java、C、Pythonなどの汎用言語では、毎回新しいスタックフレームを割り当てる必要があるため、反復は反復と比較して非常に高価です。 C / C ++では、これらのコストは、最適化コンパイラにテール再帰を使用するように指示することで簡単に除去できます。 このような変換を実装するには、値を返す前の関数の最後のアクションが別の関数（この場合はそれ自体）を呼び出すことであることが必要です。 このようなシナリオでは、2番目のサブルーチンの先頭への無条件ジャンプは安全です。 命令型言語の再帰アルゴリズムの主な欠点は、末尾呼び出しを持つことが常に可能とは限らないことです。 各呼び出しでのスタック上の関数（および関連する変数、たとえば構造体）のアドレス用のスペースの割り当て。 再帰の深さが深すぎる場合、最大サイズの制限によりスタックオーバーフローが発生する可能性があり、これは通常、RAMの量よりも桁違いに小さくなります。



末尾再帰を学習するためのテストとして、Visual Studioで簡単なC ++フィボナッチ関数を作成しました。 仕組みを見てみましょう。

int fib_tail(int n, int res, int next) { if (n == 0) { return res; } return fib_tail(n - 1, next, res + next); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

値を返す前に末尾呼び出しを行うために、 fib_tail関数は最後のアクションとして自分自身を呼び出します。 生成されたアセンブラコードを見てみましょう。 これを行うには、/ O2最適化キーを使用してリリースモードでプログラムをコンパイルしました。 このコードは次のようになります。







あります！ 最後の行に注意してください。CALLステートメントの代わりにJMPを使用します。 この場合、末尾再帰が機能し、アセンブラレベルで反復関数になったため、関数にはスタックオーバーフローの問題はありません。



これでは十分ではなかったので、入力変数nを増やしてパフォーマンスを試すことにしました。 次に、関数で使用される変数の型をintからunsigned long longに変更しました 。 プログラムを再度実行すると、突然スタックオーバーフローが発生しました。 このバージョンの関数は次のようになります。

 typedef unsigned long long ULONG64; ULONG64 fib_tail(ULONG64 n, ULONG64 res, ULONG64 next) { if (n == 0) { return res; } return fib_tail(n - 1, next, res + next); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

生成されたアセンブラコードをもう一度見てみましょう。







予想通り、末尾再帰はここにはありませんでした！ 現在、予想されるJMPの代わりに、 CALLが使用されます。 一方、2つのバージョンの関数の唯一の違いは、2番目のケースでは、32ビット変数ではなく64ビット変数を使用したことです。 これに関連して、64ビット変数を使用するときにコンパイラが末尾再帰を使用しないのはなぜですか？



プログラムを64ビットモードでコンパイルし、その動作を確認することにしました。 生成されたアセンブリコード：







ここでテール再帰が再現されました！ 64ビットのレジスタ（rax、r8、rcx、rdx）のおかげで、呼び出された関数と呼び出された関数は共通のスタックを持ち、呼び出された関数は結果を呼び出し元関数内の呼び出しポイントに直接返します。



StackOverflow Webサイトで質問しました。問題はMicrosoft C ++コンパイラ自体にあるようです。 いずれかのコメントの著者は、この問題は他のC ++コンパイラでは見られないと述べていますが、自分で確認する必要があります。



GitHubにサンプルコードを投稿しました。コピーして、自分で実行してみてください。 RedditとStackoverflowで、VS2013 Community Editionでは説明した問題は発生しないと言われました。 VS2013 Ultimateで作業しようとしましたが、そこでも遭遇しました。 近日中に、GCCでコードをテストし、結果を比較しようとします。



GitHubのサンプルプロジェクトを参照してください。



特定のケースでコンパイラが末尾再帰を実装しない理由を突然理解する必要がある場合、私の調査があなたにとって役立つことを願っています。



じゃあね！



続き： habrahabr.ru/company/pvs-studio/blog/261029