# 2024q1 Homework5 (assessment)
contributed by < `david965154` >
## 前 4 週的測驗題選出 3 題改進
### 1. [第 2 周測驗 `3` ](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3)
考慮 find_nth_bit 可在指定的記憶體空間找出第 N 個設定的位元 (即 1)
#### `fns` 函式改進
**改進程式碼，並做實驗比較**
```c
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
unsigned long mask = BIT_MASK(nr);
unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
*p &= ~mask;
}
/* find N'th set bit in a word
* @word: The word to search
* @n: Bit to find
*/
static inline unsigned long fns(unsigned long word, unsigned int n)
{
while (word) {
unsigned int bit = __ffs(word);
if (--n == 0)
return bit;
__clear_bit(bit, &word);
}
```
改為以下，可將 Time complexity 從 `n` 降為 `log(BITS_PER_LONG)` ，即 constant
```c
/* find N'th set bit in a word
* @word: The word to search
* @n: Bit to find
*/
static inline unsigned long fns(unsigned long word, unsigned int n)
{
unsigned long sum = 0;
unsigned int bits = 0;
#if BITS_PER_LONG == 64
bits = __const_hweight32(word);
if (bits <= n) {
n -= bits;
word >>= 32;
sum += 32;
}
#endif
bits = __const_hweight16(word);
if (bits <= n) {
n -= bits;
word >>= 16;
sum += 16;
}
bits = __const_hweight8(word);
if (bits <= n) {
n -= bits;
word >>= 8;
sum += 8;
}
bits = __const_hweight4(word);
if (bits <= n) {
n -= bits;
word >>= 4;
sum += 4;
}
bits = __const_hweight2(word);
if (bits <= n) {
n -= bits;
word >>= 2;
sum += 2;
}
bits = (unsigned int) (word);
if (bits <= n) {
n -= bits;
word >>= 1;
sum += 1;
}
bits = (unsigned int) (word);
if (bits <= n) {
n -= bits;
sum += 1;
}
if(!n)
return sum;
return BITS_PER_LONG;
}
```
有些想法及最後結果我寫在[詳細內容](https://hackmd.io/@david96514/HJoPc_YeR)，我認為在一開始沒去仔細 trace code 時會有一些問題，像是如果最後 n 為 1 而且 `__const_hweight2(word & 0x3)` 也回傳 1 是否會得錯誤位置，因為 `0x3` 有兩位，可能出現在 `0` 及 `1`。
但在比較整段程式碼 ( 即第 2 周測驗 3 ) 執行的效率時，我發現沒辦法有個明確的結果。
**為何無法做實驗比較** ?
我使用了 a (0~測試輪數)作為 random seed，而我不管如何測試，結果皆不相同。即使我兩次都使用一模一樣的函式仍會得出不同結果，也不是像 fns 的測試一樣有著明顯的就是一邊效率較高，而是不斷交替。因此我只好放棄小地方的改動。
在後來邱冠維同學提出了更簡短並使用 `Brian Kernighan’s Algorithm` 達成的程式碼片段。
```c
static inline unsigned long fns(unsigned long word, unsigned int n)
{
while (word && n--)
word &= word - 1;
return word ? __ffs(word) : BITS_PER_LONG;
}
```
而 Yury Norov ( linux 核心開發者)，也提出了與我類似的二分法去計算 fns ，不過此種程式碼最大的問題是會在 n 較小時效能甚至補原本的較差，不過 Yury Norov 提到，分佈既然是隨機的那就應該以整體效能來看，而非僅去觀察較小的部分。後來 Linus Torvalds 對此提出討論需中止，原因如下
>making that code header file bigger and compiles slower, and
there are *no* actual numbers to show that any of this matters.
在不常使用的的函式卻花了大量的 code size 去處理是不必要的，不但大幅增加了編譯時間，也增加了 code 本身的大小，因此應該最後會以邱冠維同學的程式碼來去改善原始程式碼。
### 2. [第 3 周測驗 `2` ](https://hackmd.io/PIEjXeR4SAuxeeO8K-rQaA?both#%E6%B8%AC%E9%A9%97-2)
不依賴任何除法指令的 `% 9` (modulo 9) 和 `% 5` (modulo 5) 程式碼
> 實作不同於《Hacker's Delight》的程式碼
```c
void divmod_9(uint32_t in, uint32_t *div, uint32_t *mod)
{
while(in >= 9){
unsigned long high = __fls(in) - 3;
in -= (9 << high);
*mod += (1UL << high);
}
*div = in;
}
```
函式解釋:
`__fls` 尋找最高位 1 之位置，並 `in` 減去 `1001 (9)` 左移 `__fls - 3` 位，
觀察以下:
```
in = 182
in = 10110110
- 10010000 1001 << (__fls(in) - 3) 即左移 4 位
mod += (1UL << (__fls(in) - 3)) 16
in = 10110110
in >= 9 進入出迴圈
in = 00100110
- 00100100 1001 << (__fls(in) - 3) 即左移 2 位
mod += (1UL << (__fls(in) - 3)) 4
in = 00000010
in < 9 跳出迴圈
in = 00000010
div = in 得到商數 20 餘數 2
```
而 `-3` 是因為避免左移後超出 `__fls(in)` 之位置。
```c
void divmod_5(uint32_t in, uint32_t *div, uint32_t *mod)
{
while(in >= 5){
unsigned long high = __fls(in) - 2;
in -= (5 << high);
*mod += (1UL << high);
}
*div = in;
}
```
而 `divmod_5` 同理，不過若可以實作相同於《Hacker's Delight》的程式碼，那麼寫成以下會更佳，直接利用 10 = 5\*2 ，沿用 `divmod_10` 之程式碼
```c
void divmod_5(uint32_t in, uint32_t *div, uint32_t *mod)
{
divmod_10(uint32_t in, uint32_t div, uint32_t mod)
*div <<= 1;
if(*mod >= 5){
*div += 1;
*mod -= 5;
}
}
```
### 3. [第 4 周測驗 `1` ](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3)
改進 `1` :
避免重複計算導致最後要右移 `1` 位， `j` 改以從 `i+1` 開始，而非 `0` 。
```c
int totalHammingDistance(int* nums, int numsSize)
{
int total = 0;
for (int i = 0;i < numsSize;i++)
for (int j = i+1; j < numsSize;j++)
total += __builtin_popcount(nums[i] ^ nums[j]);
return total;
}
```
改進 `2` :
若一次輸入多個字串需要同時計算 Total Hamming Distance ，改以利用所有 Number 中從第 0 個 bit 開始計算全部該 bit 的 Hamming Distance。
使時間複雜度 $O(n)$ (bit 數不被輸入數量影響，只與作業系統有關)。
```c
int totalHammingDistance(int* nums, int numsSize)
{
int total = 0;
int num_1s = 0;
int displace = 0;
int bits = 32;
for (int i = 0;i < bits;i++){
for (int j = 0; j < numsSize;j++){
num_1s += ((nums[j]>>displace) & 0x1);
-(~displace);
}
total += num_1s * (numsSize - num_1s);
}
return total;
}
```
## 因為自動飲料機而延畢的那一年
> 我做了這麼多努力，一點屁用都沒有啊
>
> 加冰沙是會死膩，冰沙也很棒啊，誰不喜歡冰沙啊，大家小時候不是都很喜歡喝冰沙嗎
>
> 為什麼分配冰塊這麼難，我寫程式寫了三年，沒想到卻栽在這個小小的冰塊上啊
會寫程式但現實不需要你所寫的程式，這大概是對學資工的人的最大的傷害，卻也是需要面對的課題，現實問題並非上網尋找同路人就可以解決，就是因為目前沒解答才被需要。
作者從最初打算以 3D 列印及最低運算去完成這個目標因為現實而妥協。自己在短期的付出根本無法與他人花了數年心血打造的成果比擬，雖然不服但也不得不向資本主義低頭。最後也因現實將一個自動飲料機完整的流水線轉為投冰、倒飲料，這大概就是「誠實面對自己」的最好範例。
不過最終作者還是完成了，看似簡單的 2 道工序卻花了 3 人的 14 個月，況且這三人都有大量的付出，在努力及金錢都是。這大概也是我在修這堂課之前的心境，幻想著自己有機會為 linux 核心程式碼提出貢獻，不過事實上卻是一個作業都沒全部完成，教材也沒讀完。更不敢在自己的筆記上寫著會在之後補上，因為事實就是不會補。現在每一次去點開別人作業的筆記時都只會感到自己的不足，閱讀其他教材以解釋並做實驗，更甚者設計新的寫法去改進現有的實作，這些也是我該學習的。
寫這次作業給我的啟發應該是目前最多的，這幾天每天起床到睡前都是在做前面的改進，花了整 2 天結果幾乎回到原點([詳情](https://hackmd.io/@david96514/ryyZfLOeA))，不過最無奈的是我根本沒這麼多時間可以給我浪費，到了交作業前兩天我只寫出一題改進，讓我覺得 「因為自動飲料機而延畢的那一年」 裡面的 「一項產業進步的速度，很大程度取決於做實驗修正問題的速度。」應該改成 「一項產業進步的速度，很大程度取決於發現問題並做實驗修正問題的速度。」。我一開始就發現問題，但我的問題是錯的問題，因為他根本就沒問題，而發現問題的當下很高興而不是去求證也很有問題。
其實要測試整個函式的時候有翻到 Linux 中的測試函式，但我不知道怎麼使用且找不到測試函式內呼叫的函式。直到這幾天做下來大概懂了一些函式內容再回頭看，才發現讓我如此狼狽的是一個 「從哪裡開始」 的概念。
這幾天都在看位元操作的相關函式其實讓我產生了些許興趣，漸漸習慣去使用位元操作取代加減乘除，也能比較容易讀懂位元運算，算是一大收穫。
## 研讀 CS:APP 3/e
第一章:
1.9.2 參考 [並行程式設計: 概念](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts)
Concurrency 指程式架構，將程式拆開成多個可獨立運作的工作，像是驅動程式都可獨立運作，但不需要平行化。
Parallelism 則指程式執行，同時執行多個程式。
Concurrency 可能會用到 Parallelism，但不一定要用 Parallelism 才能達成 Concurrency。在 Concurrent 中，工作可拆分成「獨立執行」的部份，於是「可以」讓很多事情一起做，但「不一定」要真的同時做。但 Parallelism 著重規劃，將能夠並行的程式，分配給不同硬體單元，使其同時執行。
第二章:
:::warning
看到 2.2.1 的 unsigned long 的上下限時想到，為什麼 linux 核心程式碼會將不太可能出現這麼大的值的變數卻使用類型 unsigned int 而不是 unsigned short? 不是能節省更多空間嗎?
:::
2.2.8 有個蠻有趣的實例，需要注意傳遞與接受變數類型相同，以避免透過此漏洞存取到其他記憶體位置的資訊
## 想投入的專案
1. [回顧 Linux 核心的 bitops 並尋求貢獻程式碼的機會](https://hackmd.io/@sysprog/linux2023-projects#%E5%9B%9E%E9%A1%A7-Linux-%E6%A0%B8%E5%BF%83%E7%9A%84-bitops-%E4%B8%A6%E5%B0%8B%E6%B1%82%E8%B2%A2%E7%8D%BB%E7%A8%8B%E5%BC%8F%E7%A2%BC%E7%9A%84%E6%A9%9F%E6%9C%83)
不過經過上面跟著邱冠維同學與 linux 核心開發者一同提出改善程式碼的時候，整理了若想要改善 linux 核心程式碼，那麼你需要考慮
1. 提出的改善程式碼需正確
2. 考量到使用的程式碼是否適合所有硬體
3. 完整的測試，需掛載於核心並在開機時執行，避免排程器影響
4. code size 非常重要，除非帶來的效益能超過你所花費的成本，大量的 code size 並沒有意義
5. 若需要改成 lookup table ，須盡量符合 cache size 64B ，不過這也會佔據大量的 code size
6. 提出的程式碼真的是 optimize 嗎? 在提交 patch 時，開發者於其他維護者會提出其他改進方法。此時若無法提出證據佐證你得更好，或提出更好的，那麼這場對話你才是被改善那個。
雖然我並未直接參與對話，但我知道我就算沒參與我也已經成為被改善的那一個了，不過也因此學到非常多。
2. [位元操作](https://hackmd.io/@sysprog/linux2023-projects#%E4%BD%8D%E5%85%83%E6%93%8D%E4%BD%9C)
正如上面提到的，因為這次的作業使我接觸了較多的位元操作，讓我也產生較大的興趣，因此我選擇了以上兩項作為想投入的專案。即使自己沒辦法對這裡做額外的貢獻，仍希望有更深入的學習機會。
3. [針對 rv32emu 實作 JIT 編譯器](https://hackmd.io/@sysprog/linux2023-projects#%E9%87%9D%E5%B0%8D-rv32emu-%E5%AF%A6%E4%BD%9C-JIT-%E7%B7%A8%E8%AD%AF%E5%99%A8)
會選這個是因為我想去挑戰較不熟悉的領域，因為作者是老師，有問題可以馬上解決，不會浪費時間在我自己造的坑裡，無須費心上網找可能是錯誤的答案。再者因為沒有答案，也就是上面的文章「需求才被人們需要」的心得，因此選這個專案是再也好不過的學習機會。
---
TODO: 重現 [回顧 bitops 並改進](https://hackmd.io/@sysprog/ByS9w_lHh) 實驗，針對 Linux v6.8+ (Ubuntu Linux 24.04 搭配的 Linux 核心版本)
TODO: 針對上述 bitops 改進，提出驗證的方式，如 Linux 核心模組, UML (見[建構 User-Mode Linux 的實驗環境](https://hackmd.io/@sysprog/user-mode-linux-env)) 或 [virtme](https://hackmd.io/@sysprog/linux-virtme)，比對產生的機械碼 (至少是 x86-64 和 Arm64)，確保提出的改進方案在「行為」層面相容於原有的實作
TODO: upstream! based on [Quiz 7](https://hackmd.io/@sysprog/linux2024-quiz7)
> 修訂[開平方根的快速計算](https://hackmd.io/@sysprog/sqrt)
Sign in with Wallet
Connect another wallet