Netrix's devLog

W tej notce opiszę moją pierwszą porządną styczność z programem CodeAnalyst i przy okazji pokażę, w jaki sposób udało mi się nieco zoptymalizować napisaną przeze mnie aplikację implementującą rozwiązywanie problemu kolorowania grafu za pomocą algorytmu genetycznego.

CodeAnalyst jest programem służącym do profilowania aplikacji. Jego zadaniem jest zbieranie różnego rodzaju próbek w trakcie działania testowanej aplikacji, które są następnie przedstawiane w formie wykresu lub tabeli. Dzięki temu widać od razu, które miejsca aplikacji mają największy wpływ na badany parametr z dokładnością do wykonywanych instrukcji Assemblera. Program ten można znaleźć na stronie producenta. Jego główne okienko jest przedstawione na obrazku obok.

Jak już wspomniałem badaną aplikacją jest moja implementacja algorytmu ewolucyjnego użytego do rozwiązania problemu kolorowania grafu. Kod tej aplikacji wraz z przykładowym grafem znajduje się tutaj. Jest to kod, od którego wychodzę w tej notce, zatem nie uwzględnia on żadnych poprawek. Poniższa tabela zawiera średnie wyniki pomiaru cykli i czasu jakie zabiera główna pętla programu na dwóch maszynach:

Optymalizacja będzie dotyczyć głównie tej pierwszej platformy, ale postanowiłem z ciekawości sprawdzić jak zmiany będą wpływać na czas wykonywania się kodu również na drugiej platformie.

Analiza programu będzie polegać na szukaniu miejsc, w których spędza on najwięcej czasu. Zatem na początek należy uruchomić program CodeAnalyst, a następnie utworzyć projekt wybierając profil Time-based profile. Według mnie dobrze jest również zaznaczyć opcje Stop data collection when app exits oraz Profile the duration of the app execution. Dzięki temu CodeAnalyst poczeka z analizą wyników aż badana aplikacja skończy działanie. Po utworzeniu projektu można przystąpić do testów. Zatem po wyciszeniu/wyłączeniu niepotrzebnych aplikacji można wybrać z menu Profile -> Start lub kliknąć zieloną strzałkę.

Po zakończeniu działania aplikacji zostanie wyświetlone podsumowanie, które wygląda mniej więcej tak:

Obie te zakładki przedstawiają dokładnie to samo, czyli procentowy udział próbek w każdej aplikacji/bibliotece/module, różnica występuje tylko w formie przedstawienia danych. Co w tym podsumowaniu jest interesującego? W tym widoku jeszcze nic, ale CodeAnalyst umożliwia podgląd szczegółów każdego z wymienionych wcześniej bytów, nawet dowolnego procesu wybranego z zakładki Processes. Jednak ponieważ ta notka obejmuje tylko jedną aplikacje, w dodatku tę, która zebrała najwięcej próbek, zatem przejdę teraz do niej. Oto co pokazuje się po dwukrotnym kliknięciu na jej proces:

W tym widoku widać już nieco więcej. Są tu pokazane funkcje, które zabierały najwięcej czasu. Na samej górze widać jedną, która zabiera aż 40% próbek, jest to funkcja EvaluateConflicts(), która zlicza konflikty dla każdego osobnika w całej populacji. Warto się jej przyjrzeć z bliska:

CodeAnalyst, wykorzystując dane zawarte w pliku .pdb, który powinien znajdować się obok pliku wykonywalnego, potrafi wyświetlić i dopasować próbki do odpowiedniego miejsca w kodzie. Można również podejrzeć wykonywany w tym miejscu kod Assemblera, co jest bardzo przydatne (żeby nie powiedzieć kluczowe) przy profilowaniu aplikacji. Co zatem widać na powyższym screenie? Jest tam coś co tak naprawdę powinno znajdować się tylko i wyłącznie w aplikacji kompilowanej w trybie Debug. To sprawdzanie poprawności odwołania się do elementu tablicy w klasie std::vector. Jest to nieco dziwne, ponieważ jest tam używany operator[], a standardowo ta wersja odwołania nie powinna być sprawdzana, w przeciwieństwie do funkcji at().
Okazuje się jednak, że implementacja STL dostarczana z kompilatorem msvc ma zaimplementowane takie sprawdzenie, które można co prawda wyłączyć flagą _SECURE_SCL ustawioną na 0, ale domyślnie ta opcja jest włączona. Więcej informacji można znaleźć tu lub bezpośrednio tutaj.

Poniższa tabela zawiera wyniki pomiarów cykli i czasu z wyłączeniem tego sprawdzania:

