RSS

Szybki komputer nie pokona szybkiego algorytmu

Liczba odsłon: 74

Gwałtow­ny roz­wój elek­tro­ni­ki spo­wo­do­wał, że na­wet na do­mo­wym biur­ku sto­ją dzi­siaj mikro­kom­pu­te­ry o mo­cy obli­cze­nio­wej po­rów­ny­wal­nej z su­per­kom­pu­te­ra­mi sprzed pa­ru lat. Teoretycz­nie po­win­no to po­zwo­lić nam wy­ko­rzys­ty­wać in­for­ma­ty­kę we wszyst­kich tych za­sto­so­wa­niach, w któ­rych jesz­cze do nie­daw­na na­gmin­nie bra­ko­wa­ło mo­cy obli­cze­nio­wej.

Niestety, ostat­ni­mi cza­sy zbyt często szyb­kość kom­pu­te­ra – za­miast skut­ko­wać po­ja­wia­niem się lep­szych, szyb­szych i bar­dziej funkcjo­nal­nych pro­gra­mów – sta­no­wi uspra­wied­li­wie­nie sto­so­wa­nia ma­ło wy­daj­nych algo­ryt­mów. Podstawową za­sa­dą opty­ma­li­zac­ji jest bo­wiem „nie opty­ma­li­zuj”. Nie, nie po­my­li­łem się: pierw­sza wer­sja pro­gra­mu po­win­na być za­pi­sa­na czy­tel­nie, ele­ganc­ko, z peł­nym wy­ko­rzys­ta­niem na­rzę­dzi ję­zy­ka pro­gra­mo­wa­nia. Dopiero w na­stęp­nym kro­ku dzia­ła­nie pro­gra­mu po­win­no zo­stać prze­ana­li­zo­wa­ne, a miej­sca, w któ­rych traci się naj­wię­cej wy­daj­noś­ci — zlo­ka­li­zo­wa­ne i prze­ro­bio­ne. Początku­ją­ce­go pro­gra­mis­tę-en­tuz­jas­tę od pro­gra­mis­ty-profesjonalisty róż­ni właś­nie to, że ten pierw­szy już na wstęp­nym eta­pie prac wpro­wa­dza do ko­du sztucz­ki zwięk­sza­ją­ce wy­daj­ność, pod­czas gdy ten dru­gi sku­pia się po­cząt­ko­wo na archi­tek­tu­rze pro­gra­mu i uru­cha­mia go, nie przej­mu­jąc się szyb­koś­cią dzia­ła­nia i póź­niej do­pie­ro opty­ma­li­zu­jąc kod.

Gorzej, gdy ten dru­gi etap nig­dy nie ma miej­sca. A na­wet dzi­siaj, w erze su­per­wy­daj­nych mikro­kom­pu­te­rów i kom­pi­la­to­rów co­raz to le­piej opty­ma­li­zu­ją­cych kod, wy­bór właś­ci­we­go algo­ryt­mu roz­wią­za­nia prob­le­mu i uni­ka­nie nie­po­trzeb­nych ope­rac­ji skut­ku­ją dra­ma­tycz­nym wzros­tem szyb­koś­ci prze­twa­rza­nia.

Przykładem mo­że być pro­gram do dzie­le­nia wy­ra­zów w tekś­cie stro­ny WWW, któ­ry nie­daw­no na­pi­sa­łem. Pierwsza wer­sja zo­sta­ła stwo­rzo­na bez oglą­da­nia się na wy­daj­ność; jej za­da­niem mia­ło być ra­czej po­twier­dze­nie tezy o moż­li­woś­ci efek­tyw­ne­go, pół­auto­ma­tycz­ne­go dzie­le­nia wy­ra­zów w tekś­cie po­prze­pla­ta­nym znacz­ni­ka­mi HTML. Program zo­stał na­pi­sa­ny względ­nie ele­ganc­ko, z uwzględ­nie­niem obiek­to­we­go po­dzia­łu na parę wy­ra­zów orygi­nal­ny-po­dzie­lo­ny i słow­nik po­dzia­łów. Wcale też nie dzia­łał wol­no: spo­ry jak na stro­nę WWW plik o obję­toś­ci 425 KiB prze­twa­rzał w cza­sie nie prze­kra­cza­ją­cym trzech se­kund, osią­ga­jąc śred­nią prze­pus­to­wość 140 KiB/s. Jak na moż­li­woś­ci kom­pu­te­ra nie było to oczy­wiś­cie wiel­kie osiąg­nię­cie, jed­nak ta­ki czas ocze­ki­wa­nia na po­dział tak ob­szer­ne­go tek­stu był jak naj­bar­dziej akcep­to­wal­ny.

