---
tags: 進階電腦系統理論與實作
---
# 2020q3 Homework6 (quiz6)
contributed by < `RinHizakura` >
> [第 6 週測驗題](https://hackmd.io/@sysprog/2020-quiz6#%E6%B8%AC%E9%A9%97-1)
> [GitHub](https://github.com/RinHizakura/NCKU-System-Software-Quiz/tree/master/quiz6)
## 測驗 `1`
### 程式原理
在理解 BFloat16 與 FP32 間的轉換方式前，先嘗試了解其推出的目的與價值。
> 以下內容取材自 [BFloat16: The secret to high performance on Cloud TPUs](https://cloud.google.com/blog/products/ai-machine-learning/bfloat16-the-secret-to-high-performance-on-cloud-tpus)
>
> 
> * BFloat16 的特點是相較於同為 16 bits 表示法的 FP16: IEEE half-precision 可以表示的範圍更大，可以用 16 bits 表示出與 FP32: IEEE single-precision 使用 32 bits 所能表示的相同範圍
> * 顯然這會導致精度(precision)的犧牲，但是因為在深度學習的應用中，一定的低精度是可以被容忍的([Suyog Gupta et al., 2015](https://arxiv.org/abs/1502.02551)、[Courbariaux et al., 2014](https://arxiv.org/abs/1412.7024))，模型往往可以在低精度的狀況下達到與使用原始精度相同的準確度(accuracy)，甚至還有可能更高([Choi et al., 2018](https://arxiv.org/abs/1809.00095))
> * BFloat16 與 FP32 之間的轉換十分簡單，兩者對於一般的數字、infinity、NaNs 的表示規範都相同，唯有 denormalize numbers 的處理比較不一樣，它們在 bfloat16 中會直接被 flush 成 0
> * 因此，受益於單筆資料使用的 bits 減少，硬體可提供更高的資料吞吐量 (throughput)
> * 另一方面，使用 BFloat16 可以減少相同模型架構下在 memory 中的數據大小，則如果在相同運算時間上作 trade-off，模型可以調整成更深、更寬、接受更大的輸入維度，而因此達到更高的準確度
> * 對於某些 memory-bandwidth-bound 的操作，BFloat16 也可以減少資料傳輸的數量，進而提升時間效率
回過來看程式內容：
```cpp
float fp32tobf16(float x) {
float y = x;
int *py = (int *) &y;
unsigned int exp, man;
exp = *py & 0x7F800000u;
man = *py & 0x007FFFFFu;
if (!exp && !man) /* zero */
return x;
if (exp == 0x7F800000u) /* infinity or NaN */
return x;
/* Normalized number. round to nearest */
float r = x;
int *pr = (int *) &r;
*pr &= BB1;
r /= 256;
y = x + r;
*py &= BB2;
return y;
}
```
* 在轉換前，首先對幾個特例做判斷
* `exp == 0` 且 `man == 0` 表示 x 代表的數字是零，不需額外處理
* 如前所述，對於 BFloat16 對於正負無限或者 NaN 的表示同 FP32(`exp == 0x7F800000u`)
* 接著，要把後 16 bit 截斷前，需要先判斷是否需要如何 rounding
* 取出 exponent 的部份，因此 `BB1 = 0x7f800000`
* 判斷此部份是 `>= 256`，表示截斷的部份是 $0.XXX \times 2^E, E >= 1$，還是 `< 256`，表示截斷的部份是 $0.XXXX \times 2^E, E <= 0$，決定是否要進位到 bfloat16 表示的 fraction 中
* 最後，捨棄後面的 16 bits，因此 `BB2 = (e) 0xffff0000`
## 測驗 `2`
### 程式原理
首先先進行必要的初始化。
* `RINGBUF_DECL(int, int_buf)` 初始化一個名為 `int_buf`，元素為 int 的 ring buffer
* `RINGBUF_INIT(my_buf, 2, int)` 初始化 `my_buf`，配置 stack 空間中 `2 + 1 * sizeof(int)` 的陣列空間，並使 my_buf.elements 指向此空間的開頭
* 需加上 `static` 關鍵字，才能確保離開 scope 時 `static_ringbuf_mem` 仍在 lifetime 中！
* 則第 9 行判斷是否為空，實際是判斷 start 是否等於 end，因為初始時都為 0，所以應當可以通過
```cpp
#define NEXT_START_INDEX(BUF) \
(((BUF)->start != (BUF)->size) ? ((BUF)->start + RB1) : 0)
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0)
#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]
#define ringbuf_write_skip(BUF) \
do { \
(BUF)->end = NEXT_END_INDEX(BUF); \
if (is_ringbuf_empty(BUF)) \
(BUF)->start = NEXT_START_INDEX(BUF); \
} while (0)
#define ringbuf_write(BUF, ELEMENT) \
do { \
ringbuf_write_peek(BUF) = ELEMENT; \
ringbuf_write_skip(BUF); \
} while (0)
```
接下來細究 `ringbuf_write` 的行為。
* `ringbuf_write_peek` 先將 `BUF->end` 位置的元素 assign 成 `ELEMENT`
* `ringbuf_write_skip` 先透過 `NEXT_END_INDEX` 判斷 `BUF->end` 是否已經在 `BUF->size`，如果是下次寫的時候就要回到 0 重新開始，否則就是寫下一個位置，因此 `RB1 = (a) 1`
* 在寫的同時，如果會覆蓋到 `start` 所在的位置，則需要把 `start` 往後推讓其變成正確的覆蓋，因此 `NEXT_START_INDEX` 和 `NEXT_END_INDEX` 是相同概念，`RB2 = (a) 1`
:::success
如果理解的沒錯的話，`ringbuf_write_skip` 應該等同下面的寫法，私心覺得會比較符合思考的邏輯 XD
```cpp
#define ringbuf_write_skip(BUF) \
do { \
if(is_ringbuf_full(BUF)) \
(BUF)->start = NEXT_START_INDEX(BUF); \
(BUF)->end = NEXT_END_INDEX(BUF); \
} while (0)
```
:::
對應的 `ringbuf_read` 的作法。
```cpp
#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);
#define ringbuf_read(BUF, ELEMENT) \
do { \
ELEMENT = ringbuf_read_peek(BUF); \
ringbuf_read_skip(BUF); \
} while (0)
```
* 讀出 `BUF->start` 位置的元素
* 並把 `BUF->start` 往下一個 index 更新
### `do { ... } while (0)` 的考量
舉個例子來說明：
```cpp
#include <stdio.h>
#define add_two_num(x,y) x++;y++
int main(void)
{
int a = 0, b = 100;
if(a == b)
add_two_num(a,b);
printf("%d %d\n",a,b);
return 0;
}
```
考慮上面的程式，我們預期會印出 `0 100`，因為 `a != b`。但其實結果並非如此，如果我們把 macro 展開，寫成不會被誤會的方式，其實同等的程式會如以下所示:
```cpp
#include <stdio.h>
#define add_two_num(x,y) x++;y++
int main(void)
{
int a = 0, b = 100;
if(a == b)
a++;
b++;
printf("%d %d\n",a,b);
return 0;
}
```
因為 `add_two_num` 沒有使用 scope，導致展開後只有 `a++` 是跟著前面的 `if` ，`b++` 自己成為了獨立的 statement。
那如果我們在 macro 中加上 scope 不就沒問題了嗎?
```cpp
#define add_two_num(x,y) {x++;y++;}
```
注意到此時我們會需要在 `y++` 後面加上分號才能使程式成立，然而在下面的狀況下：
```cpp
if(a == b)
add_two_num(a,b);
else
...
```
程式就會無法通過編譯了，因為 else 會找不到自己搭配的 if 是誰。因此，我們必須要修改成：
```cpp
#define add_two_num(x,y) do{x++;y++;}while(0)
```
從而得到使用彈性更高的 macro。
## Super Fast Circular Ring Buffer
### memcpy write
前面的題目中，我們看到了基本的 ring buffer 實作。題中，我們對 buffer 的寫入是逐個元素運行的。考慮到執行效率，我們可以善用 `memcpy`，一次寫入多個元素，如下實作
```cpp
#define min(a, b) (a) > (b) ? (b) : (a)
#define ringbuf_write_many(BUF, SRC, SRC_SIZE) \
do { \
size_t part1 = min(SRC_SIZE, ((BUF)->size - (BUF)->end)); \
size_t part1_sz = part1 * sizeof((BUF)->elements[0]); \
size_t part2_sz = SRC_SIZE * sizeof((BUF)->elements[0]) - part1_sz; \
memcpy((BUF)->elements + (BUF)->end, SRC, part1_sz); \
memcpy((BUF)->elements, SRC + part1, part2_sz); \
(BUF)->end = ((BUF)->end + SRC_SIZE) % (BUF)->size; \
} while (0);
/* Use this like:
*
* int tmp[5] = {1, 2, 3, 4, 5};
* ringbuf_write_many(&my_buf, tmp, 5);
*
*/
```
第一個 `memcpy` 計算從 `BUF->END` 到 `BUF->SIZE` 的空間，複製 `SRC` 進入 buffer，如果此段空間不足以容納整個 `SRC`，則從開頭再將溢出的部份補足。
### Virtual memory trick
根據 [Super Fast Circular Ring Buffer Using Virtual Memory trick](https://medium.com/@abhinavagarwal1996/a-fast-circular-ring-buffer-4d102ef4d4a3) 與 [enordstrm/ring_buffer](https://github.com/enordstrm/ring_buffer)，我們可以對 ring buffer 進行以下的調整。
```cpp=
#define FAIL -1
RINGBUF_DECL(int, int_buf);
int create_ring_buf(int_buf *buffer, size_t size, size_t type_size)
{
void *address;
const size_t pagesize = getpagesize();
/* adjust size to a closely and suitable one */
size = (ceil((float) (size * type_size) / pagesize) * pagesize) / type_size;
const int fd = fileno(tmpfile());
if (fd == -1)
return FAIL;
if (ftruncate(fd, type_size * size))
return FAIL;
buffer->elements = mmap(NULL, 2 * type_size * size, PROT_NONE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (buffer->elements == MAP_FAILED)
return FAIL;
address = mmap(buffer->elements, type_size * size, PROT_READ | PROT_WRITE,
MAP_SHARED | MAP_FIXED, fd, 0);
if (address != buffer->elements)
return FAIL;
address = mmap(buffer->elements + size, type_size * size,
PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, fd, 0);
if (address != buffer->elements + size)
return FAIL;
if (close(fd))
return FAIL;
return size;
}
#define RINGBUF_INIT(BUF, S, T) \
do { \
int size = create_ring_buf(&BUF, S, sizeof(T)); \
assert(size != FAIL); \
printf("Init buffer to size %d\n", size); \
BUF.size = size; \
BUF.start = 0; \
BUF.end = 0; \
} while (0);
/* So you can init like:
*
* int_buf my_buf;
* RINGBUF_INIT(my_buf, 1024, int);
*/
```
* 初始化的 buffer 大小必須要是 pagesize 的倍數，否則 `mmap` 會失敗，因此第 8 行會對此調整至滿足條件
* [tmpfile](https://man7.org/linux/man-pages/man3/tmpfile.3.html) 會建立一個暫時的檔案，這是為了建立一個可以映射到 physical memory 的介質
> **DESCRIPTION**
> The tmpfile() function opens a unique temporary file in binary read/write (w+b) mode. The file will be automatically deleted when it is closed or the program terminates.
* 因為 tmpfile 回傳的是一個 stream descriptor(`FILE *`)，需透過 [fileno](https://linux.die.net/man/3/fileno) 轉而得到其 file descriptor
* [ftruncate](https://linux.die.net/man/2/ftruncate) 將檔案調整成指定的大小，對應我們需要的實際記憶體空間
* 第 11 行透過 [mmap](https://man7.org/linux/man-pages/man2/mmap.2.html) 的參數 `MAP_ANONYMOUS` 要到一段匿名的 virtual address
* 第 23 行將這段 virtual address 的前半部份 mapping 到前面建立的 temporary file
* 第 29 行將這段 virtual address 的後半部份 mapping 到前面建立的 temporary file
:::warning
`create_ring_buf` 因為型別的原因不能使用在其他 `RINGBUF_DECL` 定義出的 ring buffer，是可以思考並改進的地方
:::
最後，我們相當於是得到了兩段 virtual address，mapping 到同一段 physical address 上。因此，我們就可以實作出在 physical memory 上循環的效果。受益於此，`memcpy` 可以一次完成，不需要在超出範圍時分成兩段進行:
```cpp
#define ringbuf_write_many(BUF, SRC, SRC_SIZE) \
do { \
memcpy((BUF)->elements + (BUF)->end, SRC, \
SRC_SIZE * sizeof((BUF)->elements[0])); \
(BUF)->end = ((BUF)->end + SRC_SIZE) % (BUF)->size; \
} while (0);
```
:::info
註: 假設 `ringbuf_write_many` 的 `SRC_SIZE` 不會超過 `(BUF)->size`
:::
則我們可以做簡單的實驗來觀察是否確實可行:
```cpp
int main()
{
int_buf my_buf;
RINGBUF_INIT(my_buf, 1024, int);
int tmp[1000];
for (int i = 0; i < 1000; i++)
tmp[i] = i;
ringbuf_write_many(&my_buf, tmp, 1000);
ringbuf_write_many(&my_buf, tmp, 30);
for (int i = 0; i < 10; i++) {
int read;
ringbuf_read(&my_buf, read);
printf("%d, ", read);
}
printf("\n");
return 0;
}
```
對應的輸出為:
```
Init buffer to size 1024
24, 25, 26, 27, 28, 29, 6, 7, 8, 9,
```
### VIPT cache
雖然前面的作法看似很理想，實際上我們可能需要小心在 cache 上的問題。
在大部分的處理器中，會採用 **Virtual address, physical cache(VIPT)** (可對照 [Address translation](https://en.wikipedia.org/wiki/CPU_cache#Address_translation)) 的位址轉換，其好處是可以折衷 **Virtually indexed, virtually tagged (VIVT)** 不需轉換，因此速度比較快的好處，以及 **Physically indexed, physically tagged(PIPT)** 不必每次 context switch 就 flush 的優勢。
雖然 VIPT 在轉換的過程中，也需要透過 MMU 來進行的位址的轉換，但在為了得到 tag 把 virtual address 轉成 physical address 的過程中，可以先用 virtual address 的 index 去找對應的 cache block，等轉換完再用 tag 去看是否 hit。
> 圖源: [Page Colouring on ARMv6 (and a bit on ARMv7)](https://community.arm.com/developer/ip-products/processors/b/processors-ip-blog/posts/page-colouring-on-armv6-and-a-bit-on-armv7)
但是 VIPT 存在 aliasing 問題，如上圖，灰色的部份是 page offset + byte index。可以看到，如果 cache line index 中包含 virtual address 的 page 和 offset 的各一部份，這表示在 MMU translation 階段與 cache line index 去對應 cache 階段的位置出現重疊。因此，當兩個不同的 virtual address 對應相同的 physical address 時，有可能會對應到不同的 cache line，如此一來，就可能會導致相同的記憶體資料在 cache 上的不一致。
為避免此問題，硬體上解決手段是: 製造商需要確保對 cache 的 index bit 皆來自 page offset，則因為 virtual page 和 physical page 的 offset 會相同，因此就可以對應在相同的 cache 位置上，避免 aliasing 的問題導致資料不一致的問題。在軟體中的解決方案則可能可以透過如 [Cache coloring](https://en.wikipedia.org/wiki/Cache_coloring) 的作法來避免。
:::danger
有一些不確定的地方待釐清:
* 在 [How does the VIPT to PIPT conversion work on L1->L2 eviction](https://stackoverflow.com/questions/55387857/how-does-the-vipt-to-pipt-conversion-work-on-l1-l2-eviction) 看到如下說法，也就是前面提到的硬體層面避免 cache aliasing 的手法。但是沒有找到比較正式的文件，不確定其可靠程度？
> In Intel CPUs, the VIPT L1 caches have all the index bits from the offset-within-page part of the address, so virt=phys, avoiding any aliasing problems. It's basically PIPT but still being able to fetch data/tags from the set in parallel with the TLB lookup for the pagenumber bits to create an input for the tag comparator.
* aliasing 既然有軟體的解法，則應該是表示硬體不一定會保證 aliasing 不會發生?([Page Colouring on ARMv6 (and a bit on ARMv7)](https://community.arm.com/developer/ip-products/processors/b/processors-ip-blog/posts/page-colouring-on-armv6-and-a-bit-on-armv7) 有提及根據硬體不同會有差異)
* 若是如此，是否需要檢驗此實作在不同硬體下的正確性？該如何檢驗？
:::
### 時間比較
比較通過 Virtual memory trick 加速的效果，實驗中比較兩個可以容納 1024 個 int 元素的 buffer，一個是使用原題目的 buffer 設計，並且利用 [memcpy write](#memcpy-write) 章節的 `ringbuf_write_many` 做寫入，另一個則是根據 [Virtual memory trick](#Virtual-memory-trick) 的設計寫入 buffer。每次實驗都向其中寫入 900 個元素，總共寫入 1000 次。如此設計實驗的目的是為了讓每次寫入都可以儘量溢出(需要從頭寫起)，因為我認為這是 virtual memory trick 可以展現其優勢的地方。
:::warning
實驗時要注意到 virtual memory trick 第一個及少數樣本點的寫入時需要比較多的時間(不知道是不是跟初始化時的 demand paging 有關?需要相關實驗確認)。所以需要排除這些 noise 不予以參考。
:::
從圖中可以看到使用 virtual memory trick 可以得到較短的時間。
另一個實驗中，比較兩個可以容納 1024 個 int 元素的 buffer，且每次實驗都僅向其中寫入 10 個元素，總共寫入 1000 次。經計算這只會有 8 次的溢出(需要從頭寫入)，但從以下的實驗結果來看，即使是這種情境下，virtual memory trick 的所需時間仍然較少。
因為在不溢出的情形下，normal ring buf 第二個 memcpy 應該是沒有作用的，因此不會有時間成本，所以不確定這種情境下 virtual memory trick 方法還是可以表現較佳的原因。不過可以知道的是，通過 virtual memory trick，確實在寫入的時間上可以得到較佳的結果。
## 測驗 `3`
### 程式原理
首先，先來關注程式中的 macro `cons`
```cpp
#define cons(x, y) (struct llist[]){{y, x}}
struct llist {
int val;
struct llist *next;
};
```
在 `cons` 中使用了 **compound literal** 的技巧，根據 C 語言規格書 **6.5.2.5 Compound literal**：
> A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.
在括號(`()`)中為型別名稱，並接續 braces(`{}`) 中的初始化 list 會行成一個 compound literal。這讓我們可以定義一個匿名的物件，並指派給某一變數或者作為 function 的參數使用。
> If the type name specifies an array of unknown size, the size is determined by the initializer list as specified in 6.7.8, and the type of the compound literal is that of the completed array type. Otherwise (when the type name specifies an object type), the type of the compound literal is that specified by the type name.
由此可知，每個 `cons` 建立的是一個單元素的 `struct llist` array，`val` 指派為 y，`next` 指派為 x。
再回顧原程式:
```cpp
struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);
```
最裡面的 `cons(NULL,A)` 首先建立了一個值為 A，`next` 指向 NULL 的 `struct llist` 空間。則往外層的 `cons(cons(NULL, A), B)`，就等於建立了一個值為 B，`next` 指向值為 A 的那個 `struct llist` 空間的 `struct llist`。則依此邏輯推理，我們知道最後的 `*list` 應該要像：
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
NULL[label=NULL,shape=plaintext]
D->C->B->A->NULL
}
```
對應預期的輸出結果是 9547，則我們知道 `A = (d)7`、`B = (c)4`、`C = (b)5`、`D = (a)9`。
接下來，從預期的輸出要是 4579，我們知道 `sort` 的作用是把 linked list 做排序，由小排到大，如果從函式名稱也可以猜到是要做 insertion sort。我們知道 insertion sort 的原理可以想成是把原始序列中的數字一一挑出來，並放到新序列的正確位置中。由此想法，下面說明對 linked list 進行排序的方式：
* 首先，我們的原始 linked list 為
```graphviz
digraph graphname{
node[shape=box]
rankdir=LR
NULL[label=NULL,shape=plaintext]
9->5->4->7->NULL
}
```
* `sorted` 會作為排序結果 linked list 的 head，首先初始為 NULL
* `current` 從第一個開始往下前進，而 `next` 會指向 `current` 的下個節點
* 則 for 迴圈的第一個 iteration 中，`sorted_insert` 會判斷出 `!*head` 為 True，因此先把 9 當成排序 linked list 的 head，圖中黃色的節點代表已經排序好的部份
```graphviz
digraph graphname{
node[shape=box]
sorted[shape=plaintext,fontcolor=red]
current[shape=plaintext,fontcolor=blue]
next[shape=plaintext,fontcolor=blue]
rankdir=LR
nine[label="9",style=filled,fillcolor=yellow]
NULL[label=NULL,shape=plaintext]
{
rank="same";
sorted->nine
current->nine
}
{
rank="same";
next->5
}
nine->5->4->7->NULL
}
```
* 下個迴圈，走到 5，`sorted_insert` 會判斷出 `(*head)->val >= node->val`，也就是排序好的部份 head 已經大於新插入節點，因此 5 指向 9 ，並將 `sorted` 更新到 5
```graphviz
digraph graphname{
node[shape=box]
sorted[shape=plaintext,fontcolor=red]
rankdir=LR
current[shape=plaintext,fontcolor=blue]
next[shape=plaintext,fontcolor=blue]
nine[label="9",style=filled,fillcolor=yellow]
five[label="5",style=filled,fillcolor=yellow]
NULL[label=NULL,shape=plaintext]
{
rank="same";
sorted->five
current->five
}
{
rank="same";
next->4
}
five->nine->4->7->NULL
}
```
* 下個 iteration，與前一個情形同理，因此變成
```graphviz
digraph graphname{
node[shape=box]
sorted[shape=plaintext,fontcolor=red]
rankdir=LR
current[shape=plaintext,fontcolor=blue]
next[shape=plaintext,fontcolor=blue]
nine[label="9",style=filled,fillcolor=yellow]
five[label="5",style=filled,fillcolor=yellow]
four[label="4",style=filled,fillcolor=yellow]
NULL[label=NULL,shape=plaintext]
{
rank="same";
sorted->four
current->four
}
{
rank="same";
next->7
}
four->five->nine->7->NULL
}
```
* 最後處理 7，在排序好的 linked list 中找到適合的位置，並將其插入
```graphviz
digraph graphname{
node[shape=box]
sorted[shape=plaintext,fontcolor=red]
rankdir=LR
current[shape=plaintext,fontcolor=blue]
next[shape=plaintext,fontcolor=blue]
nine[label="9",style=filled,fillcolor=yellow]
five[label="5",style=filled,fillcolor=yellow]
four[label="4",style=filled,fillcolor=yellow]
seven[label="7",style=filled,fillcolor=yellow]
NULL[label=NULL,shape=plaintext]
{
rank="same";
current->seven
}
{
rank="same";
next->NULL
}
{
rank="same"
sorted->four
}
four->five->seven->nine->NULL
}
```
最後，`sorted` 指向的 linked list 就是排序好的結果。由以上程式邏輯我們可以知道 `SS1 = (d) node->next = *head`、`SS2 = (b) *head = node`。
### [148. Sort List](https://leetcode.com/problems/sort-list/)
#### solution `1`
考慮最直覺的實作為使用 merge sort:
> 參考 [Merge Sort Algorithm for Singly Linked List](https://www.techiedelight.com/merge-sort-singly-linked-list/) 做了些許調整
```cpp
struct ListNode *SortedMerge(struct ListNode *a, struct ListNode *b)
{
struct ListNode dummy;
struct ListNode *tail = &dummy;
dummy.next = NULL;
while (1) {
if (a == NULL) {
tail->next = b;
break;
} else if (b == NULL) {
tail->next = a;
break;
}
if (a->val > b->val) {
tail->next = b;
b = b->next;
} else {
tail->next = a;
a = a->next;
}
tail = tail->next;
}
return dummy.next;
}
void FrontBackSplit(struct ListNode *src,
struct ListNode **front,
struct ListNode **back)
{
if (src == NULL || src->next == NULL) {
*front = src;
*back = NULL;
return;
}
struct ListNode *slow = src;
struct ListNode *fast = src->next;
while (fast != NULL) {
fast = fast->next;
if (fast) {
slow = slow->next;
fast = fast->next;
}
}
*front = src;
*back = slow->next;
slow->next = NULL;
}
struct ListNode *sortList(struct ListNode *head)
{
if (head == NULL || (head)->next == NULL)
return head;
struct ListNode *a;
struct ListNode *b;
FrontBackSplit(head, &a, &b);
a = sortList(a);
b = sortList(b);
return SortedMerge(a, b);
}
```
* `sortList` 中先透過 `FrontBackSplit`，將原始 linked-list 從中間切開成 `a` 和 `b`
* 遞迴呼叫 `sortList` 遞迴將所有的節點切成獨立後，再利用 `SortedMerge` bottom up 將節點 merge 回排序好的樣貌
* `SortedMerge` 中為經典的 merge 操作：因為 `a` 和 `b` 應為已經排序好的 linked list，因此歷循兩個 linked-list 把最小的 node 挑出來接在新的 head (`dummy`) 之下即可
則在 leetcode 上提交之結果如下圖:
#### solution `2`: [Optimizing merge sort](https://en.wikipedia.org/wiki/Merge_sort#Optimizing_merge_sort)
在上面的 merge sort 中，會先把 linked list 切成單一個節點，再一個個合併，這可能會導致 locality 不佳。一種最佳化的方式是文中提到的 tiled merge sort，當分割到 linked list 為 `S` 大小時便不再分割，`S` 是節點的資料結構可以納入 cache 的總量。則可以先透過可以 in-place 的排序演算法（insertion sort / bubble sort）進行排序後，減少在記憶體內交換特定區域的次數，再以典型的 merge sort 完成剩下的部份。實作的方法如下所示：
```cpp
void sorted_insert(struct ListNode **head, struct ListNode *node)
{
if (!*head || (*head)->val >= node->val) {
node->next = *head;
*head = node;
return;
}
struct ListNode *current = *head;
while (current->next && current->next->val < node->val)
current = current->next;
node->next = current->next;
current->next = node;
}
struct ListNode *insertion_sort(struct ListNode *head){
struct ListNode *sorted = NULL;
for(struct ListNode *cur = head; cur; ){
struct ListNode *next = cur->next;
sorted_insert(&sorted, cur);
cur = next;
}
return sorted;
}
#define THR 64
struct ListNode *tiled_sortList(struct ListNode *head, int cnt)
{
if (head == NULL || (head)->next == NULL)
return head;
struct ListNode *a;
struct ListNode *b;
FrontBackSplit(head, &a, &b);
if((cnt >> 1) < THR) {
a = insertion_sort(a);
b = insertion_sort(b);
} else{
a = tiled_sortList(a, (cnt >> 1) + (cnt & 1));
b = tiled_sortList(b, (cnt >> 1));
}
return SortedMerge(a, b);
}
struct ListNode *sortList(struct ListNode *head){
int cnt = 0;
struct ListNode *tmp = head;
while (head != NULL) {
cnt ++;
head = head->next;
}
return tiled_sortList(tmp, cnt);
}
```
幾個值得關注的點：
* 可以看到我們借用原題目的作法來實作 insertion sort
* `sortList` 首先需要求出 linked-list 的長度，做為後續判斷要採用 insertion sort 還是 merge sort 的依據
:::info
完整的實作請參考 [sort_list.c](https://github.com/RinHizakura/NCKU-System-Software-Quiz6/blob/master/sort_list.c)
:::
為了達到 tiled sort 的理想效果，需要調整 `THR` 使 insertion sort 目標的 linked list 符合 L1 cache size 範圍。`struct ListNode` 內含一個 `int` 和一個 pointer，因此其大小應為 4 + 8 = 12bytes，但考慮到 64 位元的電腦上 alignment 應該會變成 16 bytes。檢視我的 cache size:
```
$ lscpu -C
NAME ONE-SIZE ALL-SIZE WAYS TYPE LEVEL
L1d 32K 128K 8 Data 1
L1i 32K 128K 8 Instruction 1
L2 256K 1M 4 Unified 2
L3 8M 8M 16 Unified 3
```
則經計算應該要容納 32k / 16 = 2k 個節點，但是考慮到其他變數也會佔用 cache 空間，因此進行實驗觀察 `THR` 對執行時間的影響。
為確保 cache 的使用儘量不受影響，參照以前的方法使用 [isolcpus](https://www.suse.com/support/kb/doc/?id=000017747) 搭配 taskset 來做實驗。針對一個 5000 個節點的 linked-list(每次實驗都是隨機的) 進行不同 threshold 的 tiled sort，得到的結果如下。注意到紅線是 THR = 0 時的時間，也就是完全使用 merge sort 時所需時間。
從圖可以看到，THR 在大概 49 - 78 之間時間最佳。注意到圖形的階梯狀是因為 linked list 的大小固定，而 merge sort 總是把 linked list 對半分，因此 merge sort 中可能會出現的長度只會是 `5000 -> 2500 -> 1250 -> 625 -> 312 -> 156 -> 78 -> 49 ......` 。由此可以推斷在 S = 49 ~ 78 的區間是使用 insertion sort 較佳的地方。因此選擇 64 作為最終的 threshold。
不過在 leetcode 上提交的結果如下，時間看起來沒有甚麼差異:
則測試在不同數量節點下的執行時間，可以看出些許的進步。
### 補充說明
對照 [eecheng87/quiz3](https://hackmd.io/@eecheng/ryqwNCoVI) 共筆發現可能造成誤會的結論，剛好這個作業曾經偷偷寫過XD，特此提出討論：
對於同學實驗中的這張圖，同學的結論提到
> 把 insertion sort 融合到 merge sort 可以快上數百倍（實際上的數字是，優化的 merge sort 排序十萬個點只需要 1~2 ms）
但開始時有些疑惑在實驗設定的 10000 個節點下為何 merge sort 展現如此差勁的效能(500 ms，甚至劣於 insertion sort)。檢視了同學的程式碼後，如果沒有誤會，其 `optimize merge sort` 所指應該不只作 tiled sort 的優化，還包含了對 merge sort 分割方式的調整(即我程式中的 `FrontBackSplit`)。而後者其實才是導致效能提升的關鍵，如下圖是我之前實驗的結果：
可以看到對 linked-list 的切割方式差異會導致時間大幅的不同。
因此，我認為同學實驗中的時間差異主要是來自切割 linked-list 的方法而產生進步，雖然我實驗的結果中 tiled sort 的確也可以提升時間效率，但應該不至於如同學所說「 把 insertion sort 融合到 merge sort 可以快上數百倍」？
陸續再檢查是否有誤會之處。
## 測驗 `4`
### 程式原理
首先，`const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);` 是在判斷 `numsSize` 最少需要多少 bits 表示(例如 $numsSize = 12_{dec} = 0b1100$，則會得到 `log_2` = 4)。
接下來，探究題目的原理。從題目的說明我們可以知道：對於 `n` 大小的陣列，數字的範圍是 `1` 到 `n-1`，且重複的只有一個，因此我們可以從 bit 的角度去思考此題的作法。
舉例來說，假設陣列大小為 `4`，則從如果從 0 放到 3 的話
| num | bit1 | bit0 |
| --- | ---- | ---- |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
則我們可以預期 bit1 應該出現的 1 總量為 2，bit0 應該要出現的 0 總量也為 2，這對應 `if (k & bit)++c1;` 的計算。
然後，因為陣列會有一個元素重複，因此可以想成這個重複會取代 0 的存在。
| num | bit1 | bit0 |
| --- | ---- | ---- |
| 2 | 1 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
可以看到，則 bit1 的 1 數量超出，因此我們知道重複數字的 bit1 為 1，而 bit0 的數量則符合預期，因此重複數字的 bit0 為 0，則推理出題解為 $0b10 = 2_{dec}$。因此 `CCC = (b) c1 < c2`。
附上 leetcode 上測試正確的結果：
#### 其他解法
第一眼見到這一題的時候，首先想到的解法其實是用之前曾經解過的 [41. First Missing Positive 的解法](https://hackmd.io/@RinHizakura/SkjPS8vBP#41-First-Missing-Positive)相同的邏輯去思考: 把數字 1 放在 array index 1 的位置、數字 2 放在 array index 2 的位置，以此類推。放在該位置之前，如果檢查得知位置上已經是其應該有的數值了，就表示目前正在處理的數值是重複的。程式碼如下:
```cpp
#define XORSWAP_UNSAFE(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
int find(int *nums, int numsSize)
{
for (int i = 0; i < numsSize; i++) {
if (nums[i] != i) {
if (nums[nums[i]] == nums[i]) {
return nums[i];
} else {
int index = nums[i];
XORSWAP_UNSAFE(nums[i], nums[index]);
i--;
}
}
}
return -1;
}
```
如果測資符合題意，則最後一個 return 不該被執行到。附上 leetcode 上測試正確的結果：
Sign in with Wallet
Connect another wallet