Przygotowywanie i przeprowadzanie testów, analiza i prezentacja wyników na przykładzie

Zadanie

Przypuśćmy, że chcemy przetestować jak zachowują się różne strategie przydziału pamięci w alokacji ciągłej. Przyjmijmy upraszczające założenie, że jeśli chodzi o wydajność czasową, to interesuje nas tylko czas oczekiwania na wolny blok podczas alokowania pamięci (nie badamy efektywności zwalniania pamięci).

Niestety, rodzaj strategii nie jest jedynym czynnikiem decydującym o tym, jak będzie zachowywał się algorytm przydziału. W zależności od tego jak duże będziemy alokowali bloki albo na jakie straty pamięci związane z fragmentacją wewnętrzną możemy sobie pozwolić, algorytm może się różnie zachowywać. Przygotujemy więc różne testy, by sprawdzić algorytm w każdej z sytuacji.

Na początek sporządzamy listę czynników, które chcemy uwzględnić podczas testowania:

maksymalny rozmiar żądanego bloku (mały, średni, duży);
maksymalny czas życia (tzn. czas od alokacji do zwolnienia) żądanego bloku (mały, średni, duży);
strategia wyboru (pierwszy, następny, najlepszy albo najgorszy pasujący);
sortowanie listy wolnych bloków (bez sortowania, sortowanie po rozmiarze, po adresie);
fragmentacja wewnętrzna (jest albo nie ma);
współczynnik (zerowy, mały, średni, duży — jeśli jest fragmentacja wewnętrzna, to współczynnik mówi, na jak dużą stratę pamięci możemy sobie pozwolić; w przeciwnym przypadku oznacza, że zawsze alokujemy bloki o wielokrotności współczynnika).

Przygotowanie testów

Teraz chcemy przygotować testy, które w całości pokryją wszystkie możliwe wejścia dla programu przy uwzględnieniu powyższych czynników. Mamy sześć czynników, każdy przyjmuje kilka wartości (np. pierwszy 3, piąty 2). Chcąc napisać test dla każdej permutacji tych wartości, powinniśmy wygenerować 3 * 3 * 4 * 3 * 2 * 4 = 864 testy. Przykładowy test może mieć sygnaturę (1a 2c 3a 4a 5b 6a), co oznacza, że testujemy algorytm na pewnych losowych danych, gdzie rozmiar żądanego bloku jest mały (1a), jego czas życia duży (2c) itd. Niestety, nawet jeśli będziemy testowali program automatycznie to ta liczba jest zdecydowanie za duża (poza tym dodanie nowego czynnika do listy wydłuży czas testów co najmniej dwukrotnie).

Co możemy więc zrobić? Zauważmy najpierw, że jest mało prawdopodobne, że jeśli nasz program w pewnych sytuacjach zachowuje się fatalnie, to robi to tylko dla jednej konkretnej permutacji sześciu czynników. Z reguły anomalie ujawniają się gdy wystąpią dwa (najwyżej trzy) konkretne czynniki. (Jeśli maksymalny rozmiar i czas życia bloku będą bardzo duże, to niezależnie od pozostałych czynników pamięci szybko przestanie brakować.) Ta obserwacja rodzi pytanie: czy możemy tak przygotować przypadki testowe, aby każda trójka wystąpiła w jakimś teście? (Np. trójka postaci (3a 4c 6b) występuje w teście (1a 2c 3a 4c 5b 6b).) Okazuje się, że tak i pomocny nam w tym będzie program jenny.

Program uruchamiamy podając w opcji -n jakie krotki mają być pokryte testami (czy to mają być np. trójki), a dalej podajemy ile każdy czynnik może przyjmować wartości. Dodatkowo dzięki opcji -w możemy zabronić generowania testów, które zawierają pewne krotki. My napiszemy tak:

./jenny -n3 3 3 4 3 2 4 -w5b6a

Nie ma sensu przy braku fragmentacji wewnętrznej próbować alokować bloki wielokrotności zera bajtów, więc piszemy -w5b6a. Program wygeneruje sygnaturki poszczególnych testów. Okazuje się, że jest ich 67, co jest dużo mniejszą liczbą niż 864. Gdy będziemy żądali pokrycia wszystkich dwójek (-n2) liczba wygenerowanych testów zmniejszy się do 20:

 1a 2c 3b 4b 5b 6c 
 1b 2a 3c 4c 5a 6a 
 1c 2b 3d 4a 5a 6d 
 1c 2a 3a 4c 5b 6b 
 1a 2a 3c 4a 5b 6d 
 1b 2b 3a 4b 5a 6b 
 1b 2c 3d 4c 5b 6d 
 1b 2c 3b 4a 5a 6a 
 1b 2b 3b 4c 5b 6c 
 1a 2a 3d 4b 5a 6b 
 1c 2c 3c 4b 5a 6c 
 1a 2b 3a 4b 5a 6a 
 1c 2c 3a 4a 5a 6b 
 1c 2a 3b 4b 5a 6d 
 1a 2a 3d 4a 5b 6c 
 1a 2b 3a 4c 5a 6c 
 1c 2b 3c 4c 5a 6b 
 1c 2b 3d 4c 5a 6a 
 1a 2c 3a 4a 5a 6d 
 1c 2b 3b 4c 5a 6b

Prezentacja wyników

Warto zastanowić się jakie statystyki będą nas interesowały. Mogą to być:

