テンプレートまたはフォークボムのコンパイル段階に関するいくつかの詳細

最近、ポジティブテンプレートのインスタンス化に興味を持ちました。 用語コード膨張はインターネットで使用されます 。 c ++の場合、これは、コンパイラーによって生成されるコードの制御できない増加を意味する場合があります。 新しい関数のインスタンス化は、引数をより便利な型に変換するよりも優先順位が高いため、コードは増加します。 つまり テンプレートT foo（T a）; for intとcharは2つの異なる関数です。 1つの関数は、テンプレートを拒否するか、明示的な型変換を使用して取得できます。

しかし、問題を裏返し、最小限のコード行から可能な限り大きなサイズの実行可能ファイルを取得してみましょう。

結果はそれほど印象的ではありませんでした。60行のコードのうち53Mbしか得られませんでした。 そして、テストされた3つのコンパイラーのうちの1つのみで、数時間のコンパイルのコストがかかります。 14MBのボリュームの最大ボリューム/ライン比は2.3MB /ラインです。

どのように、そしてなぜそれが起こったのか。

資源

4GBのメモリを搭載したラップトップ1台、

Intel®Core（TM）i3-2330M CPU @ 2.20GHzプロセッサー、

Linux OS 3.7.3-101.fc17.x86_64

無効化されたスワップパーティション。

フォークの爆弾が投稿タイトルに登場したのと同じ理由で、スワップを無効にする必要がありました。 タスクのボリュームが十分に大きいため、コンパイラはすべてのメモリを消費し、ディスクとの積極的な交換を開始しました。これにより、マシンがしっかりと永続的にハングしました。



コンパイラーのバージョン：

• g ++（GCC）4.7.2 20120921（Red Hat 4.7.2-2）
  
  
• インテル®C ++インテル®64、バージョン13.1.1.163ビルド20130313で実行されるアプリケーション用のインテル®64コンパイラーXE
  
  
• clangバージョン3.3（トランク179304）
  
  

長い配列

最も簡単な方法は、コンパイル段階の配列とその上の文字列関数を整理することです。 このように：

