# 2024-03-{05,07,12} 問答紀錄

## vax-r
> [lab0](https://hackmd.io/@vax-r/linux2024-homework1)

整合網頁伺服器與 linenoise 套件:

## 測驗一的程式 while 如何進行優化
> Jimmy01240397

舉例一：
假設 $2^{19} + 1$ 的情況 msb 會是 19
在 while 迴圈內的 a （$2^{msb}$）的數值降到 $2^{9}$ 之前 while 內的 if 都不會成立因為
$(result(0) + 2^{10}) * (result(0) + 2^{10}) > N$ 也就是 $2^{20} > 2^{19} + 1$
$(result(0) + 2^{9}) * (result(0) + 2^{9}) <= N$ 也就是 $2^{18} <= 2^{19} + 1$
由於 $19 / 2 = 9$ 因此可以在進 while 之前先 $msb / 2$

舉例二：
假設 $2^{20} + 1$ 的情況 msb 會是 20
$(result(0) + 2^{11}) * (result(0) + 2^{11}) > N$ 也就是 $2^{22} > 2^{20} + 1$
$(result(0) + 2^{10}) * (result(0) + 2^{10}) <= N$ 也就是 $2^{20} <= 2^{20} + 1$
$20/2 = 10$

舉例三：
假設 $2^{20}$ 的情況 msb 會是 20
$(result(0) + 2^{11}) * (result(0) + 2^{11}) > N$ 也就是 $2^{22} > 2^{20}$
$(result(0) + 2^{10}) * (result(0) + 2^{10}) <= N$ 也就是 $2^{20} <= 2^{20}$
$20/2 = 10$

## 解釋為何測驗二程式相等
> Brucelee503jo3

## 客製化的測驗題
* 學號: P7???07 $\to$ [測驗題](https://hackmd.io/0MoP3JV1SqyjCbR-dO9OnA)
<s>
* 學號: NM?????54 $\to$ [測驗題](https://hackmd.io/xi1l3Ty1TcC3MJN5b4Geng)
* 學號: P76?0??02 $\to$ [測驗題](https://hackmd.io/JLFF13wRRIWjWMFlrZFyuw)
</s>

## 為什麼要加入 `& ~1UL` 來代表 log(x)
> [PochariChun](https://github.com/PochariChun/lab0-c)

為什麼要加入 `& ~1UL` ?

m = 1UL << ((31 - __builtin_clz(x))  & ~1UL);

而不是單純使用底下形式來表示最高位元呢？

m = 1UL << (31 - __builtin_clz(x)) ;

> 注意 `& ~1UL` 會 clear 最低位，例如前者在 `x = 2` 時結果為 `1`，後者則是 `2`。
> [name=lumynou5]

## brucelee503jo3
> 經驗分享
> $\to$ [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)

## weihsinyeh
> [`lib/list_sort.c` 分析](https://hackmd.io/@weihsinyeh/ry2RWmNTT)

## yeh-sudo
> [快速排序的實作評估](https://hackmd.io/@yehsudo/linux2024-homework2)

- [ ] 使用一般陣列與鏈結串列的差別？

使用一般陣列可以直接存取，成本較低，不需要像鏈結串列一樣，要實際走訪才能存取其中的元素，成本較高，所以今天如果是相同的排序演算法，使用陣列的效能可能會比鏈結串列要好。

- [ ] 合併排序法與快速排序法，哪一種的 [locality](https://en.wikipedia.org/wiki/Locality_of_reference) 較好？

一般的合併排序法在合併時，都是兩兩元素比較，容易將 cache 中的元素置換掉，導致 [cache thrashing](https://en.wikipedia.org/wiki/Thrashing_(computer_science)) ，而在快速排序法中，雖然與合併排序一樣，都是進行分割，但是在分割合併的時候，都是全部的元素在與一個 `pivot` 進行比較，所以 locality 較好，因此，為了降低 cache thrashing ，才出現了 lib/list_sort.c 這樣的改良版合併排序法。

- [ ] 用 gnuplot 製圖，為何執行時間的落點無法像教科書圖例平滑且純淨？

在執行測試中，會受到許多環境因素影響：
* 作業系統
我們的作業系統中，都會有一個 timer 去幫助 CPU 進行排程，為了避免 [starvation](https://en.wikipedia.org/wiki/Starvation_(computer_science)) ，計時器會發出一個訊號，將原本的測試中斷，會造成測量的結果不準確。
* 次要分頁錯誤 ( [Minor Page Fault](https://en.wikipedia.org/wiki/Page_fault) )
一個次要分頁錯誤會需要很多 CPU cycle 去處理，只要這個情況頻繁發生，就會影響到測試的效能。
* 網路
舉例，電腦上開著通訊軟體，當有人傳訊息給自己時， CPU 必須要接收並且處理這些封包，就算今天沒有通訊軟體的運作，也會有 APR 的廣播封包傳輸到電腦上， CPU 也一定要處理這些封包，沒辦法不管。

- [ ] 如何產生符合 Timsort 的測試資料？

使用 lab0-c 的 shuffle 產生，完成作業要求的亂數研究。