12

I have a friendly competition with couple of guys in the field of programming and recently we have become so interested in writing efficient code. Our challenge was to try to optimize the code (in sense of cpu time and complexity) at any cost (readability, reusability, etc).

The problem is, now we need to compare our codes and see which approach is better comparing to the others but we don't know any tools for this purpose.

My question is, are there some (any!) tools that takes a piece of code as input and calculates the number of flops or cpu instructions necessary for running it? Is there any tool can measure the optimacy of a code?

P.S. The target language is c++ but would be nice to know if such tools exists also for java.

4

7 に答える 7

12

これは、何かの時間を計る必要があるときにロールアウトするのが好きな小さな C++11 ストップウォッチです。

#include <chrono>
#include <ctime>

template <typename T> class basic_stopwatch
{
    typedef T clock;
    typename clock::time_point p;
    typename clock::duration   d;

public:
    void tick()  { p  = clock::now();            }
    void tock()  { d += clock::now() - p;        }
    void reset() { d  = clock::duration::zero(); }

    template <typename S> unsigned long long int report() const
    {
        return std::chrono::duration_cast<S>(d).count();
    }

    unsigned long long int report_ms() const
    {
        return report<std::chrono::milliseconds>();
    }

    basic_stopwatch() : p(), d() { }
};

struct c_clock
{
    typedef std::clock_t time_point;
    typedef std::clock_t duration;
    static time_point now() { return std::clock(); }
};

template <> unsigned long long int basic_stopwatch<c_clock>::report_ms() const
{
  return 1000. * double(d) / double(CLOCKS_PER_SEC);
}

typedef basic_stopwatch<std::chrono::high_resolution_clock> stopwatch;
typedef basic_stopwatch<c_clock> cstopwatch;

使用法：

stopwatch sw;
sw.tick();

run_long_code();

sw.tock();
std::cout << "This took " << sw.report_ms() << "ms.\n";

まともな実装では、デフォルトhigh_resolution_clockで非常に正確なタイミング情報が得られるはずです。

于 2012-09-09T16:40:14.897 に答える
3

std::clock()現在のプロセスに費やされた CPU 時間を返す関数があり<ctime>ます (つまり、CPU が他のタスクを実行していたため、プログラムがアイドル状態だった時間はカウントされません)。この機能を使用して、アルゴリズムの実行時間を正確に測定できます。戻り値を秒に変換するには、定数std::CLOCKS_PER_SEC(これも から) を使用します。<ctime>

于 2012-09-09T16:40:23.687 に答える
1

インライン アセンブリから、rdtsc 命令を使用して 32 ビット (最下位部分) のカウンターを eax に取得し、32 ビット (最上位部分) を edx に取得できます。コードが小さすぎる場合は、eax レジスタだけで適切な CPU サイクルの合計を確認できます。カウントが最大値を超える場合。32 ビット値の場合、edx は最大 32 ビット値サイクルごとにインクリメントします。

int cpu_clk1a=0;
int cpu_clk1b=0;
int cpu_clk2a=0;
int cpu_clk2b=0;
int max=0;
std::cin>>max; //loop limit

__asm
{
    push eax
    push edx
    rdtsc    //gets current cpu-clock-counter into eax&edx
    mov [cpu_clk1a],eax
    mov [cpu_clk1b],edx
    pop edx
    pop eax

}

long temp=0;
for(int i=0;i<max;i++)
{

    temp+=clock();//needed to defy optimization to  actually measure something
                          //even the smartest compiler cannot know what 
                          //the clock would be
}

__asm
{
    push eax
    push edx
    rdtsc     //gets current cpu-clock-counter into aex&edx
    mov [cpu_clk2a],eax
    mov [cpu_clk2b],edx
    pop edx
    pop eax

}
std::cout<<(cpu_clk2a-cpu_clk1a)<<std::endl;
   //if your loop takes more than ~2billions of cpu-clocks, use cpu_clk1b and 2b
getchar();
getchar();

出力: 私のマシンでは、1000 回の反復で 74000 cpu サイクル、10000 回の反復で 800000 cpu サイクル。clock() は時間がかかるためです。

私のマシンの CPU サイクルの解像度: ~1000 サイクル。はい、比較的正確に測定するには、数千回以上の加算/減算 (高速命令) が必要です。

CPU の動作周波数が一定であると仮定すると、1000 CPU サイクルは 1 GHz CPU の 1 マイクロ秒にほぼ等しくなります。これを行う前に、CPU をウォームアップする必要があります。

于 2012-09-09T18:45:13.083 に答える
0

CPU 命令の数を測定しても、ほとんど役に立ちません。

パフォーマンスはボトルネックに関連しています。目前の問題に応じて、ボトルネックはネットワーク、ディスク IO、メモリ、または CPU である可能性があります。

友好的な競争のために、タイミングをお勧めします。もちろん、これは、意味のある測定を行うのに十分な大きさのテストケースを提供することを意味します.

gettimeofdayUnix では、比較的正確な測定に使用できます。

于 2012-09-09T18:31:19.683 に答える
0

コードのブロックから CPU 時間の詳細な数値を計算するのは非常に困難です。これを行う通常の方法は、悪い / 平均 / 最良の入力データをテスト ケースとして設計することです。そして、これらのテスト ケースを使用して、実際のコードに基づいてタイミング プロファイリングを行います。詳細な入力テスト データと条件がない場合、フロップを教えてくれるツールはありません。

于 2012-09-09T16:39:39.570 に答える
0

あなたの目的に最適なのはvalgrind/callgrindです

于 2012-09-09T17:23:02.083 に答える
0

プロファイラーと呼ばれる、まさにあなたが望むことを行うソフトウェアがあります。

Windows の例は、AMD コード アナライザーとPOSIX のgprofです。

于 2012-09-09T16:41:15.323 に答える