---
# System prepended metadata

title: Raport do zadania binsearch

---

# 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:
![](https://i.imgur.com/eFyuaDT.png)
#### %chybień w L2:
![](https://i.imgur.com/f54eG21.png)


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
 ```c=
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
```c=
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;
```
![](https://i.imgur.com/PrWqSYN.png)

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

```c=
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
![](https://i.imgur.com/tKSWkGV.png)

![](https://i.imgur.com/TJsyrO1.png)


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

### __builtin_expect

```c=
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

![](https://i.imgur.com/Yf7MY4L.png)

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



