Finde tidsforbrug for C/C++ kode med valgrind -> callgrind og kcachegrind

Som jeg beskrev i mit blog-indlæg i går, så kan valgrind (primært til Linux) meget andet et at finde array-fejl i C/C++ kode. I dette blog-indlæg ser jeg nærmere på de fine muligheder, der også er i valgrind til at profilere C/C++ kode på Linux.
Hvis man har kode, som bruger lidt for meget tid eller man er usikker på hvor tiden bruges, så er valgrinds "callgrind" et rigtig godt værktøj at have med som "kode-snedker".

Lad os tage et eksempel, som er en variant at den kode, jeg havde fremme i gårsdagens blog-indlæg:

#include   
#include   
#include   

int subfunc1(int i)  
{  
  int ii;  
  double a=0;  
  for (ii=0;ii<100000;ii++) {  
    a+=sin(ii+i);  
  }  
  return i+(int)(4*a);  
}  

int func1(int i)  
{  
  return i+subfunc(i);  
}  

int func2(int i)  
{  
  int *j;  

  j = (int *)malloc(1000000);  
  free(j);  
  return i+2;  
}  

int func3(int i)  
{  
  int ii;  
  double a=0;  
  for (ii=0;ii<100000;ii++) {  
    a+=sin(tan(cos(ii+i)));  
  }  
  return i+(int)(4*a);  
}  


