Optimizacije kompajlera

Često nam je potrebno u C-u iterirati od prvog do zadnjeg elementa u znakovnom nizu (string-u).

Slijedeći program prebrojava broj pojavljivanja znaka 'o' u nizu znakova:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const size_t n = 100000;

int main() {
  int i, cnt = 0;
  char *t = malloc(n);
  memset(t, 'o', n - 1);
  t[n-1] = '\0';

  for (i = 0; i < strlen(t); ++i)
    cnt += (t[i] == 'o');

  printf("%d\n", cnt);
  return 0;
}

Kompajliranjem i pokretanjem ovog programa, primjećujemo da njegovo izvršavanje traje duže nego što bi na prvi pogled mislili.

$ gcc -otest test.c
$ time ./test
99999

real    0m2.185s
user    0m2.160s
sys     0m0.004s

Na današnjim kućnim računalima možemo očekivati da for petlja od do traje ispod dvije sekunde. Zašto onda ovaj programski isječak traje toliko?

Odgovor je u načinu na koji je implementirana funkcija strlen. Naime, ona mora iterirati cijeli znakovni niz dok ne naiđe na oznaku kraja niza '\0', odnosno vrijednost .

Stoga naša for petlja svakom provjerom i < strlen(t), napravi koraka kako bi izračunala strlen(t). Ukupan broj koraka tada je , i to je razlog duljeg izvođenja programa.

Optimizacija koju ovdje možemo napraviti je očigledna. Duljina niza se ne mijenja kako mi iteriramo kroz njega i možemo to spremiti u neku varijablu.

size_t length = strlen(t);
for (i = 0; i < length; ++i)
  cnt += (t[i] == 'o');

No, zar ne bi kompajler ovo sam mogao zaključiti? Odgovor je da. Ako proslijedimo kompajleru zastavicu za optimizaciju (-O1, -O2 ili -O3) ova optimizacija će se dogoditi sama.

Optimizacije kompajlera

Kompajler je sposoban sam napraviti neke optimizacije kako bi se naš kod izvršavao brže.

Potpnua lista optimizacija koje kompajler može napraviti nalazi se na http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html. Mi ćemo pokazati osnovno korištenje optimizacija:

$ gcc -otest test.c
$ gcc -otest1 -O1 test.c
$ gcc -otest2 -O2 test.c
$ gcc -otest3 -O3 test.c

Pokretanjem programa dobili smo sljedeća vremena izvršavanja:

Vidimo da već na najnižoj razini optimizacija -O1, optimizaciju sa strlen kompajler napravi za nas.

Na svim natjecanjima u Hrvatskoj, kompajliranje našeg izvornog koda izvodi se sa zastavicom -O2.

Bolji pristup pri iteriranju niza znakova

Naravno, konvencijalna metoda za itereriranje niza znakova u C-u uopće ne koristi poziv funkcije strlen već iskorištava postojanje '\0' na kraju niza:

char *it;
for (it = t; *it; ++it)
  cnt += (*it == 'o');

No, postoji li još brži način da se prebroji pojavljivanje slova 'o' u nizu znakova?

© 2014. Anton Grbin

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License