---
# System prepended metadata

title: Lista 12 (27 maja 2021)
tags: [kba, ask21, ćwiczenia]

---

# Lista 12 (27 maja 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  |  3  |  4  |  5  |  6  |  7  |  8  |
| ---------------------:| --- | --- | --- | --- | --- | --- | --- | --- |
|         Andriy Bernad |  X  |==X==|  X  |  X  |  X  |  X  |     |     | 6
|      Wojciech	Bogucki |  X  |  X  |  X  |  X  |     |     |     |     | 5
|          Michał Doros |  X  |  X  |  X  |  X  |  X  |  X  |  X  |  X  | 8
|         Marko Golovko |     |     |     |     |     |     |     |     | 0
|     Magdalena Jarecka |     |     |     |     |     |     |     |     | 0
|         Szymon Jędras |  X  |  X  |  X  |  X  |  X  |  X  |     |     | 6
|      Heorhii Karpenko |  X  |  X  |==X==|  X  |  X  |  X  |     |     | 6
|     Szymon Kosakowski |  X  |  X  |  X  |  X  |     |     |     |     | 4
|       Izabella Kozioł |     |     |     |     |     |     |     |     | 0
|    Franciszek Malinka |  X  |  X  |  X  |  X  |  X  |  X  |  X  |     | 7
|          Filip Pazera |  X  |  X  |  X  |  X  |     |     |     |     | 4
|     Franciszek Pindel |  X  |  X  |  X  |  X  |  X  |  X  |  X  |  X  | 8
|      Kacper Puchalski | X   |  X  | X   |  X  |     |     |     |     | 4
|        Kacper Solecki |  X  |  X  |  X  |  X  |  X  |  X  |     |  X  | 7
|       Andrzej Tkaczyk |  X  |  X  |  X  |  X  |  X  |     |     |     | 5
|     Łukasz Wasilewski |  X  |  X  |  X  |  X  |     |     |     |     | 4
|  Vladyslav Yablonskyi |  X  |  X  |  X  |  X  |  X  |     |     |     | 5
|            Adam Zyzik |  X  |  X  |  X  |  X  |  X  |     |     |     | 5
:::

## Zadanie 1

:::success
Autor: Szymon Kosakowski
:::

aliasing - kiedy kilka wskaźników wskazuje na to samo miejsce w pamięci.

restrict - na czas życia wskaźnika, tylko ten wskaźnik będzie służył do dostępu do wartośći na którą wskazuje

Kompilator nie może zooptymalizować bo *xp i *yp mogą wskazywać na to samo miejsce w pamięci. W takim wypadku swap i swap2 zwrócą inny wynik


```c=
 void swap(long *xp, long *yp) {
 *xp = *xp + *yp; /* x+y */
 *yp = *xp - *yp; /* x+y-y = x */
 *xp = *xp - *yp; /* x+y-x = y */
 }
```
```
swap:
        movq    (%rsi), %rax
        addq    (%rdi), %rax
        movq    %rax, (%rdi)
        subq    (%rsi), %rax
        movq    %rax, (%rsi)
        subq    %rax, (%rdi)
        ret
```

---

```c=
 void swap_res(long* restrict xp, long* restrict yp) {
 *xp = *xp + *yp; /* x+y */
 *yp = *xp - *yp; /* x+y-y = x */
 *xp = *xp - *yp; /* x+y-x = y */
 }
```

```
swap_res:
        movq    (%rsi), %rax
        movq    (%rdi), %rdx
        movq    %rax, (%rdi)
        movq    %rdx, (%rsi)
        ret
```  

---

```c=
 void swap2(long *xp, long *yp) {
 long x = *xp, y = *yp;
 x = x + y, y = x - y, x = x - y;
 *xp = x, *yp = y;
}
```

```
swap2:
        movq    (%rdi), %rax
        movq    (%rsi), %rdx
        movq    %rdx, (%rdi)
        movq    %rax, (%rsi)
        ret
```

## Zadanie 2

:::success
Autor: Wojciech Bogucki
:::
**Inlining**
Zamiast wywoływać funkcję bezpośrednio wklejamy jej kod w miejscu wywołania.