int main(int argc, char** argv)  
{  
  int ii,sum;  
  int iters = atoi(argv[1]);  
  printf("Running %i iterations : %s\n",iters,argv[1]);  
  for (ii=0;ii      

Vi ser at main()-funktionen kalder tre underfunktioner func1(), func2() og func3(), hvor func1() og func3() indebærer kald af trigonometriske funktioner sin(), cos() og tan(). Den sidste funktion func2() laver kun hukommelses-gymnastik med malloc() og (denne gang husket) free().

Opgaven er nu at finde ud af hvor stor del af koden, der anvendes i hver af de tre underfunktioner.

Først oversætter jeg og ser at programmet kan køre

$ gcc -g -o v2 v2.c -lm
$ ./v2 10
Running 10 iterations : 10
Iteration 0 : sum=19
Iteration 1 : sum=22
Iteration 2 : sum=18
Iteration 3 : sum=14
Iteration 4 : sum=17
Iteration 5 : sum=28
Iteration 6 : sum=42
Iteration 7 : sum=48
Iteration 8 : sum=45
Iteration 9 : sum=38

Fint nok - lad mig så kører programmel med callgrind

$ valgrind --tool=callgrind ./v2 10
==3832== Callgrind, a call-graph generating cache profiler
==3832== Copyright (C) 2002-2010, and GNU GPL'd, by Josef Weidendorfer et al.
==3832== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==3832== Command: ./v2 10
==3832==
==3832== For interactive control, run 'callgrind_control -h'.
Running 10 iterations : 10
Iteration 0 : sum=19
Iteration 1 : sum=22
Iteration 2 : sum=18
Iteration 3 : sum=14
Iteration 4 : sum=17
Iteration 5 : sum=28
Iteration 6 : sum=42
Iteration 7 : sum=48
Iteration 8 : sum=45
Iteration 9 : sum=38
==3832==
==3832== Events : Ir
==3832== Collected : 83244758
==3832==
==3832== I refs: 83,244,758

Dette koster ca 20 gange længere køretid for programmet og der er nu dannet en callgrind.out fil med navn "3832" (det tal varierer fra kørsel til kørsel). Denne analyser jeg med et andet program "kcachegrind".

Det grafiske kcachegrind er nu en del af KDE-pakken, så kører man
GNOME, vil der være en hel del support-biblioteker, som skal
apt-get/yum/yast installeres.

$ kcachegrind callgrind.out.3832

Tryk på billedet for at få det i fuld størrelse

Eksternt billede

Lad os se lidt nærmere på de enkelte dele af GUI-fladen. Først den øverste højre.

Bemærk at hver kasse er annoteret med hvor stor procendel af
tiden, der blev brugt i de enkelte programdele. Vi ser af func2() er væk - det koster intet at allokere hukommelse i forhold til de trigonometriske funktioner, som koster dyrt i func1() og func3(). Meget elegant.

Eksternt billede

I nederste højre side af kcachegrind-GUI'en har jeg valgt "Kald-graf" (engelsk "Caller-graph") og her kan man se hvilke funktioner, som kalder hinanden. I det næste billede zoomes ind på nederste højre del af kcachegrind-vinduet.

Den vakse
læser tænker sikkert "..det har pto da skrevet om tidligere". Ja næsten - læs
det gamle blog-indlæg om Doxygen
. Kcachegrind udnytter på samme vis Graphviz, så det er ikke tilfældigt.

Eksternt billede

Jeg kan anbefale jer andre kode-snedkere, at se nærmere på koblingen mellem valgrind/callgrind og kcachegrind. Det er et fantastisk makkerpar, hvis man skal bevise hvor man smider for for mange CPU-kræfter. Mon ikke jeg i et kommende blog-indlæg dykker jeg ned i dette igen. Der er flere smarte ting man kan med kcachegrind.

/pto

Kommentarer (10)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Jacob Larsen

det koster intet at allokere hukommelse i forhold til de trigonometriske funktioner, som koster dyrt i func1() og func3()

Det bør du nok skrive lidt om. Måske ala: "Det koster intet at lave en allokering/free i forhold til 100000 kald af trigonometriske funktioner." Ellers kunne folk der ikke læser koden jo komme til at tro at allokering af hukommelse er en let operation, hvilket det jo normalt ikke er.

Torben Mogensen Blogger

Ellers kunne folk der ikke læser koden jo komme til at tro at allokering af hukommelse er en let operation, hvilket det jo normalt ikke er.

Yup. Der er en udbredt misforståelse om, at malloc() og free() er stort set gratis. Man hører tit folk sige, at de ikke vil bruge sprog med GC, fordi det giver overhead. Men det gør malloc()/free() også, og endda ofte (men ikke altid) mere.

Jesper Louis Andersen

Lige præcis i det program som er vist, er der (efter hurtigt skimmeri) kun et malloc() kald umiddelbart efterfulgt af free(). Mange malloc()-implementationer husker det hukommelse de sidst frigav og prøver lige først om en ny allokering passer ind. Jeg ved at phkmalloc gjorde det i FreeBSD og vil gætte på at jemalloc gør noget i samme retning. SLAB-allokatoren ligeså.

Det giver god mening. Hukommelse der lige er frigivet har heuristisk set en god chance for at være godt placeret i cache-hierarkiet og dermed er Peters kald til malloc() stort set konstant-tids kald.

Men bliver programmets allokeringsstrategi mere komplekst, så begynder det at blive dyrt at allokere hukommelse. Og som Torben skriver, så er der eksempler på tilfælde hvor en garbage-collector outperformer manuel hukommelsesallokering. Det gælder specielt hvis man har været naiv da man legede med sin hukommelse. Det omvendte er naturligvis også tilfældet hvis man naivt tror en GC kan redde een fra misligholdelse af hukommelsen i programmet - det dør ikke med en GC, men det bliver langsomt af pommeren til.

Garbage collectors største svaghed er når deres live-heap bliver så stor at den går mod toppen af hvad maskinen indeholder af tilgængelig RAM (Præcist: hvad kernen har tildelt programmet). Det har det med at tvinge full-sweeps igennem og de er dyre. Derfor er det vigtigt at måle produktivitet af ens program: Hvor meget tid bruger din GC og hvor meget tid bruger resten af programmet (normalt kaldet mutatoren i GC-jargon) på nyttearbejde?

Rasmus Kaae

nu kan jeg godt se at dette er eksempel kode, men er det særlig realistisk?

hvis du designer et program hvor i der indgår en funktion der skal kaldes 100.000 gange - så vil du typisk ikke give dig i kast med heap allokeringer via malloc/free. selv i tilfældet med varierende størrelse af hukommelsesklumpen kan der let udøves optimering.

desuden er det en voldsom antagelse at sin/cos altid er langsommere end malloc. svjv. findes der visse platforme hvor netop disse funktioner er baseret på fixed point LUTs som er hurtigere end allokering (mener det er GBA'en).

Morten Wegelbye Nissen

Det er ikke koden men Valgrind -> Callgrind og Kcachegrind der er i fokus på denne post.

Jeg læste kommentar igennem i håb om nogen havde skrevet "I java kan man med fordel bruge ..... til at opnå det samme" - men nej, triviel skriv om malloc og free.

Peter Toft

Bingo - selve min kode er ikke så relevant her.
Jeg har med vilje valgt en latterlig nem kode, som kan læses og forstås på "nogle" sekunder.

Kommentarerne om at malloc ikke bare kan negligeres i forhold til sin() osv er naturligvis valide på nogle platforme. Det er langt fra sådan at observationer fra en Pentium-klasse maskine kan overføres f.eks. på en N900 eller mindre platforme.

Log ind eller Opret konto for at kommentere