template<long n> inline void nop(){nop<n-1>();asm("nop"); } template<> inline void nop<0>() {asm("nop");} int main(int argc, char ** argv) { nop<LVL>(); return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

その結果、main（）関数は空の無駄な nop操作で満たされる必要があります。



シーケンスnopのサイズは、再帰の深さによって理論的に決定されます。 g ++マナは、c ++ 11の最大深さが17および1024であることを示しています。

標準には特定の数値が見つかりませんでした。 再帰の最大の深さが実装によって決定されるという点だけが見つかりました。

4.7.1.14 for C ++ 03

4.7.1.15 for C ++ 11

これは経験により確認されました。 十分な大きさのLVLの場合、コンパイラーがクラッシュしました。 g ++やicpcが2 ^17に達するのとは異なり、2 ¹³でクラッシュしたclang ++に驚いた。



アセンブリは、チームによって実行されました。

  clang++ -DLVL=$(( 2**$n)) -o list$n ./list.cc -ftemplate-depth=3000000 -O$x g++ -DLVL=$(( 2**$n)) -o list$n ./list.cc -ftemplate-depth=3000000 -O$x icpc -DLVL=$(( 2**$n)) -o list$n ./list.cc -O$x
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

内に バイナリは、長期間にわたって連続的に収集されました。 各コンパイラ、最適化の各レベル。 アセンブリ結果はグラフに表示されます。 4つの画像列：

1. 使用済みメモリの時間依存。 これらのグラフは参照専用です。 コンパイル中、Xサーバーとブラウザーは機能しましたが、主な傾向は明らかです。
2. バイナリファイルのサイズ。 判明した最大値-14MB
3. 文字数。 inlineキーワードはコンパイラへの単なる推奨事項であるため、大きなNの場合、Nopsは通常の関数にグループ化されます。 それらは次のように計算されます。

    nm --demangle ./list$i|grep nop|wc -l
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

4. 正直なnopsの数。 逆アセンブラーから計算：

    objdump -d ./list$i|grep 'nop$'|wc -l
         
         
   
           
           
           
         
   
       
           
           
           
         
         
   
           
           
           
         
   
       
        

画像はクロムでのみ正しく拡大縮小するようです。

他のブラウザの場合 すべての画像を含むアーカイブへのリンク

2 ¹⁷個のicpcコンパイラの最大ファイルサイズは14MBです。 g ++の場合-12 MB。 両方ともO0。 最適化レベルO0はインライン置換を実行しないため、nop <long>文字の数はnop操作の数と一致します。

背の高い木

線形データ構造の場合、生成されるファイルのサイズは、少なくともデフォルトの最大再帰深度（clang ++の場合は256、g ++の場合は900）に制限されます。 それを回避するには、ツリーを作成してみてください。 コンパイルステージツリーの理論上の最大の深さは（sizeof（long）-1）== 63です。また、2 ⁶⁴バイトがディスクをオーバーフローさせます。 実際的な制限ははるかに少ないです。

ツリーを使用して、再帰の最大深度を超えません。

ソースコードは19行で、次のようになります。

 #ifndef LVL # define LVL 3 #endif long x = 0; template<int N=LVL, long I=0> struct foo{ inline static double bar(double m) {x++;return foo<N-1,I>::bar(m) + foo<N-1,((1<<(LVL-N))|I)>::bar(m) + I;}; }; template<long I> struct foo<0,I>{ inline static double bar(double m) {x++; return m;} }; #include <iostream> int main(int argc, char **argv){ double ret = foo<>::bar(argc); std::cout << x << " " << ret << std::endl; return int(ret); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

結果はツリーであり、その各ノードには独自のタイプがあります。 各タイプは、数字のペアで特徴付けられます。

• N-レベル番号。
• Iはレベルのノード番号です。

1つのレベル内の各ノードには、0からNまでの番号が付けられます。



ここではnopを台無しにせず、追加を使用しました。 グローバルlong x-正しいアセンブリを制御するために使用されました。 その結果、2 ^{LVL + 1が}返されます。



アセンブリは、チームによって実行されました。

  clang++ -DLVL=$n -o fbomb$n ./fbomb.cc -O$x g++ -DLVL=$n -o fbomb$n ./fbomb.cc -O$x icpc -DLVL=$n -o fbomb$n ./fbomb.cc -O$x
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

上記と同じシナリオで。

clang ++の最大LVLは18でした。 g ++およびicpc-16の場合、オプション--std = c ++ 11が指定されたかどうかに関係なく。 コンパイラがメモリを使い果たしました。



画像はクロムでのみ正しく拡大縮小するようです。

他のブラウザの場合 すべての画像を含むアーカイブへのリンク



最大ファイルサイズ：

• icpc -O0 -DLVL = 17の場合は43 MB。
  
  
• clang ++の場合は42MB -O0 -DLVL = 17;
  
  
• g ++ -O0 -DLVL = 16の場合、22MB
  
  

明示的なインスタンス化

43MB-それほど小さくはありませんが、一定量のRAMでファイルをさらに大きくすることは可能ですか？ 可能になりましたが、3つのコンパイラーのうちの1つだけ-icpc。 このためには、外部テンプレートと明示的なインスタンス生成を使用する必要があります。

テンプレートのすべてのパラメーターがその説明に示されるように、ソースコードを少し変更します。 ソースコードを3つのファイルに分割します-テンプレートの説明、メイン関数、サブツリーの部分的なインスタンス化：

標準のバージョンに関係なく、メモリ不足と完全なインスタンス化により、g ++ -c main.cc -DLVL = 21がクラッシュすることが判明しました。 clang ++についても同じ状況です。 Icpcはmain.ccを1秒未満でコンパイルします。 ただし、サブツリーのコンパイルには4時間以上かかりました。

 for i in $(seq 0 31);do echo -n "$i:";date; icpc -O2 -c ./part.cc -o part21_16_$io -DLVL=21 -D_L=16 -D_I=$i;sleep 10; done
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リンクには1分もかかりませんでした。 結果は53MBのファイルです。 このファイルは-O2で作成されました。 -O0はサイズが大きくなりますが、結果の時間と意味がないため、何度も再構築しませんでした。



最初の部分（icpc -O0 list.cc）から配列の最大の比率のボリューム/行数= 2.3MB /行が取得されました

メトリックはもちろん冗談ですが、面白いです。 2.3-発生した最大値。 誰かがより大きな態度をとったかどうかを知りたいです。



私たち全員に幸運を。



Upd ：Stripは必要ありませんでしたが、必要です。 数キロバイトあると思いましたが、サイズの割合であり、かなり大きいことが判明しました。 ストリップ後、最大サイズは37MBに低下しました（53から）。 および8.6MB（14個から）。 したがって、比率は1.43MB /行です。