# 2024q1 Homework5 (assessment)
contributed by < `idoleat` >

## 測驗題改進
* quiz1 - quick sort: 設計效能評比的測試程式
* quiz4 - XTree: 與 AVL Tree, rbtree 比較並評比較能
* quiz3 - ilog2
* quiz3 - EWMA

## 題目構想與規劃

先把前六周的作業與 integration 做好做仔細，即將加入 Andes performance and solution team (一部分工作內容是執行 benchmark 程式，找出編譯器或硬體設計上的缺陷並回報給相關團隊)，對於細節掌握很重要。在寫作業時接觸到 Linux kernel 程式碼，體認到需要有足夠基礎及素養才有辦法理解並思考是否有改進空間，或是分析做出的改動會帶來什麼影響。前年修這門課的經驗是若是基礎知識不完備，在看比較艱深的教材時容易落入一知半解的困境，就算投入更多時間也不會有更深的理解 (scalability 不好) 。探討 information theory 的部份也可以順便加強我的論文中的分析。以前和同學的專案有使用亂數作為溝通對象的共識，但我仍不知我實作之亂數產生器的特性，顯然也需要加強。另外一個目標是要有足夠的能力可以自己持續探索並精進，並在有成果時供眾人檢視、接受批評指正

前 6 週之基礎也可以應用於其他在意細節與追求性能的場景例如遊戲引擎，Godot 內所使用之資料結構、memory allocator 皆依據其需求有[自己的實作](https://github.com/godotengine/godot/tree/master/core)，著名的 EA STL/StdC 也是，隨後要對 Godot 進行改善時會有幫助

### Linux 核心同步機制研究
我注意到近期 [futex2](https://lwn.net/Articles/866112/) 及 [userspace adaptive spinning](https://lwn.net/Articles/931789/) 的探討，不過背後牽涉的議題十分廣泛，我想先從以下小步驟開始
* 完成去年暑期課程的挑戰，熟悉現有 futex 及 locking 機制，包括參考 kernel 內的 locking 相關文件
* 完成前四周作業並閱讀 Demystifying the Linux CPU scheduler
* Profile guided scheduler (out-of-tree or sched_ext) for specific workload?
* 查看 git log 及 mailing list 上的討論紀錄，分析測試已提出之解決方法並參與討論
* 如何驗證正確性？
* 外部分析：重現問題 $\to$ 套用解法 $\to$ 再觀察問題 $\to$ 是否帶來其他問題
* 內部分析：要如何以全局的角度觀察並紀錄 kernel 及應用程式行為？而且每次執行紀錄僅為其中一種可能狀況
* 不同硬體平台

除了本身對並行的興趣，最近在協助數位音樂工作站 [Zrythm](https://zrythm.org/) 的開發，Audio app 本身屬於 soft realtime 應用程式（按下琴鍵或調整任何旋鈕、滑桿送出 midi 訊號到聽到聲音盡可能要在 20ms 以內），也牽涉到 audio thread priority inversion 問題，以上研究可以助益 Zrythm 接下來 v2 週期的開發。(另外有 Ubuntu studio, KX studio 這種針對低延遲音訊配置 kernel 的發行版，可以嘗試把他通用化例如做成 kernel module 不然還要改裝低音訊延遲 kernel 或發行版對一般使用者不友善)

時程規劃上有時間就盡量做

### 實作高效記憶體配置器

## 閱讀〈因為自動飲料機而延畢的那一年〉的啟發

與作者相同的是，我也是在即將退伍之際開始著手整理最近幾年發生的故事，包括和同學創業打造了將近千萬下載的遊戲的經歷，還有後續延伸至作業系統與分散式系統的探索等。不過這中間實在發生太多互相影響的事，錯綜複雜，我實在不想強制將[高維的世界投影至一維空間](https://byvoid.com/zht/blog/high-dimensional-world-and-unified-value/)做衡量與比較，所以還在撰寫中，試圖維持事情的原貌。寫完後會在此更新。不過可以先說的是，與作者相比，我們有從學校和許多單位拿到創業競賽獎金，沒有那麼刻苦耐勞，倒是我的成績比較刻苦耐勞差點搞到被退學。至目前為止，故事發展到我正在累積經驗與接觸各種問題，並開始著手建構一個生態系，其中一項基礎建設是為我們的需求開發 micro kernel，2022 年為其寫的[文件](https://hackmd.io/@idoleat/BknyYpPVt)有很多地方需要修改，包括剃除當下只是追逐潮流的東西，文件很久沒更新的原因在於想實際起身而行而不是一直用嘴巴寫程式，待有了實際成果文件就會隨之更新。系統軟體對上服務應用程式的需求，對下使用硬體的資源，開發者需要對兩者都了解，這意味著我還有很多地方需要探索

作者提到的軟體開發相比硬體，改正並重新實驗的週期實在短太多了，這點我相當同意，除了程式設計，遊戲設計上也是如此 playtest 一樣也是需要 test early, test often，再藉由觀察玩家反應做出修正。觀察玩家行為真的是很有趣的一件事。不過不停重新實驗真的試用每個場景嗎？如果只是漫無目的的亂戳並祈禱戳到可以接受的答案那何不多先多思考一下，不然就只是跟不會收斂的人工智慧模型一樣每次實驗皆是徒勞。硬體開發方面，一直都有一派的人是先從軟體模擬出發，例如這個[汽車引擎](https://www.youtube.com/watch?v=RKT-sKtR970)與[蒸氣引擎](https://www.youtube.com/watch?v=dzfjwXtATJA)，這在遊戲開發者之間是每隔一陣子就會有人挑戰的項目，這也是我追求的其中一個目標。目前的發展大多侷限於各家的自己的解決方法無法通用於每種需求，不論是機構、房屋結構、流體模擬等。遊戲引擎看似可以達到通用設計與模擬，但其中的物理引擎模擬還是需要在效率與精度之間作取捨，例如最常見的大尺度、大力、高速物體問題，每逢誤差大到不可接受時就只能用 work around 繞過去或是就乾脆請玩家拿出更好的硬體。若有高效通用實作，我最期待的就是實驗與教育的應用

## 前 6 週學習狀況

我覺得我在學習方式上需要改進。目前在學習過程中如果我發現我沒有真的理解，也就是沒有自己的想法、無法以我的方式闡述時，我會花很多時間想辦法弄懂他（例如作業一中 [string and stack](https://hackmd.io/@idoleat/linux2024-homework1#string-and-stack) 找出字串到底在哪），使得閱讀速度相當緩慢，有時候甚至只是我多想或誤會了就顯得浪費時間，string and stack 就是如此，或是單純就只是花比較多時間才理解。若是中途我冒出了自己額外的想法（例如作業一中[間接堆疊](https://hackmd.io/@idoleat/linux2024-homework1#間接堆疊)），就會像是 rabbit hole 一樣一路往下嘗試，回過神來已經落後進度很多。個人認為即便最後嘗試結果有可能缺陷重重，但採坑也是一種經驗，如果能證明出一定達不到某結果更好，一如 100 impossibilities in distributed system 一樣。不過碩班以這種方式從頭塑造我的研究主題與結果是因為時間足夠，如此作法放在此課程會造成自身困擾。更別說其實有人可以做得又快又深入，像某些進度很快的同學（瀏覽他們共筆我總懷疑他一天是不是有 48 小時）我很是羨慕，更突顯只是我能力不足，而且參與小考以及閱讀課堂問答紀錄一樣可以發現我並不是每個地方都真的懂。

短時間內快速理解抓到關鍵點是一項重要的能力，像每週測驗就是在考驗這種能力，與他人合作時也沒有多少時間可以這樣慢慢摸，時間到產品該上線就是要上線。目前我有觀察到我在興奮狀態下是例外，可以同時快速思考和閱讀，可以多濫用這個大腦反應。

作業上如果有地方卡住了，也許可以先做其他部份，先達到大部分作業預期目標之後再加強細節，一直卡在同個地方效率十分低落。不確定其他人是否有一樣的問題，但是以我的狀況來看我會需要做出這樣的改進。或是需要一個感覺上十分危急的死線來刺激腎上腺素來突破極限。作業進度緩慢也連帶影響到我無法 review 其他同學的作業因為我會希望對於要解決的問題要先有自己的想法再去融合其他人的想法，以免被牽著鼻子走也錯失有新點子的機會。上方描述學習方式的段落也是「要有自己的想法」造成的習慣，有與在海帶芽的朋友討論過，他覺得要看哪種方式適合自己，否則虛幻的進度都是虛幻的，像他是需要大量閱讀來刺激靈感的因此先看在思考。而我在作業二理解並改進測驗中的 quick sort 前我有先花了蠻多時間用維度先思考排序是什麼，在作業一開頭用 graph 描述排序，雖然最後都沒有什麼新突破不過至少理解到排序是在重新連結節點之間的關係，所以自然在實作合併鍊結串列時不會配置記憶體。從高中煩惱這樣到底好不好到現在，依然沒有好答案。不過這邊講的例子一部份是受數學系的大學室友和在海帶芽的朋友啟發，他們總能用數學嚴謹的表達想法並且加以延伸使得我也向他們學習。前六週的教材也強調了數學對分析和觀察的重要性。

教材上

## Concurrency Primer
需要對於為何 RWM 有更詳細的解釋，否則看到 Ch 7.1 與 Ch 10 的範例不須 atomic 會有些令人困惑。
範例為：

#include <stdatomic.h>
atomic_int foo;

int getFoo()
{
    return foo;
}

void setFoo(int i)
{
    foo = i;
}

void incFoo() 
{
     ++foo; 
}

可以多加以下解釋：
之所以要 read, modify, write 而不是直接 write 是因為此運算是基於當下的狀態再做修改，最後寫回記憶體。先 read 代表前一次運算的結果對本次運算可見，而定立了前一次運算與這次運算的順序關係，即前一次運算 happens-before 本次運算。`++foo` 屬於此類。若沒有先 read，直接 write 則表示此運算並不需要與其他運算有任何順序關係，因此不需要 RMW 一氣呵成，`foo = i` 屬於此類

不過使用 compiler explorer 發現
ARM64 GCC: https://godbolt.org/z/3qK196jes
x86_64 GCC: https://godbolt.org/z/z45Enn6hv
x86_64 是使用 `lock` prefix 配 `xadd`，arm 甚至連 `dmb` 都沒有？
> 以 Arm64 來說，留意到 godbolt 輸出的 `__aarch64_ldadd4_acq_rel` 符號，搭配看 [Large System Extensions for AWS Graviton Processors](https://dev.to/aws-builders/large-system-extensions-for-aws-graviton-processors-3eci) 的反組譯結果和分析。 :notes: jserv