Come confrontare le prestazioni di due pezzi di codici

Question

Ho una competizione amichevole con un paio di ragazzi nel campo della programmazione e recentemente siamo diventati così interessati a scrivere codice efficiente. La nostra sfida era cercare di ottimizzare il codice (in termini di tempo e complessità della CPU) ad ogni costo (leggibilità, riusabilità, ecc.).

Il problema è che ora dobbiamo confrontare i nostri codici e vedere quale approccio è migliore rispetto agli altri, ma non conosciamo nessuno strumento per questo scopo.

La mia domanda è, ci sono alcuni (qualsiasi!) Strumenti che prende un pezzo di codice come input e calcola il numero di flop o di istruzioni della CPU necessarie per l'esecuzione di esso? C'è qualche strumento in grado di misurare l'ottimizzazione di un codice?

P.S. La lingua di destinazione è C++, ma sarebbe bello sapere se tali strumenti esistono anche per java.

Answer 1

Ecco un po 'di C++ 11 cronometro mi piace stendere quando ho bisogno di tempo qualcosa:

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

Usage:

stopwatch sw; 
sw.tick(); 

run_long_code(); 

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

Su qualsiasi implementazione decente, il default high_resolution_clock dovrebbe dare informazioni di sincronizzazione molto accurate.

Answer 2

È abbastanza difficile calcolare il numero di dettaglio del tempo della CPU da un blocco di codice. Il modo normale per farlo è progettare i dati di input peggiori/medi/migliori come casi di test. E fai un tempismo di profilazione basato sul tuo codice reale con questi casi di test. Non c'è nessuno strumento in grado di dirti il ​​flop quando è privo dei dati e delle condizioni del test di input.

Answer 3

C'è la funzione std::clock() da <ctime> che restituisce quanto tempo di CPU è stato speso per il processo corrente (ciò significa che non conta il tempo in cui il programma era inattivo perché la CPU stava eseguendo altre attività). Questa funzione può essere utilizzata per misurare con precisione i tempi di esecuzione degli algoritmi. Utilizzare la costante std::CLOCKS_PER_SEC (anche da <ctime>) per convertire il valore di ritorno in secondi.

Answer 4

Ci sono pezzi di software chiamati profilers che fanno esattamente ciò che si desidera.

Un esempio per Windows è AMD code analyser e gprof per POSIX.

Answer 5

migliore per il tuo scopo è valgrind/callgrind

Answer 6

misurando il numero di istruzioni della CPU è abbastanza inutile.

Le prestazioni sono relative al collo di bottiglia, a seconda del problema in questione il collo di bottiglia potrebbe essere la rete, gli I/O del disco, la memoria o la CPU.

Per una semplice competizione, suggerirei i tempi. Il che implica fornire casi di test che sono abbastanza grandi da avere misure significative, ovviamente.

Su Unix, è possibile utilizzare gettimeofday per misure relativamente precise.

Answer 7

Dall'assieme inline, è possibile utilizzare l'istruzione rdtsc per ottenere il contatore a 32 bit (parte meno significativa) in eax e 32 bit (la parte più significativa) in edx. Se il tuo codice è troppo piccolo, puoi controllare i cpu-cicli total-approate con il solo registro eax. Se il conteggio è superiore a max. di valore a 32 bit, incrementi di edx per ciclo di valori max-32 bit.

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

uscita: 74000 cpu-cicli per 1000 iterazioni e 800000 CPU-cicli per 10000 iterazioni sulla mia macchina. Perché clock() richiede molto tempo.

Risoluzione ciclo ciclo sulla mia macchina: ~ 1000 cicli. Sì, è necessario più di diverse migliaia di addizioni/sottrazioni (istruzioni rapide) per misurarle in modo relativamente corretto.

Supponendo che la frequenza di lavoro della cpu sia costante, 1000 cpu-cicli è quasi uguale a 1 micro-secondi per una CPU da 1 GHz. Dovresti riscaldare la tua cpu prima di farlo.