[C] Calcolo tempi exec

[lelone]

Ciao a tutti, ho il seguente problema:
ho implementato in C un'algoritmo du cui voglio valutarne le prestazioni (complessità in tempo). So che, se lavorassi in Linux, avrei a disposizione <sys/resource.h> la quale mi mette a disposizione una funzione "getrusage(...)" che salva il tempo d'esecuzione ogni volta che richiamata (salvandolo in una struttura rpedefinita). Purtroppo lavoro in Windows e uso Lcc-Win32 come compilatore.
Vi chiedo se esiste un metodo per calcolare i tempi d'exec del mio programma. E' indispensabile che questi tempi siano accurati, quindi con precisione almeno 0.00000 secondi.

Situazione:
main()
...
...
***salvo tempo 1***
//PROGRAMMA//
***salvo tempo2***
Stampa della differenza dei tempi

Grazie infinite, ciao
Daniele

[maiosyet]

Originariamente inviato da lelone
So che, se lavorassi in Linux, avrei a disposizione <sys/resource.h> la quale mi mette a disposizione una funzione "getrusage(...)" che salva il tempo d'esecuzione ogni volta che richiamata (salvandolo in una struttura rpedefinita).

Scusa se ne approfitto, quando hai tempo mi spieghi o mi dai un link sulla funzione getrusage? Google mi ha delle cose abbastanza strane

Grazie

[iguana13]

Con quella precisione è impossibile anche in linux.
Al massimo arrivi al millesimo (con un errore di +-10)

[Andrea Simonassi]

Fai così, dovresti avere una precisione di circa 1.0E-6 (microsecondi) e comunque mi risolve anche tempi nell'ordine dell 1.0E-7 però per essere sicuro al 100% dovresti eseguire il processo in real time, ovvero senza condividere la CPU nè con il sistema nè con altri processi, se guardi la funzione GetCPUFrequency3 vedrai anche come fare a passare in real time.

Occhio che se il programma si impalla mentre sei in real time puoi solo resettare la macchina...

Perchè funzioni bisogna però che l'hardware supporti l'high-resolution performance counter (se non hai un computer antidiluviano dovresti averlo), e che windows lo riconosca.

#include <windows.h>
#include <iostream>

UINT64 inline rdtsc()
{
    __asm{
        RDTSC
    }
}

//calcola frequenza CPU usando RDTSC come contatore di cicli di clock
//e usa QueryPerformanceCounter come timer ad alta risoluzione  
//fornito da windows

double GetCPUFrequency3 (unsigned tempo_campionamento)
{
 register UINT64 startC, endC;
 UINT64 resFrequency, hrCounterFinal, hrCounterTemp = 0, step = 0;
 double frequency;  // In Hz.  
 
 if (QueryPerformanceFrequency (reinterpret_cast<LARGE_INTEGER*> ( & resFrequency)) == 0) return 0.0;
    
 step = static_cast<UINT64> (static_cast<double> ( resFrequency) * (tempo_campionamento / 1000.0) );
 
 SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
 SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);
 
    startC = rdtsc();
  QueryPerformanceCounter (reinterpret_cast<LARGE_INTEGER*> ( &hrCounterFinal)); 
            //miglioramento possibile: valutare cicli clock chiamata QueryPerformanceCounter 
  hrCounterFinal += step;
 
  while(hrCounterTemp < hrCounterFinal)
   QueryPerformanceCounter (reinterpret_cast<LARGE_INTEGER*> (&hrCounterTemp));  
 endC = rdtsc();
 
 SetPriorityClass(GetCurrentProcess(), NORMAL_PRIORITY_CLASS);
 SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_NORMAL); 
 
 frequency = (endC - startC) / (tempo_campionamento / (1000.0)); //10000 
 
 return frequency;
}

int main()
{
    UINT64 inizio = rdtsc();    
        //per essere piu precisi bisognerebbe contare i 
	//cicli di clock persi durante la chiamata a rdtsc

	//fai qualcosa 

    UINT64 fine = rdtsc();
    UINT64 elapsed = fine - inizio;

	double CPUFREQ = GetCPUFrequency3(1000);
          //maggiore il tempo di campionamento maggiore la precisione
        
	std::cout << elapsed << " cicli di CPU" << std::endl;
	std::cout << static_cast<double> (elapsed) / CPUFREQ << " secondi " << std::endl;
 
    return 0;
}

[lelone]

Ti ringrazio innanzitutto per la tua disponibilità.
Tieni conto però che io (sicuramente non per colpa mia) ho utilizzato solamente ansi C su un compilatore Lcc-Win32.
La porzione di codice che hai appeso non mi sembra C standard, o sbaglio? Come posso adattare il tuo prezioso consiglio?

Grazie mille, ciao

