benchmark 00 tablicowej implementacji drzew czerwono czarnych

Kilka postów wcześniej zobowiązałem się przedstawić bencznarki i pomiary czasu implementacji tablicowej drzew czerwono-czarnych. Pokażę zatem, czy implementacja tablicowa naprawdę działa szybciej, o ile szybciej i w jakich sytuacjach możemy uzyskać przyspieszenie względem szablonów takich jak std::set i QMap. Benczmark 00 dotyczy wersji beta 0.00v. Na potrzeby tego bencznarku napisałem specjalny program i specjalny skrypt powłoki bash. Skrypt kompiluje, optymalizuje i profiluje kod bibliotek, kod drzewa czerwono czarnego i kod samego bencznmarku. Do kompilacji i profilowania został wykorzystany kompilator g++, więcej szczegółów kompilacji można wyczytać w pliku bench00.sh.

Do pobrania: kod źródłowy bencznarku (pobierz i zapisz jako bench00.cpp)

Do pobrania: skrypt ułatwiający uruchomienie testu (pobierz i zapisz jako bench00.sh)

Wszystkie testy w benchmarku 00 są przeprowadzane na  32bitowym typie bez znaku unsigned int. Zapewne pomiary czasu na większym typie, np. na dużych strukturach, byłyby inne. Niemniej jednak 32bitowy integer jest typowym przykładem z rzeczywistych programów, ponieważ zazwyczaj duże struktury (np. rekordy) danych przechowywane są w wektorach, a w drzewach czerwono czarnych (lub w innych strukturach ułatwiających wyszukiwanie) są przechowyane tylko klucze głóne do tych rekordów lub wręcz numery rekordów. Typowa i dobrze zaprojektowana aplikacja, choć nie zawsze, to bardzo często przechowuje właśnie typ int w drzewach czerwono czarnych. Innymi słowy, testy na typie unsinged int są, wbrew pozorom, bardzo miarodajne dla typowych programów.

Co właściwie wykonuje bencznark 00? Otóż głównie benczmark w pętli dodaje elementy, potem część z tych elementów usuwa, następnie w pętli wyszukuje elementy. Operacje dodawania i usuwania specjalnie się przeplatają w dwóch celach. Po pierwsze, aby zasymulować typową sytuację spotykaną w rzeczywistych programach, programy często modyfikują dane w trakcie swojego życia. Po drugie, aby  sprowokować słabe strony tego typu stuktur danych: biblioteki std::set i QMap w takiej sytuacji mogą mieć duży rozrzut allokowanych adresów i słabiej wykorzystywać pamieć cache, a implementacja tablicowa drzew czerwono czarnych może często reallokować i kopiować cały wektor danych. Poza wstawianiem, kopiowaniem i wyszukiwaniem, bencznark 00 w głównej pętli  także czyści (czytaj: usuwa wszystkie elementy, wywołuje metodę clear) dane. Głównych pętli jest mało, więc czyszczenie zachodzi relatywnie rzadko względem wstawiania, usuwania i wyszukiwania. Zazwyczaj taki sam stan rzeczy obserwujemy w typowych aplikacjach, które długo operują na danych, zanim je całkowicie usuną z pamięci. Podsumowując, pomimo że testy są syntetyczne, to starałem się aby w miarę możliwości odzwierciedlały typowe sytuacje w rzeczywistych programach.

Benchmark został napisany specjalnie w taki sposób, aby można było zbadać potencjalną przewagę wersji wyszukiwania z sortowaniem. W przypadku wersji z sortowaniem, przed długą serią wyszukiwania, następuje właśnie sortowanie. Czas działania wersji z sortowaniem jest powiekszony o czas sortowania, ale za to znacznie spada czas wyszukiwania, ponieważ można wyszukiwać binarnie z optymalizacją pamięci cache na ciągłym obszarze pamięci. O ile wiem, biblioteki std::set i QMap nie mają takich możliwości. Oczywiście można dane z std::set i QMap zrzucić do wektora zewnętrznego, niestety to powoduje narzut pamięciowy i (podejrzewam że) działa wolniej niż sortowanie implementacji tablicowej drzew czerwono czarnych.