Ostatecz­ną, spraw­dzo­ną już w prak­ty­ce wer­sję pro­gra­mu skom­pi­lo­wa­łem z włą­czo­ną opty­ma­li­zac­ją (opcja -O2 kom­pi­la­to­ra gcc). Poskutko­wa­ło to skró­ce­niem cza­su prze­twa­rza­nia tego sa­me­go tek­stu do 1,3 s, a więc po­nad dwu­krot­nie. Osiągana prze­pus­to­wość prze­kro­czy­ła 320 KiB/s. Biorąc pod uwa­gę, że obję­tość tek­stu ty­po­wej stro­ny WWW czy wpi­su blo­gu nie prze­kra­cza za­zwy­czaj kil­ku­nas­tu lub kil­ku­dzie­się­ciu ki­lo­baj­tów, ta­kie wy­ni­ki naj­praw­do­po­dob­niej w wie­lu przy­pad­kach oz­na­cza­ły­by ko­niec prac nad pro­gra­mem.

Tymczasem za­sto­so­wa­na słow­ni­ko­wa me­to­da za­mia­ny wy­ra­zów na ich po­dzie­lo­ne wer­sje niesie w so­bie ol­brzy­mi potencjał. Zamiast bo­wiem wy­szu­ki­wać pod­sta­wo­wą, nie­po­dzie­lo­ną for­mę wy­ra­zu w słow­ni­ku w spo­sób li­nio­wy moż­na wy­ko­rzys­tać fakt, że wy­ra­zy moż­na łat­wo upo­rząd­ko­wać alfa­be­tycz­nie i – re­kur­syw­nie dzie­ląc ich zbiór na po­ło­wy – wy­szu­kać w koń­cu pod­zbiór kil­ku wy­ra­zów, któ­re po­win­ny za­wie­rać w so­bie po­szu­ki­wa­ną po­zyc­ję. Choć me­to­da ta – zwa­na wy­szu­ki­wa­niem bi­nar­nym lub me­to­dą bi­sek­cji – wy­ma­ga utrzy­my­wa­nia ideal­ne­go upo­rząd­ko­wa­nia prze­szu­ki­wa­ne­go zbio­ru, da­je ol­brzy­mie zyski wy­daj­noś­cio­we — szcze­gól­nie przy ob­szer­nym zbio­rze da­nych. Zamiast n kro­ków po­rów­nań (dla n wy­ra­zów za­pi­sa­nych w słow­ni­ku), w naj­gor­szym przy­pad­ku ko­niecz­ne jest prze­pro­wa­dze­nie tyl­ko log2 n kro­ków.

Po za­sto­so­wa­niu me­to­dy bi­sek­cji za­rów­no do wsta­wia­nia ele­men­tów do słow­ni­ka (dzię­ki cze­mu wy­ra­zy słow­ni­ka wczy­ty­wa­ne z pli­ku tra­fia­ły od ra­zu we właś­ci­we miej­sce lis­ty), jak i do wy­szu­ki­wa­nia wy­ra­zów w słow­ni­ku, czas prze­twa­rza­nia przy­kła­do­we­go pli­ku spadł z 1,3 s do śred­nio stu mili­se­kund. To dzie­się­cio­krot­na po­pra­wa wy­daj­noś­ci. Tak szyb­kie na­rzę­dzie nie dość, że sta­je się jesz­cze wy­god­niej­sze w uży­ciu (nic tak nie cie­szy użyt­kow­ni­ka, jak na­tych­mias­to­wa re­akcja pro­gra­mu na ope­rac­ję), to jesz­cze mo­że zo­stać wy­ko­rzys­ta­ne do dyna­micz­ne­go prze­twa­rza­nia ser­wo­wa­nych stron WWW lub treś­ci ko­men­ta­rzy, bez po­trze­by bu­fo­ro­wa­nia wy­ni­ków i spraw­dza­nia spójności treś­ci.

