Misurazione del tempo estremamente precisa in C

Question

Sto cercando di capire come scrivere un codice che possa calcolare con precisione il tempo necessario per eseguire una ricerca su un BST. Attualmente sto usando il tempo e il numero totale di elementi è dell'ordine 10^5. Sembra qualcosa di simile a quanto segue: -

clock_t begin, end; 
begin = clock(); 
... 
... 
... 
end = clock(); 
difference = (end-begin)/CLOCKS_PER_SECOND; 

Tuttavia, questo non mi danno la precisione che sto cercando. Ci sono altre funzioni di libc che potrei usare?

Answer 1

BST? Che tipo di precisione vuoi? Dividere per CLOCKS_PER_SECOND essere 10^6 su un sistema a 32 bit dovrebbe dare una precisione a 6 cifre?

Il risultato è doppio?

provare

difference = (double)(end-begin)/CLOCKS_PER_SECOND; 

noti che differenza dovrebbe essere in grado di tenere una doppia.

Answer 2

Per eseguire il benchmark del proprio algoritmo, è necessario eseguire alcune ripetizioni per ottenere un intervallo di almeno centinaia di millisecondi. (Questa è una pratica standard). Per eseguire il benchmark di un algoritmo che si verifica solo nello spazio utente (nessun threading, chiamate di sistema, ecc.), Si desidera utilizzare getrusage(RUSAGE_SELF, &r) e utilizzare il valore r.ru_utime che contiene secondi e microsecondi.

Answer 3

Qt ha QElapsedTimer che supporta la misurazione fino a nanosecondi. Non posso testimoniare quanto sia accurato, IIRC utilizza diverse implementazioni su piattaforme diverse. Purtroppo è C++, che potrebbe non essere adatto a te. Inoltre:

Su piattaforme che non forniscono una risoluzione di nanosecondi, il valore restituito sarà la migliore stima disponibile.

La funzione clock() va bene per le misurazioni approssimative, ma funziona nell'intervallo del millisecondo. Contrariamente al suo nome, non penso che funzioni negli orologi della CPU, poiché le frequenze di clock dei processori moderni possono variare parecchio, rendendo impossibile determinare con precisione il tempo reale affidandosi esclusivamente agli orologi della CPU. IMO questo concetto risale ai giorni in cui le frequenze della CPU erano costanti, non esisteva alcuna gestione energetica, nessun overclocking automatico "turbo boost" o altro.

EDIT: Anche questo (time.h):

int clock_gettime(clockid_t clk_id, struct timespec *tp); 

    ... and the target struct... 

    struct timespec { 
      time_t tv_sec;  /* seconds */ 
      long  tv_nsec;  /* nanoseconds */ 
    }; 

... and the clock options... 


CLOCK_REALTIME 
    System-wide realtime clock. Setting this clock requires appropriate privileges. 
CLOCK_MONOTONIC 
    Clock that cannot be set and represents monotonic time since some unspecified starting point. 
CLOCK_PROCESS_CPUTIME_ID 
    High-resolution per-process timer from the CPU. 
CLOCK_THREAD_CPUTIME_ID 
    Thread-specific CPU-time clock. 

Answer 4

Se la libreria supporta, C11 ha timespec_get() che misurerà fino a nanosecondi, a seconda della risoluzione orologio di sistema.

Answer 5

Quello che stai facendo è molto simile a quello che ho fatto di recente.

Penso che la funzione int gettimeofday(struct timeval *tv, struct timezone *tz); soddisfi le tue necessità. Le informazioni sulla durata verranno inserite nello struct timeval tv, che ottiene il tempo in secondi e in microsecondi.Il struct timeval dalla pagina man:

struct timeval { 
       time_t  tv_sec;  /* seconds */ 
       suseconds_t tv_usec; /* microseconds */ 
}; 

un breve esempio tempi misurati gettimeofday:

struct timeval time; 
if(gettimeofday(&time, 0)) return -1; 

long cur_time = 1000000 * time.tv_sec + time.tv_usec; 
double sec = cur_time/1000000.0; 

Un esempio più sono state semplificate e facilmente avvolto come C++ classe per uso conveniente. Il codice è stato inserito nel mio github: https://github.com/lulyon/LinuxTimeCounter, che è utilizzato in un progetto del mondo reale.

Answer 6

Se si esegue il benchmark con una CPU Intel. Forse puoi dare una prova alle istruzioni RDTSC e RDTSCP.

here is a document about the instructions