C ++コードの最適化に関するいくつかの考えとヒント





私はブログのためにずっと前にこの記事を書きましたが、現在は放棄されています。 私には非常に有用な情報が含まれているように思えるので、それをただ消してほしくありません。 何かがすでに古くなっている可能性が非常に高いかもしれませんが、彼らがこれを私に示してくれたら感謝します。



原則として、高速が必要な場合はC ++が使用されます。 しかし、C ++では、多くの労力をかけることなく、Python / Rubyよりも遅いコードを取得できます。 多数のAny-Lang対C ++比較が機能するのは、このコードです。



一般に、最適化には3つのタイプがあります。



  1. 既製のテスト済みの作業コードの最適化。
  2. 最初は最高のコードを書いています。
  3. 最適なデザインを使用するだけです。


プロジェクトが完了して使用された後にのみ、完成したコードの最適化に特別な注意を払う必要があります。 原則として、プロジェクトのごく一部で最適化が必要になります。 そのため、最初にプロセッサ時間のほとんどを消費するコード内の場所を見つける必要があります。 結局のところ、マシン時間の1%しか占めない場合、コードを500%でも高速化するポイントは何でしょうか? また、原則として、コードではなくアルゴリズム自体の最適化により、速度が大幅に向上することを覚えておく必要があります。 彼らが言うのは、このタイプのそれについてです:「時期尚早な最適化は悪」(c)。



2番目のタイプの最適化は、パフォーマンス要件を考慮したコードの初期設計です。 この設計は、早期の最適化ではありません。



3番目のタイプは、完全な最適化でさえありません。 むしろ、次善の言語構成の回避です。 C ++言語は非常に複雑であるため、C ++言語を使用するときは、使用するコードがどのように実装されているかを知る必要があります。 プログラマがプロセッサとオペレーティングシステムの機能を考慮する必要があるほど十分に低いです。



1. C ++言語の機能



1.1。 引数を渡す



引数を値ではなく参照またはポインターで渡します。 引数を値で渡すと、オブジェクトの完全なコピーが作成されます。 このオブジェクトが大きいほど、コピーする必要があります。 そして、クラスのオブジェクトがヒープにメモリを割り当てる場合、それは完全に災害です。 もちろん、単純型は値で渡すことができ、また渡す必要があります。 ただし、複雑なものは、参照またはポインタによってのみ渡す必要があります。



// ,    void func1(Foo foo) { } // ,    void func2(const Foo &foo) { }
      
      







1.2。 例外



必要な場合にのみ例外を使用してください。 実際、例外はかなり重いメカニズムです。 したがって、 goto



、入れ子になったループの終了などの代わりに使用しないでください。 簡単なルール:例外は例外的な状況でのみスローされます。 これは、彼らが完全に放棄される必要があるという意味ではありません。 例外の使用自体は、少量の追加コードのためにわずかなオーバーヘッドを与えます。 パフォーマンスに対する実際の影響は、誤用のみです。



1.3。 RTTI



高速を必要とするコードでは、RTTIを使用しないでください。 ほとんどのコンパイラ(またはすべて)のRTTIメカニズムは、文字列比較によって実装されます。 ほとんどの場合、これは重要ではありません。 ただし、コードには高速が必要な場合があります。 この場合、数値クラス識別子など、別のソリューションを考え出す必要があります。



1.4。 インクリメントとデクリメント



インクリメントとデクリメントのプレフィックス形式を使用します。 C ++開発者は、接頭辞形式( ++i



および--i



)のみを使用し、必要に応じて接尾辞形式( i++



)のみを使用する習慣を身に付ける必要があります。 後置形式は、オブジェクトが変更されるまで一時値を保存して返すことで実装されます。 もちろん、単純な場合、組み込み型の操作では、コンパイラーはコードを最適化し、一時変数を作成せずに実行できます。 ただし、カスタムクラスの場合、おそらく最適化されません。



1.5。 一時オブジェクトを作成しないでください-1



