インライン展開

コンピューティングにおいて、インライン展開、またはインライン化は、関数呼び出しサイトを、呼び出された関数の本体に置き換える手動またはコンパイラの最適化です。インライン展開はマクロ展開に似ていますが、コンパイル中に行われ、ソース コード (テキスト) は変更されません。一方、マクロ展開はコンパイル前に行われ、異なるテキストが生成され、その後コンパイラによって処理されます。

インライン化は重要な最適化ですが、パフォーマンスに複雑な影響を及ぼします。^[1]経験則として、ある程度のインライン化はわずかなスペースのコストで速度を向上させますが、過剰なインライン化は、インライン化されたコードが命令キャッシュを大量に消費し、かなりのスペースを消費するため、速度を低下させます。1980年代と1990年代のインライン化に関する控えめな学術文献の調査は、Peyton Jones & Marlow 1999に掲載されています。^[2]

インライン展開はマクロ展開に似ており、コンパイラは関数が呼び出される各場所に関数の新しいコピーを配置します。インライン関数は、関数呼び出しのオーバーヘッドが節約されるため、通常の関数よりも少し速く実行されますが、メモリのペナルティがあります。関数が 10 回インライン化されると、コードに挿入される関数のコピーが 10 個あります。したがって、インライン化は、頻繁に呼び出される小さな関数に最適です。C++ では、クラスのメンバー関数は、クラス定義内で定義されている場合、デフォルトでインライン化されます ( inlineキーワードを使用する必要はありません)。それ以外の場合は、キーワードが必要です。コンパイラは、特に大きい関数の場合、プログラマーによる関数のインライン化の試みを無視することがあります。

インライン展開は、関数が呼び出されたときの時間オーバーヘッド (余分な時間) を排除するために使用されます。これは通常、頻繁に実行される関数に使用されます。また、非常に小さな関数の場合はスペース上の利点があり、他の最適化を可能にする変換でもあります。

インライン関数がない場合、コンパイラがどの関数をインライン化するかを決定します。プログラマは、どの関数をインライン化し、どの関数をインライン化しないかをほとんど、またはまったく制御できません。プログラマにこの程度の制御を与えることで、アプリケーション固有の知識を使用して、どの関数をインライン化するかを選択できるようになります。

通常、関数が呼び出されると、分岐命令または呼び出し命令 によって制御がその定義に移されます。インライン化では、分岐命令や呼び出し命令を使用せずに、制御が関数のコードに直接渡されます。

コンパイラは通常、インライン展開を使用してステートメントを実装します。ループ条件とループ本体には遅延評価が必要です。このプロパティは、ループ条件とループ本体を計算するコードがインライン展開されると満たされます。パフォーマンスの考慮は、ステートメントをインライン展開するもう 1 つの理由です。

関数型プログラミング言語のコンテキストでは、インライン展開の後にベータ削減変換が続くのが一般的です。

プログラマーは、ソース コードに対する 1 回限りの操作として、コピー アンド ペースト プログラミングを通じて関数を手動でインライン化する場合があります。ただし、インライン化を制御する他の方法 (以下を参照) の方が望ましいです。これは、プログラマーがインライン化された関数のバグを修正する際に、元の関数本体の (おそらく変更された) 複製バージョンを見落とした場合に発生するバグを助長しないためです。

この最適化の直接的な効果は、呼び出しオーバーヘッドを排除することで時間パフォーマンスが向上することですが、スペースの使用量が悪化する^{[a] (関数本体の}複製による) という代償があります。単純なケースを除いて、関数本体の複製によるコード拡張が支配的であるため、^[b]インライン展開の直接的な効果は、スペースを犠牲にして時間を改善することです。

しかし、インライン展開の主な利点は、関数本体のサイズが大きくなることでさらなる最適化とスケジューリングの改善が可能になり、関数が大きくなるにつれてより優れた最適化が可能になることです。^{[3]インライン展開が速度に与える最終的な影響は複雑で、現代のプロセッサのパフォーマンスを左右するメモリシステム（主に}命令キャッシュ）のパフォーマンスにさまざまな影響が及ぶため、特定のプログラムとキャッシュによっては、特定の関数をインライン化することでパフォーマンスが向上したり低下したりすることがあります。^[1]

