4

私は、製品の変更によるパフォーマンス関連の影響を測定するためのツールを構築しています。

これを実現するために、関数が呼び出されるか戻るたびにトレースし、それについて通知するプロファイラーを実装しました。まず、出力をファイルにダンプして、使用するデータの感覚をつかみました。多かれ少なかれ、次のようになります。

FuncCall1
   FuncCall2
      FuncCall3
      FuncRet3
      FuncCall4
      FuncRet4
      FuncCall5
        FuncCall6
        FuncRet6
      FuncRet5
    FuncRet2
FuncRet1

このデータがどのように見えるかを視覚的に理解するために、最初の 10000 回の関数呼び出しのグラフを次に示します: (x 軸: 時間、y 軸: 深さ/ネスト): 関数呼び出し/戻りグラフ( http://img444.imageshack.us /img444/4710/proflog.gif )

関数の実行が開始されると、その名前/識別子と現在の高精度のタイムスタンプがログに記録されます。関数が戻ると、開始時刻を保存したエントリを検索し、戻りをマークする新しいタイムスタンプを追加する必要があります。

要約すると、これらのデータに対して実行する操作は次のとおりです。

  1. 現在のタイムスタンプを持つ新しい関数呼び出しマークを挿入します。
  2. 特定の ID の最新の関数呼び出しを検索し、返されたタイムスタンプを保存します。
  3. 特定の関数内から呼び出された他の関数を確認します (そして、その時間が費やされている場所を確認します)。たとえば、前の例で関数 #2 を見ている場合、関数 #3、関数 # 4、Function#5 と Function#5 は Function#6 を呼び出し、それから戻ります (すべての呼び出し/戻りタイムスタンプがマークされています)。

さて、このシナリオに適したデータ構造のアイデアがいくつかあります。

  1. 各ノードのキーが関数識別子になり、各ノードの値がタイムスタンプ ペアのスタックになる自動バランス ツリー (AVL)。このアプローチにより、関数のタイムスタンプをマークするときに挿入と検索が高速になり、各ノードがスタックであるという事実が得られます。また、正しいリターン タイムスタンプを開始タイムスタンプに一致させることもできます。特定の関数は、最もネストされた/最近の関数呼び出しと一致する必要があります。このアプローチでは、ネストされた関数呼び出しを異なる識別子で維持するのは少し面倒です。なぜなら、ツリーを走査し、タイムスタンプに基づいて一致させてネストを把握する必要があるためです。理想的ではありません。

  2. まだ返されていない関数のリストを維持し (呼び出しスタック情報を保持します)、各レベルが関数呼び出しの入れ子レベルと同じになるスキップ リストを使用します。このアプローチにより、操作 #3 が簡単になりますが、ルックアップは遅くなり、返されない関数 (main() など) の非常に長いリストを維持する必要が生じる可能性があります。ここでは、ハッシュテーブルを使用して、メモリ使用量を犠牲にしてルックアップ速度を向上させることもできます。メモリ使用量は重要です。このプロファイラーは約 20 MB/秒を簡単に生成します。

これらのデータを追跡するために単純なスタックを使用しない理由は、定期的に部分的な結果を別のマシンに同期し、すべてが返される前に少なくとも部分的な結果を利用できるようにする必要があるためです。

インターバル ツリー、レンジ ツリー、およびその他の種類のデータ構造を調べましたが、私の 3 つの要件すべてを効率的に満たすものは見つかりませんでした。

たぶん、私が気付いていないすべてを満たすデータ構造があるのでしょうか? 何か案は？

アップデート：

これはどうですか：

ネストされた呼び出しと一緒に関数呼び出しを持つツリーと、返されなかった関数用の別のスタックを持つ。

これで、スタック上のすべての要素がツリー内のコピーへのポインターを持ち、新しい関数呼び出しが到着すると、スタックの一番上の要素を見て、ツリー内の表現へのポインターをトレースし、新しい関数呼び出しを追加します。その呼び出しの子として、新しく作成されたツリー ノードへのポインターを使用して、そのコピーをスタックにプッシュします。

関数の戻り値の場合も同様です。関数の戻り値ごとに、スタックの最新のエントリは常にその呼び出しになります。呼び出しポインターをトレースし、戻り時間をツリーに保存し、呼び出しをポップします。

私の考えに大きな欠陥はありますか？

更新 2:

私のアプローチは完璧に機能しました。2 日間待って、質問にお答えします。

4

3 に答える 3

1

トレースクラスを使用できます。欠点：ログに記録/測定する必要のある各関数の最初に、このトレーサーのインスタンスを宣言する必要があります。また、測定値にかなりの量のサイクルが追加されるため、このメソッドで適切にトレースできるのは巨大な関数のみです。

これを実現する別の方法は、実際のプロファイラーを作成することですが、そのようなツールはすでに存在し（gprof）、そのためのパーサーを作成します。それでもあなたはあなた自身を書くことができます...本当に長い仕事。

各関数またはグループを個別にテストすることをお勧めします。単体テストでは、これが通常の効率的な方法です。次に、プロファイラーをポップアップし、90％の時間実行している10％のコードを最適化しようとします。あなたはそれらを遠くに見ることによって細部に焦点を合わせています。

これが私のツールの1つのoutpuです：

2010年7月9日金曜日00:49:12-[3799946229640]-D：\ Code Project \ include / design / BTL / alarmithm / dispatch_policy.h :: operator（）＃| ... operator（）（）{

2010年7月9日金曜日00:49:12-[3799946246830]-D：\ Code Project \ include / design / BTL / alarmithm / dispatch_policy.h :: operator（）＃| ... shape *、shape *

2010年7月9日金曜日00:49:12-[3799946265738]-D：\ Code Project \ include / design / BTL / alarmithm / dispatch_policy.h :: operator（）＃| ...} operator（）：46027 cpu_cycles

上で述べたように、出力は巨大であり、深い分析には実用的ではありません。20Mb/ sの出力ストリームのため、プログラムを長時間監視することもできません。どこを調査すればよいかがすでにわかっている場合にのみ役立ちます。このようなツールに必要な理論上の帯域幅に関するもう1つの懸念事項は、バッファリングされたostreamを使用する必要があることです...ツールを実際のソフトウェアにさらに煩わしくします。私はすでにx10の減速を経験しました！

于 2012-05-28T22:54:15.980 に答える
1

1 つのスレッドの観点から見ると、最も効率的なのは、重大な侵入型のデータ構造を持つことだと思います。コール スタックと AVL ツリーを組み合わせると、次のようになります。

// one of these per call
struct {
    function *func; // func in the tree (or ID)
    timestamp time; // timestamp of call
    call *prev_call; // previous function call
    call *next_call; // next function call
} call;

// one of these per function
struct {
    call *last_call; // last call of this function
    your_type id; // identifier

    // insert tree-specifics here
} function;

私はこれを完全に解決していませんが、これが進むべき道だと思います。

于 2012-05-28T22:37:42.950 に答える
-1

木のアイデアは...無駄に思えます。

あなたがしていることには、単純なスタックが必要です。

  • ID/エントリのタイムスタンプ ペアをログに記録する
  • 子呼び出しを実行する
  • スタックのトップ エントリを終了タイムスタンプで変更する

また、すべての子呼び出しは、実際には同じ親の子です...

あなたの立場では、私は単に使用します：

  • 自動終了タイムスタンプ ロギング用の RAII
  • deque高速にレコードを追加するための のような構造

レコード構造は次のようになります。

struct Record {
    unsigned level;
    unsigned id;
    unsigned entry;
    unsigned exit;
};

次に、2 つのスレッド ローカル構造を保持します。

extern thread_local unsigned CurrentLevel;
extern thread_local std::deque<Record> CallRecords;

最後に、単純な RAII クラスを実装します。

class CallRecorder: boost::noncopyable() {
public:
    CallRecord(unsigned id):
        record(*CallRecords.insert(CallRecords.end(),
                                   Record{CurrentLevel++, id, time(), 0}))
    {
    }

    ~CallRecord() { record.exit = time(); --CurrentLevel; }

private:
    Record& record;
};

親の ID を各子呼び出しに渡すこともできますが、その価値はないようです。これは、ストリームを利用するときに再構築できる情報です (サイドに別のスタックを保持します)。

私は2つのメモしか持っていません：

  • 独自の実装を作成して、dequeより大きなチャンク (例では 4K ページ) を割り当て、何よりも追加を実際に最適化することをお勧めします。
  • RAII を使用して、通常の返品と例外の両方を処理します。プログラムabortが終了するため、ログに記録されません。不完全なトレースを残すため、検出できます。
于 2012-05-29T07:39:00.980 に答える