---
\_\_attribute__ (pure) oznacza, że funkcja nie ma skutków ubocznych, a zwracana wartość zależy od argumentów i stanu zmiennych globalnych.

**Czyste funkcje**
W programowaniu czysta funkcja to funkcja, która ma następujące właściwości:

1. Wartości zwracane przez funkcję są identyczne dla identycznych argumentów (brak zmian z lokalnymi zmiennymi statycznymi, zmiennymi nielokalnymi, zmiennymi argumentami odwołań lub strumieniami wejściowymi).
2. Użycie funkcji nie ma skutków ubocznych (brak mutacji lokalnych zmiennych statycznych, zmiennych nielokalnych, zmiennych argumentów referencyjnych lub strumieni wejścia / wyjścia). 

---

Treść zadania:
```c=
__attribute__((noinline))
size_t my_strlen(const char *s) {
    size_t i = 0;
    while (*s++)
        i++;
    return i;
}

const char *my_index(const char *s, char v) {
    for (size_t i = 0; i < my_strlen(s); i++)
        if (s[i] == v)
            return &s[i];
    return 0;
}
```
Funkcja my_strlen w asm:
```scala=
my_strlen:
        xorl    %eax, %eax
        cmpb    $0, (%rdi)
        je      .L4
.L3:
        addq    $1, %rax
        cmpb    $0, (%rdi,%rax)
        jne     .L3
        ret
.L4:
        ret
```
my_index z artybutem `__attribute__((noinline))`:
```scala=
my_index:
        xorl    %edx, %edx
        jmp     .L8
.L10:
        leaq    (%rdi,%rdx), %rax
        cmpb    %sil, (%rdi,%rdx)
        je      .L7
        addq    $1, %rdx
.L8:
        call    my_strlen
        cmpq    %rdx, %rax
        ja      .L10
        xorl    %eax, %eax
.L7:
        ret
```
Funkcja ``my_strlen`` zostałnie wywołana ``min(k,length(s))``(gdzie `k` to `s[k]==v`) razy. Jest ona wywoływana przy każdym sprawdzeniu warunku.

Jak usuniemy `__attribute__((noinline))`:
```scala=
my_index:
        movzbl  (%rdi), %ecx
        xorl    %edx, %edx
        xorl    %eax, %eax
        testb   %cl, %cl
        je      .L7
.L10:
        addq    $1, %rax
        cmpb    $0, (%rdi,%rax)
        jne     .L10
        cmpq    %rax, %rdx
        jnb     .L14
        leaq    (%rdi,%rdx), %rax
        cmpb    %sil, (%rdi,%rdx)
        je      .L7
        addq    $1, %rdx
        xorl    %eax, %eax
        testb   %cl, %cl
        jne     .L10
.L7:
        ret
.L14:
        xorl    %eax, %eax
        ret
```
Teraz kod procedury `my_strlen` jest bezposrednio w funkcji, więc nie wywołujemy funkcji `my_strlen` tylko mamy pętle w funkcji my_index.

Dodajemy pure : `__attribute__((noinline,pure))`

```c=
my_index:
        call    my_strlen
        addq    %rdi, %rax
        jmp     .L8
.L10:
        movq    %rdi, %r8
        addq    $1, %rdi
        cmpb    %sil, -1(%rdi)
        je      .L7
.L8:
        cmpq    %rax, %rdi
        jne     .L10
        xorl    %r8d, %r8d
.L7:
        movq    %r8, %rax
        ret
```

Teraz procedura `call    my_strlen` jest wywoływana tylko raz.

> [name=Franciszek Malinka] Mam bardziej pytanie niż uwagę. Czemu sam atrybut "pure" nie załatwia sprawy? Tj. czemu kompilator mimo tego, że funkcja jest czysta, "inlajnuje" ją w taki sposób, jak gdyby nie była pure? Nie mógłby jej mądrzej inlajnować?

## Zadanie 3

