Wie man die Leistung von zwei Stücken von Codes vergleicht

Question

Ich habe eine freundliche Konkurrenz mit ein paar Jungs im Bereich der Programmierung und vor kurzem haben wir so interessiert, effizienten Code zu schreiben. Unsere Herausforderung bestand darin, den Code (im Sinne von CPU-Zeit und Komplexität) um jeden Preis zu optimieren (Lesbarkeit, Wiederverwendbarkeit usw.).

Das Problem ist, jetzt müssen wir unsere Codes vergleichen und sehen, welcher Ansatz im Vergleich zu den anderen besser ist, aber wir kennen keine Werkzeuge für diesen Zweck.

Meine Frage ist, gibt es einige (alle!) Werkzeuge, die ein Stück Code als Eingabe und berechnet die Anzahl der Flops oder CPU-Anweisungen notwendig es für den Betrieb? Gibt es ein Tool kann die eines Codes messen?

P.S. Die Zielsprache ist C++, aber es wäre schön zu wissen, ob solche Tools auch für Java existieren.

Answer 1

Hier ist eine kleine C++ 11 Stoppuhr Ich mag heraus rollen, wenn ich zu Zeit etwas brauchen:

#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; 

Verbrauch:

stopwatch sw; 
sw.tick(); 

run_long_code(); 

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

Auf jeder anständige Implementierung der Standard high_resolution_clock geben sollte sehr genaue Zeitinformation.

Answer 2

Es ist ziemlich schwierig, die Detailierungsnummer der CPU-Zeit aus einem Codeblock zu berechnen. Der normale Weg dazu besteht darin, die schlechteren/durchschnittlichen/besten Eingabedaten als Testfälle zu entwerfen. Und machen Sie mit diesen Testfällen ein Timing-Profiling basierend auf Ihrem realen Code. Es gibt kein Tool, das Ihnen die Flops mitteilen kann, wenn es ohne die Testdaten und -bedingungen für die Detaileingabe ist.

Answer 3

Es gibt die std::clock()-Funktion von <ctime>, die zurückgibt, wie viel CPU-Zeit für den aktuellen Prozess ausgegeben wurde (dh, es zählt nicht die Zeit im Leerlauf des Programms, weil die CPU andere Aufgaben ausgeführt hat). Diese Funktion kann verwendet werden, um die Ausführungszeiten von Algorithmen genau zu messen. Verwenden Sie die Konstante std::CLOCKS_PER_SEC (auch von <ctime>), um den Rückgabewert in Sekunden umzuwandeln.

Answer 4

Es gibt Teile der Software namens profilers, die genau das tun, was Sie wollen.

Ein Beispiel für Windows ist AMD code analyser und gprof für POSIX.

Answer 5

Am besten für Ihre Zwecke ist valgrind/callgrind

Answer 6

die Anzahl der CPU-Instruktionen Mess ziemlich nutzlos ist.

Die Leistung ist relativ zum Flaschenhals, je nach Problem kann der Engpass das Netzwerk, Festplatten-IOs, Speicher oder CPU sein.

Für nur einen freundlichen Wettbewerb, würde ich Timing vorschlagen. Was bedeutet, dass Testfälle bereitgestellt werden, die groß genug sind, um sinnvolle Maßnahmen zu ergreifen.

Unter Unix können Sie gettimeofday für relativ genaue Messungen verwenden.

Answer 7

Von der Inline-Montage können Sie RDTSC Anweisung zu bekommen 32-Bit (least significant Teil) gegen die in EAX und 32-Bit (höchste wesentliche Teile) zu edx verwenden. Wenn Ihr Code zu klein ist, können Sie die Gesamtzahl der CPU-Zyklen mit nur eax Register überprüfen. Wenn die Anzahl mehr als max. 32-Bit-Wert, EDX-Inkremente pro Max-32-Bit-Wert-Zyklus.

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(); 

Ausgang: 74000 CPU-Zyklen für 1000 Iterationen und 800000 CPU-Zyklen für 10000 Iterationen auf meinem Rechner. Weil clock() zeitaufwendig ist.

CPU-Zyklus Auflösung auf meiner Maschine: ~ 1000 Zyklen. Ja, Sie benötigen mehr als mehrere Tausend Addition/Subtraktion (schnelle Anweisungen), um es relativ korrekt zu messen.

Angenommen CPU Arbeitsfrequenz konstant 1000 CPU-Zyklen nahezu gleich 1 Mikrosekunde für einen 1 GHz-CPU. Du solltest deine CPU aufwärmen, bevor du das tust.