たとえば、次のコードを使用して一時オブジェクトが作成されます。



 std::string s1, s2, s3; ... std::string s = s1 + s2 + s3;
      
      





この場合、2つの追加の一時オブジェクトが作成されstd::string tmp1 = s1 + s2;



およびstd::string tmp2 = tmp1 + s3;



。 正しい文字列連結は次のようになります。



 std::string s1, s2, s3; ... std::string s = s1; s += s2; s += s3;
      
      





1.6。 一時オブジェクトを作成しないでください-2



変数はどこでも宣言できます。 また、この変数が複雑なオブジェクトである場合、必要のない場所で宣言しないでください。 例:



 void foo(int x) { int a, b, c; std::string s; //      return if( x == 0 ) return; ... }
      
      





1.7。 メモリー予約



前の例(セクション1.5)に戻ると、絶対的に正しい連結方法は次のようになります。



 std::string s1, s2, s3; ... std::string s; s.reserve( s1.size() + s2.size() + s3.size() ); s += s1; s += s2; s += s3;
      
      





メモリ割り当て操作は非常に高価です。 また、 reserve



を呼び出して以前に一度割り当てたことがあるため、プロセッサ時間を大幅に節約できます。 STLの場合、これはvector



クラスとstring



クラスに適用されます。



1.8。 不要な作業は一切避けてください。



このアドバイスは初心者向けの本の中にあるように思え、C ++の基本的な理解で十分に理解できるはずです...しかし、経験の浅いプログラマーの中にはこれにつまずく人もいます。



 std::string s = ""; // 1 s = ""; // 2
      
      





1行目では、コンストラクタstd::string(const char *)



が呼び出されますが、これは文字列が空であることを認識しません。 彼は、その長さを把握し、メモリ割り当てとコピーサイクルを実行し、メモリハンドラを低くするなどを試みます。これは、単なるコストよりも高価です。



 std::string s; //   
      
      





2行目も同じ状況です。 operator = (const char *s)



実行されますが、「プログラマー」が空の文字列を取得したかっただけでもありません。 単純な呼び出しの方が効率的です。

 s.clear(); //  
      
      





1.9。 for / whileループで関数を呼び出すコストを見積もります



STLを使用すると、道路の機能を呼び出すことを心配する必要がありません。



 std::vector<int> vec; ... for(size_t i = 0; i < vec.size(); ++i) { ... }
      
      





この場合、安いからです。 これは、次のコードと同等です。



 size_t size = vec.size(); for(size_t i = 0; i < size; ++i)
      
      





ただし、これは常にそうではありません。 C ++ 11以前の一般的な誤解は、プログラマがstd::list::size



から同じアルゴリズムの複雑さを期待していたことでしたが、多くの実装ではその複雑さはO(N)でした。 if( list.empty() )



を呼び出す代わりに、特にif( list.size() > 0 )



if( list.empty() )



、これは特に不快に見えました。



1.10。 リストまたは両端キューを配布できるベクターを使用しないでください



vector



コンテナは、連続した一連のバイトをメモリに格納するように設計されています。 したがって、新しい要素を追加するときに、十分なメモリがない場合、コンテナは新しいメモリを割り当て、古い場所から新しい場所にデータをコピーする必要があります。 これが頻繁に発生する場合、コードのパフォーマンスが大幅に低下する可能性があります。 vector



とは異なり、 list



またはdeque



コンテナはデータの連続したシーケンスを保存しないため、コピーは必要ありません。



一方、事前バックアップでvector



を使用する(つまり、必要なすべてのメモリを1回割り当てる)ことは、最も高速で経済的な方法です。 list



またはdeque



場合、メモリの小さなチャンクが何度も割り当てられるためです。 コンテナを選択するときは、コンテナで実行される操作を正確に検討する必要があります。



1.11。 リンクまたはポインター?



ポインターではなくリンクを使用してみてください。 リンクにはチェックは不要です。 リンクはオブジェクトを直接指し、ポインターには読み取るアドレスが含まれています。



1.12。 コンストラクター初期化リスト



コンストラクター初期化リストの変数を初期化します。 それ以外の場合、最初に初期化され、次に値が割り当てられます。



 //   class Foo { public: Foo() { a = 0; //  a    s = "string"; //     } private: int a; std::string s; }; //   class Foo { public: Foo() : a(0), s("string") //    {} private: int a; std::string s; };
      
      





2.コンパイラ



コンパイラは、さまざまな最適化を実行できます。 時々彼は助けられるべきです。 逆に、手動で最適化しようとすると、そのような「ヘルプ」なしではコンパイラがコードを最適化できないことがあります。



2.1。 展開サイクル



最新のプロセッサには複数の機能デバイス(ALUおよびFPU)が含まれており、命令を並行して実行できます。つまり、1つのクロックサイクルで1つのコアで複数の命令を実行できます。 したがって、サイクルの展開により、より少ないステップで操作を実行できます。 展開により、比較および条件付き遷移の数も削減されます。



 for(int i = 0; i < len; ++i) { sum += s[i]; }
      
      





のようなものに展開する必要があります



 if( len >= 4 ) { for(; i < len - 3; i += 4) { sum += s[i]; sum += s[i + 1]; sum += s[i + 2]; sum += s[i + 3]; } } switch(len % 4) { case 3: sum += s[i + 2]; case 2: sum += s[i + 1]; case 1: sum += s[i]; break; }
      
      





以下は、 switch



なしのアセンブラコードの一部です。



 .L5: movsx rdi, BYTE PTR [rbx+rax] movsx rdx, BYTE PTR [rbx+1+rax] movsx r11, BYTE PTR [rbx+2+rax] movsx r10, BYTE PTR [rbx+3+rax] movsx r9, BYTE PTR [rbx+4+rax] movsx r8, BYTE PTR [rbx+5+rax] add rsi, rdi movsx rdi, BYTE PTR [rbx+6+rax] add rsi, rdx movsx rdx, BYTE PTR [rbx+7+rax] add rax, 8 add rsi, r11 add rsi, r10 add rsi, r9 add rsi, r8 add rsi, rdi add rsi, rdx cmp rax, rcx jne .L5
      
      





この場合、増分は4バイトではなく、8バイトであることがわかります。 ループ内の追加条件またはループカウンターに影響する計算により、ループを拡張できなくなります。



コンパイラーはループの展開に独立して関与します。 これができるように彼は助けられるべきです。 また、小さなサイクルを1つにまとめることも望ましいことです。 ただし、条件またはサイクルの大規模なボディが存在する場合は、逆に、少なくとも1つのサイクルがコンパイラーによってデプロイされるように、いくつかのサイクルに分割することをお勧めします。



2.2。 コンピューティングの怠azine-1



条件&&



(論理AND)および||



(論理OR)コンパイラーは左から右に処理します。 論理ANDを計算するときに、最初の条件がfalseの場合、2番目の条件も計算されません。 したがって、論理ORでは、最初の条件が真の場合、2番目の条件を計算しても意味がありません。 以下に簡単な例を示します。



 const char *s; ... if( strlen(s) > 3 && s[0] == 'y' ) { ... }
      
      





最初の文字がyになるように、3文字以上の文字列が必要です。 同時に、 strlen(s)



は高価な操作であり、 s[0] == 'y'



は安価です。 したがって、それらを交換する場合は、おそらく文字列の長さを計算する必要はありません。



 if( s && s[0] == 'y' && strlen(s) > 3 ) { ... }
      
      





2.3。 レイジーコンピューティング-2



遅延計算は、 &&



または||



をオーバーロードするまで機能しません。 。 オーバーロードされた演算子は関数呼び出しです:



bool operator && (1, 2)







したがって、呼び出しの前にすべての引数を評価する必要があります。



2.4。 スイッチまたは場合?



可能な限り、 switch



を使用してみてください。 if



条件とは異なり、 switch



多くの場合、テーブルを介して最適化されます。 例:



 int func(int i) { if(i == 1 ) return 10; else if( i == 2 ) return 20; else if( i == 3 ) return 30; else if( i == 4 ) return 40; else if( i == 5 ) return 50; return 100; }
      
      





で放送



 cmp edi, 1 mov eax, 10 je .L2 cmp edi, 2 mov al, 20 je .L2 cmp edi, 3 mov al, 30 je .L2 cmp edi, 4 mov al, 40 je .L2 mov al, 50 cmp edi, 5 mov edx, 100 cmovne eax, edx
      
      





そして、ここにコードがあります:



 int func(int i) { switch(i) { case 1: return 10; break; case 2: return 20; break; case 3: return 30; break; case 4: return 40; break; case 5: return 50; break; default: return 100; } }
      
      





で放送



 dec edi mov eax, 100 cmp edi, 4 ja .L10 mov eax, DWORD PTR CSWTCH.1[0+rdi*4] CSWTCH.1: .long 10 .long 20 .long 30 .long 40 .long 50
      
      





2.5。 インラインキーワード



このキーワードは、プログラムを高速化するために考案されたようです。 しかし、文字通りにそれを取りすぎて、各関数の前にinline



挿入する人もいます。 これにより、コードが膨張します。 コードが大きいほど、より多くのメモリ、特にプロセッサキャッシュ内のメモリが必要になります。 現代のコンパイラーは、長い間この言葉に注意を払うことをやめ、関数をインラインにするときとしないときを自分で決定しました。 しかし、プログラマーはまだ__forceinline



ようなものを挿入することでコードを膨張させようとします。 inline



は、本当に必要な場合にのみ使用してください。



2.6。 RVO-戻り値の最適化



この最適化により、C ++コンパイラが戻り値のコピーを作成できなくなります。 コンパイラはこの最適化を使用する必要があります。



 //   std::string foo() { std::string s = "string"; return s; //     RVO } //   std::string foo() { return std::string("string"); //    RVO }
      
      





したがって、1つの出口ポイントは、より美しいものの、あまり効果的ではありません。



 std::string bar(...) { std::string result; if( x ) { result = foo(); } return result; //   ,  RVO   } std::string bar(...) { if( x ) { return foo(); //    RVO } else { return std::string(); //    RVO } }
      
      





コンパイラーがNRVOを有効に活用することを学習したため、このアドバイスはその関連性をほとんど失い、再配置の可能性もあります。 ただし、NRVOが常に関与するとは限らず、すべてのオブジェクトに移動コンストラクターがあるわけではありません。



2.7。 構造の整列



クラスと構造体を宣言する際には、変数をサイズの降順に並べてみてください。 サイズが8バイト未満の変数をグループ化する場合は特に注意が必要です。 コンパイラは、最適化のために、変数のアドレスを整列します。これは、整列されたアドレスでlong



型の変数にアクセスするのにプロセッサクロックが1つしか必要ないためです。 一部のアーキテクチャでは、非境界整列アドレスでの読み取りは一般に不可能です。 大まかに言って、非境界変数はいくつかのメモリセルにあります。最初の部分と次の部分です。 したがって、この配置のおかげで、1バイトの変数は4または8バイトを取ります。 以下に例を示します。



 #include <stdio.h> class Foo { int a; char b; int c; char d; }; class Bar { int a; int c; char b; char d; }; int main() { printf( "%d - %d\n", sizeof(Foo), sizeof(Bar) ); return 0; }
      
      





私のマシンでは、出力は次のようになります。



 $ g++ test.cpp && ./a.out 16 - 12
      
      





アライメントは4バイトの境界に沿って実行されたことがわかります。 そして、まったく同じクラスのFoo



Bar



は、メモリ内で異なるサイズを占有します。 通常、これは無視できます。 ただし、クラスの数千のインスタンスを作成する場合は、 Bar



オプションが適しています。 もちろん、コンパイラ自体には変数を再配置する権利はありません。



もちろん、できるだけ密にパックするために、各変数のサイズを計算しないでください。 変数のサイズは、コンパイラ、コンパイルオプション、およびアーキテクチャによって異なる場合があります。 また、整列は、実際の必要なしに抑制されるべきではありません。



3.マルチスレッド



マルチスレッドコードを書くことは、同期オブジェクトを正しい場所に配置することではなく、同期を必要としないコードを書くことにあることを知っておくことが重要です。



3.1。 原子操作



一般に、カーネルへのほとんどすべてのアクセスは高価な操作です。 メモリと他の多くの課題の両方。 そのようなプログラムの呼び出しが少ないほど、より良い結果が得られます。 同期の場合、追加のオーバーヘッドにより、競合するときにコンテキストを切り替える必要が生じます。 したがって、多くの競合があり、ミューテックス/クリティカルセクションを使用して同期が実行される場合、オーバーヘッドは非常に深刻になる可能性があります。 そして、競争が激しくなればなるほど、彼らは大きくなります。 以下は、かなりよく知られているプログラム(執筆時点)のLinuxDC ++ / StrongDC ++およびおそらく同じコードに基づいた他の同様のプログラムの不良コードの例です。



 static long safeInc(volatile long& v) { pthread_mutex_lock(&mtx); long ret = ++v; pthread_mutex_unlock(&mtx); return ret; } static long safeDec(volatile long& v) { pthread_mutex_lock(&mtx); long ret = --v; pthread_mutex_unlock(&mtx); return ret; } static long safeExchange(volatile long& target, long value) { pthread_mutex_lock(&mtx); long ret = target; target = value; pthread_mutex_unlock(&mtx); return ret; }
      
      





このコードは、Linuxでのアセンブリ用にコンパイルされています。 ただし、Windowsの場合、コードは正しいです。



 static long safeInc(volatile long& v) { return InterlockedIncrement(&v); } static long safeDec(volatile long& v) { return InterlockedDecrement(&v); } static long safeExchange(volatile long& target, long value) { return InterlockedExchange(&target, value); }
      
      





違いは、Linuxではクリティカルセクションが使用され、Windowsでは重いmutexを必要としないアトミック操作が使用されることです。



3.2。 キャッシュライン



メモリの狭い間隔の領域への異なるスレッドのアクセスを許可しないようにしてください。 たとえば、次のような構造があります。



 struct Shared { int a; int b; int c; };
      
      





変数の1つにアクセスするスレッド。 スレッドが異なるコアで実行されると、 キャッシュラインピンポンと呼ばれるイベントが発生します。2つの異なるコアが互いの変更を確認する必要がある場合、キャッシュをフラッシュし、RAMからデータを要求する必要があります。 そのような場合、スレッドが共有データを必要とするとき、プロセッサのCache-Lineに適合する変数の間にメモリを挿入する必要があります。 難点は、各プロセッサのこのキャッシュラインのサイズが異なることです。 128バイトの値に焦点を当てます。



 struct Shared { int a; char pad1[128]; int b; char pad2[128]; int c; };
      
      





4.オペレーティングシステム



これは、よく使用される機能を理解している場合にのみ、下げるべきレベルです。 トラップは、最も予期しない場所に潜む可能性があります。



4.1。 記憶



頻繁なメモリ割り当てを避けるようにしてください。 これは非常に高価な操作です。 また、「100 MBを割り当てる」と「1 MBを割り当てる」の違いはわずかです。 したがって、OSカーネルにアクセスせずに大量のメモリを事前に割り当てて使用するように、コードを整理する必要があります。



メモリを頻繁に割り当てる必要がある場合、特に並列スレッドからのアクティブなメモリ操作の場合、標準ライブラリに組み込まれたアロケータは効率が悪いことに注意してください。 nedmallocTCMallocなどの代替アロケーター、またはBoost.Poolなどのメモリプールの使用を検討してください。



4.2。 I / Oバッファリング



read/write



ReadFile/WriteFile



などのシステムコールは、バッファリングを使用しません。 したがって、1バイトを読み取ると、データのブロック全体が読み取られ、そこから1バイトが返されます。 次のバイトを読み取るとき、同じブロックの読み取りが再び行われます。 同様に、書き込み時:1バイトを書き込むと、このバイトがすぐに書き込まれます。 非常に非効率的です。 したがって、たとえばfread/fwrite



などのバッファリングを提供する関数を使用する必要があります。



5.プロセッサー



5.1。 RAMはもはやRAMではありません



RAMはランダムアクセスメモリの略です。 ただし、これまでのところ、RAMを高速ランダムアクセスのソースとして使用しようとしても、良い結果にはなりません。 メモリへのアクセスには、プロセッサの数百クロックサイクルが必要だからです!



節約できるのはプロセッサキャッシュのみです。プロセッサキャッシュへのアクセスには、約12クロックサイクル( source )かかります。 このことから、必要なすべてのデータがプロセッサキャッシュに配置されるようにする必要があります。 これはプログラムのデータだけでなく、コード自体でもあります。 可能であれば、メモリへの順次アクセスを使用します。 ハッシュテーブルや連想構造などの構造を整理する場合、最大数がキャッシュに収まるように、キーに不要な情報を含めないでください。



5.2。 署名済みか未署名か?



ほとんどの場合、プログラマは変数に署名する必要があるかどうかを考えません。 たとえば、文字列の長さ-何かや他の多くの値の重量や価格のように、負の値にすることはできません。 おそらく、符号番号の値の範囲は目的の値を格納するには十分ですが、プロセッサの命令にはまだ違いがあります。 たとえば、このコードは次のとおりです。



 int func(int i) { return i / 4; }
      
      





で放送されます



 lea eax, [rdi+3] test edi, edi cmovns eax, edi sar eax, 2
      
      





そしてこれは:



 unsigned int func(unsigned int i) { return i / 4; }
      
      





はるかに短くなる:



 mov eax, edi shr eax, 2
      
      





符号なしの数値が優先される典型的な場所:除算と乗算、ループ内のカウンター、配列のインデックス。



浮動小数点データ型は符号なしにできません。 ただし、特別なプロセッサコマンドを使用します。



5.3。 枝



したがって、プロセッサパイプラインはパイプラインと呼ばれ、コマンドの連続ストリームを処理します。 プロセッサは、コマンドをノンストップでパイプラインに配信するため、あるコマンドを実行した後、すぐに別のコマンドの処理を開始します。 ただし、分岐が発生した場合、つまりif



... else



の条件では、プロセッサはif



またはelse



コマンドを使用する分岐を認識しませelse



。 したがって、彼はどちらが使用されるかを予測しようとしています。 予測でエラーが発生した場合、パイプラインがアイドル状態のときに、パイプラインデータをダンプして新しいコマンドをロードする必要があります。



これは、分岐予測子がプログラムが実行する分岐をより早く理解するほど、パイプラインがドロップされる可能性が低くなることを意味します。 通常、最も可能性の高いブランチを最初に(つまり、if条件に)配置することをお勧めします。



6.結論



そのため、この記事では、C ++コードを最適化するいくつかの方法を検討しました。 それらのいくつかがあなたにとって役に立つことを願っています。 記事に記載されていない他の方法を知っている場合は、コメントに書いてください!



最後に、さらに2つのヒントを示します。



  1. 既製のソリューションを優先します。 彼らはすでに検証されており、彼らのサポートと洗練に時間を浪費する必要はありません。彼らは他の人々の力によって発展し修正します。 自転車の発明は、自己開発には非常に優れていますが、集団開発には非常に悪いです。
  2. 高速ではなく、シンプルでわかりやすいコードを作成する方法についてもっと考えてください。 コードのシンプルさがはるかに重要です。



All Articles