インライン化の影響は、抽象化の度合いが異なるため、プログラミング言語やプログラムによって異なります。CやFortranなどの低レベルの命令型言語では、通常、コードサイズへの影響はわずかで、速度が10～20%向上しますが、より抽象的な言語では、インライン化によって削除されるレイヤーの数が多いため、インライン化の影響は大幅に大きくなります。極端な例としてSelfがあり、あるコンパイラでは、インライン化によって4～55倍の改善が見られました。^[2]

関数呼び出しを排除することによる直接的な利点は次のとおりです。

• これにより、呼び出し元関数と呼び出し先関数の両方で関数呼び出しに必要な命令が削除されます。つまり、スタックまたはレジスタへの引数の配置、関数呼び出し自体、関数プロローグ、戻り時の関数エピローグ、return ステートメント、戻り値の取得、スタックからの引数の削除とレジスタの復元 (必要な場合) が削除されます。
• 引数を渡すためにレジスタを必要としないため、レジスタのスピルが削減されます。
• これにより、参照による呼び出し(またはアドレスによる呼び出し、共有による呼び出し)を使用するときに、参照を渡して逆参照する必要がなくなります。

しかし、インライン化の主な利点は、さらなる最適化が可能になることです。関数の境界を越えた最適化は、プロシージャ間最適化(IPO) を必要とせずに実行できます。インライン化が実行されると、拡大された関数本体で追加のプロシージャ内最適化 (「グローバル最適化」) が可能になります。例:

• 引数として渡された定数は、多くの場合、一致するパラメータのすべてのインスタンスに伝播されるか、関数の一部がループから「持ち上げられる」場合があります (ループ不変コードの移動経由)。
• レジスタの割り当ては、より大きな関数本体全体で行うことができます。
• エスケープ解析や末尾複製などの高レベルの最適化は、特にそれらの最適化を実装するコンパイラが主に手続き内解析に依存している場合は、より広い範囲で実行でき、より効果的です。^[4]

これらはインライン化せずに実行できますが、呼び出し元と呼び出し先が別々のコンパイル単位にある場合、かなり複雑なコンパイラとリンカーが必要になります。

逆に、言語仕様によっては、プロシージャがインライン化された後は実行できなくなるプロシージャへの引数について、プログラムが追加の仮定を行うことが許可され、一部の最適化が妨げられることがあります。よりスマートなコンパイラ ( Glasgow Haskell Compilerなど) はこれを追跡しますが、単純なインライン化ではこの情報が失われます。

メモリ システムのインライン化のさらなる利点は次のとおりです。

• 分岐を排除し、実行されるコードをメモリ内で近接して保持すると、参照の局所性（空間的局所性と命令の順序性）が向上し、命令キャッシュのパフォーマンスが向上します。これは、順序性を特に対象とした最適化よりも小さいですが、重要です。^[5]

インライン化の直接的なコストは、各呼び出しサイトで関数本体を複製するため、コード サイズが増加することです。ただし、常にそうなるとは限りません。つまり、非常に短い関数の場合、関数本体が関数呼び出しのサイズ (呼び出し元で、引数と戻り値の処理を含む) よりも小さい場合 (簡単なアクセサー メソッドやミューテーター メソッド(ゲッターとセッター) など)、または 1 か所でのみ使用される関数の場合は、重複しません。したがって、組み込みシステムでよくあるように、コード サイズを最適化する場合は、インライン化を最小限に抑えるか、または排除することができます。

インライン化は、コード拡張（重複による）によって命令キャッシュのパフォーマンスが低下するため、パフォーマンスにも悪影響を及ぼします。^[6]この問題は、拡張前はプログラムのワーキング セット（またはコードのホット セクション）がメモリ階層の 1 つのレベル（ L1 キャッシュなど）に収まっていたが、拡張後には収まらなくなり、そのレベルでキャッシュ ミスが頻繁に発生する場合に最も顕著になります。階層のさまざまなレベルでパフォーマンスに大きな差があるため、パフォーマンスが著しく低下します。最上位レベルでは、ページ フォールトの増加、スラッシングによる壊滅的なパフォーマンス低下、またはプログラムがまったく実行されなくなる可能性があります。この最後の問題は、コード サイズが使用可能なメモリに比べて小さい一般的なデスクトップおよびサーバー アプリケーションではまれですが、組み込みシステムなどのリソースが制限された環境では問題になる可能性があります。この問題を軽減する 1 つの方法は、関数を小さなホット インライン パス（高速パス）と大きなコールド非インライン パス（低速パス）に分割することです。^[6]

