9

量のベクトルを計算するアルゴリズム用に最適化されたコードを作成しました。関数で計算されたデータを関数から取得するさまざまな試行の前後に時間を計りました。計算の特定の性質や量のベクトルの性質は関係ないと思います。コード、タイミング、および詳細の概要は次のとおりです。

すべてのコードは、次のフラグを使用してコンパイルされました。

g++ -Wall -Wextra -Werror -std=c++11 -pedantic -O3

私はこのようなクラスを持っています:

#ifndef C_H
#define C_H

#include <iostream>
#include <iterator>
#include <vector>
Class c {
    public:
        void doWork( int param1, int param2 ) const {
            std::array<unsigned long,40> counts = {{0}};
            // LOTS of branches and inexpensive operations:
            // additions, subtractions, incrementations, and dereferences
            for( /* loop 1 */ ) {
                // LOTS MORE branches and inexpensive operations
                counts[ /* data dependent */ ] += /* data dependent */;
                for( /* loop 2 */ ) {
                    // YET MORE branches inexpensive operations
                    counts[ /* data dependent */ ] += /* data dependent */;
                }
            }
            counts [ /* data dependent */ ] = /* data dependent */;
            /* exclude for profiling
            std::copy( &counts[0], &counts[40], std::ostream_iterator( std::cout, "," ) );
            std::cout << "\n";
            */
        }
    private:
        // there is private data here that is processed above
        // the results get added into the array/vector as they are computed
};

#endif

そして、このようなメイン：

#include <iostream>
#include "c.h"
int main( int argc, char * argv ) {
    Class c( //set the private data of c by passing data in );
    int param1;
    int param2;
    while( std::cin >> param1 >> param2 ) {
        c.doWork( int param1, int param2 );
    }
}

データに関する関連する詳細を次に示します。

  • 標準入力で読み取られる 2,000 万ペア (ファイルからリダイレクト)
  • c.doWork への 2,000 万回の呼び出し
  • c.doWork の外側のループで合計 6,000 万回の反復
  • c.doWork の内部ループを介した合計 1 億 8,000 万回の反復

これらすべてを実行するには、正確に 5 分 48 秒かかります。当然、クラス関数内で配列を出力できます。それは私が行ってきたことですが、コードを公開するつもりです。使用例によっては、ベクトルを出力する以外のことをしたい場合があります。その場合、関数のシグネチャを変更して、実際にユーザーにデータを渡す必要があります。ここで問題が発生します。私が試したこと：

  • メインでベクトルを作成し、参照で渡します。

    std::vector<unsigned long> counts( 40 );
while( std::cin >> param1 >> param2 ) {
    c.doWork( param1, param2, counts );
    std::fill( counts.begin(), counts.end(), 0 );
}

    これには 7 分 30 秒かかります。std::fill の呼び出しを削除しても、これは 15 秒しか短縮されないため、不一致は考慮されません。

  • 移動セマンティクスを利用して、doWork 関数内でベクトルを作成し、それを返します。これには結果ごとに動的な割り当てが必要なため、これが高速になるとは思っていませんでした。奇妙なことに、それほど遅くはありません。7分40秒。

  • 現在 doWork にある std::array を値で返します。スタック配列は移動セマンティクスをサポートしていないため、当然、これはリターン時にデータをコピーする必要があります。7分30秒

  • 参照渡しで std::array を渡します。

    while( std::cin >> param1 >> param2 ) {
    std::array<unsigned long,40> counts = {{0}};
    c.doWork( param1, param2, counts )
}

    これはオリジナルとほぼ同じになると思います。データはメイン関数のスタックに配置され、参照によって doWork に渡され、doWork がデータを書き込みます。7分20秒。これは本当に私を困惑させます。

これは参照渡しと同等であるため、doWork にポインターを渡すことは試みていません。

1 つの解決策は、当然、関数の 2 つのバージョンを用意することです。1 つはローカルで出力し、もう 1 つは返すものです。ここでの障害は、すべてのコードを複製しなければならないことです。これは、関数から結果を効率的に取得できないことが全体の問題であるためです。

だから私は当惑しています。これらのソリューションのいずれも、doWork 内の配列/ベクトルへのアクセスごとに追加の逆参照が必要であることを理解していますが、これらの追加の逆参照は、他の膨大な数の高速操作や面倒なデータ依存ブランチと比較して非常に簡単です。

これを説明するアイデアを歓迎します。私の唯一の考えは、コードがコンパイラーによって最適化されているため、元のケースでは必要な計算コンポーネントが省略されているということです。コンパイラーはそれが不要であることを認識しているためです。しかし、これはいくつかの点で禁忌のようです。

  1. ループ内のコードを変更すると、タイミングが変更されます。
  2. 元のタイミングは 5 分 50 秒ですが、ファイルからペアを読み取るだけで 12 秒かかるため、多くのことが行われています。
  3. おそらく、カウントを含む操作のみが最適化されて取り除かれていますが、それらが最適化されて取り除かれている場合、doWork での計算のサポートも不要であることにコンパイラが気付く可能性があることを考えると、それは奇妙に選択的な最適化のように思えます。
  4. カウントを含む操作が最適化されている場合、他のケースでは最適化されていないのはなぜですか。私は実際にそれらをメインで使用していません。

doWork は main とは別にコンパイルおよび最適化されているため、関数が何らかの形式でデータを返す義務がある場合、それが使用されるかどうかは不明ですか?

さまざまな方法の相対的な違いを強調するために印刷のコストを回避するための、印刷しないプロファイリングの私の方法には欠陥がありますか?

あなたが放つことができるどんな光にも感謝します。

4

3 に答える 3

0

私がすることは、それを数回一時停止して、ほとんどの場合に何をしているかを確認することです. あなたのコードを見ると、a) 最も内側のループ、特にインデックス計算、または 2) std::array.

