版本 798beb811a053d62d03e0762ccb0b7b246cb4bb3

User/yushiuan9499

Changes from 798beb811a053d62d03e0762ccb0b7b246cb4bb3 to 8383f61663d189f6c2cf5ebb01213a4f9c1c515c

# 2026 年 Linux 核心設計課程自我評量
姓名：宋昱宣  
Github 帳號：[yushiuan9499](https://github.com/yushiuan9499/)

## 成果發表與貢獻
> ? 分

本學期內只有貢獻教材以及對教材相關的 Repo 發兩個尚未合併的 PR ，屬於方案 B。  
### Github PR
- [Switch to log2 with table lookup and interpolation](https://github.com/sysprog21/kxo/pull/31)，尚未 merge  
    [相關筆記](https://hackmd.io/pIQ09u_pQU-LoyvJGHBrqg)  
    2026/05/05 在閱讀 kxo 教材時，看到 `fixed_log()` 在輸入遠離 1 時會有較大的誤差。我使用公式 $\log_2(M*2^N) = N + \log_2(M)$ 與差值法將誤差控制在至多 $2^{-19}$ 之內（考量到 rounding 誤差則是 $2^{-17}$ ），並讓執行速度提昇 20 倍。於 5/11 發 PR 至上游。  
    
- [Fix sibling selection logic](https://github.com/CMemeletzoglou/False_Sharing/pull/1)，尚未 merge
    在實驗〈[並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics#cache-coherence-%E5%B0%8D%E7%A8%8B%E5%BC%8F%E6%95%88%E8%83%BD%E7%9A%84%E8%A1%9D%E6%93%8A)〉的 false_sharing.c 時頻繁遇到 Segment fault ，發現是我的筆電 CPU 並非每個核都有 SMT ，使解析 CPU topology 時異常。於 06/02 發 PR 至上游  


### 改進教材內容
- 2026/03/14：將〈[從 √2 的存在談開平方根的快速運算-固定點定理](https://hackmd.io/HUzAPdVVSACpsnaj5Omvgw#%E5%9B%BA%E5%AE%9A%E9%BB%9E%E5%AE%9A%E7%90%86)〉中的證明改成直接以微分定義出發，並使前提的要求更少。  

### 修正教材
- 2026/04/14：〈[歐拉數 e: 描述連續變化的基石-泊松分佈](https://hackmd.io/Klv5TiUUSHKnCCMeVcnIIw#%E6%B3%8A%E6%9D%BE%E5%88%86%E4%BD%88)〉中有一段證明的文字描述少了「減去 $P(t)$」的步驟，將其補上  
- 2026/05/15：〈[你所不知道的 C 語言: 浮點數運算](https://hackmd.io/tbHqxe19SdafIq0XdBnJzQ#)〉提到  
     > 因為分數的數量是不可數的
 
     然而分數，也就是有理數，是可數的（利用互質形式的 $p/q$ 映射到 $(\text{p-th prime})^q$ 這個概念可證明有理數不比整數多）。文中想要表示的概念應為任意有限精度的浮點數，其 ULP 之間一定存在一個有理數無法被表示，此為數學的稠密性。  
- 2026/06/04：發現 〈[kxo-定點數平方根](https://hackmd.io/vauBAFkSToyAr9MbJicgyg#)〉中的實作已經提前回傳輸入是 0 的狀況，因此不必額外執行 `x | 1` 的運算，並修改教材。  

### 修錯字
- 2026/03/08：〈[你所不知道的 C 語言：數值系統](https://hackmd.io/eSVH5k6SQ7OrzZ5cT-uiKg)〉中的算式 $\frac{b\ln(e)}{e\ln(b)}=\frac{b}{\ln(b)}$ ，右式缺了分母的 $e$ 。  
- 2026/05/15：〈[你所不知道的 C 語言: 浮點數運算 - BFloat16](https://hackmd.io/tbHqxe19SdafIq0XdBnJzQ#BFloat16)〉部份 FP16 被誤植為 BP16 。  
- 2026/06/03：編譯〈[並行程式設計: Atomics 操作](https://hackmd.io/OVPTyhEPTwSHumO28EpJnQ#%E8%99%95%E7%90%86%E5%99%A8%E6%9E%B6%E6%A7%8B%E5%92%8C%E5%85%B6-Memory-Order)〉中的 `reorder.c` 時遇到編譯器警告 `printf()` 的參數 (`int64_t`) 與 `%d` 不相符，將其修改為 `%ld` 。  

<!-- TODO: 非常 Trivial 的修錯字需要放嗎？目前決定不放 -->


## 與授課教師的互動
> ? 分

一對一討論共 1 次，課堂問答共 3 次。

### 一對一討論
- 2026/05/30：討論 false_sharing.c 的目的、內容，並且在討論結束後要找出 false_sharing.c segment fault 的原因。在最後決定了期末專題的方向為 kxo 。

### 課堂問答
- 2026/03/10：詢問 Merge sort 為什麼比 Quick sort 還適合 linked list 以及為什麼 Quick sort 在陣列上能夠比較快。問答最後發現 Merge sort 的最差比較次數比 Quick sort 的最佳比較次數少，並且由授課老師提示到 Merge sort 存在 cache-aware 的版本。
- 2026/04/23：詢問 fork 與 clone 的差異以及 clone 的各個 flags 的功能以及應用場景。
- 2026/06/11：詢問 concurrency-primer.pdf 中 CAS 章節的程式碼細節，如為什麼 job 當中要使用 function pointer 、為什麼要提前初始化一批 worker。並在問答後閱讀〈[並行程式設計: Hazard pointer](https://hackmd.io/1qjBY-JZR8GHCjQADDJdcQ#)〉。
## 所見所聞所感
> ? 分
### 關於 Merge Sort v.s. Quick Sort

## 所見所聞所感  
> ? 分  
### 關於 Merge Sort v.s. Quick Sort  

我在期初的隨堂問答中，被問到為何 Merge Sort 比 Quick Sort 適合 linked list 等問題時答不上來。我才發現過去會想要快入的寫完程式，所以幾乎不去在意常數，也從來沒有實際計算過，通常都是被卡常數後才會慢慢修（只是找可以壓的地方壓，不會實際算）。並且因為像 C++ 這類語言提供了 `sort()` 函式，因此我只有需要干涉 sort 的內部行為時，才會自己刻 Merge Sort ，這導致我很少去了解 sort 。

問答後，我回去推導這兩個排序演算法的最差、平均、最佳的比較與交換次數的準確數值，發現 Merge sort 的最差比較次數比 Quick sort 的最佳比較次數還少。並從實驗證實陣列情況下 Quick sort 速度較快是因為 cache locality ，以及 linked list 下是 Merge Sort 較快。

註：
- Merge Sort 的平均比較次數因為 N 個元素中最 N/2 小的元素所在位置的期望值還找不到方法化簡，因此沒算出來。
- Quick Sort 的最差交換次數因為無法證明最差是發生在何種分佈，因此只有猜測是 $\frac{N}{2} \log_2{N}$ 。

### 關於 Linked list 的技巧
在讀過〈[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E5%BE%9E-Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E8%97%9D%E8%A1%93%E8%AB%87%E8%B5%B7)〉後才知道可以使用指標的指標寫出更簡潔的程式碼，後續也有實際使用該技巧。以及利用 `struct list_head` 嵌入結構體與 `container_of` 的技巧，使得操作 linked list 的 API 只要針對 `struct list_head` 一種型別即可。這讓我發現即便是如 linked list 之類的基本功，也有許多值得深入學習的細節。

### 關於 C 語言
這門課是我第一次把 C 語言標準拿來詳細的讀，讓我發覺我對 C 語言的認知僅限於 gcc 的 C 語言的一部分，諸如有號數可以用二補數以外的數字表示、undefined behaviour 與最佳化的關係都是上過這堂課才知道的。從這個過程中，我發現如果想要寫出可移植的程式碼，測試是不夠的，必須要直接讀語言的標準才行。

讀標準雖然很費精神（有些內容寫得真的很繞），但我覺得挺有趣的，因為可以學到不少一般程式課程不會學到的東西，像是無號數的 "overflow" 行為是被保證為 wrap-around 、下面的函式可以回傳 `NULL` 。
```c
int *f()
{
    int x = 0;
    return &x;
}
```

因為以上原因，我開始會在學語言時讀標準，例如這學期因為電機系的課程需要寫 verilog ，我就直接下載一份 verilog 2005 標準，用來對照自己寫的語法在標準中是如何規定。