2025-08-09 –, TR213
本議程介紹 Linux Kernel 中通用 min heap 函式庫的實作細節與維護經驗，內容涵蓋多項與效能與可擴充性相關的工程決策。我們使用 bottom-up variant 的 heapify 方法，能在一般情況下有效減少約 50% 的比較次數，但在 bcache 等場景中，當 heap 中存在大量重複元素時，該演算法會退化至 O(log n) 時間複雜度。因此我們提供兩種不同的 heapify API，讓使用者可依據資料特性進行選擇。
此外，我們使用 prescale counter 技術減少乘法指令的使用，並處理 retpoline 引入後間接函式呼叫效能下降的問題。原本透過 always_inline 避免間接呼叫開銷，但為控制 kernel 映像大小，後續改為非 inline 實作。
最後，為支援多種型別，我們以 C 巨集實作泛型機制，提供類似 C++ template 的使用體驗，並加上編譯期型別檢查以增強穩定性。整體實作考量效能、可維護性與靈活性，適合對資料結構實作與核心效能調整有興趣的聽眾。
Linux kernel 開發、系統程式設計、或對 kernel 資料結構實作有興趣者
Difficulty:初學者
邱冠維目前就讀於國立陽明交通大學資訊科學與工程研究所，專注於作業系統與系統軟體的設計與優化。目前是 Linux Kernel 中 min heap 函式庫的維護者，並長期投入於開源專案的開發與維護，關注底層架構效能、可攜性與程式碼品質等議題。過去也曾在 Yahoo、Logitech、Google 與 AMD 等公司實習，具備豐富的系統軟體開發經驗。
Kuan-Wei Chiu is currently a graduate student at the Institute of Computer Science and Engineering, National Yang Ming Chiao Tung University, focusing on operating systems and systems programming. He is the maintainer of the min heap library in the Linux Kernel and has been actively involved in the development and maintenance of open source projects, with particular interest in low-level performance, portability, and code quality. He has previously interned at Yahoo, Logitech, Google, and AMD, gaining extensive experience in systems software development.