# Raport do zadania binsearch

### Autor: Marcin Dąbrowski
### Numer indeksu: 315370

Konfiguracja
---

Informacje o systemie:

* Dystrybucja: Debian 10
* Jądro systemu: 4.19.0-9-amd64
* Kompilator: gcc version 8.3.0 (Debian 8.3.0-6)
* Procesor: AMD FX-6300
* Liczba rdzeni: 6

Pamięć podręczna:

* L1d: 16 KiB, 4-drożny (per rdzeń), rozmiar linii 64B
* L2: 2 MiB, 16-drożny (per 2 rdzenie), rozmiar linii 64B
* L3: 8 MiB , 64-drożny (współdzielony), rozmiar linii 64B

Pamięć TLB:

* L1d: 4KiB strony, 255-drożny, 48 wpisy
* L2: 4KiB strony, 8-drożny, 1024 wpisów

Informacje o pamięciach podręcznych uzyskano na podstawie wydruku programu
`x86info` oraz `cpuid`.

### Ważne:
Wszystkie testy zostały przeprowadzone dziesięciokrotnie, z takim samym ziarnem.

## Wnioski

### Czemu zmiana organizacji danych spowodowała przyspieszenie algorytmu wyszukiwania? Jak zmieniła się lokalność czasowa elementów przechowywanych w pamięci podręcznej?

#### %chybień w L1:
#### %chybień w L2:

Zmiana organizacji danych w tablicy przyspieszyła działanie algorytmu, pownieważ zwiększyła lokalność jego danych.

Wyjaśnię to na przykładzie:
dla tablicy o długości $n$ ułożonej niemalejąco algorytm `binsearch0` najpierw wybierał element o pozycji $n/2$, a w kolejnej iteracji $n/4$ lub $3n/4$. Ułożenie danych w tablicy powodowało, że indeksy te były oddalone od pozycji $n/2$ o $n/4$. Dla dużych wartości $n$ powodowało to, że dany element tablicy musiał być ponownie załadowany do cache'u. W zależności od $n$ ta sytuacja mogła się powtarzać wielokrotnie.

Przy nowej organizacji danych w tablicy konieczność załadowania elementu do pamięci podręcznej występuje zdecydowanie rzadziej, ponieważ (posługując się nadal tym przykładem) teraz element o indeksie $n/2$ (w oryginalnej tablicy) "sąsiaduje" z elementami $n/4$ oraz $3n/4$. Szansa na to, że następny szukany element będzie wymagał sprowadzenia z pamięci wyższego poziomu, jest zatem dużo mniejsza. Odległości pomiędzy elementami zwiększają się natomiast wraz ze wzrostem liczby iteracji. Jednak z każdą iteracją prawdopodobieństwo na to, że nastąpi kolejna, spada(bo mogliśmy znaleźć element już wcześniej). Ponowne załadowania do pamięci nie są więc tak odczuwalne jak przy funkcji `binsearch0`.

Jak można zauważyć na przestawionych powyżej wykresach dane, które udało mi się zmierzyć zdają się potwierdzać moje rozważania. Chybienia dla `binsearch1` rosną zdecydowanie mniej radykalnie niż te dla `binsearch0`, co przekłada się bezpośrednio na poprawę wydajności.

### W jaki sposób zmiana kolejności instrukcji w ciele pętli zmienia IPC?

#### Opis:
###### v0

int index=1;
do{
    int val = arr[index];
    if(val==x) return true;
    if(val > x) index*=2;
    else index = index*2 + 1;
} while(index<size+1);
return false;
int index=1;
do{
    int val = arr[index];
    if(val==x) return true;
    if(val > x) index*=2;
    else index = index*2 + 1;
} while(index<size+1);
return false;

###### v1

int index=1;
do{
    int val = arr[index];
    if(val > x) index*=2;
    if(val==x) return true;
    else index = index*2 + 1;
} while(index<size+1);
return false;


Z wykresu wynika, że w początkowej fazie ($n<13$) wersja `v0` jest w stanie wykonać więcej instrukcji na cykl. Później zmienia się to na korzyść `v1`.

### Czy użycie instrukcji wbudowanych kompilatora `__builtin_expect` i `__builtin_prefetch` przynosi jakieś zyski?

`_builtin_prefetch`
Funkcja ta pozwala na zminimalizowanie chybień w pamięć podręczną. Jej wywołanie pozwala przewidzieć, że jakaś komórka pamięci będzie potrzebna i załadowuje ją do cache'u zanim zostanie wykonany dostęp do niej.

`_builtin_expect`
Funkcja ta pozwala zakomunikować kompilatorowi, że jakiś warunek najprawdopodobniej będzie miał daną wartość np. logiczną. Ułatwia to predyktowanie odpowiednich gałęzi podczas wykonywania programu.

### __builtin_prefetch

int index=1;
do{
    int val = arr[index];
    if(val==x) return true;
    __builtin_prefetch(&arr[2*index]);
    __builtin_prefetch(&arr[2*index+1]);
    if(val > x) index*=2;
    else index = index*2 + 1;
} while(index<size+1);
return false;

#### Wykresy dla __builtin_prefetch


Zastosowanie funkcji __builtin_prefetch zdecydowanie zmniejszyło odsetek chybień w pamięć podręczną.

### __builtin_expect

int index=1;
do{
    int val = arr[index]; 
    __builtin_expect(val==x,0);
    if(val==x) return true;
    if(val > x) index*=2;
    else index = index*2 + 1; 
    __builtin_expect(index<size+1,0);
} while(index<size+1);
return false;

#### Wykres dla __builtin_expect


Nie zauważyłem zbyt dużych różnic w czasie wykonywanie programu po zastosowaniu funkcji __builtin_expect.