インライン化によるパフォーマンスの低下は、多くの場所で使用される大規模な関数で主に問題になりますが、インライン化によってパフォーマンスが低下する損益分岐点を特定することは難しく、一般的には正確な負荷に依存するため、手動の最適化やプロファイルに基づく最適化の対象となる可能性があります。^[7]これは、ループアンローリングなどの他のコード拡張最適化と同様の問題であり、ループアンローリングも処理される命令数を減らしますが、キャッシュパフォーマンスが低下するためにパフォーマンスが低下する可能性があります。

インライン化がキャッシュ パフォーマンスに及ぼす正確な影響は複雑です。キャッシュ サイズが小さい場合 (拡張前のワーキング セットよりはるかに小さい)、シーケンシャル性の向上が主となり、インライン化によってキャッシュ パフォーマンスが向上します。キャッシュ サイズがワーキング セットに近い場合、インライン化によってワーキング セットが拡張されてキャッシュに収まらなくなるため、これが主となり、キャッシュ パフォーマンスが低下します。キャッシュ サイズがワーキング セットより大きい場合、インライン化によるキャッシュ パフォーマンスへの影響はごくわずかです。さらに、ロード転送などのキャッシュ設計の変更によって、キャッシュ ミスの増加を相殺できます。^[8]

コンパイラは、さまざまなメカニズムを使用して、どの関数呼び出しをインライン化するかを決定します。これには、特定の関数に対するプログラマからの手動のヒントと、コマンドラインオプションによる全体的な制御が含まれます。インライン化は、インライン化が有益かどうかの判断に基づいて、多くの言語の多くのコンパイラによって自動的に行われますが、他の場合には、と呼ばれるキーワードまたはコンパイラディレクティブを使用して、コンパイラディレクティブによって手動で指定できます。通常、これはインライン化が必要であることを示唆するだけで、インライン化を要求するものではありません。ヒントの強さは言語とコンパイラによって異なります。 inline

通常、コンパイラ開発者は上記のパフォーマンスの問題を念頭に置き、ほとんどの場合、パフォーマンスを悪化させるのではなく向上させるために、どの関数をインライン化するかを選択するヒューリスティックをコンパイラに組み込みます。

コンパイラが特定の関数をインライン化することを決定したら、インライン化操作自体は通常簡単です。コンパイラがさまざまな言語のコード間で関数をインライン化するかどうかに応じて、コンパイラは高レベルの中間表現(抽象構文木など) または低レベルの中間表現のいずれかでインライン化を実行できます。どちらの場合も、コンパイラは引数を計算し、関数の引数に対応する変数に格納してから、呼び出しサイトに関数の本体を挿入します。

リンカーは関数のインライン化も実行できます。リンカーが関数をインライン化する場合、ライブラリ関数など、ソースが利用できない関数をインライン化することがあります (リンク時の最適化を参照)。ランタイムシステムも関数をインライン化できます。ランタイムインライン化では、 Java Hotspot コンパイラのように、動的プロファイリング情報を使用して、どの関数をインライン化するかをより適切に決定できます。^[9]

以下は、 C プログラミング言語のソース レベルで「手動で」実行されるインライン展開の簡単な例です。

int pred ( int x ) { if ( x == 0 )の場合は0を返します。それ以外の場合はx - 1を返します。}  

       
         
    
           

インライン化前:

int func ( int y ) {戻り値pred ( y ) + pred ( 0 ) + pred ( y + 1 ); }   

         

インライン化後:

