不算最大公因數也能做環狀分解:OpenJDK 旋轉演算法的一個小聰明
Standard C++ Blog · 2026-08-03
Standard C++ Blog 在 2026-08-03 轉載了 Raymond Chen 的一篇文章,主題是陣列旋轉(array rotation)裡常見的「環狀分解」演算法,如何在不預先計算最大公因數(GCD)的情況下,正確找出所有交換環。文章以 OpenJDK 的 Collections.rotate() 實作為例,對照 C++ 標準函式庫慣用的 GCD 版本 std::rotate。這是一個純演算法層面的技巧,沒有涉及規格變動,但對任何要手寫旋轉或環狀置換邏輯的人都有參考價值。
背景
陣列旋轉的目標是把 [first, last) 範圍內、以 middle 為分界的兩段互換位置,且只用 O(n) 次搬移、O(1) 額外空間完成。經典解法是把整個陣列看成一個置換(permutation):每個位置 i 最終要移到 (i + a) % n(a 為旋轉量、n 為總長度),這個置換會分解成若干個不相交的環。要不重複、不遺漏地走完所有環,傳統做法是先算出 g = gcd(n, a),因為可以證明這個置換恰好有 g 個環,且 0 到 g-1 這 g 個起點剛好各屬於一個不同的環。libstdc++、libc++ 的 std::rotate 都是這樣寫的。
核心改動
問題在於算 GCD 本身也是一筆開銷,尤其在旋轉量或陣列長度很小、呼叫次數很密集的情境下。OpenJDK 的 Collections.rotate() 換了個角度:與其先知道有幾個環,不如直接數「搬了幾個元素」,搬滿 n 個就代表所有環都處理完了。這個做法把同一個數論事實反過來用:因為每個元素恰好屬於一個環,所有環的長度加總必然等於 n,所以只要 cycleStart 依序取 0, 1, 2, ... 去起始新環,累計搬移數 nMoved 到達 n 的那一刻,必然正好對應 cycleStart 走完 0 到 g-1——迴圈會在觸碰到任何「已經處理過」的位置之前自然終止,完全不必事先知道 g 是多少。實際程式碼大致是:
for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
Object displaced = list.get(cycleStart);
int i = cycleStart;
do {
i += distance;
if (i >= size) i -= size;
displaced = list.set(i, displaced);
nMoved++;
} while (i != cycleStart);
}相較之下,GCD 版本需要先呼叫 std::gcd(n, a),再用一個 for (i = 0; i < g; ++i) 迴圈逐一處理每個環的代表元素。兩者搬移元素的總次數完全相同,差別純粹在於要不要先花一次輾轉相除法的成本去弄清楚環的數量。
影響範圍
這個技巧目前只出現在 OpenJDK 的集合工具類裡,C++ 標準函式庫尚未跟進——Raymond Chen 的文章本身也只是分析比較,並未提出要改 libc++ 或提案修改標準。但對任何自行實作旋轉、環狀緩衝區重排或原地置換演算法的工程師來說,省掉一次 GCD 呼叫在高頻率、小規模資料的情境下仍是可觀的常數因子優化,尤其是在目標平台除法成本較高、或不方便引入 <numeric> 時更明顯。
FUSE io_uring 的緩衝區大小難題:大 I/O 的空間怎麼餵給小請求
LWN.net · 2026-08-03
LWN.net 在 2026-08-03 刊出一篇會後報導,記錄 Bernd Schubert 今年五月在 Zagreb 舉行的 2026 年 LSFMM+BPF(Linux Storage, Filesystem, Memory Management, and BPF Summit)檔案系統議程上,針對 FUSE io_uring 緩衝區大小提出的疑慮:目前實作用單一固定大小的大緩衝區服務所有請求,對大量小型 I/O 與中繼資料(metadata)請求而言是明顯的記憶體浪費。這篇文章本身位於訂閱牆後,要到 2026-08-13 才會開放全文,以下內容根據相關郵件討論串與核心文件補充背景。
背景
FUSE(Filesystem in Userspace)讓檔案系統邏輯留在使用者空間,傳統上核心與使用者行程透過 /dev/fuse 裝置檔的 read()/write() 一來一往傳遞請求,每個請求都要一次系統呼叫與情境切換。FUSE-over-io-uring 這個由 Bernd Schubert(DDN)主導、陸續併入主線的功能改用 io_uring 佇列取代這條路徑:每個 CPU 核心各自擁有一條佇列,使用者行程先送出帶有 FUSE_URING_REQ_REGISTER 的 IORING_OP_URING_CMD 完成註冊,之後核心便直接把請求塞進對應核心的環狀佇列,省去逐請求的系統呼叫。
核心改動
問題出在緩衝區的配置方式:每條佇列的每個環項目(ring entry)在註冊時就配置好、供之後所有請求共用的緩衝區,而這個大小得抓得住最大可能的請求(例如大區塊讀寫)。Schubert 在郵件討論中講得很直白:「Small IOs and metadata requests do not need large buffer sizes, we need multiple IO sizes per queue」——像 stat、lookup、getattr 這類中繼資料操作,或是小區塊讀寫,其實根本用不到專門為大檔案 I/O 保留的緩衝區,但目前每條佇列只有一種尺寸可選。
目前檯面上的技術方向是 Joanne Koong 主導的核心管理緩衝環(kernel-managed buffer ring,簡稱 kmbuf),透過新增的 IOBL_KERNEL_MANAGED 旗標,把緩衝區的提供與回收邏輯交還給核心,而非要求使用者端事先固定配置,並支援「增量消耗」讓同一塊緩衝區被多個請求接力使用。同系列另一份較早公開的 io_uring 補丁測試顯示,在 passthrough_hp 伺服器、1MB 區塊大小下,直接隨機讀取吞吐量從約 2100 MB/s 提升到 2600 MB/s,緩衝隨機讀取則從 1900 MB/s 提升到 2400 MB/s。
影響範圍
這仍是 LSFMM+BPF 現場討論後尚未定案的方向,不代表已合併進主線;Schubert 提出的「每條佇列支援多種 I/O 大小」與 Koong 的核心管理緩衝環是兩條互補的路線,前者處理配置策略、後者處理緩衝區生命週期管理,兩者都指向同一個痛點:目前 FUSE io_uring 的記憶體占用是用最壞情境(大 I/O)去餵最常見的情境(中繼資料與小 I/O)。實際採用何種方案要等後續補丁與 LWN 全文釋出後才能確認。
Linux 7.2-rc6 發布:Linus 直呼「這一版大得不尋常」
LWN.net · 2026-08-03
Linus Torvalds 在 2026-08-02 發布 Linux 7.2-rc6,LWN.net 隔日刊出摘要報導。兩個版本之間累積了 537 個非合併(non-merge)commit,Torvalds 在公告裡直言:「This rc is huge... I think it's the biggest rc6 we've had in years at least by commit count.」——這是近年來按 commit 數計算最大的一次 rc6。
核心改動
依 Torvalds 的說法,這次改動的組成大致是驅動程式將近六成、網路子系統約兩成,其餘兩成分散在架構相關程式碼、工具鏈與檔案系統。他把規模暴增歸因於兩個因素:一部分是 AI/LLM 產生的補丁,他稱之為「new normal」;另一部分則是研討會後累積的網路子系統補丁回補潮。音效子系統維護者 Takashi Iwai 也提到,rc6 前送進來的 sound 修正比預期大得多。
具體修正裡比較顯眼的一項,是 x86 CPU 識別邏輯的更正:先前的補丁把 AMD Family 1Ah 底下 0xd0 到 0xef 的型號都歸類為 Zen 6,但其中 0xd0 到 0xd7 其實是 Zen 5 保留的編號。這次的 x86 fixes pull 把 0xd0-0xd7 劃回 Zen 5,Zen 6 則改對應 0xc0-0xcf、0xd8-0xef、0x50-0x5f 與 0x80-0xaf 幾個區段,避免受影響的處理器被核心誤判成下一代架構。此外 rc6 還包含針對故障 Western Digital Red Plus 硬碟的 ATA quirk,以及一輪 DRM 驅動程式清理——Torvalds 形容這輪 DRM 改動「看起來讓人有點不安,即便沒有哪一項改動本身顯得可疑」。
影響範圍
儘管規模異常龐大,Torvalds 並未表示這會延後排程,Linux 7.2 正式版預期仍照原訂時間、於八月中旬左右發布。rc6 之後照慣例只剩少數幾輪穩定修正的空間,若後續 rc 沒有出現需要延後的重大問題,7.2 將維持標準的七到八週開發週期收尾。
原始來源:LWN.net