Netrix's devBlog

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 :).

Jednym z ostatnich zadań na laboratorium Informatycznych Systemów Sterowania (i jednocześnie jedynym ciekawym) było zaimplementowanie protokołu Modbus w postaci aplikacji emulujących urządzenia master i slave, komunikujących się ze sobą bezpośrednio korzystając z portów szeregowych COM (RS-232). Zadanie to zrealizowałem minimalistycznie tworząc jedną aplikację, która emuluje oba urządzenia i implementuje 6 pierwszych publicznych funkcji wraz z podglądem rejestrów.

Aplikacja jest napisana w C# i korzysta z Windows Forms oraz klasy SerialPort (która załatwia całą komunikację po porcie COM). Całość implementacji bazuje na specyfikacji Modbusa znajdującej się tutaj. Oprócz tego podczas pisania wykorzystywałem również kilka aplikacji:

• Virtual Serial Ports Emulator (VSPE) – aplikacja emulująca pary portów COM,
• Modbus Poll – aplikacja emulująca urządzenie Master dla protokołu Modbus,
• Modbus Slave – aplikacja emulująca urządzenie Slave dla protokołu Modbus.

Dwie ostatnie aplikacje posłużyły mi jako referencja implementacji protokołu, ponieważ sama specyfikacja nie zawiera informacji o sposobie liczenia CRC i LRC, więc trzeba było do tego dojść metodą prób, błędów i Google.

Sam program obsługuje (jak już wcześniej wspomniałem) 6 pierwszych, publicznych funkcji protokołu Modbus dla obu urządzeń (Master i Slave) przesyłając dane w trybie ASCII lub RTU. Urządzenie Slave posiada podgląd rejestrów Coils, Discrete Inputs, Input Registers oraz Holding Registers, po 4096 sztuk każdy (wszystkie Read-Only, generowane na podstawie seed = 0). Aplikacja posiada również podgląd wysyłanych i otrzymywanych ramek w postaci logu transmisji.

Program wraz z kodem źródłowym znajdują się tutaj (wymaga .NET Framework 2.0) .

Dzisiejsza notka będzie o tym jak pobrać kod HTML strony WWW w aplikacji C++ korzystając z WinSock2.

Pierwszą rzeczą, którą trzeba wiedzieć jest to w jaki sposób robi to przeglądarka internetowa. Zacznę od tego jak wygląda typowy adres strony WWW na przykładzie adresu do działu artykułów na stronie http://www.gamedev.pl/:

http://www.gamedev.pl/articles.php

Powyższy adres składa się z kilku części:

• „http://” – protokół reprezentujący sposób transmisji danych, dzięki niemu przeglądarka wie w jaki sposób komunikować się z serwerem oraz na jaki port wysyłać żądania
• „www.gamedev.pl” – domena na którą będzie wysłane zapytanie – podany adres jest tłumaczony na adres IP przez serwer DNS
• „/articles.php” – adres żądanego plik lub żądanie dla serwera WWW, które aplikacja wykorzystuje do stworzenia nagłówka

Przeglądarka mając adres strony tworzy odpowiedni nagłówek, który zostaje wysłany do serwera WWW. Jak już wspomniałem adresem tego serwera jest domena zawarta w adresie WWW natomiast port jest określany na podstawie protokołu, czyli w przypadku „http://” jest to port 80. Nagłówek HTTP powinien zawierać następujące elementy:

• rodzaj zapytania – w przypadku pobrania strony jest to „GET”
• adres żądanego pliku lub żądanie – to co chcemy od serwera otrzymać, najczęściej jest to adres pliku na serwerze, czyli „/articles.php” w tym przykładzie
• wersja protokołu – typowo HTTP/1.1
• domena hosta

Dodatkowo, jeśli jest to konieczne, można wysłać informacje o tym, jakiej przeglądarki używamy (UserAgent), informacje o akceptowanych plikach, kodowaniu, ciasteczkach oraz czasie trwania połączenia, więcej można dowiedzieć się z tej strony wiki oraz samych nagłówków, które wysyła przeglądarka. Jako ciekawostkę mogę dodać, że istnieje fajna wtyczka dla Firefoxa, która pokazuje nagłówki wysyłane przez przeglądarkę – Live HTTP headers.

Oto nagłówek uzyskany z pomocą tej wtyczki podczas łączenia się do przykładowej strony:

1
2
3
4
5
6
7
8
9

GET /articles.php HTTP/1.1
Host: www.gamedev.pl
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.1; pl; rv:1.9.1.7) Gecko/20091221 Firefox/3.5.7
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: pl,en-us;q=0.7,en;q=0.3
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-2,utf-8;q=0.7,*;q=0.7
Keep-Alive: 300
Connection: keep-alive

Jak widać jest on trochę długi (usunąłem informacje o ciasteczkach, nie są tutaj potrzebne). Aby pobrać kod strony wystarczą tak naprawdę dwie pierwsze linijki. Jednak ważną rzeczą jest, aby po każdej linijce występowała para znaków \r\n a koniec nagłówka reprezentowany był przez dwie pary tych znaków. W przypadku, gdy nagłówek nie będzie zawierał tak skonstruowanego nagłówka, serwer po prostu udrzuci zapytanie.

Teraz pora na kod C++ z WinSock2, oto on:

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

// Usuwa zbędne definicje z nagłówka
#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
#endif
 
#include <winsock2.h>
#include <ws2tcpip.h>
#include <string>
 
#define BUFFER_SIZE 2048
#pragma comment(lib, "ws2_32.lib")	// Niezbędna biblioteka
using namespace std;
 
