4

私のコードには、1 億回反復するループがあります (シミュレーション モデルの 1 億回の複製に必要)。1 億回の反復ごとに、myarrayという名前の整数変数にインデックスを付けて、配列 ( )から値を取得しますage。配列の長さのため、 のインデックス付けのみが有効myarray[age]ですage=0,...,99。ただし、実際のドメインageは0,...,inf.

だから、私は次の機能を持っています

int tidx(const int& a) {
    return std::min(a,99);
}

による索引付けを可能にしmyarray[tidx(age)]ます。

どうすればこれをより効率的に行うことができますか?

[以下のパフォーマンス出力]

私が使用しているコンパイラ フラグを示すソース ファイルを作成する例:

Building file: ../SAR.cpp
Invoking: GCC C++ Compiler
g++ -O3 -Wall -c -fmessage-length=0 -Wno-sign-compare -fopenmp -MMD -MP -MF"SAR.d" -MT"SAR.d" -o"SAR.o" "../SAR.cpp"
Finished building: ../SAR.cpp

に続いperf recordてperf report：

Samples: 280  of event 'cycles', Event count (approx.): 179855989                                                                                   
 24.78%  pc2  libc-2.17.so         [.] __GI_____strtod_l_internal
 11.35%  pc2  pc2                  [.] samplePSA(int, double, int, NRRan&)
  6.67%  pc2  libc-2.17.so         [.] str_to_mpn.isra.0
  6.15%  pc2  pc2                  [.] simulate4_NEJMdisutilities(Policy&, bool)
  5.68%  pc2  pc2                  [.] (anonymous namespace)::stateTransition(double const&, int const&, int&, double const&, bool const&, bool&, bo
  5.25%  pc2  pc2                  [.] HistogramAges::add(double const&)
  3.73%  pc2  libstdc++.so.6.0.17  [.] std::istream::getline(char*, long, char)
  3.02%  pc2  libstdc++.so.6.0.17  [.] std::basic_istream<char, std::char_traits<char> >& std::operator>><char, std::char_traits<char> >(std::basic_
  2.49%  pc2  [kernel.kallsyms]    [k] 0xffffffff81043e6a
  2.29%  pc2  libc-2.17.so         [.] __strlen_sse2
  2.00%  pc2  libc-2.17.so         [.] __mpn_lshift
  1.72%  pc2  libstdc++.so.6.0.17  [.] __cxxabiv1::__vmi_class_type_info::__do_dyncast(long, __cxxabiv1::__class_type_info::__sub_kind, __cxxabiv1::
  1.71%  pc2  libc-2.17.so         [.] __memcpy_ssse3_back
  1.67%  pc2  libstdc++.so.6.0.17  [.] std::locale::~locale()
  1.65%  pc2  libc-2.17.so         [.] __mpn_construct_double
  1.38%  pc2  libc-2.17.so         [.] memchr
  1.29%  pc2  pc2                  [.] (anonymous namespace)::readTransitionMatrix(double*, std::string)
  1.27%  pc2  libstdc++.so.6.0.17  [.] std::string::_M_mutate(unsigned long, unsigned long, unsigned long)
  1.15%  pc2  libc-2.17.so         [.] round_and_return
  1.02%  pc2  libc-2.17.so         [.] __mpn_mul
  1.01%  pc2  libstdc++.so.6.0.17  [.] std::istream::sentry::sentry(std::istream&, bool)
  1.00%  pc2  libc-2.17.so         [.] __memcpy_sse2
  0.85%  pc2  libstdc++.so.6.0.17  [.] std::locale::locale(std::locale const&)
  0.85%  pc2  libstdc++.so.6.0.17  [.] std::string::_M_replace_safe(unsigned long, unsigned long, char const*, unsigned long)
  0.83%  pc2  libstdc++.so.6.0.17  [.] std::locale::locale()
  0.73%  pc2  libc-2.17.so         [.] __mpn_mul_1

からperf stat:

 Performance counter stats for './release/pc2':

         62.449034 task-clock                #    0.988 CPUs utilized          
                49 context-switches          #    0.785 K/sec                  
                 3 cpu-migrations            #    0.048 K/sec                  
               861 page-faults               #    0.014 M/sec                  
       179,240,478 cycles                    #    2.870 GHz                    
        58,909,298 stalled-cycles-frontend   #   32.87% frontend cycles idle   
   <not supported> stalled-cycles-backend  
       320,437,960 instructions              #    1.79  insns per cycle        
                                             #    0.18  stalled cycles per insn
        70,932,710 branches                  # 1135.850 M/sec                  
           697,468 branch-misses             #    0.98% of all branches        

       0.063228446 seconds time elapsed

コメントをいただければ幸いです。この情報を解釈/読み取る方法を学ぶ必要があるため、始めるのに役立つヒントがあれば幸いです.

4

5 に答える 5

10

コードを最適化するには、まずどこがボトルネックなのかを突き止める必要があります。ボトルネックを見つけるには、コードをプロファイリングする必要があります。そうしないと、まったく問題のないマイクロ/誤った最適化を行うだけで多くの時間が無駄になります。

私はあなたの最小限の作業コード例 (あなたが提供していない) でプロファイラーを使用していませんが、私の経験に基づいてこれを伝えることができます — あなたの関数はボトルネックではなく、 intidx()のパフォーマンスに関心を持つべきではありません std::min()この場合。ボトルネックがメモリ アクセスとストールした CPU サイクルである可能性が非常に高くなります。

手始めに、可能であればループを展開してみてください (コンパイラがそれを行っていない場合)。100000000 回よりも 25000000 回の反復を実行する方が効率的かもしれませんが、1 つのループ サイクルでより多くの反復を実行できます。ただし、それを行う前に、ループの展開が役に立ち、害がないことを確認する必要があります。これは通常、プロファイリングによって行われるため、コードを最適化するには、まずどこがボトルネックであるかを突き止める必要があるという点に戻ります。ボトルネックを見つけるために...ああ、待って、ここで無限ループに陥りそうになりました。中止しています。

于 2013-05-24T18:03:03.543 に答える
3

多くの人が犯す最初の間違いは、コードをじっと見つめて何かに集中し、それをもっと速くできるかどうか疑問に思うことです。

2 番目の間違いはgprof、「ボトルネック」を見つけようとして実行することです。

確実に見つけることができる唯一の有用なgprofことは、コードが CPU バウンドであり、コンパイルしたコードで CPU バウンドである場合です。取り除ける関数呼び出しの問題を見つけるのは得意ではありません。自分が行っていることを知らなかった I/O の問題を見つけるのは苦手です。

多くの人がこの方法を使用していますが、その理由は次のとおりです。

于 2013-05-24T19:18:12.967 に答える
2

プロファイリングについては、すでに適切なアドバイスが提供されています。

min<T>(T x, T y)と同等でなければなりませんreturn (x < y)?x:y;

アセンブラーとしては、次のようになります。

mov    x, %eax
cmp    y, %eax
cmovg  y, %eax

またはそれらの線に沿った何か。gcc で -O2 を有効にすると、これらの 3 つの命令は確実にインライン化されます。

于 2013-05-24T18:46:50.343 に答える
2

最適化をオンにして、実行可能ファイルをプロファイリングすることを忘れないでください。パフォーマンス テストでは、最適化されていない実行可能ファイルを実行しても、パフォーマンス特性がまったく異なるため役に立ちません。

次に、非常に多くのルックアップを回避するために何ができるかを検討してください。少ない作業 (アルゴリズムの改善) を行うと、時間がかかりません。

また、Herb Sutter が好んで呼ぶように、「時期尚早のペシミゼーション」なしでコードを記述します。

定義: 時期尚早のペシミゼーションとは、必要以上に遅いコードを書くことであり、通常は不必要な余分な作業を要求することによって行われますが、同等に複雑なコードはより高速であり、指から自然に流れ出すはずです。

たとえば、インライン化が役立つ場合とそうでない場合がありますが、インライン化を妨げないようにコードを記述したい場合があります。後で、インライン化を強制または防止し、実行環境にとって何が優れているかを比較できます。また、おそらく int のような小さな型への参照を使用したくないでしょう。最適化がない場合、参照パラメーターはおそらくポインターを使用して実装されますが、現在、ポインターは通常 int よりも大きくて低速です。32 ビット ハードウェアでも、参照は int よりも高速ではありません。

int tidx(int a) {
    return std::min(a,99);
}

その後、他の最適化手法を試すことができます。独立したタスクは並行して実行されますか? あなたのデータ構造は、参照特性の局所性に優れていますか? 並行して実行する場合、偽の共有の影響を受けていますか? SIMD またはその他のデータ並列化を使用できますか? コンパイラの設定をいじったり、コードの特定の部分で特定の最適化を有効にしたりすることもできます。ハードウェアが異なれば動作が根本的に異なる可能性があるため、ここでテストのパフォーマンスが非常に重要になります。また、これらの種類の最適化のほとんどはコードを難読化するため、見返りがほとんどまたはまったくないためにその代償を払いたくありません。

于 2013-05-24T19:14:13.497 に答える
2

検討すべきいくつかのアイデア

  • 関数の生成されたアセンブリを確認します。最適ではないものにコンパイルされる場合とされない場合があります
  • 関数をより少ない回数呼び出す
  • 一度に 4 つ (または AVX では 8 つ) の値の最小値を計算するために SSE 命令を使用するように関数を書き直します。
  • 関数の呼び出し方法を再構築します。理想的には、コードが命令キャッシュから追い出されるほど呼び出しが離れていてはなりません。
  • int を const 参照で渡さないでください。その点は何ですか？int のコピーを渡すだけです。
  • エイリアシングまたは偽の共有が呼び出しサイトで速度を低下させる可能性があるかどうかを調べます。

しかし、実際には、それは非常に単純な機能です。その実装を見るだけで得られるものはあまりありません。私の提案のほとんどは、関数がどのように呼び出されるか、どこから呼び出されるか、いつ呼び出されるか、どのデータに対して呼び出されるかに関するものです。それらはおそらくあなたが見る必要があるものです。

于 2013-05-24T18:58:37.690 に答える