# Lista 13 (10 czerwca 2021)
###### tags: `ask21` `ćwiczenia` `kba`
## Deklaracje
Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.
**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**
:::danger
| | 1 | 2(2) | 3 | 4 | 5 | 6 |
| ---------------------:| --- |:----:| --- | --- | --- | --- |
| Andriy Bernad | X | | | | | | 1
| Wojciech Bogucki | X | X | | | | | 3
| Michał Doros | X | X | X | X | X | X | 7
| Marko Golovko | | | | | | | 0
| Magdalena Jarecka | | | | | | | 0
| Szymon Jędras | X | X | | | | | 3
| Heorhii Karpenko | X | | | | X | | 2
| Szymon Kosakowski | | | | | | | 0
| Izabella Kozioł | | | | | | | 0
| Franciszek Malinka | X | X | X | X | X | X | 7
| Filip Pazera | | | | | | | 0
| Franciszek Pindel | X | X | | | | | 3
| Kacper Puchalski | X | X | X | | | | 4
| Kacper Solecki | X | X | X | X | X | X | 7
| Andrzej Tkaczyk | X | | | | | | 1
| Łukasz Wasilewski | | | | | | | 0
| Vladyslav Yablonskyi | | | | | X | | 1
| Adam Zyzik | X | X | | | | | 2
:::
## Zadanie 1
:::info
Autor: Andrzej Tkaczyk
:::
W czasie wykonywania programu procesor układa kolejne instrukcje na kolejce do wykonania. Gdy napotka skok warunkowy mamy rozgałęzienie i są dwie możliwości na ułożenie instrukcji w kolejce. Wtedy często nie wiadomo jeszcze jaka jest wartość warunku i który wariant do ułożenia kolejki wybrać. Procesor, żeby nie marnować czasu na bezczynne czekanie aż policzy wartość warunku, próbuje przewidzieć jego wartość i ułożyć na kolejce odpowiednie instrukcje.
**Predyktor skoków** - algorytm używany do przewidywania którą gałęzią pójdzie program.
W momencie w którym okaże się, że procesor się pomylił i wybrał złą gałąź, wszystkie obliczone wartości związane z tą gałęzią muszą zostać wyrzucone do śmieci, a na kolejkę muszą zostać wrzucone instrukcje z dobrej gałęzi.
Do instrukcji cmov warto optymalizować skoki które nie są łatwo przewidywalne, bo jeśli skoki są przewidywalne, to procesor nie płaci kar za złe przewidywania, bo ich nie robi.
#### oryginalna wersja:
```c=
void merge1(long src1[], long src2[], long dest[], long n) {
long i1 = 0, i2 = 0;
while (i1 < n && i2 < n)
*dest++ = src1[i1] < src2[i2] ? src1[i1++] : src2[i2++];
}
```
```asm=
merge1:
testq %rcx, %rcx
jle .L1
movl $0, %r8d
movl $0, %eax
jmp .L5
.L3:
addq $1, %r8
movq %r10, %r9
.L4:
addq $8, %rdx
movq %r9, -8(%rdx)
cmpq %r8, %rax
movq %r8, %r9
cmovge %rax, %r9
cmpq %rcx, %r9
jge .L1
.L5:
movq (%rdi,%rax,8), %r9
movq (%rsi,%r8,8), %r10
cmpq %r10, %r9
jge .L3
addq $1, %rax
jmp .L4
.L1:
ret
```
#### wersja z cmov:
```c=
void merge1a(long src1[], long src2[], long dest[], long n) {
long i1 = 0, i2 = 0;
while (i1 < n && i2 < n) {
long a = src1[i1];
long b = src2[i2];
long c = a < b;
*dest++ = a < b ? a : b;
i1 += c;
i2 += c^1;
}
}
```
```asm=
merge1a:
movq %rdi, %r10
movq %rsi, %r11
testq %rcx, %rcx
jle .L7
movl $0, %esi
movl $0, %eax
.L9:
movq (%r10,%rax,8), %r8
movq (%r11,%rsi,8), %rdi
addq $8, %rdx
cmpq %rdi, %r8
movq %rdi, %r9
cmovle %r8, %r9
movq %r9, -8(%rdx)
setl %r9b
movzbl %r9b, %r9d
addq %r9, %rax
cmpq %rdi, %r8
setge %dil
movzbl %dil, %edi
addq %rdi, %rsi
cmpq %rsi, %rax
movq %rsi, %rdi
cmovge %rax, %rdi
cmpq %rcx, %rdi
jl .L9
.L7:
ret
```
## Zadanie 2
:::success
Autor: Franciszek Pindel
:::
> Pobierz ze strony przedmiotu archiwum «ask21_lista_13.tgz», rozpakuj je i zapoznaj się z kodem źródłowym w pliku «dictionary.c». Powtórz eksperyment z [1, §5.14], tj.: uruchom program, poczekaj na wyniki profilowania, a następnie na podstawie wydruku wskaż kandydata do optymalizacji. Zmień dokładnie jedenz argumentów przekazywanych do polecenia «make gprof»: SIZE=N, HASH=0/1/2, FIND=0/1/2, LOWER=0/1, QUICK=0/1. Odpowiednia opcja zmieni rozmiar tablicy mieszającej N lub ustali wersję implementacji jednej z kluczowych funkcji w programie. Wyjaśnij co zmieniło przekazanie danej opcji. Powtarzaj powyższe kroki tak długo, aż uzyskasz najkrótszy czas wykonania programu.
* **profilowanie** - analiza zachowania programu w trakcie uruczomienia - polega na mierzeniu np. używanej pamięci albo liczby wywołań poszczególnych funkcji
Z profilu płaskiego wynika że większość czasu zajmuje posortowanie elementów (`sort wrods`), co nie dziwi, bo to jest zaimplementowane jako insertion sort
```
size 1021
hash 1
lower 0
find 0
ngram 2
quicksort 0
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
98.00 298.75 298.75 1 298.75 298.75 sort_words
1.88 304.47 5.72 965027 0.00 0.00 find_ele_rec
0.21 305.11 0.64 965027 0.00 0.00 lower1
0.05 305.26 0.15 965027 0.00 0.00 h_mod
0.03 305.36 0.10 965028 0.00 0.00 get_token
0.01 305.40 0.05 363039 0.00 0.00 save_string
0.01 305.42 0.02 965027 0.00 0.00
```
Po zmianie algorytmu na quicksort widać znaczącą poprawę, oraz widać że najwięcej czasu zabiera znajdywanie elementów (`find-ele_rec`)
```
size 1021
hash 1
lower 0
find 0
ngram 2
quicksort 1
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
93.17 11.42 11.42 965027 0.00 0.00 find_ele_rec
2.66 11.75 0.33 965027 0.00 0.00 lower1
1.47 11.93 0.18 compare_ele
0.98 12.05 0.12 965028 0.00 0.00 get_token
0.57 12.12 0.07 1 0.07 0.07 sort_words
0.41 12.17 0.05 965027 0.00 0.00 insert_string
```
Próba zmiany z wersji rekurencyjnej na iteracyjną nie przynosi poprawy, a nawet psuje (powodem jest umieszczanie elementów na początku listy zamiast na końcu, co powoduje że częściej pojawiające się elementy znajdą się na końcu listy, co wydłuża czas ich wyszukiwania - szczegóły polecam sobie doczytać, tutaj są mało istotne)
```
size 1021
hash 1
lower 0
find 1
ngram 2
quicksort 1
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
95.00 22.15 22.15 965027 0.00 0.00 find_ele_iter_f
2.71 22.79 0.63 965027 0.00 0.00 lower1
0.52 22.91 0.12 965027 0.00 0.00 insert_string
0.47 23.02 0.11 965028 0.00 0.00 get_token
0.47 23.13 0.11 compare_ele
0.39 23.22 0.09 965027 0.00 0.00 h_add
0.30 23.29 0.07 1 0.07 0.07 sort_words
0.26 23.35 0.06 363039 0.00 0.00 new_ele
0.04 23.36 0.01 965029 0.00 0.00 get_word
0.04 23.37 0.01 find_ele_rec
0.00 23.37 0.00 363039 0.00 0.00 save_string
```
Zmiana na wersję iteracyjną z umieszczaniem elementów na końcu daje nieznaczne przyspieszenie (albo i nie):
```
size 1021
hash 1
lower 0
find 2
ngram 2
quicksort 1
Flat profile:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
92.74 14.83 14.83 965027 0.00 0.00 find_ele_iter_r
4.04 15.48 0.65 965027 0.00 0.00 lower1
1.00 15.64 0.16 965028 0.00 0.00 get_token
0.75 15.76 0.12 965027 0.00 0.00 insert_string
0.56 15.85 0.09 compare_ele
0.50 15.93 0.08 1 0.08 0.08 sort_words
0.22 15.96 0.04 965027 0.00 0.00 h_add
0.13 15.98 0.02 363039 0.00 0.00 new_ele
0.06 15.99 0.01 Strlen
```
Zwiększenie rozmiaru tablicy mieszającej nie daje poprawy, bo algorytm haszujący daje wyniki z małego przedziału
```
size 199999
hash 1
lower 0
find 2
ngram 2
quicksort 1
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
93.42 13.66 13.66 965027 0.00 0.00 find_ele_iter_r
4.18 14.27 0.61 965027 0.00 0.00 lower1
0.82 14.39 0.12 965028 0.00 0.00 get_token
0.48 14.46 0.07 965027 0.00 0.00 insert_string
0.41 14.52 0.06 1 0.06 0.06 sort_words
0.34 14.57 0.05 compare_ele
```
Dopiero zmiana algorytmu hashującego pozwala zredukować czas wykonania:
```
size 199999
hash 2
lower 0
find 2
ngram 2
quicksort 1
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
50.78 0.38 0.38 965027 0.00 0.00 lower1
12.19 0.47 0.09 compare_ele
12.19 0.56 0.09 965027 0.00 0.00 find_ele_iter_r
6.77 0.61 0.05 965027 0.00 0.00 insert_string
5.42 0.65 0.04 965028 0.00 0.00 get_token
4.06 0.68 0.03 965027 0.00 0.00 h_xor
2.71 0.70 0.02 965029 0.00 0.00 get_word
2.71 0.72 0.02 1 20.04 20.04 sort_words
1.35 0.73 0.01 363039 0.00 0.00 save_string
1.35 0.74 0.01 find_ele_iter_f
```
Pozostaje polepszyć strlen która w tym kodzie ma złożoność kwadratową, ulepszona wersja nieznacznie przyspiesza program:
```
size 199999
hash 2
lower 1
find 2
ngram 2
quicksort 1
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
34.03 0.18 0.18 965027 0.00 0.00 find_ele_iter_r
20.80 0.29 0.11 965027 0.00 0.00 insert_string
11.34 0.35 0.06 compare_ele
9.45 0.40 0.05 965028 0.00 0.00 get_token
7.56 0.44 0.04 1 40.08 40.08 sort_words
3.78 0.46 0.02 965027 0.00 0.00 h_xor
3.78 0.48 0.02 965027 0.00 0.00 lower2
3.78 0.50 0.02 363039 0.00 0.00 save_string
```
## Zadanie 3
:::danger
Autor: Franciszek Malinka
:::
**Graf wywołań funkcji** - skierowany graf ilustrujący kolejność wywoływanych funkcji i relację między funkcjami wyłowującymi, a wywołanymi.
Graf został wygenerowany przy pomocy narzędzia *kcachegrind*. Każdy bloczek przedstawia jedną funkcję, krawędzie są skierowane z funkcji wołających do funkcji wołanych. Przy każdym bloczku napisany jest procentowy czas działania programu, który został spędzony w danej funkcji (sumarycznie we wszystkich jej wywołaniach).
Wywołania funkcji biblioteki standardowej C to te, których nazwy bloczków są liczbami (prawdopodobnie są to adresy wirtualne z poziomy procesu, do których odwoływał się wywołując funkcje z bibliotek współdzielonych).
Funkcje biblioteczne, w których program spędził najwięcej czasu:
- strtok (30.67%)
- malloc (10.59%)
- qsort (9.51%)
Nie mamy możliwości optymalizacji samych funkcji bibliotecznych, ale mamy możliwość np. ograniczenia liczby wywołań tych funkcji, np. zamiast alokować pamięc dopiero wtedy, kiedy chcemy dodać nowy element do hashmapy, możemy alokować za każdym razem trochę więcej pamięci (np. za każdym razem 1.5 razy więcej pamięci), żeby robić mało "dużych" malloców, zamiast dużo "małych". To zapobiega fragmentacji pamięci i zmniejsza liczbę wywołań systemowych, co wpływa na performance naszego progrmau.
## Zadanie 4
:::success
Autor: Michał Doros
:::
**fizyczna przestrzen adresowa**
zakres adresow ktore reprezentuja komorki pamieci glownej, a takze urzadzenia I/O
**translacja adresow**
Wykonywana przez MMU - memory management unit
Tlumaczenie adresu wirtualnego na fizyczny przy pomocy ponizszego wzoru
PFN odczytywane z tabeli stron (page table)
Strona ma 4096 bajtow = 2^12 B, zatem offset to ostatnie 3 cyfry 16-kowe
address = PFN * page_size + offset
Dla adresu:
0x55e7926f3000 : pfn 249dac
address = 0x249dac * 0x1000 + 0x000 = 0x249dac000
w System RAM
**numer ramki**
adres fizyczny podzielony przez rozmiar strony
mapa pamici fizycznej
mapa pamieci wirtualnej procesu 2566
## Zadanie 5
:::success
Autor: Grzegorz Karpenko
:::
**Pamięć wirtualna** – mechanizm zarządzania pamięcią komputera zapewniający procesowi wrażenie pracy w jednym, dużym, ciągłym obszarze pamięci operacyjnej, podczas gdy fizycznie może być ona pofragmentowana, nieciągła i częściowo przechowywana na urządzeniach pamięci masowej.
**RSS** to Resident Set Size i służy do pokazywania rozmiaru stron pamięci przydzielonych przez system operacyjny i aktualnie znajdujących się w pamięci RAM (RAM). Ale w rzeczywistości nie jest to dokładny pomiar wykorzystania pamięci RAM dla procesu, ponieważ nie uwzględnia bibliotek już załadowanych do pamięci.
Jeśli dwa procesy używają jednej lub więcej bibliotek, wtedy RSS doda rozmiary bibliotek dla każdego procesu, nawet jeśli biblioteki byłyby już wcześniej załadowane w przypadku jednego procesu rozpoczynającego się po drugim. Więc czasami jeśli dodamy wszystko na liście procesów, otrzymamy więcej pamięci niż całkowita przydzielona pamięć.
**VSZ** to skrót od Virtual Memory Size. Jest to całkowita ilość pamięci, do której hipotetycznie może uzyskać dostęp proces. Uwzględnia rozmiar pliku binarnego, wszelkich połączonych bibliotek i wszelkich alokacji stosu lub sterty.
**Stronicowanie na żądanie** jest metodą zarządzania pamięcią wirtualną. W systemie korzystającym ze stronicowania na żądanie system operacyjny kopiuje stronę dysku do pamięci fizycznej tylko wtedy, gdy podjęto próbę uzyskania dostępu do niej, a strona nie znajduje się już w pamięci.
**Pamięć współdzielona** jest specjalnie utworzonym segmentem wirtualnej przestrzeni adresowej, do którego dostęp może mieć wiele procesów. Jest to najszybszy sposób komunikacji pomiędzy procesami.
:::spoiler
Napewno nie mam 32Gb RAM !
:::
:::spoiler
:::
## Zadanie 6
:::success
Autor: Kacper Solecki
:::
**pamięć wymiany (swap)** - pamięć procesów trzymana na dysku twardym, gdy RAM jest przepełniony
Karty na chrome wyświetlające miliony particli:
**zbiór roboczy** - pamięć, której proces używa w danym przedziale czasowym (lub ostatnie $k$ stron do których były odwołania)
Aproksymacja zbioru roboczego:
System kiedy zdarzy się page fault skanuje strony pamięci - sprawdza, do których stron pamięci odwoływały się procesy od czasu ostatniego czyszczenia bitu Referenced.
(strony pamięci mają bit 'Referenced' ustawiany w stałych odstępach czasu na 0).
Strony, ze zgaszonym bitem Referenced, których jednocześnie ostatnie odwołanie było dawniej niż pewne ustalone $t$ uznawane są za nie będące w zbiorze roboczym - a więc są potencjalnymi ofiarami do przeniesienia na dysk (swap).
Jeżeli wszystkie strony mają zapalony bit Referenced ofiarą jest najdawniej używana strona.
Strony, które były używane mają aktualizowany czas ostatniego użycia na czas obecnego skanu.
**zbiór rezydentny** - część pamięci procesu, która obecnie znajduje się w RAMie.
**pamięć drugorzędna** - Pamięć, do której dostęp jest wolny, ale jest trwała (w znaczeniu - nie potrzebuje zasilania, aby trzymać dane), zwykle ma dużą pojemność, np. dyski twarde, pamięć urządzeń przenośnych
System używa pamięci drugorzędnej, gdy zabraknie miejsca w pamięci operacyjnej, przy wymianie danych z urządzeniami I/O, zapisuje tam dane, by nie zniknęły przy odłączeniu od prądu.
> Co dzieje się z systemem, jeśli łączny rozmiar zbiorów
roboczych wszystkich procesów jest większy niż rozmiar pamięci fizycznej?
**trashing** - System drastycznie spowalnia, odwołania do pamięci na dysku są bardzo wolne, a brakuje nam miejsca by trzymać całą aktualnie używaną pamięć w RAMie.
Sign in with Wallet
Connect another wallet