3

を使用して 2D 配列を動的に割り当てる C++ で記述された再帰関数がありますnew。関数が全存続期間中にヒープとスタックに割り当てる総容量を測定するにはどうすればよいですか?

スタックを測定する方法の例(私のコードではありません)を次に示します。

unsigned int maxStackLocation ; 
unsigned int minStackLocation ; 
main () 
{ 
    //get the address of a local variable before calling Quicksort 
    //the stack grows down, so this is the max stack location 
    int localVariable;
    void *currPtrLocation = (void*)(&localVariable); 
    maxStackLocation = *(unsigned int *)(&currPtrLocation); 
    //we get the value for the minimum stack location in quicksort itself 
    //call quicksort 
    Quick (A, num); 
    space = maxStackLocation - minStackLocation;
} 
//some redundant function whose stack usage will be measured
void Quick (unsigned int A[], int num) 
{ 
    if (num <= 1) 
    { 
        //check the stack usage 
        //figure out where we are on the stack by looking at the byte  
        // address of the local variable 
        //we do this by making a pointer to a local variable, and then  
        //casting it to a integer 
        void *currPtrLocation = (void*)(&num); 
        unsigned int currStackLocation = *(unsigned int*)(&currPtrLocation); 
        if (currStackLocation < minStackLocation) 
            minStackLocation = currStackLocation; 
        return; 
    }
}

Edit
Borgleader は、私の最初の質問「最大容量関数がその全期間にわたってヒープとスタックに割り当てる」が正しくないことを指摘しています。「最大」を「合計」に変更しました。

4

3 に答える 3

7

実際、Valgrind は非常に正確な測定を行うことができます。必要なのは、関数を呼び出すできるだけ単純な例を書くことだけです。

たとえば、main()for-loop を使用して (関数に渡された)引数をstd::cout出力し、次の出力を生成するプログラム:

zaufi@gentop /work/tests $ valgrind --tool=drd --show-stack-usage=yes ./stack-usage-test-1
==26999== drd, a thread error detector
==26999== Copyright (C) 2006-2012, and GNU GPL'd, by Bart Van Assche.
==26999== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==26999== Command: ./stack-usage-test-1
==26999==
./stack-usage-test-1
==26999== thread 1 finished and used 11944 bytes out of 8388608 on its stack. Margin: 8376664 bytes.
==26999==
==26999== For counts of detected and suppressed errors, rerun with: -v
==26999== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

ご覧のとおり、唯一のスレッドがスタックでほぼ 12K を消費します。そして間違いなく、このスペースのほとんどmain(). より良い測定を行うには、ターゲット関数を別のスレッドで実行する必要があります。次のようにします。

#include <iostream>
#include <thread>

int main(int argc, char* argv[])
{
    auto thr = std::thread([](){std::cout << __PRETTY_FUNCTION__ << std::endl;});
    thr.join();
    return 0;
}

このコードは、次の出力を生成します。

==27029== thread 2 finished and used 1840 bytes out of 8384512 on its stack. Margin: 8382672 bytes.
==27029== thread 1 finished and used 11992 bytes out of 8388608 on its stack. Margin: 8376616 bytes.

それは間違いなく良いです。したがって、何もしない関数を測定すると、最小スタック使用量が得られます (最後の例では、約 1840 バイトです)。したがって、ターゲット関数を別のスレッドで呼び出す場合は、結果から 1840 バイト (またはそれ以下) を差し引く必要があります...


次の単純なアルゴリズムを使用して自分でできることとほぼ同じです。

  1. ヒープから 8M バッファを割り当てます (Linux/pthreads のデフォルトのスタック サイズですが、実際には他の (妥当な) サイズを割り当てることができます)
  2. パターンで埋める
  3. 割り当てられて埋められたばかりの領域にスタックが割り当てられた新しいスレッドをフォークしますpthread_attr_setstack()((または友人を使用して))
  4. そのスレッド内でターゲット関数を呼び出して終了できるとすぐに
  5. メインスレッドで、pthread_join()成功した後、バッファを分析して、以前に割り当てたパターンが保持されていない領域を見つけます

(でも)その場合、何もしないスレッドで最初の測定を行う方がよいでしょう-上記の最小使用サイズを取得するだけです。

于 2012-12-03T23:01:21.703 に答える
3

スタック使用量を測定するためのあなたの例はスポットオンであり、(ほぼ) 正しい答えが得られます。ヒープ使用量を決定するための提案もありますが、最初に....