のサイズcountsが常に 40の場合は、

  long counts[40];
  memset(counts, 0, sizeof(counts));

それはスタックに割り当てられ、時間がかからず、memset他の何をしていても時間がかかりません。

実行時にサイズが変化する場合、次のような静的割り当てを行います。

void myRoutine(){
  /* this does not claim to be pretty. it claims to be efficient */
  static int nAlloc = 0;
  static long* counts = NULL;
  /* this initially allocates the array, and makes it bigger if necessary */
  if (nAlloc < /* size I need */){
    if (counts) delete counts;
    nAlloc = /* size I need */;
    counts = new long[nAlloc];
  }
  memset(counts, 0, sizeof(long)*nAlloc);
  /* do the rest of the stuff */
}

この方法countsは、常に十分な大きさであり、ポイントは、1)newできるだけ少ない回数で行い、2) 索引付けをcountsできるだけ単純に保つことです。

しかし、念のため、最初に一時停止を行います。それを修正した後、次に何が修正できるかを確認するためにもう一度やり直しました。

于 2013-04-28T22:13:20.513 に答える
0

非正統的な解決策が適用される場合があり、これはその 1 つかもしれません。配列をグローバルにすることを検討しましたか?

それでも、ローカル変数の重要な利点の 1 つは、オプティマイザーが関数からの情報のみを使用して、ローカル変数へのすべてのアクセスを見つけることができることです。これにより、レジスタの割り当てが非常に簡単になります。

static関数内の変数はほぼ同じですが、あなたの場合、そのスタック配列のアドレスがエスケープされ、オプティマイザーが再び打ち負かされます。

于 2013-04-29T00:04:35.880 に答える
0

コンパイラの最適化は注目すべき 1 つの場所ですが、もう 1 つ注目すべき場所があります。コードに加えた変更により、キャッシュ レイアウトが乱れる可能性があります。アレイに割り当てられたメモリが毎回異なるメモリ部分にある場合、システムのキャッシュ ミスの数が増加し、パフォーマンスが低下する可能性があります。CPU のハードウェア パフォーマンス カウンターを調べて、より正確に推測できます。

于 2013-04-28T22:14:21.187 に答える