{"id":879,"date":"2011-04-13T22:15:50","date_gmt":"2011-04-13T21:15:50","guid":{"rendered":"http:\/\/netrix.org.pl\/?p=879"},"modified":"2011-04-13T22:15:50","modified_gmt":"2011-04-13T21:15:50","slug":"optymalizacja-aplikacji-c-z-wykorzystaniem-amd-codeanalyst","status":"publish","type":"post","link":"https:\/\/netrix.org.pl\/index.php\/2011\/04\/13\/optymalizacja-aplikacji-c-z-wykorzystaniem-amd-codeanalyst\/","title":{"rendered":"Optymalizacja aplikacji C++ z wykorzystaniem AMD CodeAnalyst"},"content":{"rendered":"

W tej notce opisz\u0119 moj\u0105 pierwsz\u0105 porz\u0105dn\u0105 styczno\u015b\u0107 z programem CodeAnalyst i przy okazji poka\u017c\u0119, w jaki spos\u00f3b uda\u0142o mi si\u0119 nieco zoptymalizowa\u0107 napisan\u0105 przeze mnie aplikacj\u0119 implementuj\u0105c\u0105 rozwi\u0105zywanie problemu kolorowania grafu za pomoc\u0105 algorytmu genetycznego.<\/p>\n

\"CodeAnalyst<\/a>CodeAnalyst jest programem s\u0142u\u017c\u0105cym do profilowania aplikacji. Jego zadaniem jest zbieranie r\u00f3\u017cnego rodzaju pr\u00f3bek w trakcie dzia\u0142ania testowanej aplikacji, kt\u00f3re s\u0105 nast\u0119pnie przedstawiane w formie wykresu lub tabeli. Dzi\u0119ki temu wida\u0107 od razu, kt\u00f3re miejsca aplikacji maj\u0105 najwi\u0119kszy wp\u0142yw na badany parametr z dok\u0142adno\u015bci\u0105 do wykonywanych instrukcji Assemblera. Program ten mo\u017cna znale\u017a\u0107 na stronie producenta<\/strong><\/a>. Jego g\u0142\u00f3wne okienko jest przedstawione na obrazku obok.<\/p>\n

Jak ju\u017c wspomnia\u0142em badan\u0105 aplikacj\u0105 jest moja implementacja algorytmu ewolucyjnego u\u017cytego do rozwi\u0105zania problemu kolorowania grafu. Kod tej aplikacji wraz z przyk\u0142adowym grafem znajduje si\u0119 tutaj<\/strong><\/a>. Jest to kod, od kt\u00f3rego wychodz\u0119 w tej notce, zatem nie uwzgl\u0119dnia on \u017cadnych poprawek. Poni\u017csza tabela zawiera \u015brednie wyniki pomiaru cykli i czasu jakie zabiera g\u0142\u00f3wna p\u0119tla programu na dw\u00f3ch maszynach:<\/p>\n\n\n\n\n
Procesor<\/th>\nSystem<\/th>\nKompilator<\/th>\nCz\u0119stotliwo\u015b\u0107 zegara<\/th>\nLiczba cykli<\/th>\nCzas<\/th>\n<\/tr>\n
AMD Turion64 2 GHz<\/td>\nMS Windows 7<\/td>\nmsvc<\/td>\n25 MHz (QPF)<\/td>\n4111926149 cykli (QPC)<\/td>\n164,48 s<\/td>\n<\/tr>\n
Intel Pentium 4 2,66 GHz<\/td>\nLinux<\/td>\ng++<\/td>\n2659,98 MHz (cpuinfo)<\/td>\n268359191768 cykli (__rdtsc())<\/td>\n100,89 s<\/td>\n<\/tr>\n<\/table>\n

Optymalizacja b\u0119dzie dotyczy\u0107 g\u0142\u00f3wnie tej pierwszej platformy, ale postanowi\u0142em z ciekawo\u015bci sprawdzi\u0107 jak zmiany b\u0119d\u0105 wp\u0142ywa\u0107 na czas wykonywania si\u0119 kodu r\u00f3wnie\u017c na drugiej platformie.<\/p>\n

Analiza programu b\u0119dzie polega\u0107 na szukaniu miejsc, w kt\u00f3rych sp\u0119dza on najwi\u0119cej czasu. Zatem na pocz\u0105tek nale\u017cy uruchomi\u0107 program CodeAnalyst, a nast\u0119pnie utworzy\u0107 projekt wybieraj\u0105c profil Time-based profile<\/em>. Wed\u0142ug mnie dobrze jest r\u00f3wnie\u017c zaznaczy\u0107 opcje Stop data collection when app exits<\/em> oraz Profile the duration of the app execution<\/em>. Dzi\u0119ki temu CodeAnalyst poczeka z analiz\u0105 wynik\u00f3w a\u017c badana aplikacja sko\u0144czy dzia\u0142anie. Po utworzeniu projektu mo\u017cna przyst\u0105pi\u0107 do test\u00f3w. Zatem po wyciszeniu\/wy\u0142\u0105czeniu niepotrzebnych aplikacji mo\u017cna wybra\u0107 z menu Profile -> Start<\/em> lub klikn\u0105\u0107 zielon\u0105 strza\u0142k\u0119.<\/p>\n

Po zako\u0144czeniu dzia\u0142ania aplikacji zostanie wy\u015bwietlone podsumowanie, kt\u00f3re wygl\u0105da mniej wi\u0119cej tak:
\n\"CodeAnalyst<\/a>\"CodeAnalyst<\/a><\/p>\n

Obie te zak\u0142adki przedstawiaj\u0105 dok\u0142adnie to samo, czyli procentowy udzia\u0142 pr\u00f3bek w ka\u017cdej aplikacji\/bibliotece\/module, r\u00f3\u017cnica wyst\u0119puje tylko w formie przedstawienia danych. Co w tym podsumowaniu jest interesuj\u0105cego? W tym widoku jeszcze nic, ale CodeAnalyst umo\u017cliwia podgl\u0105d szczeg\u00f3\u0142\u00f3w ka\u017cdego z wymienionych wcze\u015bniej byt\u00f3w, nawet dowolnego procesu wybranego z zak\u0142adki Processes<\/em>. Jednak poniewa\u017c ta notka obejmuje tylko jedn\u0105 aplikacje, w dodatku t\u0119, kt\u00f3ra zebra\u0142a najwi\u0119cej pr\u00f3bek, zatem przejd\u0119 teraz do niej. Oto co pokazuje si\u0119 po dwukrotnym klikni\u0119ciu na jej proces:
\n\"CodeAnalyst<\/a><\/p>\n

W tym widoku wida\u0107 ju\u017c nieco wi\u0119cej. S\u0105 tu pokazane funkcje, kt\u00f3re zabiera\u0142y najwi\u0119cej czasu. Na samej g\u00f3rze wida\u0107 jedn\u0105, kt\u00f3ra zabiera a\u017c 40% pr\u00f3bek, jest to funkcja EvaluateConflicts(<\/em>), kt\u00f3ra zlicza konflikty dla ka\u017cdego osobnika w ca\u0142ej populacji. Warto si\u0119 jej przyjrze\u0107 z bliska:
\n\"CodeAnalysy<\/a><\/p>\n

CodeAnalyst, wykorzystuj\u0105c dane zawarte w pliku .pdb, kt\u00f3ry powinien znajdowa\u0107 si\u0119 obok pliku wykonywalnego, potrafi wy\u015bwietli\u0107 i dopasowa\u0107 pr\u00f3bki do odpowiedniego miejsca w kodzie. Mo\u017cna r\u00f3wnie\u017c podejrze\u0107 wykonywany w tym miejscu kod Assemblera, co jest bardzo przydatne (\u017ceby nie powiedzie\u0107 kluczowe) przy profilowaniu aplikacji. Co zatem wida\u0107 na powy\u017cszym screenie? Jest tam co\u015b co tak naprawd\u0119 powinno znajdowa\u0107 si\u0119 tylko i wy\u0142\u0105cznie w aplikacji kompilowanej w trybie Debug. To sprawdzanie poprawno\u015bci odwo\u0142ania si\u0119 do elementu tablicy w klasie std::vector<\/em>. Jest to nieco dziwne, poniewa\u017c jest tam u\u017cywany operator[]<\/em>, a standardowo ta wersja odwo\u0142ania nie powinna by\u0107 sprawdzana, w przeciwie\u0144stwie do funkcji at()<\/em>.
\nOkazuje si\u0119 jednak, \u017ce implementacja STL dostarczana z kompilatorem msvc<\/em> ma zaimplementowane takie sprawdzenie, kt\u00f3re mo\u017cna co prawda wy\u0142\u0105czy\u0107 flag\u0105 _SECURE_SCL<\/em> ustawion\u0105 na 0, ale domy\u015blnie ta opcja jest w\u0142\u0105czona. Wi\u0119cej informacji mo\u017cna znale\u017a\u0107 tu<\/strong><\/a> lub bezpo\u015brednio tutaj<\/strong><\/a>.<\/p>\n

Poni\u017csza tabela zawiera wyniki pomiar\u00f3w cykli i czasu z wy\u0142\u0105czeniem tego sprawdzania:<\/p>\n\n\n\n\n
Procesor<\/th>\nSystem<\/th>\nKompilator<\/th>\nCz\u0119stotliwo\u015b\u0107 zegara<\/th>\nLiczba cykli<\/th>\nCzas<\/th>\nZysk<\/th>\n<\/tr>\n
AMD Turion64 2 GHz<\/td>\nMS Windows 7<\/td>\nmsvc<\/td>\n25 MHz (QPF)<\/td>\n3191994350 cykli (QPC)<\/td>\n127,68 s<\/td>\n22,37%<\/td>\n<\/tr>\n
Intel Pentium 4 2,66 GHz<\/td>\nLinux<\/td>\ng++<\/td>\n2659,98 MHz (cpuinfo)<\/td>\n269220460226 cykli (__rdtsc())<\/td>\n101,21 s<\/td>\n-0.32%<\/td>\n<\/tr>\n<\/table>\n

W przypadku msvc<\/em> wida\u0107, \u017ce jest ju\u017c lepiej, a przypadek gcc<\/em> zosta\u0142 praktycznie nietkni\u0119ty, zatem nie posiada on domy\u015blnie tego typu sprawdzania. Na poni\u017cszych screenach widniej\u0105 wyniki ponownego pr\u00f3bkowania aplikacji.
\n\"CodeAnalysy<\/a>\"CodeAnalyst<\/a><\/p>\n

Jak mo\u017cna zauwa\u017cy\u0107, ta drobna poprawka pozwoli\u0142a kompilatorowi zinline’owa\u0107 ca\u0142\u0105 funkcj\u0119 EvaluateConflicts(). Dzi\u0119ki temu aplikacja wykonuje si\u0119 szybciej o ok. 22 %. Kod tej wersji znajduje si\u0119 pod tym<\/strong><\/a> linkiem.<\/p>\n

Jednak na tym nie koniec poprawek, poniewa\u017c jest jeszcze jedno miejsce, z kt\u00f3rym da si\u0119 co\u015b zrobi\u0107. Ot\u00f3\u017c je\u015bli si\u0119 przyjrze\u0107 podsumowaniu ca\u0142ej aplikacji jeszcze raz, mo\u017cna zauwa\u017cy\u0107, \u017ce sp\u0119dza ona du\u017co czasu w funkcji insert()<\/em> drzewa std::_Tree<\/em>, kt\u00f3re jest implementacj\u0105 zbioru (std::set<\/em>) w bibliotece standardowej. Klasa ta jest u\u017cywana w operatorze selekcji w celu wybrania losowych i niepowtarzaj\u0105cych si\u0119 osobnik\u00f3w do turnieju. Co za tym idzie, funkcja insert()<\/em> jest wywo\u0142ywana minimum raz dla ka\u017cdego wolnego miejsca w turnieju (w przypadku testowym jest 50 miejsc), a\u017c do wype\u0142nienia ca\u0142ej nowej populacji (tutaj 5000), czyli kr\u00f3tko m\u00f3wi\u0105c – do\u015b\u0107 cz\u0119sto.<\/p>\n

Rozwi\u0105zaniem, kt\u00f3re przyj\u0105\u0142em w tym miejscu by\u0142o ca\u0142kowite pozbycie si\u0119 klasy std::set<\/em> na rzecz w\u0142asnego sposobu wybierania losowych i r\u00f3\u017cnych osobnik\u00f3w do turnieju. Wynikiem tego jest taka oto klasa:<\/p>\n

\r\ntemplate\r\nclass RandomSet    \/\/ singleton\r\n{\r\npublic:\r\n    RandomSet()\r\n    { \r\n        for(uint i = 0; i < RANGE; ++i)\r\n        { m_aSet[i] = i; }\r\n    }\r\n\r\n    const uint* GetRandomSet(uint uCount, uint uInnerRange)\r\n    {\r\n        uint uTemp, uRand;\r\n        for(uint i = 0; i < uCount; ++i)\r\n        {\r\n            uRand = rand() % (uInnerRange - i);\r\n            uTemp = m_aSet[i];\r\n            m_aSet[i] = m_aSet[i + uRand];\r\n            m_aSet[i + uRand] = uTemp;\r\n        }\r\n        return m_aSet;\r\n    }\r\n    \r\nprivate:\r\n    uint m_aSet[RANGE];\r\n};\r\n<\/pre>\n
Klasa ta wykorzystuje tablic\u0119, w kt\u00f3rej zapisane s\u0105 kolejno indeksy wszystkich osobnik\u00f3w. Przy ka\u017cdym wywo\u0142aniu funkcji GetRandomSet()<\/em> tablica ta jest ponownie mieszana tak, by na jej pocz\u0105tku znalaz\u0142y si\u0119 w miar\u0119 losowe warto\u015bci. Dzi\u0119ki temu, \u017ce wybierane warto\u015bci s\u0105 zamieniane z warto\u015bciami z pocz\u0105tku tablicy, zbi\u00f3r pozostaje pe\u0142ny ale jest on stopniowo mieszany, przy czym najwi\u0119ksza r\u00f3\u017cnorodno\u015b\u0107 wyst\u0119puje zawsze na pocz\u0105tku tablicy. To ostatnie nie ma tak naprawd\u0119 wi\u0119kszego znaczenia, poniewa\u017c najwa\u017cniejsze jest to, \u017ceby funkcja zwraca\u0142a za ka\u017cdym razem r\u00f3\u017cne warto\u015bci.<\/p>\n
Kolejna tabela zawiera wyniki test\u00f3w po wprowadzeniu tych zmian:<\/p>\n\n\n\n\n
Procesor<\/th>\nSystem<\/th>\nKompilator<\/th>\nCz\u0119stotliwo\u015b\u0107 zegara<\/th>\nLiczba cykli<\/th>\nCzas<\/th>\nZysk<\/th>\n<\/tr>\n
AMD Turion64 2 GHz<\/td>\nMS Windows 7<\/td>\nmsvc<\/td>\n25 MHz (QPF)<\/td>\n1144922576 cykli (QPC)<\/td>\n45,8 s<\/td>\n64,13 %<\/td>\n<\/tr>\n
Intel Pentium 4 2,66 GHz<\/td>\nLinux<\/td>\ng++<\/td>\n2659,98 MHz (cpuinfo)<\/td>\n105596054178 cykli (__rdtsc())<\/td>\n39,7 s<\/td>\n60,78 %<\/td>\n<\/tr>\n<\/table>\n
W przypadku tej poprawki mo\u017cna ju\u017c zaobserwowa\u0107 znaczny zysk i to na obu platformach (Windows - 64%, Linux - 61 %). Na poni\u017cszych obrazkach kolejne zrzuty z CodeAnalyst.
\n\"CodeAnalyst<\/a>\"CodeAnalyst<\/a><\/p>\n
Wida\u0107 tutaj, \u017ce ilo\u015b\u0107 pr\u00f3bkowanego kodu znacznie zmala\u0142a, a proporcje mi\u0119dzy funkcjami zn\u00f3w si\u0119 zr\u00f3\u017cnicowa\u0142y. Dzi\u0119ki temu mo\u017cna zobaczy\u0107, \u017ce funkcja GetRandomSet()<\/em> zabiera znacznie mniej pr\u00f3bek ni\u017c EvaluateGeneration()<\/em>. Kod tej wersji mo\u017cna pobra\u0107 st\u0105d<\/strong><\/a>.<\/p>\n
Pozostaje teraz ponownie zapyta\u0107, czy mo\u017cna co\u015b tu jeszcze zoptymalizowa\u0107? Mo\u017ce i mo\u017cna, ale prawdopodobnie zajmie to ju\u017c troch\u0119 wi\u0119cej czasu ni\u017c poprzednie poprawki. Jednym z oczywistych krok\u00f3w jakie mo\u017cna tutaj wykona\u0107 to zast\u0105pienie std::vector<\/em> zwyk\u0142ymi tablicami dynamicznymi, ale w tym przypadku zysk jest osi\u0105galny tylko na Linuksie co pokazuje kolejna tabela:<\/p>\n\n\n\n\n
Procesor<\/th>\nSystem<\/th>\nKompilator<\/th>\nCz\u0119stotliwo\u015b\u0107 zegara<\/th>\nLiczba cykli<\/th>\nCzas<\/th>\nZysk<\/th>\n<\/tr>\n
AMD Turion64 2 GHz<\/td>\nMS Windows 7<\/td>\nmsvc<\/td>\n25 MHz (QPF)<\/td>\n1144922576 cykli (QPC)<\/td>\n46,2 s<\/td>\n-0.89 %<\/td>\n<\/tr>\n
Intel Pentium 4 2,66 GHz<\/td>\nLinux<\/td>\ng++<\/td>\n2659,98 MHz (cpuinfo)<\/td>\n105596054178 cykli (__rdtsc())<\/td>\n37 s<\/td>\n6,78 %<\/td>\n<\/tr>\n<\/table>\n
Kod tego przypadku znajduje si\u0119 tutaj<\/strong><\/a>.<\/p>\n
I to w\u0142a\u015bciwie tyle, wnioski? CodeAnalyst jest bardzo dobrym narz\u0119dziem do profilowania aplikacji, jest \u0142atwy w obs\u0142udze, a co najwa\u017cniejsze jest za darmo. Opr\u00f3cz tego warto zwraca\u0107 uwag\u0119 na implementacje biblioteki standardowej w u\u017cywanym kompilatorze, poniewa\u017c mo\u017cna si\u0119 nieco zdziwi\u0107, tak jak to mia\u0142o miejsce w przypadku std::vector<\/em> w tym przyk\u0142adzie. Dodatkowo warto czasami poszuka\u0107 innych rozwi\u0105za\u0144 dla niekt\u00f3rych problem\u00f3w, poniewa\u017c wyniki mog\u0105 okaza\u0107 si\u0119 ca\u0142kiem zaskakuj\u0105ce.<\/p>\n
Na koniec jeszcze taka ma\u0142\u0105 dygresja odno\u015bnie algorytmu ewolucyjnego - operator mutacji powinien testowa\u0107 prawdodpobie\u0144stwo dla ka\u017cdego genu osobnika (czyli koloru w\u0119z\u0142a), a nie tak jak w tej implementacji, dla ca\u0142ego osobnika :).<\/p>\n","protected":false},"excerpt":{"rendered":"
W tej notce opisz\u0119 moj\u0105 pierwsz\u0105 porz\u0105dn\u0105 styczno\u015b\u0107 z programem CodeAnalyst i przy okazji poka\u017c\u0119, w jaki spos\u00f3b uda\u0142o mi si\u0119 nieco zoptymalizowa\u0107 napisan\u0105 przeze mnie aplikacj\u0119 implementuj\u0105c\u0105 rozwi\u0105zywanie problemu kolorowania grafu za pomoc\u0105 algorytmu genetycznego. CodeAnalyst jest programem s\u0142u\u017c\u0105cym do profilowania aplikacji. Jego zadaniem jest zbieranie r\u00f3\u017cnego rodzaju pr\u00f3bek w trakcie dzia\u0142ania testowanej aplikacji, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[155,156,179,159,68,158,157],"_links":{"self":[{"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/posts\/879"}],"collection":[{"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/comments?post=879"}],"version-history":[{"count":126,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/posts\/879\/revisions"}],"predecessor-version":[{"id":1015,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/posts\/879\/revisions\/1015"}],"wp:attachment":[{"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/media?parent=879"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/categories?post=879"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/tags?post=879"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}