Testarea timpului de execuție al unui program

From Algopedia
Jump to: navigation, search

Testarea duratei de execuție a unui program

Pentru a testa cît timp rulează programul nostru vom folosi tot funcția gettimeofday().

#include <stdio.h>
#include <sys/time.h> // pentru structura timeval

long long start; // momentul de timp cind a pornit programul (in microsecunde)

// returneaza timpul in microsecunde (o milionime de secunda)
inline long long getTime() {
  struct timeval tv;

  gettimeofday(&tv, NULL);
  return tv.tv_sec * 1000000LL + tv.tv_usec;
}

int main() {
  int i, suma;
  long long durata;

  start = getTime(); // timpul de inceput al programului, prima instructiune din main()

  // ... urmeaza programul propriu-zis
  // ... toate calculele se fac aici
  // ... iata cod care "consuma" timp
  suma = 0;
  for ( i = 0; i < 1000000; i++ )
    suma = (suma + i) % 1234;
  // afisam suma, altfel codul de mai sus este eliminat de compilator
  printf( "%d\n", suma );
  // ... am terminat codul consumator de timp
  // ... apoi, la final de program, chiar inainte de return 0
  // ... calculam timpul de executie

  durata = getTime() - start;
  printf( "Timpul de executie al programului in microsecunde: %lld\n", durata );
  return 0;
}

Execuție a unui program pînă la expirarea timpului alocat

Pentru a executa un program pînă la un moment dat vom folosi aceeași funcție gettimeofday(). Acest lucru ne folosește în unele situații precum:

  • atunci cînd programul nostru calculează un rezultat care poate fi îmbunătățit în timp (gen mutarea în timpul unui joc)
  • atunci cînd la olimpiadă scriem un program ce folosește backtracking pentru a găsi soluția, care este posibil să nu se încadreze în timpul alocat, caz în care ne oprim după timpul alocat și afișăm soluția găsită pînă atunci în speranța că este cea optimă

Ideea de bază este să împărțim programul în segmente de calcul ce se execută iterativ, într-o buclă while. În acea buclă while vom testa timpul, ieșind din buclă dacă timpul rămas este mai mic de o milisecundă.

Exemplul unu

Iată un exemplu de program care încearcă să calculeze suma numerelor de la 1 la un miliard modulo 1234 avînd o secundă la dispoziție. El afișează numărul de iterații și suma calculată pînă la momentul respectiv:

#include <stdio.h>
#include <sys/time.h>   // pentru structura timeval

#define MAXTIME 1000000 // timpul de executie maxim permis

long long start; // momentul de timp cind a pornit programul (in microsecunde)

// returneaza timpul in microsecunde (o milionime de secunda)
inline long long getTime() {
  struct timeval tv;

  gettimeofday(&tv, NULL);
  return tv.tv_sec * 1000000LL + tv.tv_usec;
}

int main() {
  int i, suma;

  start = getTime(); // timpul de inceput al programului, prima instructiune din main()

  // ... urmeaza programul propriu-zis
  // ... trebuie sa despartim calculul in ceva iterativ
  // ... in bucla principala vom testa timpul
  // ... iata un exemplu de program
  suma = i = 0;
  while ( i < 1000000000 && (getTime() - start) < (MAXTIME - 1000) ) {
    suma = (suma + i) % 1234;
    i++;
  }
  // ... am terminat codul mai devreme cu 1000 microsecunde (o milisecunda)
  // ... pentru a nu risca sa depasim timpul
  // ... deoarece vom mai face afisari, la final

  printf( "Am apucat sa fac %d iteratii\n", i );
  printf( "Suma pina la %d este %d\n", i, suma );

  return 0;
}

Iată un exemplu de execuție pe un calculator cu procesor core 2 duo la 2GHz:

Am apucat sa fac 4309481 iteratii
Suma pina la 4309481 este 428

