104: Benchmark wersji 0.1.1.4

Z jednodniowym opóźnieniem postanowiłem opublikować wyniki benchmarku obu implementacji obecnej wersji bazy danych, oznaczonej numerem 0.1.1.4. Przyznam szczerze, spodziewałem się wyników zupełnie odmiennych od tych, które uzyskałem.

Jak testowałem?

Początkowo planowałem napisać kawałek kodu, który będzie uruchamiał oba programy dla zadanych danych testowych i sprawdzał ich czas. Niestety, niemożliwe było użycie bashowego time'a, ze względu na to, że programy uruchamiają się w sh. Ten zaś ma zupełnie inny format wyjściowy time, który utrudnia pobranie odpowiednich danych oraz ma mniejszą dokładność.

Dlatego ostatecznie doszedłem do wniosku, że szybciej, chociaż może mniej wygodnie, będzie przeprowadzić testy ręcznie. Cykl wykonania jednego testu wyglądał zatem tak:

• napisanie testu wewnątrz main.cpp, który ze standardowego wejścia pobiera potrzebne dane
• kompilacja obu wersji
• testowanie czasu dla każdego przewidzianego zestawu, dla obu implementacji po trzy razy
• zapisanie wyników

Jakie testy wykonałem?

• heap(n), czyli wygenerowanie drzewa binarnego o n, którego liście znajdują się wyłącznie na ostatnim poziomie i (z wyjątkiem liści) każdy wierzchołek ma dokładnie po jednym następcy i dziecku
• heap(n) i usunięcie korzenia, czyli wygenerowanie drzewa jak powyżej, a potem usunięcie korzenia wraz z jego następcami i potomkami. W tym teście średnia dla danego zestawu była liczona jako różnica średniej uzyskanych wartości oraz średnia wartości z odpowiadającego zestawu testu pierwszego - celem było zmierzenie czasu usunięcia wszystkich wierzchołków
• line(n) z przejściem, czyli wygenerowanie linii z n postami, przy pomocy metody addEntry() wraz z przejściem do każdego nowego posta przy użyciu goTo()
• line(n), jak wyżej, ale bez użycia goTo()

Jakich danych wejściowych użyłem?

• Dla testów typu heap testowałem implementacje na danych wejściowych: 3, 10, 16, 23, co odpowiada kolejno 7, 1 023, 65 535 i 8 388 607 postom
• Dla testów typu line sprawdziłem wejścia 10, 1 000, 100 000 i 10 000 000.

Jakich wyników się spodziewałem?

Początkowo myślałem, że szybsze będą indeksy, zawsze myślałem, że działania na zwykłych zmiennych wykonywane są szybciej niż działania na wskaźnikach. Jednak wykonane w międzyczasie testowe pomiary wykazały, że prędkości obu implementacji są bardzo zbliżone. Wtedy myślałem, że tak już pozostanie. Znów nie miałem racji.

Jakie wyniki uzyskałem?

W większości przypadków zwyciężają wskaźniki. Indeksy okazały się szybsze w niektórych testach z mniejszymi danymi wejściowymi, jednak różnica jest na poziomie błędu statystycznego. Co mnie rzeczywiście zainteresowało to ogromna przewaga wskaźników w najcięższych testach. Wygląda na to, że obecnie wskaźniki wygrywają rywalizację, ze względu na szybkość, zerową fragmentację danych i wygodę użytku.