czas znalezienia właściwego bloku na liście wolnych bloków (jest on wprost proporcjonalny do liczby węzłów, które przejdziemy na liście);
liczba wolnych bloków (czyli długość listy wolnych bloków);
liczba zaalokowanych bloków;
procentowa zajętość pamięci;
liczba błędów (błąd jest sygnalizowany w przypadku braku pasującego bloku na liście).

Do wizualizacji statystyk użyjemy programu gnuplot, który ma możliwość generowania wykresów z danych liczbowych podawanych z pliku.

Zautomatyzowanie procesu

A w jaki sposób zorganizujemy proces automatycznego testowania? Będą nam przydatne następujące programy:

alloc.cpp — program wczytujący z wejścia wartości czynników 3–6 oraz ciąg poleceń (żądań przydziału lub zwolnienia bloków), symulujący działanie algorytmu i wypisujący na wyjście statystyki;
testgen.cpp — program generujący na podstawie wartości czynników 1–2 losowy ciąg poleceń;
skrypt pomocniczy przyjmujący wartości wszystkich czynników, który uruchamia generatora testów, uruchamia alloc na wygenerowanym teście i zapisuje do pliku graficznego wykres ze statystykami;
skrypt generujący sygnatury testów programem jenny, uruchamiający poszczególne testy (za pomocą skryptu pomocniczego) i zapisujący wyniki w postaci strony HTML.

Powyższe programy i skrypty, jak również program jenny umieszczone są tutaj: paczka ze skryptami.

Analiza wyników

Na wykresach przedstawione są zmiany poszczególnych statystyk w czasie. Jednostką na osi X jest pojedyncze polecenie (żądanie przydziału lub zwolnienia bloku), natomiast jednostki na osi Y podane są w legendzie.

Przykładowe wyniki

Już pobieżna analiza otrzymanych statystyk pozwala na następujące wnioski:

dla krótkiego czasu życia bloków wykresy są postrzępione, a zapełnienie pamięci nie przekracza 2%;
w przypadku długiego czasu życia bloków (210 jednostek) błędy zaczynają się pojawiać przy pamięci zapełnionej w 80%;
strategie pierwszy i następny pasujący wymagają średnio przejścia połowy listy wolnych bloków, przy czym statystyki poprawiają się wraz ze wzrostem współczynnika fragmentacji;
w niektórych przypadkach wykres liczby błędów gwałtownie rośnie, pomimo tego, że praktycznie cała pamięć jest wolna.

Ostatnie spostrzeżenie każe nam przypuszczać, że coś jest nie tak z implementacją programu. Szukając prawidłowości w występowaniu tej anomalii stwierdzamy, że we wszystkich felernych przypadkach używana jest strategia najlepszy pasujący, przy jednoczesnym niezerowym współczynniku fragmentacji (w 3/4 przypadków jest to fragmentacja wewnętrzna). Po analizie kodu stwierdzamy, że rzeczywiście popełniliśmy błąd w naliczaniu liczby błędów, który ujawnia się gdy algorytm znajduje idealnie (plus minus fragmentacja) pasujący blok na końcu listy wolnych bloków. Ten przypadek pokazuje nam, że w praktyce pokrywanie testami wszystkich trójek sprawdza się bardzo dobrze (powyższy błąd został naprawdę popełniony przez autora programu i udało się go zlokalizować właśnie drogą przedstawionej analizy).

GPROF — program monitorujący wydajność

W naszym przykładzie zbieranie statystyk było w miarę proste i mogliśmy je zrealizować sami. Czasami jednak warto będzie skorzystać z dodatkowego programu zbierającego statystyki — takim programem jest gprof. Potrafi on w tle monitorować programy i generować różne raporty. Aby użyć gprof, należy skompilować i zlinkować program z opcją -pg:

cc -o myprog myprog.c utils.c -g -pg

albo:

cc -g -c myprog.c utils.c -pg
cc -o myprog myprog.o utils.o -pg

Podczas działania tak uzyskanego programu, gprof niewidocznie monitoruje go i tworzy raport gmon.out. Przede wszystkim możemy mierzyć czas wykonywania poszczególnych procedur a także liczbę ich wywołań. Ten plik nie jest przeznaczony do czytania, wyniki odczytujemy również z pomocą gprof. Typowe wywołanie:

a.out            (uruchamiamy)
gprof a.out      (generujemy raport)

Monitorowanie programów skompilowanych bez -pg może dać nieoczekiwane rezultaty!

Generowane raporty można oglądać w bardzo róznej postaci (szczegóły w man gprof). Oto przykład (za GNU gprof):

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 33.34      0.02     0.02     7208     0.00     0.00  open
 16.67      0.03     0.01      244     0.04     0.12  offtime
 16.67      0.04     0.01        8     1.25     1.25  memccpy
 16.67      0.05     0.01        7     1.43     1.43  write
 16.67      0.06     0.01                             mcount
  0.00      0.06     0.00      236     0.00     0.00  tzset
  0.00      0.06     0.00      192     0.00     0.00  tolower
  0.00      0.06     0.00       47     0.00     0.00  strlen
  0.00      0.06     0.00       45     0.00     0.00  strchr
  0.00      0.06     0.00        1     0.00    50.00  main
  0.00      0.06     0.00        1     0.00     0.00  memcpy
  0.00      0.06     0.00        1     0.00    10.11  print
  0.00      0.06     0.00        1     0.00     0.00  profil
  0.00      0.06     0.00        1     0.00    50.00  report
...

Należy sobie zdawać sprawę, że pomiary dokonywane przez gprof nie są idealne i obarczone pewnym błędem. O tym i innych informacjach na temat programu na GNU gprof.