Deoarece împărțirile durează mult mai mult decît adunările am putea trage concluzia că pe acest calculator putem face circa patru milioane de împărțiri pe secundă. În realitate să nu uităm că și apelul funcției de obținere a timpului durează.

Exemplul doi

Deoarece testarea timpului ocupă și ea timp este bine să nu o facem foarte des. Dacă segmentul de calcul este extrem de scurt, cum ar fi în exemplul trecut o împărțire și o adunare, vom petrece timp foarte mult calculînd timpul. Dacă segmentul de calcul este foarte lung riscăm să depășim timpul în unul dintre segmente.

Cum putem modifica exemplul anterior pentru a lungim segmentul de calcul? Vom calcula împărțirile în grupe de cîte 1000. Deoarece împărțirile sînt totuși foarte rapide un astfel de segment de calcul va fi în continuare foarte rapid. Iată noua variantă:

#include <stdio.h>
#include <sys/time.h>   // pentru structura timeval

#define MAXTIME 1000000 // timpul de executie maxim permis
#define BATCH 1000

long long start; // momentul de timp cind a pornit programul (in microsecunde)

// returneaza timpul in microsecunde (o milionime de secunda)
inline long long getTime() {
  struct timeval tv;

  gettimeofday(&tv, NULL);
  return tv.tv_sec * 1000000LL + tv.tv_usec;
}

int main() {
  int i, j, suma;

  start = getTime(); // timpul de inceput al programului, prima instructiune din main()

  // ... urmeaza programul propriu-zis
  // ... trebuie sa despartim calculul in ceva iterativ
  // ... in bucla principala vom testa timpul
  // ... iata un exemplu de program
  i = suma = 0;
  while ( i < 1000000000 && (getTime() - start) < (MAXTIME - 1000) ) {
    for ( j = i; j < i + BATCH; j++ )
      suma = (suma + j) % 1234;
    i += BATCH;
  }
  // ... am terminat codul mai devreme cu 1000 microsecunde (o milisecunda)
  // ... pentru a nu risca sa depasim timpul
  // ... deoarece vom mai face afisari, la final

  printf( "Am apucat sa fac %d iteratii\n", i );
  printf( "Suma pina la %d este %d\n", i, suma );

  return 0;
}

Pe același calculator vom obține rezultatul:

Am apucat sa fac 152449000 iteratii
Suma pina la 152449000 este 870

Iată că de la patru milioane de împărțiri pe secundă am sărit la 152 de milioane, ceea ce sună mult mai plauzibil.

Dacă modificăm programul să execute bucla în segmente de zece mii în loc de o mie (constanta BATCH obținem rezultatul:

Am apucat sa fac 157300000 iteratii
Suma pina la 157300000 este 622

Precum vedeți nu avem o variație prea mare: de la 152 de milioane am sărit la 157 de milioane. Putem spune cu certitudine că numărul de împărțiri pe secundă pe care le poate executa acest procesor este de circa 160 de milioane.

Concluzie

Am învățat să măsurăm timpul de execuție al unui program și să executăm un program vreme de o perioadă de timp fixată. Trebuie însă să reținem o lecție importantă, din fizică, care ne afectează în cazul de față:

Efectul observatorului

Actul observării unui fenomen va schimba acel fenomen.

Cu alte cuvinte, măsurarea unui sistem fizic nu se poate face fără a perturba acel sistem. Acesta este în multe cazuri rezultatul instrumentelor, care, din necesitate, alterează starea a ceea ce măsoară ele într-un fel sau altul. Un exemplu tipic este măsurarea presiunii unui cauciuc la mașină, care este greu de făcut fără a lăsa niște aer să scape, ceea ce schimbă presiunea originală. Spunem că într-un sistem fizic ceea ce măsurăm este, în realitate, un sistem format din sistemul original în care includem instrumentele folosite.

Efectul observatorului poate fi redus pînă la nesemnificativ folosind instrumente mai bune sau tehnici de observare mai bune. În cazul nostru am redus efectul măsurării folosind segmente mai mari de calcul.