# 2024-04-30, 05-02 討論簡記

:::success
"**You never fail until you stop trying.**"
― Albert Einstein
(當你停下嘗試的腳步，就意味著失敗)
:::

## fns 的改進
> [[PATCH] bitops: Optimize fns() for improved performance](https://lore.kernel.org/mm-commits/[e-mail]/)

[第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)的測驗 3：「考慮 `find_nth_bit` 可在指定的記憶體空間找出第 N 個設定的位元」，取自 Linux 核心的 `fns` 函式，引導學員提出改進。
[FNS 比較](https://hackmd.io/@david96514/HJoPc_YeR)
> 延伸閱讀: [Refining Data Structure Implementations in the Linux Kernel for Improved Performance](https://youtu.be/3Wk8fZVdbZo)

## zack-404
> [Homework5](https://hackmd.io/@zack-404/2023q1Homewotk5)

第三週 - 浮點數

$ python
>>> 0.1 + 0.2 == 0.3
False
>>> 0.1 + 0.2
0.30000000000000004
>>> 0.3
0.29999999999999999

如何讓 0.1 + 0.2 == 0.3 成立

不同語言會有不同的 $\epsilon$ 去界定相等

python: `float_info.epsilon = 2.2e-16`
c++: `std::numeric_limits<float>::max_digits10 = 6`

## jimmy01240397
> [Homework1](https://hackmd.io/@Jimmy01240397/linuxkernal2024-homework1)

https://github.com/torvalds/linux/blob/master/lib/list-test.c

以計算機結構來講為何會比較快：
1. 降低分支
2. cache

commit c0d15cc7ee8c0d1970197d9eb1727503bcdd2471
Author: Dave Jones <[e-mail]>
Date:   Tue Jul 16 22:44:08 2013 -0400

    linked-list: Remove __list_for_each

commit 75d65a425c0163d3ec476ddc12b51087217a070c
Author: Linus Torvalds <[e-mail]>
Date:   Thu May 19 13:50:07 2011 -0700

    hlist: remove software prefetching in hlist iterators

## 164253
### 如何有效的測試 sort
#### 背景狀況
現有的 kernel 在 lib 下有 test_sort.c 和 test_list_sort.c 兩筆測試，但觀察可以發現實作上十分簡陋，是否穩定、原地排序、最差狀況等都沒有測試，同樣的 rbtree_test.c 也沒有測試速
這點和我原先的預期差距極大，這麼大一個 linux kernel 居然連基本的時間複雜度都沒測。

#### 過於複雜的測試方法
由於考慮到潮汐現象(此處特指測試程式常因外部干擾，造成時間浮動極大)，我原本提出測多種不同的資料總數，並微分且計算增長率，推斷是 $n^2$ 或 $n\log_2n$ 。
但老師指出潮汐現象在 kernel 中容易解決，只需要在測試時禁止搶占、並關掉或暫停終端等，因此不是嚴重的問題。
且對於 kernel 來說，需要的是較簡易且大致的測試，需要考慮每次測試不能有太大的時間成本，先提供較主要的測試內容，細節交由開發者處理即可。

#### 改進的方法
意料之外的，就和各類競賽一樣，由於一秒可以估算為能跑 $10^8\sim10^9$ 個運算，帶入 $n=5\times10^5$ 和 $n=10^6$ 就可大致排除 $n^2$ 的作法，且每次測試僅需一秒。
而我原先也提出可能會卡常數等問題，但可以用 linux kernel 中現有的實作估算常數。

#### kernel 中其他類似的不足
顯然的， lib 中 test 系列之程式碼都有些簡陋，例如 rbtree, hashtable 和其他常見的資料結構。
尤其 hashtable 甚至沒有對多個相同 key 的複雜度做測試。
rbtree 也仍是教科書上常見的實作方式，而不是競賽中數年前一致認定程式碼極短又簡潔、速度更快、且支援所有 treap 和 splay tree 操作的范浩強無旋 treap 。
(註：范浩強 treap 其中一個重要部分就是根據馬可夫鍊，以保證樹的平衡，也因此保證比起旋轉這種高成本的操作，用切割替代是不會造成錯誤的方法)
> 先前有人提過相同的改進，但最後未獲收錄，待寫出完整測試並確認速度

#### 額外發現的效益
長期以來潮汐效應對競賽圈是非常嚴重的困擾，記憶體限制也常是用 page fault 等方式偵測，而使用者塞入惡意程式碼，更改答案或偷看測資，或者試圖癱瘓系統等問題更沒有有效的解決方法，現有處理是開一個沙箱，然後賭大家打不穿他。
lab0 中對記憶體的處理方式，以及上述的潮汐解決方法，對競賽都是有重大效益的東西。
> 額外的待解決問題：如何解決拿到 pid 後，被 kernel 回收而程式卻不知道的現象。

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

`getcpu()`, `putcpu()` 如何實作？

---

:::info
:information_source: 若你想在課堂討論，請標示 GitHub 帳號名稱，伴隨著第五次或第六次作業的超連結。
:::

> [2024 年開放原始碼專案協作](https://hackmd.io/@sysprog/ByLJ8DUFT)

## SHChang-Anderson

## LULser0204
https://hackmd.io/@LULser/linux2024-homework5

lvalue C99 6.3.2.1 p.46
>The name ‘‘lvalue’’ comes originally from the assignment expression E1 = E2, in which the left operand E1 is required to be a (modifiable) lvalue. It is perhaps better considered as representing an object ‘‘locator value’’. What is sometimes called ‘‘rvalue’’ is in this International Standard described as the ‘‘value of an expression’’.

>An obvious example of an lvalue is an identifier of an object. As a further example, if E is a unary expression that is a pointer to an object, *E is an lvalue that designates the object to which E points.

## marvin0102

## HenryChaing

我 kernel module 無法 rmmod.