# 2020q1 Homework3 (quiz3)
contributed by < `KYG-yaya573142` >
> [第 3 週測驗題](https://hackmd.io/@sysprog/linux2020-quiz3)
## 測驗 1
### XOR linked list 原理
XOR 運算特性為
* $A \oplus A = 0$
* $A \oplus 0 = A$
* $A \oplus 1 = \neg A$
* $(A \oplus B) \oplus B = A$
```cpp
typedef struct __list list;
struct __list {
int data;
struct __list *addr;
};
```
當初填做答表單會全錯就是因為我沒理解 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 實作的核心邏輯，在 XOR linked list 中 node 儲存的 `addr` 內容是 address of previous node (之後簡稱 prev) 及 address of next node (之後簡稱 next) 以 XOR 運算的結果 `addr = prev ^ next`，根據上述 XOR 的運算特性，可以用以下方式在 node 間移動
* `addr ^ prev = next`
* `addr ^ next = prev`
而在 list head 和 list tail 的 node，根據 $A \oplus 0 = A$ 可知其儲存的 `addr` 剛好都是鄰近的唯一 node 的指標
* `0 ^ next = addr = next`
* `prev ^ 0 = addr = prev`
```graphviz
digraph xs {
rankdir=LR;
node [shape=record]; //default node style
node1 [label="addr1|(0 ^ addr2)", xlabel="head"];
node2 [label="addr2|(addr1 ^ addr3)"];
node3 [label="addr3|(addr2 ^ addr4)"];
node4 [label="addr4|(addr3 ^ 0)", xlabel="tail"];
node1->node2->node3->node4
}
```
```cpp
#define XOR(a, b) ((list *) ((uintptr_t) (a) ^ (uintptr_t) (b)))
void insert_node(list **l, int d) {
list *tmp = malloc(sizeof(list));
tmp->data = d;
if (!(*l)) {
tmp->addr = NULL;
} else {
(*l)->addr = XOR(tmp, (*l)->addr);
tmp->addr = *l;
}
*l = tmp;
}
```
* 從 list head 新增 node，所以原本 list head 的 `*l` 需要更新儲存的 `addr` 為 next node 與 prev node 的 XOR
* `*l` 原本位於 list head，`(*l)->addr` 直接是 next node 的位置
* 新增的 `tmp` 就是 prev node
* 若尚無任何 node，新增的 node 會是唯一的 node 所以儲存的指標為 `NULL`
```cpp
void delete_list(list *l) {
while (l) {
list *next = l->addr;
if (next)
next->addr = XOR(next->addr, l);
free(l);
l = next;
}
}
```
* 從 list head 開始依序 `free` 掉 node
* `l` 原本位於 list head，`l->addr` 直接是 next node 的位置
* `free` 掉 `l` 以前須先更新 next node 中儲存的位置，因為原本的 next node 會變成新的 list head
* `XOR(next->addr, l)` 的結果會是 `next` 的下個 node 的位置
* `while` 直到 `free` 完所有 node
### 解題思路
```cpp=
list *sort(list *start)
{
if (!start || !start->addr)
return start;
list *left = start, *right = start->addr;
left->addr = NULL;
right->addr = XOR(right->addr, left);
left = sort(left);
right = sort(right);
...
```
* 6~11 行的部分利用遞迴的方式分割 list，但一次遞迴只分割出一個 node
* `left` 指向分割出的單一 node
* `right` 指向剩下的 node
* `start` 會指向已經排序完成的 list head
```cpp=12
...
for (list *merge = NULL; left || right;) {
if (!right || (left && left->data < right->data)) {
list *next = left->addr;
if (next)
next->addr = XOR(left, next->addr);
if (!merge) {
start = merge = left;
merge->addr = NULL;
} else {
merge->addr = LL1;
left->addr = LL2;
merge = left;
}
left = next;
} else {
...
```
* 第 13 行開始執行 merge sort
* `if (!right || (left && left->data < right->data))` 是實行排序判斷的位置，採用遞增順序所以數值小的排在前面
* 先探討將 `left` 的 node 接上 `merge` 的情況 (也就是 `left->data` 比較小，或是奇數 node 的情況)
* 15~17 行先將 node 從 list 分離出來
* 此時 `left` 指向這個分離出來的單一 node
* `next` 指向剩餘的 list
* 19~21 行代表此時 `merge` 無任何 node
* `left` 會是唯一的 node，所以儲存的指標為 `NULL`
* `start` 會指向已經排序完成的 list head，所以也是指向 `left`
* 22~25 行要將 `left` 接在 `merge` 的前面
* `merge` 是原本的 list head，`merge->addr` 直接是 next node 的位置
* `merge` 的 prev node 就是前面接上的 `left`，
* `merge->addr` 須更新為 `prev node ^ next node`，因此 `LL1` 應填入 `XOR(merge->addr, left)`
* `left` 會是新的 list head，所以 `left->addr` 會直接指向 next node，因此 `LL2` 應填入 `merge`
```cpp=27
...
} else {
list *next = right->addr;
if (next)
next->addr = XOR(right, next->addr);
if (!merge) {
start = merge = right;
merge->addr = NULL;
} else {
merge->addr = RR1;
right->addr = RR2;
merge = right;
}
right = next;
}
}
return start;
}
```
* 整體的邏輯與將 `left` 的 node 接上 `merge` 時的邏輯一樣，只是改為將 `right` 接上，就不再贅述原理
* `RR1` 應填入 `XOR(merge->addr, right)`
* `RR2` 應填入 `merge`
### 改善程式碼
#### `delete_list`
後來實際使用時，發現 `delete_list(queue)` 後不會將 `queue` 指標設為 NULL，這會導致接下來 `insert_node(&queue)` 會發生 segmentation fault
```cpp
int main(int argc, char const *argv[])
{
list *queue = NULL;
insert_node(&queue, 666);
delete_node(queue);
insert_node(&queue, 777); //seg. fault
}
```
因此我將 `delete_list` 改為使用 pointer to pointer 來實作
```cpp
void delete_list(list **l) {
while (*l) {
list *next = (*l)->addr;
if (next)
next->addr = XOR(next->addr, *l);
free(*l);
*l = next;
}
}
```
#### `show`
原本的實作缺乏簡單展示 list 內容的函式，而且 XOR linked-list 處理起來較複雜，因此實作一個輔助函式來顯示 list 的所有內容
```cpp
void show(list *target)
{
if (!target) {
printf("empty list\n");
return;
}
printf("head-> ");
list *prev = NULL, *next = target;
while(target) {
printf ("%d ", target->data);
next = XOR(target->addr, prev);
prev = target;
target = next;
}
printf("<-tail\n");
return;
}
```
### 最佳化策略 - 修改 `sort` 分割 node 的方式
原本 `sort` 中每次只會分割出一個 node，參照 [lab-0](https://hackmd.io/_a-DyVJ6T2SwYZO4kZLyNQ) 中 [merge sort](https://github.com/KYG-yaya573142/lab0-c/blob/73554501e945a60b23548de4d20b6941a166f3ac/queue.c#L195) 的做法，修改為每次會將 list 分為一半。實作的程式碼如下，明顯有使用過多變數的缺點，但現階段還想不到更漂亮的寫法
```cpp
list *merge_sort(list *start)
{
if (!start || !start->addr)
return start;
list *left = start, *right = start->addr;
list *tmp1 = start, *tmp2 = start->addr;
list *prev = NULL, *next = start;
/* split list into half */
while (right && XOR(right->addr, tmp1)) {
/* advance right by 2 nodes */
right = XOR(right->addr, tmp1);
tmp1 = right;
right = XOR(right->addr, tmp2);
tmp2 = right;
/* advance left by 1 node */
next = XOR(left->addr, prev);
prev = left;
left = next;
}
right = XOR(left->addr, prev);
right->addr = XOR(right->addr, left);
left->addr = XOR(left->addr, right);
left = merge_sort(start);
right = merge_sort(right);
...
```
以下列程式碼檢查，結果正確
```cpp
#define total_nodes 100
int main(int argc, char const *argv[])
{
list *queue = NULL;
srand(time(NULL));
for (int i = 0; i < total_nodes; i++) {
insert_node(&queue, (rand() % 100));
}
queue = merge_sort(queue);
show(queue);
}
```
#### 效能差異
使用以下程式碼進行測試
```cpp
#define total_nodes 1000
#define sample_size 100
int main(int argc, char const *argv[])
{
struct timespec t_start, t_end;
list *queue1 = NULL;
srand(time(NULL));
FILE *fp = fopen("./out_statistic", "w");
for (int i = 1; i < total_nodes + 1; i++) {
double t1[sample_size] = {0};
double mean1 = 0.0, sd1 = 0.0, result1 = 0.0;
int count1 = 0;
/* measure sample_size times of data and
* remove outliers based on the 95% confidence level
*/
for (int n = 0; n < sample_size; n++) {
/* generate linked-list for testing */
for (int node = 0; node < i; node++)
insert_node(&queue1, (rand() % 100));
clock_gettime(CLOCK_MONOTONIC, &t_start);
queue1 = merge_sort(queue1, i); /* measurement */
clock_gettime(CLOCK_MONOTONIC, &t_end);
t1[n] = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
mean1 += t1[n]; //sum
delete_list(&queue1);
}
mean1 /= sample_size; //mean
for (int n = 0; n < sample_size; n++) {
sd1 += (t1[n] - mean1) * (t1[n] - mean1);
}
sd1 = sqrt(sd1 / (sample_size - 1)); //standard deviation
for (int n = 0; n < sample_size; n++) { //remove outliers
if (t1[n] <= (mean1 + 2 * sd1) && t1[n] >= (mean1 - 2 * sd1)) {
result1 += t1[n];
count1++;
}
}
result1 /= count1;
fprintf(fp, "%d %.5lf samples: %d\n", i, (result1/1000), count1);
assert(count1 > 80); /* remove too many samples, considered unrepresentative */
}
fclose(fp);
return 0;
}
```
* 排序所需時間明顯降低
### 最佳化策略 - 使用 tiled merge sort
Wiki 的 Merge sort 中談到 [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort) 的策略
> For example, the tiled merge sort algorithm stops partitioning subarrays when subarrays of size S are reached, where S is the number of data items fitting into a CPU's cache. Each of these subarrays is sorted with an in-place sorting algorithm such as insertion sort, to discourage memory swaps, and normal merge sort is then completed in the standard recursive fashion.
* 先將子序列分割，直到子序列小於某個閾值 S 就停止分割
* S 值為可完整放進處理器 cache 中的元素數量
* 每個大小為 S 的子序列，都透過適用於小規模 in-place (即不需要額外配置記憶體) 排序演算法進行排序，減少在記憶體內交換特定區域的次數
#### CPU 硬體組態
* Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
* 4 CPU cores
* 8 threads
* L1i cache: 32 KB (x4 cores)
* L1d cache: 32 KB (x4 cores)
* 8-way set associative
* L2 cache: 256 KB (x4 cores)
* 8-way set associative
* L3 cache: 8 MB
* 16-way set associative shared cache
剛好可以用 CSAPP Cache memories 講義中的範例
* 64 bytes per block (cache line)
* 8 blocks per set
* total 64 sets
* node 的大小為 16 bytes
* 一個 block 可以存放 4 nodes
* $4 (nodes)\times 64(sets)=256$ 個連續的 node 會用掉所有 set 中的一個 block (因為是 set associative)
* $256\times 8=2048$ 個 node 會剛好用完 L1 cache
* 但這只是理想的算法，快取還需要存放除了 node 以外的資料，且每個 node 的記憶體位置不一定是連續的
#### in-place algorithm - insertion sort
我選用 insertion sort 做為 in-place 排序演算法
```cpp
list *insert_sort(list *head)
{
if (!head || !head->addr)
return head;
/* pick first node from head */
list *result = head;
head = head->addr;
head->addr = XOR(result, head->addr);
result->addr = NULL;
while (head) {
/* detach node from head */
list *next = head->addr;
if (next)
next->addr = XOR(head, next->addr);
/* insertion sort */
list *node = result, *prev = NULL, *tmp = NULL;
while (node && node->data < head->data) {
tmp = node;
node = XOR(prev, node->addr);
prev = tmp;
}
if (!prev) { /* insert at head */
head->addr = result;
result->addr = XOR(result->addr, head);
result = head;
}
if (!node) { /* insert at tail */
head->addr = prev;
prev->addr = XOR(prev->addr, head);
}
if (prev && node) { /* insert in between prev and node */
prev->addr = XOR(XOR(prev->addr, node), head);
node->addr = XOR(head, XOR(node->addr, prev));
head->addr = XOR(prev, node);
}
head = next;
}
return result;
}
```
#### 找出適當的 S
修改原本 merge sort 部分的程式碼
```cpp
list *merge_sort(list *start, int count)
{
...
/* split list */
...
/* use in-place alg. when list size <= threshold */
if ((count >> 1) > threshold) {
left = merge_sort(start, (count >> 1) + (count & 0x1));
right = merge_sort(right, count >> 1);
} else {
left = insert_sort(start);
right = insert_sort(right);
}
...
```
* 當子序列數量低於 S 就切換成使用 insertion sort
* `threshold` 就是閾值 S，直接設為 global variable 以方便實驗時進行更動
* 為了方便計算子序列資料數量，直接把總資料數量 `count` 當作參數帶進 `merge_sort`
* 最後一樣用 merge sort 來合併所有子序列
實驗的程式碼如下
```cpp
#define total_nodes 1000
int main(int argc, char const *argv[])
{
list *queue = NULL;
struct timespec t_start, t_end;
srand(time(NULL));
for (threshold = 0; threshold < 500; threshold++) { /* use different threshold */
for (int i = 0; i < total_nodes; i++) { /* generate random list */
insert_node(&queue, (rand() % 100));
}
clock_gettime(CLOCK_MONOTONIC, &t_start);
queue = merge_sort(queue, total_nodes);
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t1 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
printf("%d %lld\n", threshold, (t1/1000));
delete_list(&queue);
}
return 0;
}
```
* 量測不同 S 時，排序所需的時間
* 實驗的 list 總共有 1000 nodes
* 水平黑線是原本 [`merge_sort`](#最佳化策略---修改-sort-分割-node-的方式) 排序 1000 個 nodes 的所需時間
* 分別在 62、125、250、500 有明顯的速度落差
* 當 S 在 125 以內時，排序所需的時間會快於單純使用 merge sort
* S 在 61 以內時具有最快的速度
:::warning
原本以為這漂亮的圖有特別的意義，後來才想到一件事情
* 每次 merge sort 都會把 list 分為一半
* 所以我使用的 1000 nodes 經過分割後，產生的子序列只會有幾種固定的大小，剛好是 500、250、125、62 ...
* 例如當 S 在 126~250 之間時，實際能被 insertion sort 處理的子序列大小永遠是 125，因為上一個子序列大小是 250
:::
* 比對原本的 merge sort 可以看到所需時間降低
* 會有階梯狀的原因如上述說明，是因為子序列大小每次都是對半分造成的
#### 使用 CSAPP 的 cache lab
本來在思考是否有方法可以了解 merge sort 在不同 S 下使用 cache 的情況，發現可以使用 [Valgrind - Cachegrind](https://valgrind.org/docs/manual/cg-manual.html)，但同時也想到之前在 CSAPP 的 [cache lab](http://csapp.cs.cmu.edu/3e/labs.html) 中有提供一個模擬 cache 行為的程式，因此決定先嘗試這個比較簡單的方法
* 首先在程式碼本身盡量移除跟 merge sort 無關的部分，避免干擾
```cpp
#define total_nodes 1000
int main(int argc, char const *argv[])
{
list *queue = NULL;
srand(time(NULL));
for (int i = 0; i < total_nodes; i++) { /* generate random list */
insert_node(&queue, (rand() % 100));
}
queue = merge_sort(&queue, total_nodes);
return 0;
}
```
* 使用 valgrind 來紀錄不同 S 值下執行程式的 address trace
```shell
$ valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ./test > out
```
* 接著使用 CSAPP 的作業參考範例 `csim-ref` 來模擬，使用的參數是對照 [CPU-硬體組態](#CPU-硬體組態) 設置的
```shell
$ ./csim-ref -s 6 -E 8 -b 6 -t out
```
#### S = 0 (單純 merge sort)
```
hits:609821 misses:3846 evictions:3334
```
#### S = 50
```
hits:519978 misses:3764 evictions:3252
```
#### S = 100
```
hits:591181 misses:3759 evictions:3247
```
#### S = 200
```
hits:737422 misses:3733 evictions:3221
```
#### S = 400
```
hits:1140759 misses:3730 evictions:3218
```
* cache eviction 和 cache miss 都沒有明顯的差異，但是 cache hit 隨著 S 提高而增加
* 在假設模擬器正確的前提下，可以推斷出
* 在測試的範圍內，都不會出現 L1 cache 不夠用的情況
* 提高 S 確實能讓處理器更善用 L1 cache，但由於 insertion sort 比 merge sort 慢，過高的 S 會導致 insertion sort 的效能劣勢將 cache 的優勢抵銷，甚至是降低整體的效能
### 修改 lab0-c 裡頭的 harness.c (待補)
## 測驗 2
### 解題思路
```cpp
#include <stddef.h>
struct node {
int data;
struct node *next;
} *head;
void insert(struct node *newt) {
struct node *node = head, *prev = NULL;
while (node != NULL && node->data < newt->data) {
prev = node;
node = node->next;
}
newt->next = node;
if (prev == NULL)
head = newt;
else
prev->next = newt;
}
```
* `while` 迴圈實際上是在排序，將 `newt` 根據資料大小插入 list 中適當的位置
```cpp
void insert(struct node *newt)
{
struct node **link = &head;
while (*link && AA)
BB;
newt->next = *link;
*link = newt;
}
```
* `link` 是 pointer to pointer，可以理解為一般 pointer 儲存的是某個變數的位置，而 pointer to pointer 儲存的就是某個指標的位置，因此 `*link` 是指標
* `while` 迴圈做的事情一樣是排序，必須先對 `link` 進行 dereference 一次才會得到指向 list element 的指標，因此 `AA` 應填入 `(*link)->data < newt->data`
* pointer to pointer 儲存的是指標的位置，因此必須使用取址運算子 `&` 來取用指標的位置，因此 `BB` 應填入 `link = &(*link)->next`
### 對執行時間與 [Branch predictor](https://en.wikipedia.org/wiki/Branch_predictor) 的影響
使用以下程式碼進行實驗，分別測試兩種不同的 `insert` 的所需時間
```cpp
int main(int argc, char const *argv[])
{
struct timespec t_start, t_end;
head = NULL;
for (int i = 0; i < 1000; i++) {
struct node *newt = malloc(sizeof(struct node));
newt->data = i;
newt->next = NULL;
clock_gettime(CLOCK_MONOTONIC, &t_start);
//insert(newt);
insert_ptp(newt);
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t1 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
printf("%d %lld\n", i, t1);
}
return 0;
}
```
* 無顯著的差異，可能要進一步提升測試的資料總數
使用 `perf` 來分析 branch 的差異
```shell
$ sudo perf stat --repeat 5 -e branch-instructions:u,branch-misses:u ./test
```
* `insert`
```
Performance counter stats for './test' (5 runs):
1,383,346 branch-instructions:u ( +- 0.01% )
10,871 branch-misses:u # 0.79% of all branches ( +- 1.04% )
0.004962 +- 0.000679 seconds time elapsed ( +- 13.68% )
```
* `insert_ptp`
```
Performance counter stats for './test' (5 runs):
1,382,351 branch-instructions:u ( +- 0.00% )
10,659 branch-misses:u # 0.77% of all branches ( +- 0.75% )
0.004709 +- 0.000558 seconds time elapsed ( +- 11.85% )
```
* `insert_ptp` 在 branch-instructions:u 還是 branch-misses:u 有些微的改善，但是不明顯
嘗試改用 [perf record & perf report](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial#perf-record-perf-report) 來分析
```shell
$ sudo perf record -F 100000 -e branch-misses:u,branch-instructions:u ./test
$ sudo perf report
```
* `insert`
```
333 branch-misses:u ◆
919 branch-instructions:u
```
```
Samples: 919 of event 'branch-instructions:u', Event count (approx.): 1386496
Overhead Command Shared Object Symbol
69.75% test test [.] insert
6.16% test libc-2.27.so [.] vfprintf
5.70% test libc-2.27.so [.] _IO_file_xsputn@@GLIBC_2.2.5
2.57% test libc-2.27.so [.] _int_malloc
```
```
Samples: 333 of event 'branch-misses:u', Event count (approx.): 11279
Overhead Command Shared Object Symbol
16.23% test libc-2.27.so [.] _dl_addr
12.54% test test [.] insert
11.38% test libc-2.27.so [.] printf
9.02% test libc-2.27.so [.] vfprintf
8.80% test libc-2.27.so [.] _IO_do_write@@GLIBC_2.2.5
7.87% test test [.] main
```
* `insert_ptp`
```
365 branch-misses:u ◆
947 branch-instructions:u
```
```
Samples: 947 of event 'branch-instructions:u', Event count (approx.): 1385333
Overhead Command Shared Object Symbol
72.25% test test [.] insert_ptp
7.83% test libc-2.27.so [.] vfprintf
3.23% test libc-2.27.so [.] _int_malloc
```
```
Samples: 365 of event 'branch-misses:u', Event count (approx.): 11535
Overhead Command Shared Object Symbol
17.59% test libc-2.27.so [.] _dl_addr
15.87% test test [.] main
14.58% test libc-2.27.so [.] _IO_file_xsputn@@GLIBC_2.2.5
11.35% test libc-2.27.so [.] _IO_file_write@@GLIBC_2.2.5
9.71% test libc-2.27.so [.] vfprintf
7.63% test libc-2.27.so [.] _IO_do_write@@GLIBC_2.2.5
5.21% test test [.] insert_ptp
```
* 從 branch-misses:u 的詳細報告就可以看出差異
* `insert` 造成的 branch-misses 占了 333 筆資料的 12.54%
* `insert_ptp` 造成的 branch-misses 占了 365 筆資料的 5.21%
###### tags: `linux 2020`
Sign in with Wallet
Connect another wallet