# 2019q3 Homework1 (review)
contributed by < `Benny1117Yen` >
###### tags: `進階電腦系統理論與實作2019`
* [G01: review](https://hackmd.io/@sysprog/rJM4SPw8S)
## 作業要求
* 從 [課程簡介和注意須知](https://docs.google.com/presentation/d/1Wo22s5aYuuyry97-z2MMmUmdxhjD0wKTdhxIW5oqjvo/edit?usp=sharing), [第 1 週測驗題](https://hackmd.io/@sysprog/HksKVpUIr) 選出你感興趣的 3 個題組進行作答，並且回答附帶的「延伸問題」
* 應當包含 [課程簡介和注意須知](https://docs.google.com/presentation/d/1Wo22s5aYuuyry97-z2MMmUmdxhjD0wKTdhxIW5oqjvo/edit?usp=sharing) 的 Page 9 到 Page 16 裡頭的 C 語言程式設計議題
* 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [對 Linked List 進行氣泡排序](https://hackmd.io/s/BklGm1MhZ) 的模式來撰寫共筆，需要詳細分析自己的想法、參閱的材料 (包含 C 語言規格書的章節)，以及==進行相關實驗==
* 閱讀 [第一週課程進度](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 所有材料，記錄所見所聞並提問，若有不能理解的部分，請標註出來。善用 HackMD 的語法 `:::info` 和 `:::` 標註你的提問
:::info
像是這樣標註提問
:::
* 將你的共筆加到 [2019q3 Homework1 (作業區)](https://hackmd.io/@sysprog/HJvjIvDIr)
* 截止日期：
* Sep 25, 2019 (含) 之前
## 第一周測驗
:::info
目的: 檢驗學員對 [bitwise operator](https://hackmd.io/s/By0MltO_m)
:::
---
## 測驗 `1`
考慮以下 C 程式的 `align4` 巨集的作用是，針對 4-byte alignment，找到給定地址的 round up alignment address。
```cpp
#include <stdio.h>
#define align4(x) (((x) + K) & (-4))
int main(void) {
int p = 0x1997;
printf("align4(p) is %08x\n", align4(p));
return 0;
}
```
預期程式輸出 `align4(p) is 00001998`
Answer : `K = 3`
### 想法 & 思考
:::danger
注意共筆書寫規範：中英文之間以空白字元區隔
:notes: jserv
:::
題目說明是針對 4-byte alignment，並且找 round up alignment address。
所以首先我複習了[解讀計算機編碼的單元](https://hackmd.io/@sysprog/rylUqXLsm#%E8%A8%88%E7%AE%97%E6%A9%9F%E7%82%BA%E4%BD%95%E5%A6%82%E6%AD%A4%E7%B7%A8%E7%A2%BC)以及[記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/BkuMDQ9K7?type=view#data-alignment)，
* 了解到 4 bytes alignment 的意思就是， data 的 address 可以公平的被 4 整除。
* [參考資料1](https://stackoverflow.com/questions/13122846/align-macro-kernel)舉了一例
```c
Say you have a number: 0x1006
For some reasons you want to align it to a 4 bytes boundary.
With a 4-byte boundary, you know aligned values are 0x1000, 0x1004, 0x1008, etc. You then also know the aligned value of 0x1006 is 0x1008.
How would you get 0x1008? The alignment mask for alignment value 4 is (4 - 1) = 0x03
Now 0x1006 + 0x03 = 0x1009 and 0x1009 & ~0x03 = 0x1008
This operation is the __ALIGN_MASK macro.
If you want to pass the value 4 (the alignment) instead of directly 0x03 (the alignment mask), you have the ALIGN macro
```
所以說題目所給的 `0x1997`，按照這個邏輯，address 若能被 4 除盡則對齊自己；反之，被 4 除不盡則要如[參考資料2](https://github.com/spotify/linux/blob/master/include/linux/kernel.h)`＃41` 所寫
```cpp=
#define ALIGN(x,a) __ALIGN_MASK(x,(typeof(x))(a)-1)
```
mask 等於 cast 成 int type，因為 4 byte align 所以 a 填入 4，所以是 (4-1)，意思就是用完整的 4bytes 來存餘數的部分。又
```cpp=
#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))
```
所以我們的 K 填的是 3，而 C 語言是用二補數編碼，所以 ~3 的 二補數是 -4，
因此，`0x1997 + 3 `以 16 進位表示是 `0x199a`，`0x199a & -4 `就等於 `0x1998`，以 %08x 輸出即`0x00001998`。
### 測試實作 & 延伸
[小實驗1](https://github.com/P86071244/C_projects_training/blob/master/Course/L1/demo6.c)實際跑測驗1，結果吻合。
[小實驗2](https://github.com/P86071244/C_projects_training/blob/master/Course/L1/demo16.c)以參考資料2 來自[spotify/linux/include/linux/kernel.h](https://github.com/spotify/linux/blob/master/include/linux/kernel.h#L41)作為延伸把參考資料1 的`0x1006`扔入此 macro 中，得到`0x1008`。
```cpp=
#include <stdio.h>
#define ALIGN(x,a) __ALIGN_MASK(x,(typeof(x))(a)-1)
#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))
int main() {
int x = 0x1006;
printf("%08x\n", ALIGN(x, 4));
return 0;
}
```
---
## 測驗 `2`
考慮以下 C 程式可取得以 `sizeof(int)` 為 alignment 基礎的整數空間，也就是說，當 `sizeof(int)` 為 `4` 的時候:
* 給定 `char arr[13];`，`INT_SIZE_OF(arr)` 要得到 `16`;
* 給定 `short int s;`，`INT_SIZE_OF(s)` 要得到 `4`
```cpp
#include <stdint.h>
#define INT_SIZE_OF(n) \
((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y))
```
* 參考資訊: [Memory access and alignment](https://lwn.net/Articles/260832/)
Answer : `X = -1` `Y = -1`
### 想法 & 思考
測驗2 跟測驗1 很像，在 alignment 部分選用 `sizeof(int) = 4` 來 align。我們看到給定 `sizeof(n)` 填入 `char` 時是 `1 byte`，而 `short int` 是 `2 bytes`
* 也就是說在這個 macro 中，`n` 是 `arr` 時，`sizeof(arr) = 13`；`n` 是 `s` 時，`sizeof(s) = 2`。
```cpp=
#define INT_SIZE_OF(n) \
((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y))
```
* 那由於都不整除 4，所以說參考前面的
```cpp=
#define ALIGN(x,a) __ALIGN_MASK(x,(typeof(x))(a)-1)
#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))
```
所以用 `typeof(x))(a)-1` 來對齊下一個位子，此時 `X` 也就等於 `-1`，`mask` 就等於 `sizeof(int) + X = 3` ，而 `~(sizeof(int) + Y)` 就等於 `~(mask)` 也就是等於 `~3`。
* 說明一下為何要 `& ~(sizeof(int) – 1)` ， `_INTSIZEOF(n)` 做的事情就是將 `n` 的長度化為 `int` 長度的整數倍。
`~（4-1）=~（00000011b）= 11111100b` ，這樣任何數 `& ~(sizeof(int) – 1)` 後最後兩位肯定為 `0`，就肯定是 `4` 的整數倍了。
(sizeof(n) + sizeof(int) – 1）就是將大於 `4m` 但小於等於 `4（m+1）` 的數提高到大於等於`4（m+1）` 但小於 `4(m+2)`，這樣再 `& ~(sizeof(int) – 1)` 後就正好將原長度補齊到4的倍數了。
有個有趣的比喻，如[參考資料1](https://blog.csdn.net/guanjianhe/article/details/82845712)
* 問題1: 假設有要把一批貨物放到集裝箱裡，貨物有 `12` 件，
一個箱子最多能裝 `6` 件貨物，求箱子的數目。
解答：顯然我們需要 `12÷6=2` 個箱子，並且每個箱子都是滿的。
* 問題2: 把問題1的條件改一下，假設一個箱子最多能裝5件貨物，那麼現在的箱子數是多少？
解答：`12÷5 = 2.4` 個，但是根據實際情況，箱子的個數必須為整數，自然我們就要取3。
* 問題3: 設一個箱子最多可以裝M件貨物，且現有N件貨物，
則至少需要多少個箱子，給出一般的計算公式。
這裡要注意兩點：
1、箱子的總數必須為整數
2、`N` 不一定大於 `M`，很顯然，即使 `N ≤ MN`，也需要一個箱子
定義 `/` 運算為取整數運算，即對任意兩個整數 `N,M`，必然有且只有唯一的整數X，滿足 `X × M ≤ N < (X + 1) × M` ，那麼記 `N / M = X`，這也是 C語言裡 `/` 運算的含義。
* `/` 運算有一個基本的性質：若 `Ｎ＝ＭＸ＋Ｙ` ，則 `N / M = X + Y / M`。注意: `N` 不可以隨便拆，假設 `N = A + B`，那麼一般情況下 `N / M` 不一定等於 `A / M + B / M`，如果 `A` 和 `B` 至少有一個是 `M` 的倍數，才能保證式子一定成立。
* 根據上面 `/` 運算符的定義，來討論問題3，已知 `N / M = X`，那麼:
1.當 `N` 正好是 `M` 的倍數時，即 `N = M x X` 時，箱子數就是 `X = N /M`。
2.如果 `N` 不是 `M` 的倍數，即 `N = M x X + Y(1 ≤ Y < M)` 那麼還要多一個箱子來裝剩下的 `Y` 件貨物，則箱子總數為 `X + 1 = N / M + 1`。
* 既然每次都要去判斷 `N` 和 `M` 的倍數關係，於是出現了以下公式。
$$(N + M - 1) / M$$
* 推導:
1.當 `N = MX` 時，`(N + M - 1) / M = MX / M + (M - 1) / M = X`
2.當 `N = MX + Y(1 ≤ Y < M)` 時，由 `1 ≤ Y < M` 兩邊同時加上 `M - 1`，得到 `M ≤ Y - 1 + M < 2M -1 < 2M`
3.根據 `/` 運算的定義 `(Y - 1 + M) / M = 1`，所以 `(N + M - 1) / M = (MX + Y + M - 1) / M = MX / M + (Y + M - 1) / M = X + 1(1 ≤ Y < M)` ，推出公式 `(N + M - 1) / M` 與討論結果一致。
* 所以看回 `((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y))` 這裏，`sizeof(int)` 相當於箱子的容量 `M`，變量的真實字節大小相當於貨物總數 `N`，整個 macro 就是求 `n` 所佔的 bytes 數目。而 `&~(sizeof(int)-1))` 它用到了 bitwise 的技巧，若 `M` 是 power of 2，$M = 2^Y$，則 `N / M = N >> Y = (N & ~(M-1)) >> Y`。
### 測試實作 & 延伸
[小實驗3](https://github.com/P86071244/C_projects_training/blob/master/Course/L1/demo7.c)實際跑測驗2，我代入 `int = 4` 、 `char arr[13]` 、 `short int s` ，分別會輸出，`4` 、 `16` 、 `4`。
```cpp=
#include <stdio.h>
#define INT_SIZE_OF(n, X, Y) \
((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y))
int main() {
char arr[13];
short int s;
printf("%ld\n", sizeof(int));
printf("%ld\n", INT_SIZE_OF(4, -1, -1));
printf("%ld\n", INT_SIZE_OF(arr, -1, -1));
printf("%ld\n", INT_SIZE_OF(s, -1, -1));
return 0;
}
```
延伸來自[linux/include/linux/kernel.h](https://github.com/spotify/linux/blob/master/include/linux/kernel.h#L41)
---
## 測驗 `3`
考慮以下 C 程式碼:
```cpp=
#include <stdbool.h>
bool func(unsigned int x) {
return x && ((x & (~x + 1)) == x);
}
```
可改寫為以下等價的程式碼:
```cpp=
bool func(unsigned int x) {
unsigned int unknown = 0;
while (x && unknown <= 1) {
if ((x & Z) == 1)
unknown++;
x >>= 1;
}
return (unknown == 1);
}
```
請補完程式。
Answer : `Z = 1`
### 想法 & 思考
我實驗了一下原本的程式碼，將 `x` 等於 `0`, `1`, `2`, `3`... `15` 代入，得到
|x|~x|~x+1|x & (~x + 1)|(x & (~x + 1)==x)|
|:----:|:----:|:----:|:----:|:---:|
|0000|1111|1110|0000 (overflow)|0|
|0001|1110|1111|0001|1|
|0010|1101|1110|0010|1|
|0011|1100|1101|0001|0|
|0100|1011|1100|0100|1|
|0101|1010|1011|0001|0|
|0110|1001|1010|0010|0|
|0111|1000|1001|0001|0|
|1000|0111|1000|1000|1|
|1001|0110|0111|0001|0|
|1010|0101|0110|0010|0|
|1011|0100|0101|0001|0|
|1100|0011|0100|0100|0|
|1101|0010|0011|0001|0|
|1110|0001|0010|0010|0|
|1111|0000|0001|0001|0|
會發現 `x & (~x + 1)`後會留下最右邊 `1 bit` 的 `1`，且只有 `x` = `1`, `2`, `4`, `8` 這些 `power of 2` 時，`(x & (~x + 1)==x)` 會等於 `1` (True)，也就是說只有這些 `x` `&` `自己的二補數` 才會等於自己。
再來看到改寫程式碼的部分，解讀一下後發現:
* `unknown` 類似於 counter，一開始初始值為 `0` ，確保一定會進入 while 迴圈，而用來作為 while 迴圈該不該跳出的條件是 `unknown > 1`。
* 那麼迴圈中的 `if` 條件跟 `x >>= 1`，又分別代表說，如果我今天 `x` & `Z` 等於 `1`時，`unknown` 會加一，就會跳出 while 並且 return True ，而要是這個 if 條件不成立時，x 會繼續往右邊移動 `1bit` 直到符合 if 條件。
* 因此結合前面觀察所得，我們應該讓 `Z` 等於 `1`，這樣才能作為判斷是否所有 `bit數` 只有 `1` 處有 `1`，且只要是 `power of 2`，即使第一次迴圈中不會進到 if 條件，但也可以透過 `x >>= 1` 向右移動直到 if 條件成立，且 `unknown` 加一而跳出迴圈，return True。
### 測試實作 & 延伸
[小實驗4](https://github.com/P86071244/C_projects_training/blob/master/Course/L1/demo5.c)實驗原程式碼跟改寫的程式碼。
```cpp=
#include <stdbool.h>
#include <stdio.h>
bool func(unsigned int x) {
return x && ((x & (~x + 1)) == x);
}
bool func1(unsigned int x) {
unsigned int unknown = 0;
while(x && unknown <=1) {
if ((x & 1) == 1)
unknown++;
x >>= 1;
}
return (unknown == 1);
}
int main() {
printf("%d\n",func(0));
printf("%d\n",func(1));
printf("%d\n",func1(0));
printf("%d\n",func1(1));
return 0;
}
```
輸出為
```cpp=
0 //驗證原程式碼 x 代入 0
1 //驗證原程式碼 x 代入 1
0 //驗證改程式碼 x 代入 0
1 //驗證改程式碼 x 代入 0
```
[參考資料](https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array/11227902#11227902)這是個探討如何 branch prediction, branchless 的介紹:
:::danger
修正用語:
1. "data" 應該翻譯為「資料」;
2. 繁體中文用「機率」;
:::
他說假設這是在1800年代-在進行長距離或無線電通信之前。
您是路口的操作員，並且聽到火車駛入。 您不知道應該走哪條路。 您停下火車，詢問駕駛員他們想要哪個方向。 然後您適當地設置開關。
火車很重，慣性很大。 因此，它們要花很多時間才能啟動和減速。
有沒有更好的辦法？ 您猜火車將朝哪個方向行駛！
* 如果您猜對了，它將繼續進行。
* 如果您猜錯了，機長會停下來，後退並大喊大叫，以撥動開關。 然後，它可以沿著其他路徑重新啟動。
** 如果你每次都猜對了，那麼火車永遠不會停下來。
** 如果你猜錯太多次，那麼火車會花費很多時間來停車，返回，然後再啟動。
考慮一個if條件語句：在處理器層面上，這是一個分支指令：
當處理器看到這個分支時，沒辦法知道哪個將是下一條指令。該怎麼辦呢？貌似只能暫停執行，直到前面的指令完成，然後再繼續執行正確的下一條指令？
現代處理器很複雜，因此它需要很長的時間"熱身"、"冷卻"
是不是有個更好的辦法呢？你猜測下一個指令在哪！
* 如果你猜對了，你繼續執行。
* 如果你猜錯了，你需要flush the pipeline，返回到那個出錯的分支，然後你才能繼續。
** 如果你每次都猜對了，那麼你永遠不會停。
** 如果你猜錯了太多次，你就要花很多時間來滾回，重啟。
這就是 branch prediction，所以怎樣能很好的預測，盡可能地使火車必須返回的次數變小？你看看火車之前的選擇過程，如果這個火車往左的概率是99%。那麼你猜左，反之亦然。如果每3次會有1次走這條路，那麼你也按這個三分之一的規律進行。
換句話說，你試著定下一個模式，然後按照這個模式去執行。這就差不多是分支預測是怎麼工作的。
大多數的應用都有很好的分支預測。所以現代的分支預測器通常能實現大於90%的命中率。但是當面對沒有模式識別、無法預測的分支，那分支預測基本就沒用了。
Further reading: ["Branch predictor" article on Wikipedia](https://en.wikipedia.org/wiki/Branch_predictor)
#### 綜上所述，問題所在就是這 if-statement :
```cpp=
if (data[c] >= 128)
sum += data[c];
```
注意到數據是分佈在0到255之間的。當數據排好序後，基本上前一半大的的數據不會進入這個條件語句，而後一半的數據，會進入該條件語句。
連續的進入同一個執行分支很多次，~~這對分支預測是非常友好的~~，這對分支預測有幫助。可以更準確地預測，從而帶來更高的執行效率。
:::danger
避免寫出「這對分支預測是非常友好的」這樣不倫不類的句子
:notes: jserv
:::
:::success
訂正
:::
#### 快速理解一下:
```c
T = branch taken
N = branch not taken
data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
```
但是當資料是完全隨機的，分支預測就沒什麼用了。因為中央處理器無法預測隨機的資料。因此就會有大概 50% 的機率預測出錯。
```c
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (completely random - hard to predict)
```
#### 我們能做些什麼呢?
如果編譯器無法優化帶條件的分支，如果你願意犧牲程式碼的可讀性，以換來更好的效能，你可以用下面的一些技巧。
Replace:
```cpp=
if (data[c] >= 128)
sum += data[c];
```
with:
```cpp=
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
```
這消滅了分支，把它替換成 bitwise operations。
* 分析
```cpp
`<<` : 左移運算符，num << 1，等價於num*2
`>>` : 右移運算符，num >> 1，等價於num/2，空位以符號位來補齊
`>>>`: 無符號右移，忽略符號位(最高位)，空位都以0補齊
`~` : 非運算符，當位為0，則結果為1，但位為1，則結果為0
```
:::danger
`>>>` 是否存在於 C 語言規格書呢？
:notes: jserv
:::
:::success
`>>>` 出現在 C++ 中，C語言並沒有。
:::
* 當 `data[c]` 大於 `128` 時，`int t = (data[c] - 128) >> 31`，根據帶符號的右移位運算法則，得到 `t=0`，則 `~t=-1`(即所有的位都為1); 從而 `~t & data[c] = data[c]`，故等效 `sum += data[c]`。
* 當 `data[c]` 小於或者等於 `128` 時，`int t = (data[c] - 128) >> 31`，根據帶符號的右移位運算法則，得到 `t=-1`，則 `~t=0`; 從而 `~t & data[c] = 0`，故等效此未進入分支。
這是他 C++ 跑出來的結果:
```c
// Branch - Random
seconds = 11.777
// Branch - Sorted
seconds = 2.352
// Branchless - Random
seconds = 2.564
// Branchless - Sorted
seconds = 2.587
```
然後觀察到:
* 有 branch: Sorted 跟 unsorted data 效率有很大的區別。
* 而用了 bitwise operaion：Sorted 跟 unsorted data 效率沒有很大的區別。
* 在使用C++的情況下，按位操作還是要比排好序的分支操作要慢
- 一般的建議是盡量避免在關鍵循環上出現對數據很依賴的分支。（就像這個例子）
:::danger
上述討論未涉及 C++ 特性，應以 C 語言為標的
:notes: jserv
:::
## 小結
補數忘光光的我，只好一直反覆念 jserv 老師的參考資料，活化自己腦袋，
現在則是對 macro 中的 align 比較有感覺了，數論的部分我認為還需要再努力，bitwise operaion 實在有許多深奧之處。
Sign in with Wallet
Connect another wallet