W przypadku msvc widać, że jest już lepiej, a przypadek gcc został praktycznie nietknięty, zatem nie posiada on domyślnie tego typu sprawdzania. Na poniższych screenach widnieją wyniki ponownego próbkowania aplikacji.

Jak można zauważyć, ta drobna poprawka pozwoliła kompilatorowi zinline’ować całą funkcję EvaluateConflicts(). Dzięki temu aplikacja wykonuje się szybciej o ok. 22 %. Kod tej wersji znajduje się pod tym linkiem.

Jednak na tym nie koniec poprawek, ponieważ jest jeszcze jedno miejsce, z którym da się coś zrobić. Otóż jeśli się przyjrzeć podsumowaniu całej aplikacji jeszcze raz, można zauważyć, że spędza ona dużo czasu w funkcji insert() drzewa std::_Tree, które jest implementacją zbioru (std::set) w bibliotece standardowej. Klasa ta jest używana w operatorze selekcji w celu wybrania losowych i niepowtarzających się osobników do turnieju. Co za tym idzie, funkcja insert() jest wywoływana minimum raz dla każdego wolnego miejsca w turnieju (w przypadku testowym jest 50 miejsc), aż do wypełnienia całej nowej populacji (tutaj 5000), czyli krótko mówiąc – dość często.

Rozwiązaniem, które przyjąłem w tym miejscu było całkowite pozbycie się klasy std::set na rzecz własnego sposobu wybierania losowych i różnych osobników do turnieju. Wynikiem tego jest taka oto klasa:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

template<uint RANGE>
class RandomSet    // singleton
{
public:
    RandomSet()
    { 
        for(uint i = 0; i < RANGE; ++i)
        { m_aSet[i] = i; }
    }
 
    const uint* GetRandomSet(uint uCount, uint uInnerRange)
    {
        uint uTemp, uRand;
        for(uint i = 0; i < uCount; ++i)
        {
            uRand = rand() % (uInnerRange - i);
            uTemp = m_aSet[i];
            m_aSet[i] = m_aSet[i + uRand];
            m_aSet[i + uRand] = uTemp;
        }
        return m_aSet;
    }
 
private:
    uint m_aSet[RANGE];
};

Klasa ta wykorzystuje tablicę, w której zapisane są kolejno indeksy wszystkich osobników. Przy każdym wywołaniu funkcji GetRandomSet() tablica ta jest ponownie mieszana tak, by na jej początku znalazły się w miarę losowe wartości. Dzięki temu, że wybierane wartości są zamieniane z wartościami z początku tablicy, zbiór pozostaje pełny ale jest on stopniowo mieszany, przy czym największa różnorodność występuje zawsze na początku tablicy. To ostatnie nie ma tak naprawdę większego znaczenia, ponieważ najważniejsze jest to, żeby funkcja zwracała za każdym razem różne wartości.

Kolejna tabela zawiera wyniki testów po wprowadzeniu tych zmian:

W przypadku tej poprawki można już zaobserwować znaczny zysk i to na obu platformach (Windows – 64%, Linux – 61 %). Na poniższych obrazkach kolejne zrzuty z CodeAnalyst.

Widać tutaj, że ilość próbkowanego kodu znacznie zmalała, a proporcje między funkcjami znów się zróżnicowały. Dzięki temu można zobaczyć, że funkcja GetRandomSet() zabiera znacznie mniej próbek niż EvaluateGeneration(). Kod tej wersji można pobrać stąd.

Pozostaje teraz ponownie zapytać, czy można coś tu jeszcze zoptymalizować? Może i można, ale prawdopodobnie zajmie to już trochę więcej czasu niż poprzednie poprawki. Jednym z oczywistych kroków jakie można tutaj wykonać to zastąpienie std::vector zwykłymi tablicami dynamicznymi, ale w tym przypadku zysk jest osiągalny tylko na Linuksie co pokazuje kolejna tabela:

Kod tego przypadku znajduje się tutaj.

I to właściwie tyle, wnioski? CodeAnalyst jest bardzo dobrym narzędziem do profilowania aplikacji, jest łatwy w obsłudze, a co najważniejsze jest za darmo. Oprócz tego warto zwracać uwagę na implementacje biblioteki standardowej w używanym kompilatorze, ponieważ można się nieco zdziwić, tak jak to miało miejsce w przypadku std::vector w tym przykładzie. Dodatkowo warto czasami poszukać innych rozwiązań dla niektórych problemów, ponieważ wyniki mogą okazać się całkiem zaskakujące.

Na koniec jeszcze taka małą dygresja odnośnie algorytmu ewolucyjnego – operator mutacji powinien testować prawdodpobieństwo dla każdego genu osobnika (czyli koloru węzła), a nie tak jak w tej implementacji, dla całego osobnika :).