int main()
{
	//************************************************
	// Inicjalizacja WinSock2
	//************************************************
	WSADATA wsaData;
	int error;
	string answer;
	ZeroMemory(&wsaData, sizeof(wsaData));
 
	if(FAILED(WSAStartup(MAKEWORD(2,2), &wsaData)))	// MAKEWORD(2,2) - Wersja WinSock
	{
		return 1;
	}
 
	char recvBuffer[BUFFER_SIZE];
	addrinfo hint;					// Struktura przechowująca dane o połączeniu
	addrinfo* wsResult;				// Wskaźnik na rezultat
	SOCKET pSocket;					// Właściwy pSocket
 
	ZeroMemory(recvBuffer, sizeof(recvBuffer));
	ZeroMemory(&hint, sizeof(hint));
	hint.ai_family = AF_UNSPEC;		// Rodzaj transmisji - nieokreślony
	hint.ai_socktype = SOCK_STREAM;	// Typ gniazda - strumień
	wsResult = NULL;
	pSocket = INVALID_SOCKET;
 
	//************************************************
	// Tworzenie zapytania	
	//************************************************
 
	// Wyciąganie informacji z adresu
	string httpAddress = "http://www.gamedev.pl/articles.php";
	string temp = httpAddress.substr(httpAddress.find("http://") + sizeof("http://") - 1);	// Tylko http:// więc można wyciąć
	string domain = temp.substr(0, temp.find_first_of('/'));								// Domena
	string addressTail = temp.substr(temp.find_first_of('/'));								// Żądanie pliku
 
	// Tworzenie nagłówka
	temp = string("GET ") + addressTail + " HTTP/1.1\r\n"
			   + "Host: " + domain + "\r\n"
			   //+ "User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; pl; rv:1.9.1.5) Gecko/20091102 Firefox/3.5.5\r\n"
			   //+ "Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8\r\n"
			   //+ "Accept-Language: pl,en-us;q=0.7,en;q=0.3\r\n"
			   //+ "Accept-Encoding: gzip,deflate\r\n"
			   //+ "Accept-Charset: ISO-8859-2,utf-8;q=0.7,*;q=0.7\r\n"
			   //+ "Keep-Alive: 300\r\n"
			   //+ "Connection: keep-alive\r\n"
			   + "\r\n\r\n";
 
	// Pobieranie IP serwera z serwera DNS
	if(FAILED(getaddrinfo(domain.c_str(), TEXT("80"), &hint, &wsResult)))
	{
		printf("Nie udalo sie pobrac IP\n");
		return 1;
	}
 
	// Wskaźnik na zwrócone adresy
	addrinfo* ptr = wsResult;
 
	// Tworzenie socketu
	if(FAILED(pSocket = socket(wsResult->ai_family, wsResult->ai_socktype, wsResult->ai_protocol))) 
	{
		freeaddrinfo(wsResult);
		printf("Nie udało się utworzyc socketu\n");
		return 1;
	}
 
	//************************************************
	// Wysyłanie zapytania	
	//************************************************
 
	// Łączenie się do serwera
	if(FAILED(connect(pSocket, ptr->ai_addr, (int)ptr->ai_addrlen))) 
	{
		printf("Nie udalo sie polaczyc do serwera\n");
		goto Error;
	}
 
	// Wysyłanie nagłówka
	if(FAILED(send(pSocket, temp.c_str(), temp.size(), 0)))
	{
		printf("Nie udalo sie wyslac naglowka\n");
		goto Error;
	}
 
	// Kończenie wysyłania
	if(FAILED(shutdown(pSocket, SD_SEND)))
	{
		printf("Nie udalo sie zamknac polaczenia\n");
		goto Error;
	}
 
	//************************************************
	// Odbieranie danych
	//************************************************
 
	// Odbieranie danych
	do
	{
		ZeroMemory(recvBuffer, sizeof(recvBuffer));
		error = recv(pSocket, recvBuffer, sizeof(recvBuffer), 0);
 
		if(error > 0)
		{
			answer += string(recvBuffer);
		}
	}
	while(error > 0);
 
	closesocket(pSocket);		// Zamknięcie socketu
	freeaddrinfo(wsResult);		// oraz zwolnienie struktury addrinfo
 
	printf("Kod HTML strony \"http://www.gamedev.pl/articles.php\":\n\n%s", answer.c_str());
	return 0;
 
Error:
	closesocket(pSocket);
	freeaddrinfo(wsResult);
	return 1;
}

Wynikiem tego kodu jest wyświetlony kod HTML przykładowej strony.

Czas nadszedł, jak obiecałem (przynajmniej sobie w myślach), umieszczam prezentacje wraz z kodem źródłowym silnika prezentacji. Prezentacja była robiona w grupie, ja zająłem się silnikiem, kolega Konrad Polak dopieścił grafikę, a reszta dbała o informacje :).

Teraz troszkę o silniku. Silnik bazuje na SDL, filmiki wyświetlam z pomocą DirectShow, muzykę odtwarzam dzięki IrrKlang (Nie DS, ponieważ z IrrKlang miałem gotowe). Silnik składa się z 3 części:

• Core: odpowiedzialny za obsługę scen, obsługę zdarzeń
• Scene: układa scenę z poszczególnych kontrolek
• Controls: klasa bazowa, z której dziedziczą poszczególne kontrolki

Ogólnie uważam, że dość dobrze zaprojektowałem ten silnik, jeśli ktoś miałby rady to chętnie wysłucham ( lub przeczytam).

Jak mówiłem z projektem zamieszczam kod, jeśli ktoś jest zainteresowany.

Download

PS. W lewym i prawym dolnym rogu są strzałki, wystarczy najechać :).

// Download się zagubił ;(