0

現在、valgrind/callgrind を使用して、さまざまなアルゴリズムの実装を測定および比較しています。アルゴリズムに 2 つの実装があり、処理チェーンが次のようになっているとします。

void main()
{
    //Procedure 1
    fun1();
    //Procedure 2
    fun2();
    //Procedure 3
    Algorithm_imp_1();  //Algorithm_imp_2(); 
   //Procedure 4
    fun4();
}

これら 2 つの実装の違いは、2 つの異なるアルゴリズムの実装が実行される 3 番目の手順にあります。どちらの実装が優れているかを確認するために、現在、kachegrind の助けを借りて valgrind/callgrind を使用しています。

私がイメージできる限り、Algorithm_imp_1()が よりも効率的である場合Algorithm_imp_2()、その 2 つの指標: 1 つはプログラムの実行に使用された絶対時間であり、もう 1 つは 3 番目の手順にかかる時間の割合であり、小さいはずです。ただし、valgrind で得たものは非常に紛らわしいです。

Method 1 whole procedure: overall circle 106858896849   
        Algorithm_imp_1():  circle 2971828457(3.03%)
Method 2 whole procedure: overall circle 137889090577
        Algorithm_imp_2(): circle 351826053(0.26%)

両方の方法の全体の手順は、3 番目の部分を除いて同じであるため、3 番目の部分の消費時間の割合が小さければ、プログラムの実行にかかる全体の時間も短くなるはずです。しかし、上記で観察したことは矛盾しています。私の分析の何が問題なのか疑問に思っていました。ありがとう！

4

1 に答える 1

1

シェルには組み込みtimeコマンドがあります。それを使用すると、壁時計だけでなく、ユーザー時間とシステム時間も表示されます。

linux> /bin/sh
$ time a.out
    0m1.01s real     0m0.00s user     0m0.00s system

0.01 秒よりも高い解像度が必要な場合は、 と を使用できgetrusageますgettimeofday。

関数をプロファイリングするときは、インストルメンテーションをできるだけ関数の近くに配置することをお勧めします。valgrind のようなものを使用すると、関数内で何が起こっているかが見えなくなる可能性が高くなります。

測定が有用であるためには、測定の信号対雑音比が高くなければなりません。

linux> cat a.c
#include <stdio.h>
#include <unistd.h>
#include <sys/time.h>
#include <sys/resource.h>

/*
 * Time elapsed in milli-seconds. Tweak this to get micro-seconds. 
 */

int
time_diff(struct timeval *t2, struct timeval *t1)
{
    int r;

    r = (t2->tv_sec - t1->tv_sec)*1000 + t2->tv_usec/1000 - t1->tv_usec/1000;

    return(r);
}

int
main()
{
    struct rusage r1, r2;
    struct timeval t1, t2;

    (void)gettimeofday(&t1, 0);
    (void)getrusage(RUSAGE_SELF, &r1);

    sleep(1); /* Function to be profiled. */

    (void)getrusage(RUSAGE_SELF, &r2);
    (void)gettimeofday(&t2, 0);

    printf("real = %d (ms), user = %d (ms), system = %d (ms)\n", 
            time_diff(&t2, &t1),
            time_diff(&r2.ru_utime, &r1.ru_utime),
            time_diff(&r2.ru_stime, &r1.ru_stime));

    return(0);
}

上記を実行すると、以下のようなものが表示されるはずです。

linux> a.out
real = 1000 (ms), user = 0 (ms), system = 0 (ms)
于 2012-12-19T22:23:16.057 に答える