Jak widać, wciąż opła­ca się do­bie­rać właś­ci­we dla da­ne­go prob­le­mu algo­ryt­my i po­świę­cać czas opty­ma­li­zo­wa­niu two­rzo­ne­go opro­gra­mo­wa­nia.


Warto jeszcze dodać, że jeśli od początku kod pisany jest zgodnie z pewnymi zasadami, to nie trzeba potem tracić czasu na optymalizację czegoś, co domyślnie powinno być już z głową napisane. To będą raczej odniesienia z myślą o c/c++, ale i częściowo w innych językach do zastosowania. Jak choćby operacje na tablicach – korzystajmy z wskaźników lub iteratorów (w zależności od sytuacji), a nie bezpośredniego odwołania do n-tego elementu tablicy. Tak samo korzystanie z const, choć przede wszystkim powinno logicznie dzielić program, to przecież też dodatkowo pomaga kompilatorowi w stworzeniu optymalnego kodu. Już nie wspomnę o takich sztuczkach jak restrict, które też narzucają przemyślenie algorytmu pod kątem dostępu do danych. Ja jestem więc za tym, żeby, o ile to możliwe (akurat choćby z tego restrict bym zrezygnował czasami), tworzyć od razu kod, który umożliwi późniejszą optymalizację – modularnie, podzielony, przejrzysty, czytelny, bez udziwnień, ale jednocześnie z wykorzystaniem tych prostych rzeczy, które i tak się wie, że potem się zrobi, a które nie wpływają negatywnie na czytelność kodu, a czasami wręcz poprawiają ją.
Ja się wychowałem jeszcze na ośmiobitowym Atari i na demoscenie, więc optymalizacja kodu to dla mnie oczywistość. Przykład to choćby procedura narysowania punktu (plot) na „maluchu”, systemowa to czas rzędu bodaj 2,5 tysiąca cykli procesora, zoptymalizowana wg jednego z czasopism to 130 cykli procesora. Zaś „ploty” wykorzystywane w demach zeszłu do 21, czy nawet 19 cykli procesora.
Dziś brak optymalizacji widać w wielu programach, które z wersji na wersję potrafią zacząć chodzić np. dwukrotnie wolniej. Straszne.
const to w sumie narzędzie wymuszenia architektury programu w kodzie, choć w niektórych przypadkach w języku C++ niestety jego użycie nie jest do końca tak przejrzyste, jak by mogło być.
Co do restrict — programuję częściej w C++ niż w C, więc nie pamiętam, kiedy ostatni raz użyłem tego słowa kluczowego, o ile w ogóle :)
Co do odwoływania się do elementów tablic: w przypadku bloków funkcjonalnych typu „czarna skrzynka”, wykorzystywanych później w kodzie wyższego poziomu, warto stosować takie sztuczki. Jednak tenże kod wysokiego poziomu będzie na pewno czytelniejszy, gdy zastosuje się odwołania indeksowe (choć w niektórych przypadkach iteratory będą równie dobrze, choć też wcale nie są niezwykle oszczędne). Poza tym, w architekturze IA-32 indeksy wcale nie oznaczają złej wydajności dzięki instrukcji LEA.
Demo scena kojarzy mi się bardziej z optymalizacją rozumianą jako specjalizacja kodu. Swoją drogą, jak już jesteśmy przy 8-bitowcach. Była taka gra jak Gyron i twórcy szumnie chwalili się, że przepisali funkcje rysujące okręgi, bo normalnie to one wolno działały bardzo. Ano przepisali. Korzystali przy tym z tablic, które posiadały długości linii poziomych dla każdej linii pionowej ;) Jest optymalizacja, można szybciej, ale i wielkość okręgu była ograniczona wtedy. W branży, w której robię (gry), też są takie różne rodzaje optymalizacji. Czasami, jeśli w 999 na 1000 przypadków sprawdza się jakaś okrojona wersja działania, to korzysta się z niej, itd.

