# 2024q1 Homework5 (assessment)
contributed by < [weihsinyeh](https://github.com/weihsinyeh) >
## 從前 4 週的測驗題選出 3 題改進
[2024q1 Homework4 (quiz3+4)](https://hackmd.io/@weihsinyeh/ByOQ5cpaT)
### 第四周 測驗 `1`
```c=
unsigned popcount(unsigned v)
{
int n;
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101;
return v >> 24;
}
```
將上面以每 4 個位元 (nibble) 去計算 1 的數量，但在作業四後，知道平行是加快程式效能的關鍵，因此如果能減少每一個單位要執行的次數，就可以增加平行，讓相同的計算能夠重複運算各個單位。而上面第 4 ~ 9 行是計算每4個位元出現 1 的數量。而上面第 11 行將每個 (nibble) 計算 1 的數量加上下一個 (nibble) 計算 1 的數量。
因此現在如果用 2 個位元，透過公式 : $b_i = \lfloor\frac{x}{2^i}\rfloor - 2\lfloor\frac{x}{2^{i+1}}\rfloor$，計算每 2 個位元 1 的數量，會變成$b_{1} + b_0 = \lfloor\frac{x}{2^1}\rfloor - 2\lfloor\frac{x}{2^{1+1}}\rfloor + \lfloor\frac{x}{2^0}\rfloor - 2\lfloor\frac{x}{2^{0+1}}\rfloor = x - \lfloor\frac{x}{2^{1}}\rfloor$。
```c=1
int n;
n = (v >> 1) & 0x55555555;
v -= n;
v = ((v+v>>2)) & 0x????????;
```
在想問號是甚麼時我發現一個問題。知道原本要選 nibble 為一個最小單位的原因。$b_3+b_2+b_1+b_0$ 的範圍為 $[0,4]$ ，接著兩個合併後的範圍為 $[0,8]$。探討這件事的原因是因為接下來要用這行計算一個byte 的 1 出現的數量 `v = (v + (v >> 4)) & 0x0F0F0F0F;` 限制。
```
b7 b6 b5 b4| b3 b2 b1 b0
b7+b6+b5+b4| b3+b2+b1+b0
b7+b6+b5+b4+b3+b2+b1+b0
```
因此希望相加的範圍是在一個 nibble 可以表示的範圍中 $[0,2^4-1]=[0,15]$。因此原先如果兩個位元為單位，相加$b_1+b_0$ 的範圍$[0,2]$ ，接著兩個要合併後的範圍為 $[0,4]$。這樣就會超出二個位元可以表示的範圍 $[0,2^2-1]=[0,3]$。
```
b7 b6 b5 b4| b3 b2 b1 b0
b7+b6| b5+b4| b3+b2| b1+b0
|b7+b6+b5+b4| |b3+b2+b1+b0
```
因此不能用上面問號的形式，需要用下面再做加法時前要先清掉，不能做完才清掉。減少每個單位的數量，來增加平行的次數。
```c=4
v = ((v & 0x33333333)+((v >> 2) & 0x33333333));
v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101;
return v >> 24;
```
再來就是增加最後面合併的次數讓他能夠避免用乘法的方式。第五行做的事情如下:
```
|b7+b6+b5+b4| |b3+b2+b1+b0
|b7+b6+b5+b4+b3+b2+b1+b0
```
因此接下來繼續擴展，將第5行改成這樣。改完突然發現這樣不就是 《Hacker's Delight》P87 提供的解法(下方的註解)，繞了一大圈又回到起點。但是由於知道範圍的那件事情，也因此知道右移 4、8 與 16 都不會有問題。所以不用需要分開去與常數 & 。
```c=5
v = (v + (v >> 4)) & 0x0F0F0F0F; // (v & 0x0F0F0F0F) + ((v >> 4) & 0x0F0F0F0F));
v = (v + (v >> 8)) & 0x00FF00FF; // (v & 0x00FF00FF) + ((v >> 8) & 0x00FF00FF));
v = (v + (v >> 16)) & 0x0000FFFF; // (v & 0x0000FFFF) + ((v >> 16) & 0x0000FFFF));
return v;
```
接續因為上面有考慮進位的範圍，進而可以想通原先書中說明減化成下面的原因。前天閱讀時還在這段話旁邊標記問號。
> **《Hacker's Delight》P87**
> Clearly, the last *and* is unnecessary, and other *and*’s can be omitted when there is no danger that a field’s sum will carry over into the adjacent field.
```c=5
v = (v + (v >> 4)) & 0x0F0F0F0F; // (v & 0x0F0F0F0F) + ((v >> 4) & 0x0F0F0F0F));
v = (v + (v >> 8));
v = (v + (v >> 16));
return v& 0x0000003F;
```
最簡單的說明就是原先有 32 個位元，也因此當我把兩個 nibble 計算的數量 A 與數量 B相加後，一定要將 nibble 1 的位元清掉，因為 32 在範圍 $[0,2^6-1]=[0,63]$ 中，因此用 6 個位元來表示。 這也說明為什麼 6 7 行可以簡化成那樣，因為相加後不會進位到更高的 8 個位元，或是更高的 16 了。所以不需要清 0 。
```
nibble 1 | nibble 0
數量 A | 數量 A + 數量 B
```
因為在作業4的時候知道當二個位元是 (11) 時，則 1 的數量為 2(10)， 是 (10)或(01) 時，則 1 的數量為 1(01)， 是 0(00) 時，則 1 的數量為 0(00)。這讓我想看能不能其他的方式來寫。在觀察位元之間的關係後，結果中的第 0 個位元是原先二個位元的 $\oplus$，結果中的第一個位元則是原先二個位元的 and 。所以將原先第 1 ~ 3 行替換，整個 popcount 變成如下:
```c
int v0 = (v^(v>>1)) & 0x55555555;
v = ((v&(v<<1)) & 0xAAAAAAAA) + v0;
v = ((v & 0x33333333)+((v >> 2) & 0x33333333)) ;
v = (v + (v >> 4)) & 0x0F0F0F0F;
v = (v + (v >> 8)) ;
v = (v + (v >> 16));
return v& 0x0000003F;
```
但這樣還不如原先的寫法簡潔，因此還要想其他可能。
後來看到 《HAKMEN》P79 裡面用 3 個位元為單位。也就是用 8 進位。
這樣一開始就可以改成。
```c=1
unsigned popcount(unsigned v)
{
unsigned int tmp;
tmp = v - ((v>>1) & 033333333333) - ((v>>2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
```
`(tmp + (tmp >> 3)) & 030707070707`是會算出每6個位元出現 1 的數量，但我因為看不懂為什麼 mod 63 就可以得到所有每6個位元出現 1 的數量的總和。所以將他們用一個數字列出來看。
```
1 000 000 000 000 100 111 000 011 111 // 134237727
1 000 000 000 000 001 011 000 010 011 // 134223379 （第四行）
0 001 000 000 000 000 001 011 000 010 // 16781509 （tmp >>3）
0 001 000 000 000 001 000 011 000 101 // (tmp+ (tmp >> 3)) & 030707070707
```
先將每 6 個位元視為一組$B$，因此原先的會排列成 : $B_5B_4B_3B_2B_1B_0$，而他們的十進位的值為 : $B_5\times64^5+B_4\times64^4+B_3\times64^3+B_2\times64^2+B_1\times64^1+B_0\times64^0$ $=B_5(63+1)^5+B_4(63+1)^4+B_3(63+1)^3+B_2(63+1)^2+B_1(63+1)^1+B_0(63+1)^0$
再取餘數就為 : $B_5+B_4+B_3+B_2+B_1+B_0$
因為上面這個作法是將最小單位從 4 個位元變成 3 個位元。我覺的這樣可以增加平行的次數，會加快，所以就我參考 [vax-r](https://hackmd.io/@vax-r/linux2024-homework4) 的 bench 寫法，來計算兩種不同方法的平均執行時間。
```shell
popcount use nibble avg time : 36.715820
popcount use oct avg time : 30.370616
```
從上面的實驗得知用 oct 的作法可以比較快，雖然它符合之前的推論可以增加平行的次數，但我有點懷疑這是不一樣程式碼的寫法，所以將他們編譯成組合語言。
我先把原先 4 個位元的寫法換成跟比較快的 3 個位元的寫法再去比較。
```c
int popcount_nibble(unsigned v)
{
unsigned tmp = v - ((v >> 1) & 0x77777777) - ((v >> 2) & 0x33333333) -
((v >> 3) & 0x11111111);
return ((tmp + (tmp >> 4)) & 0x0F0F0F0F) % 255;
}
int popcount_oct(unsigned v)
{
unsigned tmp = v - ((v >> 1) & 033333333333) - ((v >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
```
發現是寫法的問題。因為在執行多次後 nibble 用時較 oct 少，且builtin 都會是最快的。branchless （測驗題的寫法）則都是最慢的。
```
popcount use builtin function avg time : 14.869000
popcount use branchless avg time : 23.643507
popcount use nibble avg time : 18.887740
popcount use oct avg time : 19.187075
```
`__builtin_popcount` 是 gcc 的內建函式。因為找gcc github上沒有找到 source code 的實作，而我因為覺得查表法是最快的方式，所以我用了查表法做實驗看平均時間是否能比其他方法用時少。
> 在 Intel SSE 指令集提供 `popcnt` 指令，於是下方的實驗反映出硬體指令的優勢。參見 [SIMD (SSE) population count](https://github.com/WojciechMula/sse-popcount) :notes: jserv
補充說明查表法並不一定總是比較快，因為他也要能在一個 cache line (主流的 CPU Cache 的 Cache Line 大小多為 64 Bytes) 能儲存資料的範圍內 (64 Bytes) 才會快。否則執行時間反而會包含處理 cahce miss 的時間。
< [commit 3b24010](https://github.com/weihsinyeh/Sorting-Lab/commit/3b240102777da775df48ed44cdcf8c36c4551782) >
```
popcount use builtin function avg time : 16.200390
popcount use lookup table avg time : 19.295659
popcount use branchless avg time : 26.588892
popcount use nibble avg time : 20.798930
popcount use oct avg time : 21.010737
```
雖然在 oct 的程式碼比 nibble 少一道減法的操作。但是因為我現在算出來的時間差距很小，這很難說明哪一種操作會比較好。有三件事情並未考慮在實作中。
(1) 我的指令可能轉換成 0.5 cpu cycle 的指令。
(2) 使用計算執行的時間是用 gettime() 不精準，此外我不只用 gettime() 還用了先執行 $1000000$ 次再 $/ 1000000$，這讓我原先以為要這樣就算執行時間很短我也可以測量得到。但回憶起第一周的論文
> **〈 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 〉**
> Pre-processing: We pre-process measurements prior to statistical processing. We discard measurements that are larger than the p percentile, for various2 values of p. The rationale here is to test a restricted distribution range, especially the lower cycle count tail. The upper tail may be more influenced by data-independent noise. This (heuristic) process gives good empirical results (makes detection faster); nevertheless we also process measurements without pre-processing.
這裡就有提到 "upper tail may be more influenced by data-independent noise"。 因此如果我是執行 $1000000$ 次再 $/ 1000000$ 這樣比較準確的時間會因為 upper tail，而時間變長，增加不確定的因素，因此這種作法將原先「應該被捨棄的偏離正常的值」也考慮進去
(3) 要用 RDTSC 參考[linux/tools/perf/util/tsc.c](https://github.com/torvalds/linux/blob/master/tools/perf/util/tsc.c) dtsc 限制在特定的 CPU 上，且指令不被打亂。或是 How to Benchmark Code Execution Times on Intel IA-32 and IA-64 Instruction Set Architectures White Paper。之所以會有特殊的指令是因為 CPU 執行的時候有 timming intterrupt、round robin、作業系統 wake up 等 task 也在執行，所以測量時間的指令要先不被打亂，且避免要測量執行時間的程式是被限制在一個 CPU 上，避免因 process migration 而影響測量的執行時間。
我改成 rdtsc 的程式碼，算 cpu cycle 。參考 cpucycle.h
```c
#if defined(__i386__) || defined(__x86_64__)
unsigned int hi, lo;
__asm__ volatile("rdtsc\n\t" : "=a"(lo), "=d"(hi));
return ((int64_t) lo) | (((int64_t) hi) << 32);
```
用 `hi` 跟 `lo` 去存取暫存器的值。其中是用 rdtsc 這個指令(組合語言) 存取暫存器得到 CPU cycle 的值，但這個暫存器為32 位元所以用 `hi` 跟 `lo` 去儲存由 64 bits 組成的 CPU cycle 。
從電腦一開機就會去累計 CPU cycle 的值。暫存器從 0 開始，所以有可能這個值會 overflow。 x86_64 每次都是讀 64 個位元。但暫存器有時是 32 個位元跟 64 個位元。現在是用 64 個位元存 CPU cycle 因為這樣減少 overflow 發生的頻率，但因為向下相容 rdtsc 以前是用 32 位元存的，所以現在分別用 32 個位元的暫存器存 `hi` 跟 `lo`。
< [commit f41c480](https://github.com/weihsinyeh/Sorting-Lab/commit/f41c48082328faabd923d9f261267e682930f72f) >
```
popcount use __builtin_popcount avg cpu cycle : 13
popcount use lookup table avg cpu cycle : 15
popcount use branchless avg cpu cycle : 15
popcount use oct avg cpu cycle : 14
popcount use nibble avg cpu cycle : 14
```
在這裡可以看出來用 rdtsc 跑出來的效果其實每個操作都只差 1 個 CPU Cycle 。之所以不同的實作但跑出來的 CPU Cycle 差不多，是因為 1 個 CPU Cycle 可以有很多 issue。dual-issue processor 是最基本的，所以增加多一點指令也不會改變最後的 CPU Cycle 總量，因為 "Super Scalar processor is a CPU that implements a form of parallelism called instruction-level parallelism within a single processor."。因為它可以將多出來的指令也放到一個 CPU Cycle 去執行。
所以像是有些程式碼看起來比較多行或是轉成組合語言有比較多指令，但最後的執行時間卻也比較少。其原因來自「有些指令可以做 instruction-level parallelism 但有些因為 data dependency 的關係無法 insturction-level parallelism。」或是「有些指令是透過複雜的電路去實現功能。」。所以就算程式碼數量減少了，也有看組合語言是否減少，其中又跟編譯器有關係 `gcc -O0` `gcc -O1` ...有關。而就算指令數量減少還要看是甚麼指令。
### 第三周 測驗 `1`
##### Analysis of the Lookup Table Size for Square-Rooting.
Table lookup 的功能是為了讓減少 digit-recurrence 的延遲。
---
## 研讀第 1 到第 6 週「課程教材」
### [Linux 核心設計: 不只挑選任務的排程器](https://hackmd.io/@sysprog/linux-scheduler)
排程器廣義含有 CPU、I/O、網路、硬體圖形加速框架都會有排程器。這裡探討的是 CPU 排程器(行程排程器)。排程器已不在只是挑選下一個可以執行的行程了，還要顧及公平(fairness)，公平需考量多核處理與執行時間還有任務類型(I/O bound或CPU bound)。
因此要設計排程器要站在上帝視角。多核處理器除了要負載平衡，還有任務的類型，任務搬遷的成本。電源管理涵蓋降頻/拉高時脈、休眠，動態管理與關閉/開啟CPU。目前 Linux 6.6 以前預設的(框架)排程器CFS。預測任務的執行用機器學習。
排程器間還可以切換。CPU isolation 代表希望某些任務固定在特定CPU上，對即時處理(能在特定的時間範疇完成)非常重要。
Apache Spark 用functional programming 運算資源與實體裝置映射。
映射關係是數學上的的映射。加一層indirection。作業系統讓應用程式與硬體耦合度降低。
pipe `|` (建立管道讓行程A的資料傳遞給行程B)本身就含 context switch 隱含任務的切換。
```shell
$ perf bench sched pipe
```
藉由大量的 pipe 操作，讓 Linux 得以頻繁切換二個任務。A 傳給 B，B 傳給 A。從而測量排程器的成本。
taskset 用 bitmask 指定任務要分配給哪個(些) CPU。下方限定在 CPU 0 。因為之前為了負載平衡會打散到不同CPU，但在CPU多的時候這個代價是很高的。所以上面花比較多時間在 context switch。如果限定在一個 CPU 則花比較少時間 context switch 。
```shell
$ taskset -c 0 perf bench sched pipe
```
goroutine 不用有系統排程器的介入。紀錄有多少任務要去處理的資料結構是 runqueue 。
response time 不是越快越好，要區分是哪一種level的任務作相對應的處理。
高 thoughput 與低 latency 兩個不能兼顧?
EWMA 適合在電源管理上給 CPU 降頻依據。參考:`linux/kernel/sched/fair.c`。 `linux/kernel/sched/pelt.c` Per Entity Load Tracking。每個排程單元叫做scheduling entity。為了精準追蹤的排程單元的負載，作為降頻與負載的依據。linux 裡面不傾向浮點數 (將浮點數對應到 fixed point)，因此跟進階能源管理有關。
挖礦是積極的 batch process。
### [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHy72937Me)
gcc 限制巨集展開的數量。執行擋到系統呼叫 execve，並不是每個編譯器都有編譯、組譯、連結，反例：amacc 直接編譯產生執行檔(machine code)，而之所以要分三個階段是為了要模組化、除錯方便。
preprocessor （替換器不是編譯器）輸出後就不會再見到 `#include` 的字。 hello 程式需要到連結階段 (relocation) 才會知道 printf 的位址。
object file 可以被 relocate ，所以是 relocatable(最終可以透過linker 去重新配置記憶體位址)。用更簡單的程式語言寫出一個編譯器。編譯器是字串處理的程式碼。Ｃ runtime(crt) 處理返回值。用 self compliation 驗證編譯器是否可靠。
維根斯坦想讓語言公式化。讓語言用很正規的方式去表達。讓理解語言變成機械化。
S-expression 建構 AST
for while 迴圈在C語言是語法糖，因為都可以變成goto。
我從來沒有發現 Compiler 的書上面，盾牌是 Syntax Directed Translator(但這個無法跟處理器架構分開，舉例 : 0/0 在不同處理器上面有不同處理方式。)，然後屠龍刀是LALR Parser Generator，然後龍是 Complexity Compiler Design。看到了覺得很開心。
T_開頭表示 token。 { Open brace }。四則運算在語意分析上面不單純，因為整數的除法還要去轉換型態(Type checking)。 0:false !0:true。變數的scope 會改變 dynamic scope in bash。
function call 是先呼叫再傳遞參數，還是先傳遞參數再呼叫。且不是每次傳遞都可以用暫存器，有時還要配置記憶體。[ABI](https://en.wikipedia.org/wiki/Application_binary_interface)。有些最佳化和硬體沒有關係像是 dead code elimination
GSL DSL (自己寫編譯系統)
最佳化 CFG P38 會少一到指令? bb2 bb3 順序交換。
變成 0 的魔法時候的會將數學先計算完，雖然compiler 不會幫忙算數學，但像是在建成 AST 的地方，會看哪些 type 的轉換，這個地方會算簡單的數學。
### [你所不知道的C語言：技巧篇](https://hackmd.io/@sysprog/c-trick)
### [Linux 核心原始程式碼巨集: max, min](https://hackmd.io/@sysprog/linux-macro-minmax)
### [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)
### [Linux 核心設計: 中斷處理和現代架構考量](https://hackmd.io/@sysprog/linux-interrupt)
User mode 到 kernel mode 的 IRQ 會換數字。
### Scheduler
Code selector (cs) register 指向程式的 current privilege level。當使用者呼叫 system call 的時候會從 3(user mode) 變成 0(kernel mode)。
### Concurrency Primer
Threads 會共用狀態的位元，也因此要知道 Threads 讀寫的順序。
Atomicity: 有64位元的整數，每次bus只能存取32位元，有二個 Threads 就會發生一個在寫most significant half，另一個正在讀least significant half。所以在讀這一段的時候我很困惑 tore reads and writes 就算 atomic 也無法解決。但後來想一下我認為意思是指令是 atomic 也無法解決 tore reads and writes，解決的辦法是讓要被存取的變數一次只能被一個 thread 存取，(用lock)。[can-you-have-torn-reads-writes-between-two-threads-pinned-to-different-processor](https://stackoverflow.com/questions/64602829/can-you-have-torn-reads-writes-between-two-threads-pinned-to-different-processor)
#### 5.1 Exchange (atomic)
```
原先的例子 : 會將 worker thread 的 60 -> 61 的變化量忽略
UI | worker thread
1. read 60 |
| 2. read 60
| 3. set 61 (increase)
4. set 0 |
修正的方法 : 將 read 和 set 合併成一道指令成 `exchange`
UI | worker thread
1. exchage 60 & 0 |
| 2. read 0
| 3. set 1 (increase)
```
#### 5.3 Fetch and ...
如果 worker thread 的 read 跟 set 沒有 atomic 的問題 : UI set 0 不成功。
```
UI | worker thread
| 1. read 60
2. exchage 60 & 0 |
| 3. set 61 (increase)
```
### 6. block and lockless
block 透過要 lock 變數(mutex)，使 thread 要輪流才能存取被 lock 起來的資源，但容易造成 deadlock 。
lockfree 則是確保一定有 thread 在運作避免有 deadlock 。
### 8. Implement atomic RMW with LL/SC
因為 RISC 架構缺少 RMW 指令，且 processor 會隨時去執行其他的 thread 。因此用一個loop 確定`++foo;`有成功，因為至少一個 thread 會去修改 foo 。但我還在想這跟 processor 切換到其他 thread 的關係，因為切換到其他 thread 最後也會切回到原先要修改的 thread ，那這樣也可以保證有 make progress ，如果要考慮特例的話，就是原先要修改的 thread 突然中止不執行修改的指令。那這種情況也有可能會出現在所有 threads 而導致所有 threads 都無法 make progress。我還要想一下。
### 9. Do we always need sequentially consistent operations?
ARM (hardware architecture) 是 weakly-ordered , 所以要有 CPU 有特殊指令 `dmb` (memory barriers) 才不會指令執行的順序被編譯器打亂。這句話讓我很困惑，因為 ARM 也是在做 CPU 的。
SMP symmetric multiprocessor system :
電腦裡面不是 CPU
cache 跟主記憶體不一致。 所以要確保 cache 的東西是對的。
快的去等慢的。 cacheline 大小不同。只在乎 cache line 是否內容一置。 cache coherence。
MESI 協議。
cache coherece interface
有一個 store buffer 更新 cache 不用等電路 ready 先存到 store buffer 。終究 cpu 狀態不一樣。
要達到 cache 一致要廣播（高成本）。cache invalidate 。
store buffer 是 weakly ordered 的一個機制。先把要做的事情存起來。讓 CPU 可以先做下一道指令。
[參考並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency-atomics)
global interrupt
### 課程回顧
## 4/16
nvidia RDMA
thread local storage
__thread
有一個區域，執行緒不要共享，cache coherence
glibc 一直再進化 / Meta folly 要建立產業標準 de facto standard。
PSI : Pressure Stall Information
CFS :
## CS:APP 3/e (至少到第二章)
## 自動飲料機
剛剛看到飲料機第三杯飲料做出來的影片，感覺得他們真的很開心，影片最後剛好停在他比讚的畫面。回憶整個過程都紀錄回顧文中，一開始設計 pipeline 到螺旋製冰機，每個零件都是設計很久。最後那一刻真的很感人。回去看老師的筆記時，有一句話我覺得是看完這個故事最想說出來的心得：如果你每天都做跟別人一樣的事情，憑什麼跟別人不一樣。
### 課程心得
在學習本課程 5 週之後，可以很明顯地感受到學習是很快樂的。首先是這堂課的課程內容，不會限制在幾份 ppt 上面。舉例而言當發現一個問題的答案可能在《The Art of Computer Programming》中，我就可以沒有壓力地去花很多時間，更理解原理背後的數學。跟修其他課最大的差別就是，考試是限縮在幾份投影片上面，當發現不懂一個事情背後的運作，我可能去找相關的書籍，但每次找到一個知識的深度就會停止，因為花更多地時間探究更深，另一方面是壓縮讀完考試範圍的時間。同時也發現就算比別人多懂更多原理，只要別人比自己更熟習考試範圍與技巧，他就能得到更多分。所以我很喜歡這堂課的安排，雖然也有作業與考試的壓力，但我已經將「有沒有學到才是最重要的。」這句話記住。再來是在這堂課的程式碼不再只是達成功能，其實背後有很多數學，每次看到那些數學真的可以證明是這樣的效果，都很開心自己還活著可以看到這些數學。還有看《Hacker's Delight》bitwise中數學巧妙的運用，如果不是這堂課我應該就錯過這一本書了。再讀的時候作者會逐步描述想出這個想法的過程，讓讀者能參與其中，意猶未盡地閱讀。
還有大二上一開始讀資工系的時候，我每天都很開心，那個時候作業超級多幾乎都寫不完，但每寫出一個程式都很有成就感，覺得自己又進步了。但到大四的時候，開始學習人工智慧，發現很多作業都只是調整參數，雖然調整參數也很重要，但跟想像的資工系落差很大。同時看了透過大型語言模型訓練的東西，都覺得他就是原先資料集大，模型大，即便對於要解決的問題本身沒有了解的很深入，也能硬訓練出來。當要說明背後到底發生甚麼，得到的答案就是:「這就XX模型訓練出來的。」。這讓我覺得學這些很不踏實，用一些 python 的函式，其中裡面的演算法也沒看過，就直接拿去用。然後用完了看訓練結果怎樣來說明自己有沒有做對。如果剛好能夠訓練出來，準確度很高就說自己做對了。上這堂五週過後，我不覺得實力有很大的提升。但是這五週過後，讓我最有收穫的就是開始意識到當要用一個方法的時候，要理解背後原理後才能用。而這個就是能夠做跟別人不一樣的地方。過去都覺得我離自己的理想有很大的差距，我只知道要達到理想一定要努力，但這五週後，知道要彌補這個差距達到理想的方法之一了。
同時，我現在跟別人討論工作時，其他人如果說:「應該...。」，或是只說結果不說實作的具體細節，都讓我覺得這場對話是浪費時間，無法從中獲得任何資訊量。也因此現在寫測驗題或是程式的時候，我最後都會問自己一次，如果我的回答出現「應該...。」，我就會知道自己一定還沒想清楚，然後找到想法的漏洞就去補起來。這反映在寫程式前，需要確定的是寫程式的目的，寫程式的邏輯想法是否正確。如果這些都沒想清楚，那乾脆不要寫，否則就只是在錯誤的路徑徒勞無功。也因此我現在看到一些很複雜的邏輯，我都會自己在手寫演練，要確認每一個細節。避免看一行程式就猜想他是那樣的功能，所以務必要去驗證想法。
剛剛寫改進測驗 4 的第一題，我原先前幾天把那個 popcount 在 《Hacker's Delight》的環節看過一次，我還寫了筆記，也自己帶數字驗證，然而我剛剛改進的時候，竟然改到最後變成書裡面的想法。即便我讀過書了，思考過程中都沒有意識到自己正在經歷書中的思考論述。直到最後一刻把想法的程式寫出來，才發現這個就是前幾天看到的。所以念完書就算驗證後也不代表有真的吸收想法。
## 期末專題
### ttt
因為 tic-tac-toe 的作業有電腦跟電腦的對局，因為上到 CPU scheduler 的時候，我想去找時間去更理解process 跟 thread 。剛好在這個作業裡面的對局功能會有實作的機會。
### Linux 排程器研究
因為我想要做一個作業系統，然後從實作作業系統的過程就可以更了解作業系統了。然而要做出一個作業系統，還缺乏很多基本素養，所以想從小地方開始學習，想看完《Demystifying the Linux CPU Scheduler》。所以選這個當期末專題就可以花比較多時間讀這本書。
### [嵌入式向量圖形系統](https://www.facebook.com/groups/1531876370923589/?multi_permalinks=1579977659446793&ref=share&locale=zh_TW)
在這個專題可以了解 rect clipping 演算法，再用 Linux framebuffer 呈現，我希望能夠從這個專題學習到這件事情然後應用到嵌入式系統將他們投影到真實的環境中。
Sign in with Wallet
Connect another wallet