int func ( int y ) { int tmp ; if ( y == 0 ) tmp = 0 ; else tmp = y - 1 ; /* (1) */ if ( 0 == 0 ) tmp += 0 ; else tmp += 0 - 1 ; /* (2) */ if ( y + 1 == 0 ) tmp += 0 ; else tmp += ( y + 1 ) - 1 ; /* (3) */ return tmp ; }   

     
                           
                         
                   
     

これは単なる例であることに注意してください。実際の C アプリケーションでは、パラメーター化されたマクロやインライン関数などのインライン言語機能を使用して、コンパイラにコードをこのように変換するように指示することが望ましいでしょう。次のセクションでは、このコードを最適化する方法を示します。

アセンブラ マクロは、インライン化の代替アプローチを提供します。これにより、通常は、マクロ展開によって、単一のマクロ ソース ステートメント (0 個以上のパラメータを持つ) から一連の命令をインラインで生成できます。パラメータの 1 つは、代わりに、シーケンスを含む 1 回限りの別のサブルーチンを生成し、関数へのインライン呼び出しによって処理するオプションである場合があります。例:

移動元=配列1、移動先=配列2、インライン=いいえ

インライン化には、さまざまなヒューリスティックが研究されてきました。通常、インライン化アルゴリズムには一定のコード バジェット (プログラム サイズの許容増加量) があり、そのバジェットを超えずに最も価値のある呼び出しサイトをインライン化することを目指します。この意味で、多くのインライン化アルゴリズムは通常、ナップサック問題に倣ってモデル化されています。^[10]どの呼び出しサイトがより価値があるかを判断するために、インライン化アルゴリズムはそれらの利点、つまり実行時間の予想される短縮を推定する必要があります。通常、インライナーは、さまざまなコード パスの実行頻度に関するプロファイリング情報を使用して利点を推定します。^[11]

プロファイリング情報に加えて、新しいジャストインタイムコンパイラは次のようないくつかのより高度なヒューリスティックを適用します。^[4]

• どのコード パスが実行時間を最大限に短縮するかを推測し (インライン化の結果として追加のコンパイラ最適化を有効にすることにより)、そのようなパスの認識される利点を高めます。
• コンパイル単位のサイズとすでにインライン化されているコードの量に基づいて、インライン化のコストあたりのメリットのしきい値を適応的に調整します。
• サブルーチンをクラスターにグループ化し、単一のサブルーチンではなくクラスター全体をインライン化します。ここで、ヒューリスティックは、クラスターの適切なサブセットのみをインライン化すると、何もインライン化しない場合よりもパフォーマンスが低下するメソッドをグループ化することによってクラスターを推測します。

インライン展開自体は、呼び出しのオーバーヘッドを排除するため最適化ですが、変換を可能にする点でさらに重要です。つまり、コンパイラが関数本体をその呼び出しサイトのコンテキストで展開すると (多くの場合、引数は固定定数になります)、以前は不可能だったさまざまな変換を実行できるようになります。たとえば、条件分岐は、この特定の呼び出しサイトでは常に true または常に false になる場合があります。これにより、デッド コードの削除、ループ不変コードの移動、または誘導変数の削除が可能になります。

前のセクションの C の例では、最適化の機会が豊富にあります。コンパイラは、次の手順に従います。

• tmp += 0(2) と (3) でマークされた行のステートメントは何も行いません。コンパイラはこれらを削除できます。
• 条件は0 == 0常に真なので、コンパイラは（2）でマークされた行を結果tmp += 0（何もしない）に置き換えることができます。
• コンパイラは条件y+1 == 0を に書き換えることができますy == -1。
• コンパイラは式(y + 1) - 1を に縮小できますy。
• 式yと はy+1両方ともゼロにはなりません。これにより、コンパイラは 1 つのテストを省略できます。
• などのステートメントでは、if (y == 0) return yの値はy本体でわかっており、インライン化できます。

新しい関数は次のようになります。

int func ( int y ) { if ( y == 0 )は0を返します。if ( y == -1 )は-2を返します。2 * y - 1を返します。}   

       
         
       
         
       