A co do adresowania to może się tak nie znam, może się nie spotkałem, ale przeważnie szybciej mi działały i nadal działają pętle typu:
for (i = 0, element = &tablica; i < iloscelementow; ++ i, ++ element) cośtam z *element
niż
for (i = 0; i < iloscelementow; ++ i) cośtam z tablica[i]
I jakoś (od czasu, gdy zrozumiałem wskaźniki – dużo w sumie tu przecież do rozumienia nie ma) raczej nie mam problemu z ich rozumieniem/czytaniem. Może to kwestia preferencji ;)
Kompilatora, który by zgrabnie skompilował taką pętlę (drugą), aby działała równie szybko jak ta pierwsza, też nie widziałem.
Jak już jechać z pętlą na wskaźnikach, to nie ma co nawet używać jakiegokolwiek indeksu zazwyczaj (przy założeniu, że mamy co najmniej jeden element, bo tylko wtedy ma sens pobieranie jakiegokolwiek wskaźnika):
element tablica[n];
register element *biezacy = tablica;
element *za_ostatnim = tablica + n;
do {
 coś z *biezacy
} while (++biezacy != za_ostatnim);
Prawda, prawda. Choć swoją drogą najczęściej i tak korzystam albo z iteratorów. A nawet jeśli indeks do czegoś potrzebny, to zawsze można biezacy-tablica. Pytanie jeszcze na przyszłość. 'code' w nawiasach kwadratowych działa?
Programista ze mnie marny, ale gdyby wziąść przykłady z życia codziennego: popularna kolejka do kasy w sklepach. Często widze, że ktoś z jednym produktem musi czekać, aż inni przed nim wypakują cały wózek(troche napewno działa prawo Murphy'ego i do którejkolwiek kasy byśmy nie podeszli zawsze nasza będzie najdłuższa). Gdyby tak sprawdzać ile danych (produktów) będzie miał poszczególny proces, wątek, operacja i najpierw obliczać(obsługiwać) te z najmniejszą ilością. Znacznie wcześniej by mogły przejść do kolejnych zadań. Szczególnie irytujące zdarzenie, gdy do obiadu brakuje jednego produktu, trzeba iść do sklepu i w olejce z tą jedną rzeczą głodni czekamy, aż kilkoro ludzi przed nami większe zakupy zrobi, a tak moglibyśmy wcześniej przejść do kolejnej czynności.
Ad. poprzedniej wypowiedzi, jakie wrażenia po lekturze Systemów operacyjnych? :)
@Jarosław Ciupiński:
Nie działa, ale postaram się za jakiś czas zaimplementować.
@Krzysiek Knapp:
Wbrew pozorom sprawa nie jest taka prosta. Napiszę o tym artykuł.
@Mateusz Dereniowski:
Lektura systemów operacyjnych ma się nie jak do rzeczywistości, skoro Badaboom przy pomocy GeForce'a 9600GT potrafi mi film skonwertować w 15 minut pomiędzy dwoma formatami, a to samo zadanie na DualCore T2300 przy uzyciu darmowego konwertera wykonywane jest w nieco ponad 30 minut, więc teoria sobie, rzeczywistość, sobie, chyba że Badaboom opracowywali ludzie, którzy kupowali 1 bułke i stali w długiej kolejce, a multum innych programów niepotrafiących korzystać z wielordzeniowości(czy to CPU, czy to GPU), programiści syci, którzy właśnie dokładali do kolejki pełen wózek produktów. Czyż nie zauważamy, że pomimo coraz większej liczby rdzeni w procesorach, niewiele programów zostaje przygotowanych pod takie dobrodziejstwo??