:::danger
Autor: Łukasz Wasilewski
:::
![](https://i.imgur.com/X6OgL2R.png)
Wydruk z GodBolta:
```asm=
foobar:
        test    rsi, rsi
        je      .L1
        sub     rdx, rcx #x = y-z
        lea     rax, [rdi+rsi*8]#wyznaczenie końca tabeli
        imul    rdx, rdx#x^2
.L3:
        mov     QWORD PTR [rdi], rdx
        add     rdi, 8
        add     rdx, 7
        cmp     rdi, rax
        jne     .L3
.L1:
        ret
```
```c=
void foobar(long a[], size_t n, long y, long z){
    if (n == 0) return;
    long x = y-z;
    long x_kwadrat = x*x;
    long *end = a + n;
    do {
        *a = x_kwadrat;
        a++;
        x_kwadrat+=7;
    } while (a != end);
}
```
Niezmienniki pętli: to wartości które nie zmieniają się podczas wykonania pętli, czyli tutaj x i x^2. Są wykonane przed pętlą.
Zmienne indukcyjne to zmienne, które z każdym wykonaniem pętli rosną lub maleją o stałą wartość. Tutaj są to i oraz j.
Strength reduction: Zastąpienie przez kompilator pewnych operacji szybszymi np zastąpienie mnożenia dodawaniem, lub wyliczenie niezmienników tylko raz. Tutaj są to zastąpienie j=7*i; a[i]=j+x * x przez

```
movq    rdx,(rdi)
add     $8,rdi
add     $7,rdx i wyliczenie niezmienników.
```

```
// i = rdx, j = rsi
j = 7 * i;
// osłabiona:
j = (i << 3) - i;
```

## Zadanie 4

:::success
Autor: Filip Pazera
:::
![](https://i.imgur.com/YGXT4Ut.png)

**eliminacja wspólnych podwyrażeń** - technika polegająca na obliczaniu wspólnych podwyrażeń tylko raz a następnie wykorzystywaniu wyniku wielokrotnie.

```=
neigh:
        subq    $1, %rdx
        leaq    -1(%rcx), %r8
        addq    $1, %rcx
        imulq   %rsi, %rdx
        leaq    (%rdx,%rsi,2), %rsi
        leaq    (%rdx,%r8), %r9
        addq    %rcx, %rdx
        movq    (%rdi,%rdx,8), %rax
        movq    %rsi, %rdx
        subq    %rcx, %rsi
        addq    (%rdi,%r9,8), %rax
        subq    %r8, %rdx
        addq    (%rdi,%rdx,8), %rax
        addq    (%rdi,%rsi,8), %rax
        ret
```

Wersja odtworzona z powyższego kodu:

```c=
long neigh(long a[], long n, long i, long j) {
    long jp1 = j + 1;
    long jm1 = j - 1;
    long i_minus = (i - 1) * n;
    long i_plus = i_minus + 2 * n;  // (i + 1) * n
    
    return a[i_minus + jm1] + a[i_minus + jp1] 
         + a[i_plus - jp1]  + a[i_plus - jm1];
}
```

Wyrażenia obliczone tylko raz: `j-1`, `j+1`, `(i-1)*n`, `(i+1)*n`.

W celu lepszego zoptymalizowania kodu zauważamy, że podwyrażenie `(i + 1) * n` występuje jedynie jako część większego podwyrażenia `(i + 1) * n + j`, a `(i - 1) * n` - część `(i - 1) * n - j`.
```c=
long neigh(long a[], long n, long i, long j) {
    long u = (i + 1) * n + j;
    long d = (i - 1) * n - j;
    long ul = a[u - 1];
    long ur = a[u + 1];
    long dl = a[d + 1];
    long dr = a[d - 1];
    return ul + ur + dl + dr;
}
```
Instrukcje wygenerowane z powyższego kodu:
```=
neigh:
        addq    $1, %rdx
        imulq   %rsi, %rdx
        addq    %rsi, %rsi
        leaq    (%rdx,%rcx), %r8
        subq    %rsi, %rdx
        subq    %rcx, %rdx
        movq    8(%rdi,%r8,8), %rax
        addq    -8(%rdi,%r8,8), %rax
        addq    8(%rdi,%rdx,8), %rax
        addq    -8(%rdi,%rdx,8), %rax
        ret
```

## Zadanie 5

:::success
Autor: Szymon Jędras
:::
![](https://i.imgur.com/YjQwca6.png)
**programy profilujące** - programy służące do interpretowania danych będących wynikiem ubocznym programu skompilowanym z flagą `-pg`.
**profil płaski** - mówi ile czasu program spędza w każdej funkcji jako absolutna wartość.
**profil grafu wywołań** - pokazuje historię wywołań.
**zliczanie interwałowe** - jest to sposób liczenia czasu spędzonego w odpowiednich funkcjach. Co pewien interwał (1.0 do 10.0 ms) system przerywa wykonywanie programu i sprawdza w jakiej funkcji się znajduje.

#### Jakie informacje niesie ze sobą profil płaski i profil grafu wywołań?
profil płaski:
![](https://i.imgur.com/wzgBPpw.png)
procent czasu jaki program spędził wykonując daną funkcję,
czas spędzony w tej funkcji albo funkcji powyżej,
czas spędzony w tej funkcji,
liczba wywołań funkcji,
czas spędzony w danej funkcji podzielony przez liczba wywołań,
czas spędzony w danej funkcji albo funkcjach pochodnych podzielony przez liczba wywołań.

profil grafu wywołań:
![](https://i.imgur.com/CxisA14.png)
procent czasu spędzonego w tej funkcji (wlicza to funkcje wywołane przez daną funkcję)
czas spędzony w tej funkcji
liczba wywołań funkcji


#### Czemu profilowanie programu wymaga zbudowania go ze specjalną opcją kompilatora -pg? 
Ta flaga powoduje, że każde wywołanie funkcji woła funkcję `mcount`, która powoduje zapisanie informacji użytych później do profilowania.

#### Jak przy pomocy programu profilującego zidentyfikowano w [1, §5.14.2] procedury, które należało zoptymalizować?
Program profilujący dawał nam informacje ile czasu nasz program spędzał na konkretnym etapie programu.

#### Które optymalizacje przyniosły największy efekt?
1. Zmienienie algorytmu sortującego
2. Polepszenie algorytmu hashującego
3. Zmienienie algorytmu przeszukującego listę z rekurencyjnego na iteracyjny (2)
4. Zwiększenie tablicy
5. Zmienienie algorytmu zmieniającego duże litery na małe litery


## Zadanie 6

:::success
Autor: Kacper Solecki
:::

```c=
void nonsense(long a[], long k,
    long *dp, long *jp) {
    long e = a[2];
    long g = a[3];
    long m = a[4];
    long h=k-1;
    long f=g*h;
    long b = a[f];
    long c=e*8;
    *dp=m+c;
    *jp=b+4;
}
```

**ścieżka krytyczna** - zajmująca najwięcej czasu ścieżka zależności między danymi, dająca ograniczenie dolne na czas wykonywania kodu. 

```=
nonsense:
        subq    $1, %rsi
        imulq   24(%rdi), %rsi
        movq    16(%rdi), %r8
        movq    (%rdi,%rsi,8), %rax
        movq    32(%rdi), %rsi
        addq    $4, %rax
        leaq    (%rsi,%r8,8), %rsi
        movq    %rsi, (%rdx)
        movq    %rax, (%rcx)
        ret
```

```graphviz
digraph G {
node [shape = rectangle, style = filled, fillcolor = darkslategray1]
load [fillcolor = darkturquoise]
store [fillcolor = white]
mul
add
sub
lea
load2 [label = "load", fillcolor = darkturquoise]
load3 [label = "load", fillcolor = darkturquoise]
load4 [label = "load", fillcolor = darkturquoise]
store2 [label = "store", fillcolor = white]
{rank = same; store;store2;lea;add}
node [shape = box, style = filled, fillcolor = gray]
rsi [label = "%rsi"]
rdi [label = "%rdi"]
rdx [label = "%rdx"]
rcx [label = "%rcx"]
rsi2 [label = "%rsi"]
rax2 [label = "%rax"]
r82 [label = "%r8"]
{rank = same; rsi, rdi, rdx, rcx}
{rank = same; rsi2, rax2, r82}
rsi -> sub
sub -> mul
rdi -> load [color = red]
rdi -> load2
load -> mul [color = red]
load2 -> r82
mul -> load3 [color = red]
rdi -> load3
rdi -> load4
load3 -> add [color = red]
load2 -> lea
load4 -> lea
lea -> rsi2
lea -> store
rdx -> store
add -> store2 [color = red]
rcx -> store2
add -> rax2 
}
```

Na czerwono zaznaczona jest ścieżka krytyczna.

Load latency = 4
Store latency = 4
![](https://i.imgur.com/VYbUuqJ.png)

**mikro-operacje** - elementarne operacje, które mogą być przetworzone przez jednostkę funkcyjną.

Operacja
```
imulq 24(%rdi), %rsi
```
Zostanie rozłożona na mikro-instrukcje, ponieważ musi zarówno wczytać dane z pamięci, jak i wykonać operację arytmetyczną - nie ma jednostki funkcyjnej, która robi obie te rzeczy

## Zadanie 7

:::success
Autor: Michał Doros
:::



**out-of-order** - wykonywanie instrukcji “do przodu”, niekoniecznie zgodnie z kolejnością. Procesor niekoniecznie wykonuje instrukcje w sekwencyjnej kolejności, tak jak my sobie to wyobrażamy w naszym modelu. Mimo to procesor gwarantuje, że niezależnie od tego w jakiej kolejności wykona instrukcje, to rezultat działania naszego kodu będzie identyczny z tym, jaki byśmy otrzymali, gdyby wykonywał je sekwencyjnie.

**mikroarchitektura** - opis sprzętowej implementacji procesora, określa elementy procesora takie jak bloki funkcjonalne i jednostki wykonawcze oraz połączenia między nimi
> cytat z 5.7: “the underlying system design by which a processor executes instructions.”

**jednostki funkcyjne** części procesora wyspecjalizowane do wykonywania konkretnego rodzaju operacji

| T-  | Stage 1                                        | Stage 2                          | Stage 3                         | Stage 4                          | Stage 5                          |
| --- | ---------------------------------------------- | -------------------------------- | ------------------------------- | -------------------------------- | -------------------------------- |
| 1   | rsi -= 1, load 24(rdi), load 16(rdi)           |                                  |                                 |                                  |                                  |
| 2   |                                                | load 24(rdi), load 16(rdi)       |                                 |                                  |                                  |
| 3   |                                                |                                  | load 24(rdi), load 16(rdi)      |                                  |                                  |
| 4   |                                                |                                  |                                 | load 24(rdi), load 16(rdi)       |                                  |
| 5   |                                                |                                  |                                 |                                  | load 24(rdi), load 16(rdi)       |
| 6   | mulq rdi, rsi                                  |                                  |                                 |                                  |                                  |
| 7   |                                                | mulq rdi, rsi                    |                                 |                                  |                                  |
| 8   |                                                |                                  | mulq rdi, rsi                   |                                  |                                  |
| 9   | load (rdi, rsi, 8), load 32(rdi)               |                                  |                                 |                                  |                                  |
| 10  |                                                | load (rdi, rsi, 8), load 32(rdi) |                                 |                                  |                                  |
| 11  |                                                |                                  | load (rdi, rsi, 8),load 32(rdi) |                                  |                                  |
| 12  |                                                |                                  |                                 | load (rdi, rsi, 8), load 32(rdi) |                                  |
| 13  |                                                |                                  |                                 |                                  | load (rdi, rsi, 8), load 32(rdi) |
| 14  | rax += 4, lea (rsi, r8, 8), oblicz adres (rcx) |                                  |                                 |                                  |                                  |
| 15  | oblicz adres (rdx), store rax                  |                                  |                                 |                                  |                                  |
| 16  | store rsi                                      | store rax                        |                                 |                                  |                                  |
| 17  |                                                | store rsi                        | store rax                       |                                  |                                  |
| 18  |                                                |                                  | store rsi                       | store rax                        |                                  |
| 19  |                                                |                                  |                                 | store rsi                        |                                  |

19 instrukcji + dispatch przed rozpoczęciem + retirement po zakończneiu

## Zadanie 8

:::success
Autor: Franciszek Pindel
:::

> Posługując się programem llvm-mca (ang. machine code analyzer) wbudowanym w Compiler Explorer przedstaw symulację pojedynczego wywołania funkcji «nonsense». Do parametrów programu dodaj: «-mcpu=haswell -timeline -iterations=1».  Na  diagramie Timeline view wskaż punkty **wysłania** (ang. dispatch), **wykonania** i **zatwierdzenia** (ang. retire) instrukcji. Ile czasu zajmuje wykonanie funkcji według symulatora? Wyjaśnij dokładnie z czego wynikają przestoje w przetwarzaniu instrukcji? Na którym z rejestrów procesor użył techniki **przezywania rejestrów** (ang. register renaming)?

* **wysłanie** - moment w którym funkcja została zdekodowana, rozdzielona na mikro-operacje i czeka na wysłanie do odpowiednich jednostek funkcyjnych
* **wykonanie** - instrukcja została wykonana przez jednostki funkcyjne
* **zatwierdzenie** - wynik wykonania instrukcji może zostać zapisanym do rejestrów (np. byliśmy w branchu i przewidzenie skoku okazało się poprawne)
* **przezywanie rejestrów** - rejestry są modyfikowane dopiero po zatwierdzeniu. Przekazywanie rejestrów jest techniką pozwalającą na komunikację pomiędzy jednostkami pamięci bez konieczności pobierania potrzebnej wartości z rejestru. Najłatwiej to pokazać na przykładzie: załóżmy że są wykonywane dwie instrukcje:

```
movq $3, %rax
addq $4, %rax
```

Ponieważ `movq` modyfikuje rejestr `%rax`, to w specjalnej tabeli zostanie utworzona para `(tag, rejestr)`, np:

```
(11, %rax)
```

skojarzy tag `11` z rejestrem `%rax`

Gdy `addq` będzie dekodowana, to jako operand otrzyma tag odpowiadający rejestrowi do którego się odnosi, czyli `11`

Gdy `movq` się wykona, wyprodukuje parę `(3, 11)` zawierającą wartość rejestu i odpowiadający mu tag, teraz może się wykonać `addq` pobierając wartość z odpowiadającego tagu

W ten sposób dane przepływają bez udziału rejestrów

`D` - instrukcja została wysłana
`e` - instrukcja się wykonuje
`E` - instrukcja została wykonana
`R` - instrukcja została zatwierdzona
`=` - instrukcja wysłana, czeka na wykonanie
`-` - instrukcja wykonana, czeka na zatwierdzenie

```
Timeline view:
                    01234567
Index     0123456789        

[0,0]     DeER .    .    . .   subq	$1, %rsi
[0,1]     DeeeeeeeeER    . .   imulq	24(%rdi), %rsi
[0,2]     DeeeeeE---R    . .   movq	16(%rdi), %r8
[0,3]     .D=======eeeeeER .   movq	(%rdi,%rsi,8), %rax
[0,4]     .DeeeeeE-------R .   movq	32(%rdi), %rsi
[0,5]     .D============eER.   addq	$4, %rax
[0,6]     .D=====eE-------R.   leaq	(%rsi,%r8,8), %rsi
[0,7]     . D======eE-----R.   movq	%rsi, (%rdx)
[0,8]     . D============eER   movq	%rax, (%rcx)
[0,9]     .  DeeeeeeeE-----R   retq
```

Licząc do momentu wykonania ostatniej instrukcji wykonanie trwało 16 cykli

Przestoje w wykonaniu instrukcji wynikają z tego, że instrukcje czekają na dane, które jeszcze nie zostały obliczone (w trakcie prezentacji omówię szczegółowo każdą z instrukcji)

Przezywanie rejestrów odbyło się dla rejestru `%rsi`, `%r8`, `%rax` (zauważmy, że w momencie wykonywania instrukcji `movq	(%rdi,%rsi,8), %rax` teoretycznie wartość `%rsi` została zmieniona przez kolejną instrukcję, ale nie stało się tak dzięki przezywaniu)