[ Pobierz całość w formacie PDF ]
.W przypadku trzech zmiennych A, B i C mo¿eto wygl¹daæ nastêpuj¹co:void (*MyFunctions[8])()={MyFunction0, // A=false, B=false, C=falseMyFunction1, // A=false, B=false, C=trueMyFunction2, // A=false, B=true, C=falseMyFunction3, // A=false, B=true, C=trueMyFunction4, // A=true, B=false, C=falseMyFunction5, // A=true, B=false, C=trueMyFunction6, // A=true, B=true, C=falseMyFunction7 // A=true, B=true, C=true}W naszej przyk³adowej aplikacji wykorzystaliœmy tê ideê wielokrotnie.Abywybraæ kolejne s³owo z listy jako kandydata do umieszczenia na diagramie,program analizuje ka¿d¹ literê ka¿dego s³owa na liœcie i wyszukuje wszystkiewyst¹pienia tej litery w diagramie.Przy ka¿dym wyst¹pieniu poszukiwanej literyprzeprowadzana jest seria testów, maj¹cych na celu sprawdzenie, czy w miejscutego wyst¹pienia badane s³owo z listy mo¿e zostaæ skrzy¿owane ze s³owemistniej¹cym na diagramie.Z³o¿onoœæ tego procesu stanowi wspania³e pole dooptymalizacji.Po pierwsze, dla ka¿dej litery alfabetu tworzona jest lista jej wyst¹pieñ(pozycji) w diagramie; ka¿dorazowo, gdy nowe s³owo umieszczane jest nadiagramie, listy zwi¹zane z jego literami s¹ uaktualniane.Dziêki temu w celuznalezienia wszystkich wyst¹pieñ ¿¹danej litery wystarczy przetworzyæ zwi¹zan¹z ni¹ listê, zamiast przeszukiwaæ 150 pozycji diagramu.Po drugie, z ka¿d¹ „kratk¹” diagramu zwi¹zana jest informacja o tym, czy s³owo,do którego owa kratka przynale¿y, ma orientacjê poziom¹ czy pionow¹.Informacjata ma postaæ dwóch zmiennych boolowskich HorizWord i VertWord; dla kratki nienale¿¹cej do danego s³owa obie te zmienne maj¹ wartoœæ false, dla kratkile¿¹cej na przeciêciu s³Ã³w obydwie równe s¹ true, dla pozosta³ych kratekdok³adnie jedna z nich równa jest true.Dziêki temu, testuj¹c dan¹ pozycjêdiagramu jako kandydata na skrzy¿owanie s³Ã³w, ³atwo mo¿emy okreœliæ kierunek, wktórym ulokowaæ nale¿y ewentualne nowe s³owo – jest to ten kierunek, dlaktórego odpowiednia zmienna (HorizWord lub VertWord) ma wartoœæ false.Po trzecie, z ka¿d¹ kratk¹ le¿¹c¹ na przeciêciu s³Ã³w zwi¹zana jest informacja opunktacji tego przeciêcia (score); dla kratek nie le¿¹cych na przeciêciachwartoœæ ta równa jest zeru.Informacja ta tworzona jest w momencie krzy¿owanias³Ã³w, a dziêki niej obliczenie sumarycznej punktacji zwi¹zanej z przeciêciamiwymaga tylko zsumowania punktacji wszystkich kratek, zamiast czasoch³onnegowykrywania przeciêæ i osobnej „wyceny” ka¿dego z nich.Obliczaj¹ca punktacjêfunkcja CalcScore() jest przecie¿ jednym z „w¹skich garde³” aplikacji, cowynika z tabeli 4.2.Wykorzystywanie ró¿nego rodzaju tablic przegl¹dowych jest szczególnymprzypadkiem bardziej ogólnego aspektu optymalizacji – unikania obliczeñniepotrzebnych, na przyk³ad dubluj¹cych siê.Jaskrawym przyk³adem takiego„dublowania” jest w naszej aplikacji dwukrotne sprawdzanie mo¿liwoœciskrzy¿owania ka¿dej pary s³Ã³w.Je¿eli na przyk³ad w liœcie wystêpuj¹ s³owa JARi ROD, to najpierw do poziomo (na przyk³ad) ulokowanego s³owa JAR dopasowujesiê pionowe skrzy¿owanie ROD, a nieco póŸniej do pionowo ulokowanego s³owa RODtworzy siê poziome skrzy¿owanie JAR.W obydwu przypadkach wynik jest ten sam, awiêc druga próba okazuje siê wyraŸnie niepotrzebna.Rozwi¹zanie tego problemu ma charakter doœæ skomplikowany, jego istot¹ jestjednak wprowadzenie pewnego uporz¹dkowania s³Ã³w, jeœli chodzi o kolejnoœæpobierania ich do testów; mo¿na sformu³owaæ w tym wzglêdzie dwie dosyæ ogólneregu³y.Dla pustego diagramu: po umieszczeniu na diagramie pierwszego s³owa kandydatamina utworzenie z nim skrzy¿owania s¹ wy³¹cznie s³owa wystêpuj¹ce w liœcie nadalszych ni¿ ono pozycjach.Dla diagramu czêœciowo zape³nionego: wœród s³Ã³w wystêpuj¹cych na liœcie pobadanym s³owie odnajduje siê s³owo najdawniej umieszczone na diagramie – s³owoto wraz z nastêpnymi s³owami na liœcie tworzy zbiór kandydatów do badania namo¿liwoœæ skrzy¿owania z badanym s³owem.Po zaimplementowaniu opisanych usprawnieñ ponownie zmierzyliœmy czas kompletnejanalizy 11-elementowego zbioru s³Ã³w.Oto wynik:obecny czas wykonania: 24,33 sekundy;usprawnienie w tym kroku: 203600 proc.;przyspieszenie globalne: 3270 razy.To ju¿ nie s¹ ¿arty – takie usprawnienie oznacza skrócenie obliczeñ np.z 10lat do jednego dnia! Oto przyk³ad, jak zbêdne operacje potrafi¹ sparali¿owaæka¿de obliczenie.W naszej aplikacji kryje siê jeszcze jedna, tym razem niezbyt spektakularnamo¿liwoœæ ulepszenia – w celu okreœlenia, czy dana kratka diagramu le¿y naskrzy¿owaniu s³Ã³w, bada siê zwi¹zane z ni¹ dwie zmienne HorizWord i VertWord,gdy tymczasem wystarczy³oby badanie, czy punktacja zwi¹zana z dan¹ kratk¹ jestniezerowa.Wprowadzaj¹c tê modyfikacjê, otrzymujemy niewielkie, choæ zauwa¿alneprzyspieszenie:obecny czas wykonania: 23,68 sekundy;usprawnienie w tym kroku: 2,7 proc.;przyspieszenie globalne: 3360 razy.Jest to znacznie wiêcej, ni¿ zdzia³aæ mo¿e nawet najbardziej inteligentnaoptymalizacja automatyczna – wobec czego materialnych kszta³tów nabierastwierdzenie ze wstêpu do rozdzia³u o przewadze optymalizuj¹cego programistynad optymalizuj¹cym kompilatorem.Wysokopoziomowe techniki optymalizowania generowanego koduIstnieje wiele technik optymalizowania kodu Ÿród³owego aplikacji pod k¹temefektywnoœci kodu generowanego przez kompilator.Nale¿y przy okazji pamiêtaæ otym, i¿ kod „wygl¹daj¹cy” optymalnie z punktu widzenia C++ niekoniecznie musiskutkowaæ efektywnym kodem wynikowym, a tak¿e o tym, i¿ efektywnoœæ koduŸród³owego niekoniecznie idzie w parze z jego czytelnoœci¹.Specyfika nowoczesnych procesorówStopieñ z³o¿onoœci wspó³czesnych procesorów znajduje siê w œcis³ej relacji zez³o¿onoœci¹ kodu, jaki przychodzi im wykonywaæ.Co prawda jedyn¹ bezpoœredni¹mo¿liwoœci¹ kontroli kodu wynikowego generowanego z programu napisanego wjêzyku wysokiego poziomu s¹ wszelkiego rodzaju „wstawki” asemblerowe i nieinaczej jest w C++, jednak¿e niektóre postaci kodu Ÿród³owego daj¹ kod bardziejefektywny z punktu widzenia architektury konkretnego procesora.W nastêpnychpunktach zak³adamy, i¿ procesorem, pod k¹tem którego optymalizujemy kod naszejaplikacji, jest Pentium II – znakomita wiêkszoœæ rozpatrywanych tu jego cechodnosi siê tak¿e do równorzêdnych procesorów AMD serii K.Przewidywanie rozga³êzieñNajwa¿niejsz¹ cech¹ sprzêtowej optymalizacji procesora Pentium II jestmo¿liwoœæ statycznego i dynamicznego przewidywania rozga³êzieñ (ang.branchprediction).W kodzie procesorów serii x86 wyró¿niæ mo¿emy trzy rodzaje skoków:bezwarunkowe, warunkowe w przód i warunkowe w ty³
[ Pobierz całość w formacie PDF ]