彼の著書「より効率的な C++」の項目 27 で、Scott Meyers (ちなみに、C++ に関する私のお気に入りの著者) は、一般的な意味で、およびポータブルまたはセミポータブル C++ の範囲内で、オブジェクトが既に使用されているかどうかを明確に区別することができない理由を説明しています。スタック、ヒープに割り当てられるか、静的に割り当てられます。しかし、彼の説明は、オブジェクト自体の観点から割り当てられたオブジェクトに関するものであり、そのような割り当てを要求するコードの観点からの割り当てに関するものではありません。割り当てを要求するコードの観点からは、その割り当てを要求した方法に基づいて、その型に関係なく、オブジェクトがヒープまたはスタックに割り当てられているかどうかを確実に知ることができます。(サイドバー: もちろん、これは実際にランタイム スタックを使用しているシステムに依存します。C++ 標準が保証していないことをすぐに指摘する人もいますが、これらの標準スノッブのいずれも、ランタイム スタックを使用しない標準準拠の C++ コンパイラの実際の例を指摘することはありません。議論に戻ります...) 例えば:

int Fred;  // Fred is allocated on the stack
int *Barney = new int; // Barney is allocated on the heap

フレッドは範囲外に出ると破壊します。Barney を使い終わったら、明示的に Barney を削除する必要があります。これは、STL 型を含むユーザー定義型でも同じように機能します。

std::string Fred; // Fred is allocated on the stack (see disclaimer*)
std::string *Barney = new std::string(); // Barney is allocated on the heap

// *Disclaimer:  May not be totally true on some small embedded processors that
//               implement the runtime stack in a special small address space
//               separate from “normal” RAM.

...しかし: Fred として知られる std::string オブジェクト自体はスタックに割り当てられますが、もちろん、そのデータは可変長で、次のように無限に拡張できる必要があるため、そのデータをスタックに割り当てることはできません。それに文字を追加します。そのため、std::string の管理部分 (つまり、std::string オブジェクト自体) のみをスタックに割り当てることができます。

Scott Meyer の項目 27 と、この議論への適用性に戻ります。

myClass *someFunction() {
    int someInputParameter = 42;
    myClass Fred(someInputParameter); // Fred is allocated on the stack
    myClass *Barney = new myClass(someInputParameter); // Barney is allocated on the heap
    return Barney;
}

Scott Meyer の項目 27 によると、Fred も Barney も、自分がスタック割り当てかヒープ割り当てか、さらに言えば静的に割り当てられているか (つまり、「グローバル」または「ファイル スコープ」または「一部の静的メンバー」かどうかを自分で知ることはできません。他のクラス」)。しかし、 someFunction() 内では、割り当てをどのように要求したかがわかっているため、それを知ることができます。


さて、あなたの問題に戻ります:

私が言ったように、スタック使用量を測定するために示した例はスポットオンです。main() で、「localVariable」がスタックに割り当てられていることは確かです。そして、「currPtrLocation」がスタック上にあることは Quick() で確実にわかっています。また、スタックが減少した場合、main() が Quick() を呼び出すため、Quick() の「currPtrLocation」のアドレスが main() の「localVariable」のアドレスよりも低くなるため、算術演算が機能することが確実にわかります。 . 「currPtrLocation」よりも低いスタック位置に割り当てられている他の変数が Quick() にある可能性があるため、完全に正しい答えは得られませんが、測定値は非常に近くなります。確かにあなたが気にする必要があります。エラーの量がどうであれ、コール スタックの深さに関係なく固定エラーです。かなりの回数再帰を行うと、全体のパーセンテージとしてのエラーは無視できます。最後にもう 1 つ: スタックが大きくなるシステムにもソリューションを移植できるようにしたい場合は、「localVariable」と「currPtrLocation」のアドレスの差の方向を検出し、差を計算できます (つまり、引数を減算)に応じて。

ヒープ使用量について:

システムには、ヒープ使用統計を測定するために結び付けることができるフックがある場合がありますが、それを掘り下げたくない場合は、Synxis が提案したことに沿って何かを行うことができますが、その答えにはいくつかの深刻な問題があります。まず第一に、Synxis の提案では、重要ではない戻りアドレス、こぼれたレジスタなどを含むすべてのスタック オーバーヘッドが見落とされています。第二に、質問で示したようにスタック測定手法を使用する場合、スタック割り当てオブジェクトの割り当ての合計を苦労して維持する必要はありません。第 3 に、ヒープに割り当てられたオブジェクト (sizeof() 演算子で取得できるサイズ) の割り当てのみを合計すると仮定すると、単にそれらを合計し続けることはできません。「totalSize」がすべての合計サイズを維持するように、それらを削除するときに割り当てのサイズを差し引く必要があります現在割り当てられたオブジェクトであり、totalSize の最高水準点を個別に追跡する必要があります。そうすれば、アルゴリズムが一度に使用したメモリの最大量を知ることができます。そうしないと、RAM が 4G しかないにもかかわらず、アルゴリズムが 758 ギガバイトなどを使用したと報告されたときに混乱する可能性があります。最後に、特定のオブジェクト自体をスタックまたはヒープのどちらに割り当てる場合でも、ヒープ上で独自の内部割り当てを行う場合があります。(そのオブジェクトでメソッドを呼び出すときにスタックに一時的な割り当てを行う場合、そのメソッドにもスタック追跡コードを配置しない限り、スタックの合計は、既に説明したように正確ではありませんが、エラーはメソッドが呼び出し動作を変更する可能性のある条件を実行するかどうかに応じて、多かれ少なかれ一定であり続けます。)とにかく、スタックまたはヒープに割り当てるこの「特定のオブジェクト」に関して。独自の内部ヒープ メモリを割り当てる場合、内部オブジェクトにヒープ割り当て追跡を追加しない限り、それらの内部オブジェクトに割り当てられたヒープ メモリの量が失われます。そのため、システムで利用できるヒープ統計フックを調べたほうがよいでしょう。

ここで、ヒープ割り当てを自分で追跡したいと仮定すると... 別の選択肢として、作成するすべてのオブジェクトに対してアルゴリズムが派生できる基本クラスを作成することが考えられます。基本クラスは、基本クラスの静的クラス変数を使用して、基本クラス自体がすべての totalSize 追跡 (「new」の追加と「delete」の減算) を行うように operator new & operator delete をオーバーライドできます。

于 2012-12-03T21:22:01.343 に答える
1

プラットフォーム、呼び出し規約、最適化モードなどによって異なるため、正確な合計サイズを取得することはほとんど不可能です。ただし、見積もりを行うことはできます。呼び出された関数によって常に処理されるとは限らないため、パラメーターはカウントしません(呼び出し規約によって異なります)。

これを行うためのC++またはC機能はありません。
この番号を示すデバッガーはわかりません。私はValgrindとcoを使用したことがないので、この番号を表示できるかどうかはわかりません(表示されるとは思えません)
。最後のオプション:自分で数えてください...

unsigned int totalSize = 0;

int partition(unsigned int A[], int num, int left, int right, int pivot)
{
    /// UpdateTotalSize
    totalSize += sizeof(unsigned int);
    /// /UpdateTotalSize
    unsigned int value = A[pivot];
    A[pivot] = A[right];
    A[right] = value;

    /// UpdateTotalSize
    totalSize += sizeof(int);
    /// /UpdateTotalSize
    int store = left;

    for(int i = left; i < right; i++)
        if(A[i] < value)
        {
            // This variable does not count in the total size:
            // allocated, then deallocated, and so on...
            unsigned int tmp = A[i];
            A[i] = A[store];
            A[store] = tmp;
            store++;
        }

    /// UpdateTotalSize
    totalSize += sizeof(int);
    /// /UpdateTotalSize
    int tmp = A[store];
    A[store] = A[right];
    A[right] = tmp;
    return store;
}

void quick(unsigned int A[], int num, int left = -1, int right = -1)
{
    if(num <= 1)
        return;

    if(left <= -1)
        left = 0;
    if(right <= -1)
        right = right = num - 1;

    if(left >= right)
        return;

    /// UpdateTotalSize
    totalSize += sizeof(int);
    /// /UpdateTotalSize
    int pivot = (left + right) / 2;

    /// UpdateTotalSize
    totalSize += sizeof(int);
    /// /UpdateTotalSize
    int pivotNew = partition(A, num, left, right, pivot);

    quick(A, num, left, pivotNew - 1);
    quick(A, num, pivotNew + 1, right);
}

これは単なる合計サイズの見積もりであることに注意してください。また、この例では、精神的に行うことができます。

最後になりましたが、最適化がオンになっている場合、このカウントは信頼できないため、最適化なしでのみ使用してください。

于 2012-12-02T11:18:45.400 に答える