再帰のため、完全なインライン展開は常に可能であるとは限りません。再帰的にインライン展開すると、呼び出しは終了しません。制限された量を展開する、呼び出しグラフを分析して特定のノードでループを切断する（つまり、再帰ループ内の一部のエッジを展開しない）など、さまざまな解決策があります。^[12]マクロ展開でも、再帰展開が終了しないため、同様の問題が発生し、通常は再帰マクロを禁止することで解決されます（CおよびC++の場合と同様）。

従来、 Cなどの言語では、インライン展開はパラメータ化されたマクロを使用してソース レベルで実行されていました。 C99で使用できる真のインライン関数を使用すると、このアプローチに比べて次のような利点があります。

• C では、マクロ呼び出しでは型チェックは実行されず、引数が適切に構成されているかどうかもチェックされませんが、関数呼び出しでは通常、型チェックが行われます。
• C では、マクロは関数と同じ意味で return キーワードを使用することはできません (マクロではなく、展開を要求した関数を終了させます)。言い換えると、マクロは、その中で呼び出された最後の式の結果以外のものを返すことはできません。
• C マクロは単なるテキスト置換を使用するため、引数と演算順序の再評価によって、意図しない副作用や非効率が生じる可能性があります。
• マクロ内のコンパイラ エラーは、プログラマが入力したコードではなく、展開されたコードを参照するため、理解するのが難しいことがよくあります。したがって、インライン コードのデバッグ情報は、マクロ展開されたコードよりも通常は役立ちます。
• 多くの構造は、マクロを使用して表現するのが不自然または不可能であったり、大幅に異なる構文を使用したりします。インライン関数は通常の関数と同じ構文を使用し、簡単に自由にインライン化およびアンインライン化できます。

多くのコンパイラは、いくつかの再帰関数をインライン展開することもできます。^[13]再帰マクロは通常、違法です。

C++ の設計者であるBjarne Stroustrup は、マクロは可能な限り避けるべきだと強調し、インライン関数の広範な使用を推奨しています。

多くのコンパイラは、それが有益である場合には、積極的に関数をインライン化します。これにより実行可能ファイルが大きくなる可能性がありますが、メモリ容量が CPU 速度よりも速く増加するにつれて、積極的なインライン化がますます望ましいものになってきています。インライン化は、関数型言語やオブジェクト指向プログラミング言語における重要な最適化であり、これらの言語では、従来の最適化を効果的に行うために、通常は小さな関数に十分なコンテキストを提供するためにインライン化に依存しています。

Javaや関数型言語を含む多くの言語は、インライン関数のための言語構造を提供していませんが、それらのコンパイラやインタープリタは積極的なインライン展開を実行することがよくあります。^{[4]他の言語は、一般的にコンパイラ}ディレクティブ（プラグマ）として明示的なヒントのための構造を提供します。

Ada プログラミング言語には、インライン関数用のプラグマが存在します。

Common Lispの関数は次のように宣言することでインライン関数として定義できるinline: ^[14]

 ( declaim (インラインディスパッチ)) ( defun dispatch ( x ) ( funcall ( get ( car x ) 'dispatch ) x ))  
   
   
         

HaskellコンパイラGHCは十分に小さい関数や値をインライン化しようとしますが、インライン化は言語プラグマを使用して明示的に指定することができます。[ ^15]

key_function :: Int -> String -> ( Bool , Double ) {-# INLINE key_function #-}       

CとC++には、インライン化が有益かもしれないというヒントとなるキーワードがありますinlineが、新しいバージョンでは、その主な目的は関数の可視性とリンク動作を変更することです。^[16]

• マクロ
• 部分的な評価
• 末尾呼び出しの除去
• コードのアウトライン

無料の辞書であるウィクショナリーで、インライン展開 またはインライン化を調べてください。

• 「C++ プログラムにおける仮想関数呼び出しの排除」、Gerald Aigner とUrs Hölzle著
• 「C++ プログラムにおける間接関数呼び出しのオーバーヘッドの削減」Brad Calder と Dirk Grumwald 著
• ALTO - DEC Alpha のリンク時間最適化ツール
• 「上級テクニック」ジョン・R・レバイン著
• Brandon Bray 著「Visual C++ .NET によるプログラム全体の最適化」