2026q1 Homework1 (warmup)

# 2026q1 Homework1 (warmup) contributed by < Lyciih > {%hackmd NrmQUGbRQWemgwPfhzXj6g %} [2026 年 Linux 核心設計課程作業 —— warmup](https://hackmd.io/@sysprog/linux2026-warmup) ## 細讀〈[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)〉 ### 感想：在[為什麼不該在台灣用「視頻」一詞？](https://matters.town/a/i35tafyix5o2)中，我發現了原來「視頻」中的「頻」是指頻率的意思，之前如果不把單個字拆開來研究的話其實沒有想過這件事。文中介紹到，此處的「頻」詳細來說是指「用來傳遞影像訊號或同步脈衝的訊號頻率」。這讓我聯想到玩遊戲時常會聽到的「幀率」，也叫[「影格速率」](https://zh.wikipedia.org/zh-tw/%E5%B8%A7%E7%8E%87)、或「 FPS 」，用來描述遊戲畫面每秒重新繪製多少張，與視頻想表達的意思相近。不同的地方在於影像的來源跟產生的方式。其他感想： - 原來「電鋸」並不是用電驅動的，以前只顧著看電影但沒有發現。 - 原來「緩存」是「緩衝存儲器」的意思。 - 原來「 render 」較精準的翻譯是「算繪」。由於我的碩士論文與圖學有關，在論文口試時也被校外委員問過渲染這個詞。後來經過討論後，折衷的做法是在論文中第一次出現「渲染」這個詞的地方說明了論文中提到的渲染指的是「 render 」。 ### 我的疑問： - 遍歷假設一開始我看不太懂，詢問GPT後，也只有一些模糊的概念。目前的理解是，不停的做某個實驗並統計實驗的結果，則各種結果佔全部結果的比例，會趨近所有可能結果在狀態空間中的比例？感覺有種蒙地卡羅的味道？ - 下圖是我目前的理解。 ![圖片](https://hackmd.io/_uploads/Byk3kyPFbl.png) ### 作業問題回答： * "render" 在電腦圖學語境中為何應強調「如實呈現」？「渲染」一詞喪失什麼關鍵意涵？在 Linux 核心原始程式碼中，"render" 出現在哪些場景、語境又有哪些？翻閱詞典 (善用學校圖書館) 並考據詞源 * 說明 constant 與 immutable 的差異，並探討程式設計中的關鍵考量 * [constant](https://dictionary.cambridge.org/zht/%E8%A9%9E%E5%85%B8/%E8%8B%B1%E8%AA%9E-%E6%BC%A2%E8%AA%9E-%E7%B9%81%E9%AB%94/constant) 在劍橋辭典中的意思是：`經常發生的;連續發生的;連續不斷的` * [immutable](https://dictionary.cambridge.org/zht/%E8%A9%9E%E5%85%B8/%E8%8B%B1%E8%AA%9E-%E6%BC%A2%E8%AA%9E-%E7%B9%81%E9%AB%94/immutable) 在劍橋辭典中的意思是：`永恆的;不可改變的` * 在最新的 [C23](https://www.open-std.org/jtc1/sc22/wg14/) 規格書中 * 比較 concurrent 與 parallel 的語意差異，並說明為何「並行」較貼近 concurrent 的本意 * 當我們撰寫 Linux 核心文件，應如何區分 process, thread, task, job 等術語，才能避免跨領域誤解又省去過多的中英並陳？ ## 細讀〈[GNU/Linux 開發工具](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fr1Psrf0KW)〉 ### LaTeX 波函數的 LaTeX 語法: `$\psi(x)$` - $\psi(x)$ 密度矩陣的 LaTeX 語法: `$\rho$` - $\rho$ - 一般密度矩陣定義 $\rho = |\psi\rangle \langle \psi|$ ### git 以前我使用 git ，只會用 `git add .` + `git commit` + `git push` 這三種指令，不假思索的只用一個 branch 開發整個專案，根本沒有分支的概念。基本上只是搭配 github 當作備份而已，沒有完全發揮 git 被發明出來的用意，趁著這次機會總算能體驗到各種 git 提供的功能。在關於 git 的教學中，有提供一個網站可以透過闖關遊戲的方式來學習 git 的各種指令，我覺得很好玩，花了一天把全部的關卡都解完。 ![image](https://hackmd.io/_uploads/HkuruH3KWx.png) ![image](https://hackmd.io/_uploads/BychXShY-x.png) ### perf 參考資料：[羅根學習筆記](https://zh-blog.logan.tw/2019/07/10/analyze-program-performance-with-perf-events/) #### 範例程式1: 計算圓周率 `perf_top_example.c` ```c #include <stdio.h> #include <unistd.h> double compute_pi_baseline(size_t N) { double pi = 0.0; double dt = 1.0 / N; for (size_t i = 0; i < N; i++) { double x = (double) i / N; pi += dt / (1.0 + x * x); } return pi * 4.0; } int main() { printf("pid: %d\n", getpid()); sleep(10); compute_pi_baseline(50000000); return 0; } ``` #### 編譯 ``` $ gcc -std=c99 -g -o example perf_top_example.c` ``` #### 測量 ``` $ perf record -g ./example ``` #### 觀看報告 ``` $ perf report ``` ![圖片](https://hackmd.io/_uploads/HyatGnAtZg.png) 可以觀察到大部分的開銷都集中在 `compute_pi_baseline` #### 範例程式2: 矩陣相乘 `matrix-v1.c` :::spoiler 實驗環境 ```shell $ cat /etc/os-release NAME="Linux Mint" VERSION="21.3 (Virginia)" ID=linuxmint ID_LIKE="ubuntu debian" PRETTY_NAME="Linux Mint 21.3" VERSION_ID="21.3" HOME_URL="https://www.linuxmint.com/" SUPPORT_URL="https://forums.linuxmint.com/" BUG_REPORT_URL="http://linuxmint-troubleshooting-guide.readthedocs.io/en/latest/" PRIVACY_POLICY_URL="https://www.linuxmint.com/" VERSION_CODENAME=virginia UBUNTU_CODENAME=jammy $ lscpu 架構： x86_64 CPU 作業模式： 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 供應商識別號： GenuineIntel Model name: Intel(R) Xeon(R) CPU E3-1231 v3 @ 3.40GHz CPU 家族： 6 型號： 60 每核心執行緒數： 2 每通訊端核心數： 4 Socket(s): 1 製程： 3 CPU max MHz: 3800.0000 CPU min MHz: 800.0000 BogoMIPS: 6783.89 Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault invpcid_single pti ssbd i brs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts md_clear flush_l1d ibpb_exit_to_user Virtualization features: 虛擬： VT-x Caches (sum of all): L1d: 128 KiB (4 instances) L1i: 128 KiB (4 instances) L2: 1 MiB (4 instances) L3: 8 MiB (1 instance) NUMA: NUMA 節點： 1 NUMA node0 CPU(s)： 0-7 Vulnerabilities: Gather data sampling: Not affected Indirect target selection: Not affected Itlb multihit: KVM: Mitigation: VMX disabled L1tf: Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable Mds: Mitigation; Clear CPU buffers; SMT vulnerable Meltdown: Mitigation; PTI Mmio stale data: Unknown: No mitigations Reg file data sampling: Not affected Retbleed: Not affected Spec rstack overflow: Not affected Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization Spectre v2: Mitigation; Retpolines; IBPB conditional; IBRS_FW; STIBP conditional; RSB filling; PBRSB-eIBRS Not affected; BHI Not affected Srbds: Mitigation; Microcode Tsa: Not affected Tsx async abort: Not affected Vmscape: Mitigation; IBPB before exit to userspace $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04.3) 11.4.0 ``` ::: ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdint.h> #define N 1024 #define NUM_ROUNDS 5 static int32_t a[N][N]; static int32_t b[N][N]; static int32_t c[N][N]; __attribute__((noinline)) static void load_matrix() { FILE *fp = fopen("input.dat", "rb"); if (!fp) { abort(); } if (fread(a, sizeof(a), 1, fp) != 1) { abort(); } if (fread(b, sizeof(b), 1, fp) != 1) { abort(); } fclose(fp); } __attribute__((noinline)) static void mult() { size_t i, j, k; for (i = 0; i < N; ++i) { for (j = 0; j < N; ++j) { for (k = 0; k < N; ++k) { c[i][j] += a[i][k] * b[k][j]; } } } } __attribute__((always_inline)) static inline void escape(void *p) { __asm__ volatile ("" : : "r"(p) : "memory"); } int main() { int r; load_matrix(); for (r = 0; r < NUM_ROUNDS; ++r) { memset(c, '\0', sizeof(c)); escape(c); mult(); escape(c); } return 0; } ``` #### 編譯 ``` $ gcc matrix-v1.c -o matrix-v1 -mno-sse2 -Wall -O2 -g -fno-omit-frame-pointer ``` #### 產生測試資料 ``` $ dd if=/dev/urandom of=input.dat bs=$((8 * 1024 * 1024)) count=1 ``` #### 以 perf stat 取得總體統計數據 ``` $ perf stat -e cycles,instructions ./matrix-v1 Performance counter stats for './matrix-v1': 95,785,073,294 cycles 37,686,138,060 instructions # 0.39 insn per cycle 26.543938341 seconds time elapsed 26.529436000 seconds user 0.011998000 seconds sys ``` #### 以 perf record -g 取樣 ``` $ sudo perf record -g ./matrix-v1 ``` #### 以 perf report 讀取報告 ``` $ sudo perf report -g graph,0.5,caller ``` ![圖片](https://hackmd.io/_uploads/Sy_B5hRFZe.png) 在 mult 欄按 a 觀看詳細內容 ![圖片](https://hackmd.io/_uploads/B1P55n0FWe.png) 可以發現 imul 佔用大量的執行時間，文章的作者猜測可能是 cache-miss ，於是想用 perf 針對 cache-miss 進行觀測。要觀測 cache-miss 需要找到相關的事件選項。 #### 以 perf list 查詢合適的事件種類 ``` $ perf list ``` 雖然跟文章作者使用不同的 CPU ，但一樣找到了同樣的觀測選項。 ![圖片](https://hackmd.io/_uploads/Sk64Tn0KZl.png) #### 重新使用 perf record 記錄 cycles、instructions 與 L1-dcache-load-miss 的事件次數 ``` $ sudo perf record -g -e cycles,instructions,L1-dcache-load-misses ./matrix-v1 ``` #### 再次以 perf report 讀取報告 ``` $ sudo perf report -g graph,0.5,caller ``` 這次觀察了三種選項，我們選擇觀看第三個選項的報告。 ![圖片](https://hackmd.io/_uploads/rk3XR20Kbg.png) 可以看到 cache-miss 都發生在 mult 函式中。 ![圖片](https://hackmd.io/_uploads/B1iBRhRYWg.png) 在 mult 的欄位上按下 a ，觀看更詳細的內容。 ![圖片](https://hackmd.io/_uploads/HyykJ6AY-g.png) #### 統計 matrix-v1 的 cache-miss 發生次數 | 指令 | 次數 | | ----------------- | ------------- | | imul (%rax), %edx | 112,544,952 | | add $0x1000, %rax | 5,017,847,773 | | add $0x4, %rcx | 198,762,201 | | add %edx, %esi | 6,586,141 | | cmp %rdi, %rax | 89,581,774 | | 總和 | 5,425,322,841 | | 平均 (除以 5 * 1024 * 1024 * 1024) | 101.05% | cache-miss 發生次數在迴圈中的佔比竟然超過100% !? ![圖片](https://hackmd.io/_uploads/HJI1MTCFWl.png) #### 範例程式2: 執行矩陣乘法之前先轉置矩陣 b `matrix-v2.c` ```c static int32_t bT[N][N]; __attribute__((noinline)) static void transpose() { size_t i, j; for (i = 0; i < N; ++i) { for (j = 0; j < N; ++j) { bT[i][j] = b[j][i]; } } } __attribute__((noinline)) static void mult() { size_t i, j, k; transpose(); for (i = 0; i < N; ++i) { for (j = 0; j < N; ++j) { for (k = 0; k < N; ++k) { c[i][j] += a[i][k] * bT[j][k]; } } } } ``` #### 用同樣的命令編譯 matrix-v2.c ``` $ gcc matrix-v2.c -o matrix-v2 -mno-sse2 -Wall -O2 -g -fno-omit-frame-pointer ``` #### 再次使用 perf stat 測量 matrix-v2 的總體統計數據 ``` $ sudo perf stat -e cycles,instructions,L1-dcache-load-misses ./matrix-v2 Performance counter stats for './matrix-v2': 10,204,459,433 cycles 32,302,151,961 instructions # 3.17 insn per cycle 343,137,247 L1-dcache-load-misses 2.837096672 seconds time elapsed 2.818573000 seconds user 0.007984000 seconds sys ``` #### 再次使用 perf record 記錄 cycles、instructions 與 L1-dcache-load-miss 的事件次數 ``` $ sudo perf record -g -e cycles,instructions,L1-dcache-load-misses ./matrix-v2 ``` ![圖片](https://hackmd.io/_uploads/r1mVUT0Y-g.png) #### 統計 matrix-v2 的 cache-miss 發生次數 | 指令 | 次數 | | ----------------- | ------------- | | imul (%rsi,%rax,4),%edx | 49,162,793 | | add $0x1,%rax | 103,876,222 | | add %edx,%ecx | 71,573,598 | | cmp $0x400,%rax | 79,379,898 | | 總和 | 303,992,511 | | 平均 (除以 5 * 1024 * 1024 * 1024) | 5.66% | #### 改良前後的比較改良後的程式在效能上有大幅的改善。 | 項目 | matrix-v1 | matrix-v2 | 差異百分比 | | -------------------- | --------- | ----------- | ---------- | | Insn Per Cycle（個） | 0.39 | 3.17 | 712% | | L1 Data Cache Miss (次) | 5,425,322,841 | 303,992,511 | -95% | | 總花費時間（秒） | 26.54 | 2.83 | -90% | ### 簡介 perf_events 與 Call Graph #### 實際操作 1 範例程式:[callgraph.c](https://zh-blog.logan.tw/static/sourcecode/2019/10/06/callgraph.c) #### 編譯 ```shell $ gcc -g -O2 -fno-omit-frame-pointer callgraph.c -o callgraph ``` #### 測量 ```shell $ sudo perf record -g --call-graph fp -o callgraph.fp.perf.data ./callgraph $ sudo perf record -g --call-graph dwarf -o callgraph.dwarf.perf.data ./callgraph $ sudo perf record -g --call-graph lbr -o callgraph.lbr.perf.data ./callgraph ``` 三者的檔案大小不同 ![圖片](https://hackmd.io/_uploads/r1DFvy1qbe.png) #### 觀察記錄檔案的內容 ```shell $ sudo perf report --stdio -i [filename] ``` fp: ``` 99.99% 5.92% callgraph callgraph [.] main | |--94.08%--main | | | |--58.78%--A | | | | | |--23.49%--C | | | | | --23.47%--B | | | | | --11.74%--C | | | |--23.44%--B | | | | | --11.72%--C | | | --11.77%--C | --5.92%--__libc_start_call_main main ``` dwarf: ``` 99.98% 5.66% callgraph callgraph [.] main | |--94.33%--main | | | |--59.02%--A | | | | | |--23.96%--B | | | | | | | --11.71%--C | | | | | --23.34%--C | | | |--23.62%--B | | | | | --11.93%--C | | | --11.59%--C | --5.66%--_start __libc_start_main_impl (inlined) __libc_start_call_main main ``` lbr: ``` 99.99% 5.94% callgraph callgraph [.] main | |--94.05%--main | | | |--82.21%--A | | | | | |--35.20%--B | | | | | | | --11.69%--C | | | | | --11.80%--C | | | --11.74%--B | C | --5.94%--_start __libc_start_main@@GLIBC_2.34 __libc_start_call_main main ``` 可以看到 lbr 的結果與前兩者差異較大，並且有奇怪的 stack ，另外三張圖中都有跳過 A 呼叫 B 或 C 的情況。這些是因為 `Sibling Call Optimization` 造成的。 #### 使用 -fno-optimize-sibing-calls 重新編譯 ```shell $ gcc -g -O2 -fno-omit-frame-pointer -fno-optimize-sibling-calls callgraph.c -o callgraph ``` #### 重新測量 ```shell $ sudo perf record -g --call-graph fp -o callgraph.fp.perf.data ./callgraph $ sudo perf record -g --call-graph dwarf -o callgraph.dwarf.perf.data ./callgraph $ sudo perf record -g --call-graph lbr -o callgraph.lbr.perf.data ./callgraph ``` fp: ``` 99.99% 5.82% callgraph callgraph [.] main | |--94.17%--main | | | --94.14%--A | | | |--70.73%--B | | | | | --47.04%--C | | | --11.76%--C | --5.82%--__libc_start_call_main main ``` dwarf: ``` 99.98% 5.77% callgraph callgraph [.] main | |--94.21%--main | | | --94.17%--A | | | |--70.61%--B | | | | | --46.94%--C | | | --11.99%--C | --5.77%--_start __libc_start_main_impl (inlined) __libc_start_call_main main ``` lbr: ``` 99.99% 5.89% callgraph callgraph [.] main | |--94.10%--main | | | --94.03%--A | | | |--70.59%--B | | | | | --47.05%--C | | | --11.83%--C | --5.89%--_start __libc_start_main@@GLIBC_2.34 __libc_start_call_main main ``` 這次，三種測量的結果就很相近， stack 也符合預期。 ## 探討〈[linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)〉文中的練習題，將函式原型改為 `void remove(list_entry_t head, int value)` ```clike void remove(list_entry_t **head, int value){ list_entry_t **dummy = head; while((*dummy)->value != value) dummy = &(*dummy)->next; *dummy = (*dummy)->next; } ``` 我的疑問: - 使用 indirect pointer 雖然變優雅了，但會不會多了解指標的開銷？ - 在討論 [LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/description/) 的段落中 - 長度相近的 linked list 合併真的會比不等長的快嗎？還是只是省了某部份的時間，卻多了另一部份的時間？感想：原來環狀的意義在於省去雙向鏈結佔用的空間(可以在 cache line 中多放一些)但又同時彌補反向查詢的功能。並且在嵌入式環境中，因為沒有 MMU ，所以 NULL 的位置其實可以使用，環狀的好處就是可以不去使用 NULL 當結尾，使 NULL 可以被其他需求利用。 - 案例探討: Leetcode 2095. Delete the Middle Node of a Linked List 中利用快慢指標 - 檢查 linked list 是否有環 - 在環狀 linked list 找到中點的方法很有趣，以前沒有想過。用不停檢查是否曾經走過的方法，會佔用很多空間。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.