Wstęp.
No dobra. Mamy już całkiem solidne podstawy teoretyczne pod praktyczną analizę algorytmów. Jest tylko jeden problem. Maszyna Turinga w liczeniu czegokoliwek jest straszliwie upierdliwa, ze względu na swoją wyjątkową prostotę konstrukcji i przez to toporność w wykonywaniu zadań. Jeżeli ktoś mi nie wierzy, niech rozpisze sobie algorytm dzielenia dwóch liczb na jednotaśmowej maszynie, albo nawet na dwutaśmowej. Jest z tym mnóstwo pracy, a efekt i tak jest mało miarodajny, ze względu na kosmiczne wręcz uproszczenia względem realnych rozwiązań. A jako że musimy być dokładni, a jednocześnie jesteśmy leniwi, znaleźliśmy sobie o wiele lepszy model do analiz. Prosty na tyle, żeby nie uciekł za bardzo od tego co jest nam potrzebne i obejmował klasę operacji dostępnych w każdym procesorze, a skomplikowany na tyle, żeby umieć robić operacje całkiem złożone natychmiastowo (np. owe dzielenie). Maszyna RAM, Random Access Machine, bo takie jej anglosaskie imię, będzie tematem dzisiejszych rozważań. Zaczniemy od wprowadzenia kolejnych pojęć jednocześnie wyjaśniając konstrukcję maszyny i jej korzenie. Zapraszam.
Rzecz pierwsza. Zarys konstrukcji.
Mając w głowie fakt, że model maszyny RAM, ma nam ułatwić pracę i ma być delikatną abstrakcją nad komputerem, możemy sobie zbudować taki mniej więcej model tego, jak mogłaby ona wyglądać. Jak wiemy, albo nie wiemy, komputer składa się generalnie z trzech rzeczy: procesora, pamięci i urządzeń wejścia wyjścia (IO) (Jest to model architektury von Neumanna, Harvardzka ma pamięć na program osobno. Dodatkowo procesor jest w obu rozbity na jednostkę sterującą i arytmetyczno logiczną. Procesor współczesny agreguje obie te jednostki, więc dla uproszczenia miejmy procesor). Obrazek dla poprawienia nastroju i zrozumienia:
Urządzenia wejścia wyjścia, to jest coś co jest nam tutaj zupełnie zbędne, bo po kiego grzyba badając złożoność algorytmów, obecność klawiatur albo innych drukarek, a nawet dysków twardych?
Pamięć? Bardzo potrzebna, tam będą nasze dane wejściowe, tam będziemy mogli zapisać nasz program (Czemu trzeba program zapisać w pamięci? To zaraz.). Jako że mamy już dane i program, musimy mieć coś co ten program wykona i zadziała na danych z pamięci. Takim urządzonkiem będzie procesor, który będzie miał dwie zdolności: komunikacja z pamięcią i wykonywanie rozkazów (Czym jest rozkaz? To zaraz.).
A więc procesor i pamięć. Bueno. Mamy zarys, teraz szczegóły.
Rzecz druga. Pamięć.
Pamięć. W zasadzie pojęcie proste i oczywiste, bo oznacza miejsce gdzie coś można zapisać. Jednak warto opisać budowę tego "czegoś" gdyż okaże się później kluczowa w jednym z poruszanych zagadnień. Pamiętamy, że funkcję pamięci w maszynie Turinga mogła pełnić odpowiednio skomplikowana przestrzeń stanów, albo sama taśma, w której miejsca było nieskończenie wiele. Jednak jak już wcześniej wspomnieliśmy, musimy mieć coś bardziej przyziemnego, coś bardziej realnego i zbliżonego do komputera jaki znamy.
W takim komputerze jaki znamy, pamięci są przeróżne. Bardzo szybkiego dostępu w procesorach, zwane "Cache"em, szybkiego dostępu RAM (Random Access Memory i mimo tych samych liter nie można zamieniać go z RAMem z maszyny, którą opisujemy), relatywnie szybkiego dostępu z dyskami SSD (Solid State Drive) oraz wolnego z dysków HDD (Hard Disc Drive) i super wolnego z taśm magnetycznych o kosmicznych pojemnościach (np. 300TB). My jako że w maszynie RAM mamy taki trochę prosty procesor, to nie mamy mega szybkiej pamięci (bo nie wszystkie procesory mają cache), mamy za to szybką pamięć RAM. Nie jest oczywiście to tak nazwane w samym modelu, jednak jak ktoś kodził kiedyś w assembly, zauważy że właśnie się tak ją traktuje, najprościej ją również tak sobie odwzorować w głowie, gdyż zachowuje się niemal identycznie. Niemal. Właśnie. Jakie są więc różnice?
Samą pamięć będziemy sobie wyobrażać jako wektor. Wektor ten się zaczyna, ale się nie kończy. Taka trochę półprosta. Samo zaczynanie można by usunąć, zakładając, że każdy startujący program na takiej maszynie posiada "gdzieś" zapisane gdzie zaczyna się jego przydział pamięci i zabronić mu poruszania się w lewo od tej pamięci, ale prościej jest założyć że się zaczyna a nie kończy (Chodzi tu o warunek nieskończonej ilości pamięci). Skoro się zaczyna i nie kończy, musi coś mieścić. W naszym modelu mieści liczby, niezależnie od wielkości. Pamięć ta, tak samo jak taśma maszyny Turinga, jest podzielona na "komórki". Komórki owe są miejscem na pojedyncze liczby, a do tych liczb będzie się później można odwołać, czyli odczytać z nich, albo do nich zapisać.
Odwołać? W jaki sposób?
Otóż każda komórka będzie miała przypisaną liczbę porządkową, która będzie ją jednoznacznie definiować. Ta liczba porządkowa nazwana będzie przez nas adresem. Adres ten jednak, zaczynać się będzie w zerze, tj. pierwsza komórka pamięci będzie adresowana jako \(0\). Dlaczego? Ano dlatego, że adresowanie w komputerach jest zdefiniowane przez przesunięcie (offset) od początku przydzielonej dla nas pamięci, a więc pierwsza komórka będzie od początku przesunięta o \(0\), druga o \(1\), trzecia o \(2\) itd. Do komórki pamięci będziemy się więc odwoływać przez adres. Zapisywać pod adres i odczytywać spod adresu. Do samych adresów jeszcze wrócimy, mówiąc o trybach adresowania, ale to później.
To w zasadzie tyle ile musimy wiedzieć na razie. Teraz o troszkę innej pamięci.
Rzecz trzecia. Rejestry.
Rejestr w procesorze to jest generalnie kawałek układu w samym procesorze, który mieści jakąś porcję pamięci. We współczesnych procesorach jest to kolejno 8, 16, 32, 64 bitów oraz wiele więcej poprzez wektorowe rejestry, które to są łączonymi rejestrami do wykonywania pojedynczych operacji na wielu danych jednocześnie (SIMD - single instruction, multiple data), np. dodawania 8 64 bitowych rejestrów do innych 8 64 bitowych rejestrów w za jednym razem. Ich zaletą jest to, że będąc bezpośrednio w środku procesora, są niemalże natychmiastowe w dostępie (mega, mega, mega szybsze niż zwykła pamięć RAM, a nawet szybsza niż cache), ale ich celem nie jest przechowywanie danych. Ich celem jest przechowywanie danych, na których procesor będzie wykonywał operacje. Bo trzeba wiedzieć, że procesor nie wykonuje operacji na pamięci, tylko na rejestrach, nawet jeżeli może do niej zapisać, lub czytać, to czyta do rejestru i zapisuje z rejestru. ZAWSZE. Ano dlatego, że mając układ scalony, który wykonuje mnożenie, będzie on spięty z bitami w rejestrze, który jest fizycznie w procesorze, a nie z pamięcią, gdyż wymagałoby to spięcia się z wszytkimi komórkami pamięci, co jest obiektywnie niewykonalne (i głupie zarazem). W przypadku maszyny RAM też tak będzie, jednak tutaj definicja rejestru będzie trochę płynniejsza niż w zwykłym procesorze. Mianowicie, skoro rejestr to miejsce, z którym procesor może wchodzić w interakcję w kontekście wykonywanych operacji, to w maszynie RAM, każda komórka pamięci będzie rejestrem. Mówiąc prościej, procesor naszej maszyny, czy też mówiąc ściślej, jednostka wykonawcza naszej maszyny, może wykonywać operacje natychmiastowe (czyli takie jak na rejestrach) z każdym miejscem w pamięci. Analizując algorytmy np. w C++ zauważymy że ma to sens.
Rzecz czwarta. Rozkazy.
"Das ist ein Befehl, Herr Obersturmführer!" - chciałoby się zakrzyknąć słysząc podtytuł. I dokładnie w ten sposób traktować będziemy nasz procesor. Będziemy mu kazali robić rzeczy i on je będzie bezkrytycznie robił. Nakaz ten będzie zwany rozkazem właśnie. Procesor jest generalnie głupim urządzeniem, więc rozkazy będą jak najprostsze. My jako że budujemy abstrakcję na realny procesor, musimy wypracować minimalny zestaw tych rozkazów. Rozkazy zaś mogą być różne. Mogą nie pracować na żadnych rejestrach, ale mogą też używać konkretnych, a mogą też używać podanych. Generalnie będą one operować na rejestrach (pamiętamy że w RAM rejestrem jest każda komórka pamięci). Na myśl, intuicyjnie, przychodzą nam np. rozkazy dodawania zawartości dwóch rejestrów, rozkazy mnożenia, dzielenia, kopiowania, usuwania, czyli takie proste, generyczne rozkazy, które w maszynie przeznaczonej do liczenia różnych rzeczy, byłyby najbardziej przydatne. Ale czy można dla nich znaleźć wspólną bazę?
Rzecz piąta. Program.
Pamiętacie jak mówiłem, że program znajduje się w pamięci? Teraz powiem dlaczego. Otóż procesor jest urządzeniem dosyć prostym i operuje na rzeczach prostych. Więc jak komputer startuje, co taki procesor ma zrobić? Skąd ma wiedzieć co ma zrobić? W procesorach generalnie panuje taki myk, że procesor spodziewa się, że we wcześniej ustalonym "gdzieś miejscu" znajduje się początek programu, który on ma wykonywać. Taki program to seria rozkazów. Rozkaz to tak naprawdę liczba, którą procesor rozumie jako rozkaz. Obok liczby reprezentującej rozkaz jest seria innych liczb, które, wedle ustalonego wcześniej standardu, składają się na to jakie parametry ma dany rozkaz. Więc taki procesor sczytuje z pamięci liczbę, zastanawia się przez moment co z nią zrobić, po odkodowaniu co ma zrobić, robi to, i sczytuje następny rozkaz. I tak dalej i tak dalej, aż się te rozkazy nie skończą (wiadomo, że są jeszcze inne szczegółowe mechanizmy na taki koniec programu i jak się ma taki procesor wtedy zachować, ale to nie temat na dziś). My więc również zakładamy, że nasz program znajduje się gdzieś w pamięci naszej maszyny i że procesor wie, gdzie zacząć jego sczytywanie.
Ciekawym też mechanizmem jest to, jak procesor porusza się po takich rozkazach. Generalnie odbywa się to tak, że sobie ciśnie jeden po drugim. Co jednak jeżeli mamy, np. pętlę, czyli taką serię rozkazów która wykonuje się cyklicznie \(n\) razy, i robi się ona tysiąc razy? Będziemy tę serię tysiąc razy kopiować? Zajmie nam to mnóstwo pamięci i znacząco upośledzi możliwości wykonywania czegokolwiek. Bez sensu więc i głupie. Potrzebne nam więc będą tak zwane skoki, czyli mechanizm pozwalający dosłownie wskoczyć w dowolne miejsce w programie, a nie tylko rozkaz po rozkazie kolejno. Żeby takie skoki zrealizować, musimy wiedzieć gdzie skoczyć. Możemy to zrealizować na kilka sposobów. We współczesnych procesorach implementuje się to jako rejestr, który jest adresem następnej instrukcji, jaką będziemy wykonywać. I tak zmieniając zawartość tego rejestru, procesor, będzie "skakać" po dowolnych miejscach programu, jakie sobie wybierzemy. Nazywa się on RIP (Instruction Pointer, R jako przedrostek wprowadzony w x64) w x86_64, czy EIP w x86. Można też czasami spotkać się z nazwą PC (Program Counter). Maszyna RAM również taki rejestr będzie miała i będzie go używała również do nawigowania po programie.
Rzecz szósta. Maszyna rejestrowa.
Maszyna RAM jest dosyć złożona, patrząc na to skąd się wywodzi bezpośrednio. Mając opisane podstawy pojęciowe, można przejść do ciekawych rzeczy związanych z tym jak powstała.
Modeli maszyn rejestrowych jest masę. Zaczynając od modelu Hao Wanga, przez Minskiego i Melzaka, i kończąc na Hartmanisie, następowała ich stopniowa ewolucja. Ciekawym faktem jest to, że nie ma jednoznacznych definicji tej maszyny. Każdy kto opracowywał swoją, miał swoją wizję i swoje pojęcia, ale wszystkie składają się w ostateczności do tego co zaraz pokażemy. Nie będziemy opisywać każdej z nich z osobna, może kiedyś to zrobimy, ale teraz przyjrzymy się czym maszyna rejestrowa jest, by później korzystając z tej wiedzy ujrzeć pełną postać maszyny RAM.
Maszyna rejestrowa jest to w uproszczeniu maszyna, która do operacji używa rejestrów, w odróżnieniu do maszyn stosowych, które używają stosu (czyli specjalnego miejsca w pamięci, w strukturze stosowej. Co to jest stos i jak działa, to na później.). Co to znaczy? Znaczy to tyle, że wykonując np. dodawanie dwóch liczb, procesor będzie spodziewał się tych dwóch liczb w określonych jako operandy/argumenty rejestrach i wynik zapisze do rejestru. W stosowej, procesor spodziewałby się dwóch liczb na stosie, zdjąłby je, dodał i wynik wyrzucił na szczyt stosu. Ot cała tajemnica. Maszyna ta jednak ma pewne właściwości o których należy powiedzieć, a są to:
-
Dowolna, skończona liczba rejestrów. Chodzi tu o brak ograniczenia górnego na liczbę rejestrów. Po co ten brak? Ano dlatego, że będzie można modelu użyć, skalując go dowolnie do każdego algorytmu w zależności od potrzeb. Będą to zarówno rejestry przeznaczenia ogólnego, czyli np. do dodawania i mnożenia, i również rejestry specjalne, np. rejestr rozkazów, z adresem następnej instrukcji, lub np. rejestr stanu, który w realnych rozwiązaniach pokazuje, czy nie nastąpiło np. przepełnienie podczas mnożenia, czy dodawania (w abstrakcyjnym modelu to nie nastąpi, ale chodziło o przykład), albo np. czy porównanie wykazało, że liczby są sobie równe. Będą one używane jako operandy rozkazów, jak i wskaźniki potrzebne do obsługi logiki.
-
Zestaw jak najmniejszy i jak najprostszych instrukcji. Bo chodzi nam o zbudowanie fajnej abstrakcji nad wszysktimi procesorami. Będą to wiec instrukcje arytmetyczne, sterujące (typu skok do adresu), porównania, skoki warunkowe, kopiowania, czyszczenia, ładowania, zapisywania. Niejednokrotnie udowadniano, że wszystkie te instrukcje można ograniczyć np. do trzech, albo dwóch (Maszyna Minskyiego), ale my nie schodzimy aż tak głęboko w dół, może kiedyś zejdziemy dla zabawy teoretycznej. Nie będziemy rozważać instrukcji np. do liczenia AES, czy SHA, czyli takich, które implementują już konkretne algorytmy, a są dostępne w procesorach.
Maszyna ta wykonuje program, który jest dostarczony jej w formie jakiejś sekwencji rozkazów w pamięci. I to w sumie tyle. Nic mądrego się tutaj nie dzieje. Maszyna RAM jest więc maszyną rejestrową.
Rzecz siódma. Operacje pośrednie i bezpośrednie.
Ważną właściwością, której niektóre modele maszyn rejestrowych nie miały, były operacje pośrednie. Co to znaczy?
Otóż, jeżeli dobieramy się do jakiejś komórki pamięci podczas wykonywania rozkazu, musimy znać tej komórki adres. Mając taki adres możemy do owej komórki zapisać, albo z niej odczytać. Wykonując rozkaz spodziewamy się konkretnych rejestrów, na których operacje będziemy wykonywać. Ale co jeżeli nie chcemy być konkretni?
Możemy w tym przypadku zastosować tzw. adresowanie pośrednie (albo niebezpośrednie), czyli takie, które wskaże nam, gdzie zapisać jakąś liczbę, a miejsce do którego zapiszemy, będzie wybrane podczas wykonania samego programu. Np. Mając instrukcję dodawania:
dodaj rejestr1, rejestr2, rejestr3Procesor doda rejestr pierwszy do drugiego, a wynik umieści w trzecim. Ale co jeżeli np. pozwolilibyśmy użytkownikowi wybrać, jako parametr algorytmu, gdzie może zapisać wynik? Stworzylibyśmy ścianę ifów w zależności od wejścia? Trochę słabo. Na pomoc przychodzi nam jednak adresowanie pośrednie, dzięki któremu możemy zrobić tak:
dodaj rejestr1, rejestr2, [rejestr3]Czyli dodaj rejestr pierwszy do drugiego, a następnie zapisz wynik do rejestru, którego adres znajduje się w rejestrze trzecim. Ot cała filozofia. Po co w ogóle jest takie adresowanie? Dla wygody po pierwsze, a po drugie, że w ten sposób można uzależnić wykonanie od wejścia, tak jak pokazaliśmy to na przykładzie. Można np. opisać to troszkę prościej, zakładając, że na wejściu dostaniemy \(n\) liczb, które należy pomnożyć przez \(2\) i zapisać w kolejnych rejestrach. Nie mając adresowania pośredniego, będziemy musieli każdy adres rejestru mieć na starcie podany, a że nie znamy liczby wejściowcyh liczb, będzie to niemożliwe. Mając adresowanie pośrednie możemy zrobić pętlę i każdą kolejną liczbę zapisywać w kolejnych rejestrach w zależności od kroku pętli. Bardzo mądry wynalazek.
Maszyna RAM jest więc maszyną rejestrową z adresowaniem pośrednim i bezpośrednim.
Rzecz ósma. Maszyna RAM.
Maszyna RAM. Co to znaczy ten RAM? Random-Access Machine, czyli maszyna losowego dostępu, mówi nam to, że mamy dostęp do każdej komórki pamięci i do każdego rozkazu instant. Bo w takiej maszynie Turinga, żeby dostać się do \(20\) komórki pamięci, musieliśmy zrobić \(20\) przesunięć na prawo, nie mieliśmy więc możliwości natychmiastowego odczytu, albo zapisu. Wiemy już że jest to maszyna rejestrowa, że ma zdolność adresowania pośredniego. Czy ma ona coś jeszcze? Odpowiedź brzmi... Nie. To wszystko. Jest to bardzo prosty model, a jednocześnie bardzo mocny w swej konstrukcji i pozwoli to nam na bardzo wygodną i jednocześnie ładnie korespondującą z rzeczywistością analizę algorytmów. Warto dodać, że procesorek takiej maszyny RAM można sobie zwielokrotnić, modelując algorytmy wykonywane wielowątkowo. Model zostanie tak samo dokładny, męczyć się będziemy tylko przy synchronizacjach dostępu do pamięci.
Rzecz dziewiąta. Analiza kodu wedle rozkazów.
Udało nam się już znaleźć sens maszyny RAM. Znamy jej konstrukcję, znamy jej zastosowania i zalety. Sprawdźmy czy jest idealna do naszych rozwiązań. Wróćmy do sortowania bąbelkowego. Napiszmy sobie teraz, taki algorytm w wersji hardkorowej, bo w wersji pojedynczych rozkazów dla procesora x86 używając tylko rozkazów, jakie opisaliśmy sobie wcześniej jako elementy maszyny. Sprawdźmy czy jest to wygodne.
Jeżeli nie pamiętamy czym jest sortowanie bąbelkowe, odsyłam do artykułu o maszynie Turinga, gdzie owy omówiliśmy. Albo w losowe miejsce internetu. Dla uproszczenia implementacji, założę że jako argumenty dostaję wskaźnik na tablicę 8 bajtowych intów i rozmiar owej tablicy jako 8 bajtowy int, dokładnie w tej kolejności. Kod napiszę w NASM pod Windows10 na x86_64. Będzie to poprawny kod, dlatego że będziemy używać tylko prostych intstrukcji i będziemy mieli do dyspozycji rejestry, co prawda dużo mniej niż "niezliczoną ilość", i są one "natychmiastowe" tak jak w maszynie RAM. Oto owy kod, który za moment omówimy:
section .bss
section .text
global bubble_sort
bubble_sort:
mov rax, rcx ;array
mov r8, rdx ;size
dec r8
mov rcx, -1
outer_loop:
inc rcx
cmp rcx, r8
je end_of_outer_loop
mov r9, r8
sub r9, rcx
mov rdx, -1
inner_loop:
inc rdx
cmp rdx, r9
je outer_loop
mov r10, [rax + rdx*8]
cmp r10, [rax + rdx*8 + 8]
jle inner_loop
mov r11, [rax + rdx*8 + 8]
mov [rax + rdx*8 + 8], r10
mov [rax + rdx*8], r11
jmp inner_loop
end_of_outer_loop:
ret
Kod może być troszkę niezrozumiały, dlatego teraz wyjaśnię po kolei wszystkie użyte mechanizmy:
- mov dst, src - kopiuje zawartość src do dst
- inc mem1 - inkrementuje, czyli zwiększa o 1 mem1
- dec mem1 - dekrementuje, czyli zmniejsza o 1 mem1
- cmp mem1, mem2 - wykonuje porównanie dwóch liczb mem1 oraz mem2. Wynik porównania zostanie odnotowany w rejestrze EFLAGS dzięki czemu będziemy mogli wykonać skok warunkowy. Ale jaki?
- je dst_label - wykonuje skok do etykiety dst_label, jeżeli porównanie wykazało równość mem1 i mem2. Etykieta to jest adres. Liczba. Dla ułatwienia jednak, program, który to kompiluje do kodu wykonywalnego, pozwala nam adresy etykietować, żeby łatwiej nam się pisało. Jak sobie taki kod zdekompilujecie, to zobaczycie, że tekst etykiet został zastąpiony realnymi adresami w kodzie.
- jle dst_label - skok do etykiety dst_label, jeżeli porównanie wykaże że mem1 jest mniejszy bądź równy mem2
- jge dst_label - skok do etykiety dst_label, jeżeli porównanie wykaże że mem1 jest większy bądź równy mem2
- jmp dst_label - skok do etykiety dst_label, bez pytania o nic
- sub mem1, mem2 - odejmuje mem2 od mem1 i zapisuje wynik w mem1
- ret - oznacza powrót, czyli skok, do funkcji z której nasza została wywołana
Przy używaniu niektórych instrukcji użyłem jeszcze nierejestrowych operandów/argumentów, zamkniętych w nawiasy kwadratowe. Co one oznaczają? Ano adresowanie pośrednie. W x86 ma ono swoją konwencję, można ją sobie przestudiować, ale ja tutaj wytłumaczę tylko jak zostało użyte tutaj:
- mov reg1, [reg2 + reg3*\(2^n\) + \(2^n\)] - oznacza że weź reg2 dodaj do niego reg3 pomnożony przez jakąś potęgę dwójki i dodaj do niego jakąś potęgę dwójki, wyjdzie Ci z tego jakiś adres w pamięci, i zawartość z pod tego adresu pamięci wrzuć do reg1. Jeżeli zmienimy kolejność operandów, czyli zrobimy:
- mov [reg2 + reg3*\(2^n\) + \(2^n\)], reg1 - otrzymamy instrukcję, która robi odwrotnie, czyli zawartość rejestru reg1 wpisuje do pamięci, której adres sobie wyliczymy w nawiasach kwadratowych
Działa to nie tylko w mov, ale np. w cmp też, co widać w kodzie. Działa to również w wielu innych instrukcjach, dlatego że jest to wygodne i architekci procesorów dają nam takie opcje w prezencie.
No to teraz mamy rozszyfrowane co się w tym kodzie wydarzyło. Czy można by ten kod napisać lepiej, zoptymalizować bardziej? Jasne że tak. Tutaj jednak miał być prosty i łatwy do rozszyfrowania. I taki jest. Jeżeli ktoś nie wierzy, że działa, można sobie go skopiować i nasmem przetworzyć do binarnego formatu, i wykonać. Polecam mi nie ufać i sprawdzać.
Skoro mamy już kod maszyny RAM (realnej nawet), policzmy sobie ile operacji wykona sortując tablicę wielkości \(n\). Jednym słowem sprawdźmy jaka będzie złożoność czasowa tego algorytmu w tym modelu. Na początku:
section .bss
section .text
global bubble_sort
bubble_sort:
mov rax, rcx ;array
mov r8, rdx ;size
dec r8
mov rcx, -1
Przerzucamy sobie wartości rejestrów dla wygody z jednego miejsca w drugie i przygotowujemy pętlę. \(4\) operacje. Ta dekrementacja r8 jest dlatego, że pętli zewnętrznych będzie \(n - 1\) więc skoro w parametrze mamy \(n\) to sobie odejmujemy \(1\).
outer_loop:
inc rcx
cmp rcx, r8
je end_of_outer_loop
mov r9, r8
sub r9, rcx
mov rdx, -1
Jesteśmy w głównej pętli. Wykona się ona \(n - 1\) razy i robi ona:
- inkrementację,
- porównanie,
- skok do końca programu po przekroczeniu, czyli wykona się raz w przeciągu całego algorytmu
- kopiowanie,
- odejmowanie,
- kopiowanie, przygotowanie następnej pętli
Mamy więc \(5\) operacji wykonywanych \(n - 1\) razy, razem więc \(5n - 5\). Następnie mamy pętlę wewnętrzną, sortującą:
inner_loop:
inc rdx
cmp rdx, r9
je outer_loop
mov r10, [rax + rdx*8]
cmp r10, [rax + rdx*8 + 8]
jle inner_loop
mov r11, [rax + rdx*8 + 8]
mov [rax + rdx*8 + 8], r10
mov [rax + rdx*8], r11
jmp inner_loop
Mamy tutaj więc:
- inkrementację,
- porównanie,
- skok jeżeli pętla się zakończy, więc będzie się wykonywać tyle razy ile zewnętrzna pętla
- kopiowanie,
- porównanie,
- skok jeżeli wyjdzie pozytywne, tj. nie trzeba będzie zamienić miejscami, w naszym przypadku pesymistycznym trzeba zawsze, więc nie wykona się ani razu
- kopiowanie,
- kopiowanie,
- kopiowanie,
- skok żeby kontynuować pętlę
A więc, cała wewnętrzna pętla wykona się \(n-1\) potem \(n - 2\) potem \(n - 3\) i tak dalej aż do \(1\), a więc \(\displaystyle(n - 1)+1) \cdot \frac{n - 1}{2} = \frac{n^2 - n}{2}\). Operacji które się w niej wykonują będzie, jak wyliczyliśmy \(9\), a więc sumując wszystko razem, będziemy mieli \(\displaystyle \frac{9n^2 - 9n}{2}\). Cudownie. Dodajmy do tego jeszcze jeden jedyny skok do końca programu przy ostatnim porównaniu zewnętrznej pętli. Sumując więc wszystko razem uzyskamy:
\(\displaystyle5n - 5+ \frac{9n^2 - 9n}{2} + 1 = \frac{10n - 10}{2} + \frac{9n^2 - 9n}{2} + \frac{2}{2} = \frac{9n^2 + n - 8}{2}\)
Cudownie, mamy więc złożoność \(O(n^2)\), taka jak powinna wyjść. Czy było łatwiej niż z maszyną Turinga? Zdecydowanie tak. Ale...
Kto dziś pisze algorytmy w assembly? Zapaleńcy, albo ludzie którzy nie mają wyjścia, albo ludzie wymagający maksymalnej kontroli nad kodem. Takich jest dosyć mało. Większość ludzi pisze w językach wysokiego poziomu. Mając w głowie, że maszyna RAM modeluje nam rozkazy i jest to model abstrakcyjny, możemy te rozkazy troszkę bardziej pokryć abstrakcją. Co to znaczy? Znaczy to tyle, że np. spróbujmy zastąpić słowo rozkaz, operacją. W C++ nie ma rozkazów. Są operacje, takie jak dodawanie, odejmowanie, kopiowanie. Ostatecznie skompilują się one do pojedynczych rozkazów takich jakie opisaliśmy wyżej w assembly, więc czy można nie pisać w assembly i próbować liczyć złożoności? Oczywiście że tak i zaraz pokażemy dlaczego i w jaki sposób.
Rzecz dziesiąta. Wysokopoziomowe operacje.
Popisaliśmy w assembly, trochę ciężko było, więc przejdźmy do bardziej przyjemnych rzeczy. Napiszmy sobie teraz, to samo sortowanie co przed momentem, tylko w C++. A oto one:
template<typename T>
void cpp_bubble_sort(std::vector<T>& vector) {
for (size_t iteration = 0; iteration < vector.size() - 1; iteration++) {
for (size_t index = 0; index < vector.size() - iteration - 1; index++) {
if (vector[index] > vector[index + 1]) {
T buffer = vector[index + 1];
vector[index + 1] = vector[index];
vector[index] = buffer;
}
}
}
}
Nie ma rozkazów, ale mamy konkretne, zdefiniowane operacje. Pojedźmy więc po kolei:
for (size_t iteration = 0; iteration < vector.size() - 1; iteration++) { Mamy tutaj jedno przypisanie, \(n - 1\) porównań, \(n - 1\) inkrementacji, więc w sumie \((n - 1) + (n - 1) + 1 = 2n - 1\). Ok, jedziemy dalej:
for (size_t index = 0; index < vector.size() - iteration - 1; index++) {Jesteśmy w pętli wewnętrznej, więc tutaj będziemy schodkowo wykonywać tych operacji coraz mniej, a więc na początku jedno przypisanie, \(n - 1\) porównań, \(n - 1\) inkrementacji, później, jedno przypisanie, \(n - 2\) porównań, \(n - 2\) inkrementacji, później, jedno przypisanie, \(n - 3\) porównań, \(n - 3\) inkrementacji, aż nam \(n\) nie dojdzie do \(2\). Sumarycznie więc będzie:
\(\displaystyle (1 + (n - 1) + (n - 1)) + (1 + (n - 2) + (n - 2)) + ... + (1 + (2 - 1) + (2 - 1)) = \frac{(2n - 1 + 3) \cdot (n - 1)}{2} = \frac{(2n + 2) \cdot (n - 1)}{2} = \frac{2n^2 - 2}{2} = n^2 - 1\)
Ale to tylko obsługa pętli, teraz wnętrze:
if (vector[index] > vector[index + 1]) {
T buffer = vector[index + 1];
vector[index + 1] = vector[index];
vector[index] = buffer;
}Mamy tu jedno porównanie, jedno zapisanie do bufora, jedno zapisanie do zmiennej w tablicy, i potem z bufora znów do tablicy. Klasyczny swap. Mamy tu więc \(4\) operacje, które stopniowo będziemy mnożyć najpierw przez \(n - 1\), potem przez \(n - 2\) itd. aż do końca, czyli łącznie:
\(\displaystyle 4(n-1) + 4(n-2) + ... + 4(2-1) = \frac{(4(n - 1) + 4) \cdot (n-1)}{2} = \frac{4n \cdot (n-1)}{2}= \frac{4n^2 - 4n}{2} = 2n^2 - 2n\)
No to teraz posumujmy wszystko naraz:
- obsługa pętli zewnętrznej: \(2n - 1\)
- obsługa pętli wewnętrznej: \(n^2 - 1\)
- porównania i swapy: \(2n^2 - 2n\)
A więc:
\((2n - 1) + (n^2 - 1) + (2n^2 - 2n) = 3n^2 -2\)
Złożoność więc wyszła modelowa, \(O(n^2)\), czyli dokładnie taka, jakiej się spodziewaliśmy.
Rzecz jedenasta. Wnioski.
Zrobiliśmy masę pracy, masę analiz. Tylko po co?
Policzyliśmy sobie już wcześniej złożoność maszyną Turinga, maszyną RAM bardzo nisko, i wysokopoziomowo w C++, i za każdym razem, mimo różnic w faktycznej, dokładnej liczbie wykonanych operacji, złożoność wyszła nam dokładnie taka sama. Dlaczego?
Obsługując maszynę RAM, w modelu NASMowym jaki użyliśmy, żeby mieć namiastkę realności, jesteśmy ograniczeni. Bardzo. W normalnym RAMie, nie musielibyśmy się martwić o to czy możemy użyć rejestru, ile ich mamy, jak szybko się do nich dostaniemy, czy możemy użyć konkretnych trybów adresowania. Mamy komputerek z nieskończoną ilością pamięci i rejestrów, a skoro tak, to znaczy, że możemy dla każdej operacji wyznaczyć konkretne rejestry z puli i nie martwić się o jakieś bufory, liczniki itd. Skoro nie musimy się o to martwić i możemy te operacje sobie w dowolne rejestry rozpisać, możemy tym samym powiedzieć, że wykonujemy jakąś tam operację, bez martwienia się o to jak jest ona obsługiwana. Dokładnie to zrobiliśmy opisując kod w C++. Wyliczyliśmy sobie, że wykonamy ileś inkrementacji, ileś porównań, ileś odejmowań, bez szukania dlań rejestrów ani pamięci. Dlatego maszyna RAM jest tak potężnym modelem dającym się skalować niemal dowolnie wysoko. O ile łatwiej nam napisać kod w C++, albo jakiejś Javie, niż w assembly i liczyć każdą poszczególną instrukcję. Oczywiście będziemy mieli idealną wiedzę o wykonaniu algorytmu i dokładne informacje o jego czasie wykonania, ale na 99% jak napiszemy ten algorytm w C++, kompilator zrobi to od nas dużo lepiej i to pewnie z każdą dużą jego wersją jeszcze lepiej niż poprzednio. Warto więc, mając wiedzę o tym jak analizować kod i dlaczego nie musimy go analizować na super niskim poziomie, pisać algorytmy wysokopoziomowo. Dlatego, że jest dużo łatwiej i szybciej, i taki jest cel tego modelu. Znaczące ułatwienie analizy przy zachowaniu ścisłej poprawności. I to, z każdym kolejnym przykładem, udało nam się udowodnić.
Podsumowanie.
Mamy wszystko czego potrzebowaliśmy by bez zbędnych ceregieli przejść do konkretnych już algorytmów i podejść stosowanych w ich projektowaniu. Wiemy już co to jest maszyna RAM, skąd się wzięła, po co jest, dlaczego jest lepsza w analizie od maszyny Turinga i jak za jej pomocą analizować algorytmy nawet w językach wysokiego poziomu.
Dziękuję za uwagę i do zobacznia w następnych artykułach :)
Komentarze