[Andrea Simonassi]

E' un bel casino in ANSI C, visto che non puoi usare la keyword ASM...

devi scriverti un moduletto in assembly e compilarlo (ehm... assemblarlo) col MASM32 (scaricalo qui http://www.masm32.com/ ).

Per nostra fortuna il visual studio puo generare codice assembly, che sono andato a modificare un pelino per ottenere questo

	.386P
_TEXT	SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT	ENDS
_DATA	SEGMENT DWORD USE32 PUBLIC 'DATA'
_DATA	ENDS
CONST	SEGMENT DWORD USE32 PUBLIC 'CONST'
CONST	ENDS
_BSS	SEGMENT DWORD USE32 PUBLIC 'BSS'
_BSS	ENDS
$$SYMBOLS	SEGMENT BYTE USE32 'DEBSYM'
$$SYMBOLS	ENDS
$$TYPES	SEGMENT BYTE USE32 'DEBTYP'
$$TYPES	ENDS
_TLS	SEGMENT DWORD USE32 PUBLIC 'TLS'
_TLS	ENDS
_TEXT	SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT	ENDS


PUBLIC	_rdtsc

_TEXT	SEGMENT
_rdtsc	PROC NEAR					
push	ebp
	mov	ebp, esp
	sub	esp, 192				
	push	ebx
	push	esi
	push	edi
	lea	edi, DWORD PTR [ebp-192]
	mov	ecx, 48					
	mov	eax, -858993460				
	rep stosd

	db 0FH ;masm32 non assembla l'RDTSC 
        db 31H ;ergo inseriamo direttamente l'opcode in linguaggio
               ;macchina

	pop	edi
	pop	esi
	pop	ebx
	add	esp, 192
	cmp	ebp, esp
	mov	esp, ebp
	pop	ebp
	ret	0
	

_rdtsc	ENDP
_TEXT	ENDS
END

a sto punto il codice (spero ANSI) C sarebbe:

#include <windows.h>
#include <stdio.h>

UINT64 rdtsc();

double GetCPUFrequency3(unsigned tempo_campionamento)
{
 register UINT64 startC, endC;
 UINT64 resFrequency, hrCounterFinal, hrCounterTemp = 0, step = 0;
 double frequency;  // In Hz.  
 
 if (QueryPerformanceFrequency( (LARGE_INTEGER*) & resFrequency) == 0) return 0.0;
    
 step = (UINT64) ((double) resFrequency * (tempo_campionamento / 1000.0));
 
 SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
 SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);
 
    startC = rdtsc();
  QueryPerformanceCounter((LARGE_INTEGER*)  &hrCounterFinal); 
  hrCounterFinal += step;
 
  while(hrCounterTemp < hrCounterFinal)
   QueryPerformanceCounter((LARGE_INTEGER*)&hrCounterTemp);  
 endC = rdtsc();
 
 SetPriorityClass(GetCurrentProcess(), NORMAL_PRIORITY_CLASS);
 SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_NORMAL); 
 
 frequency = (endC - startC) / (tempo_campionamento / (1000.0)); //10000 
 
 return frequency;
}

int main()
{
    UINT64 inizio, fine, elapsed;
	double CPUFREQ;

	inizio = rdtsc();  
	//fai qualcosa 	
    fine = rdtsc();
    elapsed = fine - inizio;

	CPUFREQ = GetCPUFrequency3(1000);         
	
	printf("%e secondi\n" ,(double)elapsed / CPUFREQ);
 
    return 0;
}

Compila e linka insieme al file .obj generato dal MASM32 dovrebbe funzionare

[Andrea Simonassi]

Ho un po' guardato l'assembly generato da visual studio, in effetti è troppo (visto che non uso altro che il segmento codice).

Eccolo ottimizzato.

	.386P
_TEXT	SEGMENT PARA USE32 PUBLIC 'CODE'
_TEXT	ENDS

PUBLIC	_rdtsc

_TEXT	SEGMENT
_rdtsc	PROC NEAR	     

	db 0FH
        db 31H
          
	ret	0
_rdtsc	ENDP
_TEXT	ENDS
END

[lelone]

Ti ringrazio per l'aiuto che mi hai dato. Purtroppo però, con questo maledetto compilatore non riesco a linkare il mio file con l'obj del Masm. Non si può fare qual'cosa di alternativo, indubbiamente meno sofisticato, con un include del time.h? Non mi fornisce strumenti sufficienti al colcolo questa libreria?

Grazie mille
Daniele

[iguana13]

No: credo che arrivi al secondo

Al limite usi la GetTickCount() di windows, semplice da usare.
L'unico problema è che arrivi solo al millisecondo...

[Andrea Simonassi]

Puoi usare QueryPerformanceCounter (vedi MSDN per sintassi)


Ciao