Benczmark, poza pomiarem czasu, służy także do przetestowania poprawności działania. Dla wszystkich testów jest wyliczana suma kontrolna. Suma kontrolna musi być taka sama dla wszystkich czterech struktur: std::set, QMap i RBTree w wersji z sortowaniem i bez sortowania. Suma kontrolna jest wyświetlana na standardowe wyjście, można ręcznie sprawdzić czy jest taka sama dla wszystkich testów (tzn dla takich samych parametrów programu, i oczywiście poza rodzajem testu)

Benchmark uruchamiany z linii polecenia przyjmuje siedem parametrów. Są nimi kolejno liczby całkowite:  loop subloop size_i size_r size_f range seed.

Parametr loop oznacza ilość powtórzeń całego testu. Ilość czyszczeń (metoda clear) jest równa parametrowi loop.

Parametr subloop oznacza ilość pętli podrzędnych, w każdej pętli podrzędnej bencznark wykonuje serię wstawień, usunięć i wyszukiwań.

Parametr size_i oznacza ilość wstawień, a właściwie prób wstaień. Bencznark losuje liczbę losową z zakresu od zera do range (dokładnie od zera do range minus jeden), a następnie wstawia tę liczbę pod warunkiem że nie ma jej w zbiorze.

Parametr size_r oznacza ilość usunięć, a właściwie ilość prób usunięć. Bencznark losuje liczbę losową z zakresu od zera do range-1, a następnie usuwa tę liczbę pod warunkiem że jest ona w zbiorze.

Parametr size_f oznacza ilość wyszukiwań. Bencznark losuje liczbę losową z zakresu od zera do range-1, a następnie próbuje ją wyszukać w zbiorze.

Parametr range służy do określania zakresu liczb losowych jakie są wstawiane, usuwane i wyszukiwane w zbiorze.

Parametr seed służy do zainicjowania generatora liczb losowych.

Pierwszy benchamrk wykonuję poniższą komendą:

./bench00.sh 1 1 5000000 2500000 2500000 10000000 1234

Benczmark próbuje dodać 5mln elementów, następnie próbuje usnąć 2.5mln, po czym przeprowadza 2.5mln wyszukiwań liczb całkowitych bez znaku z zakresu od zera do 10mln. Zestawieie czasów:

18.595s - std::set

18.755s - QMap

13.846s - RBTree bez sortowania

13.107s - RBTree z sortowaniem

Widać, że w tym teście implementacja tablicowa drzew czerwono czarnych zdecydowanie jest najszybsza. Wersja z sortowaniem jest jeszcze minimlanie szybsza.

Spróbujmy teraz zwiększyć ilość wyszukiwania:

./bench00.sh 1 1 5000000 2500000 10000000 10000000 1234

30.507s - std::set

31.163s - QMap

23.530s - RBTree bez sortowania

21.078s - RBTree z sortowaniem

Zgodnie z oczekiwaniami, widzimy że wersja z sortowaniem działa jeszcze szybciej względem innych wersji.

Kolejna próba, tym razem sprawdzimy jak działa rozbicie dodawania, usuwania i wyszukiwania na 10 części.

./bench00.sh 1 10 500000 250000 10000000 2000000 1236

2m11.604s - std::set

2m14.663s - QMap

1m38.975s - RBTree bez sortowania

1m7.564s - RBTree z sortowaniem

I tu widać, że wersja z sortowaniem jest około dwa razy szybsza.

W kolejnej próbie została zmniejszona ilość wyszukiwań i zostala zwiększona ilość pętli podrzędnych. Ilość pętli głównych też została zwiększona, ale ilość pętli głównych można traktować niemal tak samo jak ilość wykonania tego samego benchamrku.

./bench00.sh 3 30 500000 250000 100000 5000000 1237 

2m19.707s - std::set

2m20.476s - QMap

1m41.704s - RBTree bez sortowania

1m42.054s - RBTree z sortowaniem

Widzimy zgodnie z oczekiwaniami, że implementacja tablicowa znowu jest najszybsza, a dla małej ilości wyszukiwań nie opłacało się sortować.

Podsumowując, implementacja tablicowa jest bardziej wydajna, a jeśli możliwe jest zastosowania sortowania przed dlugą serią wyszukiwań, to implementacja tablicowa drzew czerwono czarnych jest ponad dwa razy szybsza.