sysprog
      • Sharing URL Link copied
      • /edit
      • View mode
        • Edit mode
        • View mode
        • Book mode
        • Slide mode
        Edit mode View mode Book mode Slide mode
      • Customize slides
      • Note Permission
      • Read
        • Owners
        • Signed-in users
        • Everyone
        Owners Signed-in users Everyone
      • Write
        • Owners
        • Signed-in users
        • Everyone
        Owners Signed-in users Everyone
      • Engagement control Commenting, Suggest edit, Emoji Reply
      • Invitee
    • Publish Note

      Share your work with the world Congratulations! 🎉 Your note is out in the world Publish Note

      Your note will be visible on your profile and discoverable by anyone.
      Your note is now live.
      This note is visible on your profile and discoverable online.
      Everyone on the web can find and read all notes of this public team.
      See published notes
      Unpublish note
      Please check the box to agree to the Community Guidelines.
      View profile
    • Commenting
      Permission
      Disabled Forbidden Owners Signed-in users Everyone
    • Enable
    • Permission
      • Forbidden
      • Owners
      • Signed-in users
      • Everyone
    • Suggest edit
      Permission
      Disabled Forbidden Owners Signed-in users Everyone
    • Enable
    • Permission
      • Forbidden
      • Owners
      • Signed-in users
    • Emoji Reply
    • Enable
    • Versions and GitHub Sync
    • Note settings
    • Engagement control
    • Transfer ownership
    • Delete this note
    • Insert from template
    • Import from
      • Dropbox
      • Google Drive
      • Gist
      • Clipboard
    • Export to
      • Dropbox
      • Google Drive
      • Gist
    • Download
      • Markdown
      • HTML
      • Raw HTML
Menu Note settings Sharing URL Help
Menu
Options
Versions and GitHub Sync Engagement control Transfer ownership Delete this note
Import from
Dropbox Google Drive Gist Clipboard
Export to
Dropbox Google Drive Gist
Download
Markdown HTML Raw HTML
Back
Sharing URL Link copied
/edit
View mode
  • Edit mode
  • View mode
  • Book mode
  • Slide mode
Edit mode View mode Book mode Slide mode
Customize slides
Note Permission
Read
Owners
  • Owners
  • Signed-in users
  • Everyone
Owners Signed-in users Everyone
Write
Owners
  • Owners
  • Signed-in users
  • Everyone
Owners Signed-in users Everyone
Engagement control Commenting, Suggest edit, Emoji Reply
Invitee
Publish Note

Share your work with the world Congratulations! 🎉 Your note is out in the world Publish Note

Your note will be visible on your profile and discoverable by anyone.
Your note is now live.
This note is visible on your profile and discoverable online.
Everyone on the web can find and read all notes of this public team.
See published notes
Unpublish note
Please check the box to agree to the Community Guidelines.
View profile
Engagement control
Commenting
Permission
Disabled Forbidden Owners Signed-in users Everyone
Enable
Permission
  • Forbidden
  • Owners
  • Signed-in users
  • Everyone
Suggest edit
Permission
Disabled Forbidden Owners Signed-in users Everyone
Enable
Permission
  • Forbidden
  • Owners
  • Signed-in users
Emoji Reply
Enable
Import from Dropbox Google Drive Gist Clipboard
   owned this note    owned this note      
Published Linked with GitHub
Subscribed
  • Any changes
    Be notified of any changes
  • Mention me
    Be notified of mention me
  • Unsubscribe
Subscribe
# 2025-05-20 問答簡記 ## 從「四邊包繩-不打洞」看 Linux 核心記憶體模型 ![0-world](https://hackmd.io/_uploads/S1YEH9D-xl.jpg) 近日「四邊包繩-不打洞」的[布條標語事件](https://news.ltn.com.tw/news/politics/breakingnews/5046954),為 2025 年雙北世界壯年運動會增添意外的插曲:在充滿活力的運動員剪影、可愛的賽會吉祥物以及鮮明的官方標誌之間,一行突兀的黑色文字「四邊包繩-不打洞」赫然印於其上,本應是印刷輸出前,設計稿旁提供給製作廠商的加工備註 —— 指示布條的 4 個邊緣需摺入尼龍繩進行強化縫合 (即「包繩」),以便施工時能直接用繩索綑綁固定,無需再進行打孔作業 —— 卻意外成為公開展示的一部分。該烏龍事件無疑肇因於製稿、審稿到輸出的某個環節,例如設計圖層未正確隱藏、RIP (Raster Image Processor) 轉檔時未能過濾非印紋物件,或是最終校對時的疏忽,導致這句純粹的內部生產指示被誤認為是宣傳標語的一部分,最終被堂而皇之噴印在布條中央。 此插曲不僅為賽事增添意想不到的討論熱度,更為我們提供用以闡釋複雜的作業系統議題:在多核處理器系統中,若缺乏適當的同步 (synchronization) 機制,程式內部的「生產備註」(如同未最終確定的資料狀態或中間計算結果,對應布條上的「四邊包繩-不打洞」文字) 是如何可能被錯誤地、過早地「公開展示」 (即被其他處理器核不正確地觀測到,如同這行文字被印出) 。其結果,便是程式的「意圖」 (僅作為內部參考) 與最終「實際觀察結果」 (成為公開標語) 之間,發生如同這面布條般鮮明而具體的脫鉤。 ![question](https://hackmd.io/_uploads/S1-GxoDWlx.png) 在多核處理器系統中,其中一核處理器 (生產者) 的寫入操作 (如,先更新資料 `object->value`,再設定旗標 `ready = 1` 以宣告完成),經過編譯器最佳化、CPU 本身的亂序執行 (out-of-order execution) 及複雜的快取一致性協定 (cache coherence protocol) 交互作用後,另一核處理器 (消費者) 的「觀察順序」可能與生產者的「意圖順序」大相逕庭。消費者處理器核可能先「觀察」到旗標 `ready` 已被設定,卻讀取到尚未更新的舊資料 `object->value` —— 彷彿公眾先看到「布條已掛上」(旗標 `ready`),但上面的「標語內容」(資料 `object->value`) 卻是錯誤的「生產備註」(舊資料) 。這種觀察到的不一致性,正是所謂的資料競爭 (data race) 或可見性問題 (visibility problem) 的典型表現。 [Linux 核心記憶體模型](https://lpc.events/event/17/contributions/1551/attachments/1326/2662/lkmm.2023.11.14b.pdf) (LKMM) 正是為了弭平這種「意圖」與「實際觀察結果」之間的鴻溝而制定的嚴謹契約,明確定義在多核處理器環境下,一個處理器核的記憶體操作結果何時及如何能被其他處理器核正確「觀察」到。LKMM 以 "[happens-before](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-ordering)" 關係對記憶體操作順序的保證,並要求硬體、編譯器與作業系統核心程式碼共同遵守這份契約,確保「生產備註」不會意外成為被錯誤「觀察」到的「公開標語」。 若想確保「先寫資料,再立旗標」的意圖能夠被其他處理器核正確「觀察」到 (即資料的生產先於旗標的宣告,並且這種順序對觀察者可見),就必須在程式中明確拉起同步的「繩子」 —— 記憶體屏障 (memory barrier),也要禁止任何「打洞」 —— 避免未經同步保護的競爭寫入 (data race) 污染共享資料,導致資料外洩或不一致,如同布條上若有破洞,資訊可能因此不完整或被誤解。下面的生產者/消費者範例展示正確的做法: ```c /* CPU 0 — producer: 意圖先更新資料,再宣告完成 */ object->value = 42; /* 1. 生產內容 (如同撰寫正確的標語) */ smp_store_release(&ready, 1); /* 2. 綁上繩子並宣告完成 (release 語意確保之前的寫入對其他核處理器可見) */ /* CPU 1 — consumer: 意圖在確認完成後,才讀取資料 */ if (smp_load_acquire(&ready) == 1) { /* 3. 檢查旗標 (acquire 語意確保能觀察到 release 前的所有寫入) */ int v = object->value; /* 4. 保證能觀察到 42 (讀取到正確的標語內容) */ /* ... */ } ``` 在此範例中,`smp_store_release(&ready, 1)` 如同生產者在確認「標語內容」(`object->value = 42`) 無誤後,才將「布條掛上並繫好繩子」(設定 `ready` 旗標並透過 `release` 語意確保其之前的寫入對其他處理器核可見)。`release` 語意保證在此操作之前的所有記憶體寫入,對於後續能「觀察」到 `ready == 1` 的其他處理器核而言,都已完成並可見。這就防止消費者處理器核「觀察」到「旗標先被印上,內容卻還是半成品」的窘境,確保公眾不會看到錯誤的「生產備註」。 `smp_load_acquire(&ready)` 則是消費者處理器核在「觀察」到「布條已掛好」(`ready == 1`) 後,才去讀取「標語內容」(`object->value`)。`acquire` 語意確保在此操作之後的所有記憶體讀取,不會被重排序到旗標讀取之前,並且能夠「觀察」到由匹配的 `release` 操作所保證的正確資料狀態。消費者處理器核因此能確信自己「觀察」到的是最終的「產品標語」(`object->value` 為 `42`)。 這對「繩子」(`release` 和 `acquire` 語意) 將生產者和消費者的操作適當地「束緊」,使得任何處理器核在「觀察」到 `ready == 1` 時,必然也能「觀察」到 `object->value` 的最新內容 (即 `42`) 。若省略這些屏障所隱含的排序與可見性保證,就極可能重演布條事件:消費者處理器核可能先「觀察」到 `ready` 旗標的更新,但 `object->value` 的「觀察結果」卻仍是舊值,因為其讀取操作可能被重排,或生產者的寫入尚未對其可見。 LKMM 搭配 `litmus` 和 `herd` 等工具,協助開發者精確驗證其並行程式碼是否真正「把繩子縫好」(正確使用記憶體屏障及帶有排序語意的 atomic 操作)、「沒留下任何洞」(無資料競爭)。這確保程式的內部狀態 (如同生產備註) 不會意外洩漏,最終呈現給所有處理器核「觀察」的「正式訊息」(共享資料狀態) 始終一致且符合預期。如此一來,即使硬體與編譯器為了效能而積極重排指令,整體系統行為也能在 LKMM 的規範下,保證「觀察結果」的一致與可預測,避免「四邊包繩」的烏龍在程式世界中上演。 ### 一旗先舉-不見值) 「一旗先舉-不見值」指先寫入資料,再把 `ready` 旗標設為 1;但若省略帶有釋放 (release) 語意的操作 (如 `smp_store_release`) 或相應的完整記憶體屏障,硬體和編譯器的最佳化行為可能導致旗標的寫入效果比資料的寫入效果更早對其他處理器核可見。另一核處理器讀到 `ready == 1`,卻仍看到過期的資料,就像旗子先高高舉起,真正內容卻還沒到。依 LKMM,單憑程式碼中的順序 (program order) 並不能保證跨越多核處理器的可見性與順序;只有如 `smp_store_release()` 與 `smp_load_acquire()` 這類同步基本操作 (primitive),才能在旗標與資料之間建立 happens-before 關係,確保「旗起」必然伴隨「值現」。 ### 二讀同步-不保序) 「二讀同步-不保序」指出僅藉由二次讀取 (read → read) 並依賴其間的控制相依性 (control dependency),想在多核處理器系統內建立資料讀取的先後關係,實際上無法保證順序。典型情境是: ```c /* CPU 0 */ y = 42; WRITE_ONCE(x, 1); /* WRITE_ONCE 僅保證 x 的單一最小寫入,見下方「註一」 */ /* CPU 1 */ while (READ_ONCE(x) != 1) /* 第一次讀取:輪詢旗標。READ_ONCE 保證 x 的單一最小讀取 */ cpu_relax(); r = y; /* 第二次讀取:期望已見 42,但若無 acquire 語意或 smp_rmb,順序不保證 */ ``` > 註一: 若無 `smp_store_release` 或 `smp_wmb` 於此前,y 的寫入順序對 CPU 1 不保證 > 註二: 程式註解中的「最小」是指 atomic 程式開發者直覺以為「先讀 `x` 等到 1,再讀 `y`」即可同步,但在 LKMM 裡,`READ_ONCE(x)` 和 `r = y;` 之間僅有控制相依,這不足以阻止硬體將 `y` 的讀取 (可能來自較早的快取狀態) 排在 `x` 實際變為 1 的可見性事件之前,或編譯器將 `r = y;` 的讀取不當最佳化 (儘管 `READ_ONCE` 的存在會限制部分最佳化) 。結果就變成旗標已讀到 1,`y` 卻仍是舊值,順序完全不受保障。 換言之,單純「二次讀取同步」缺乏如 `smp_load_acquire` 所提供的取得 (acquire) 屏障的保證順序能力。想讓第二次讀取 `y` 能正確觀察到 CPU~0~ 在寫 `x` 之前對 `y` 的寫入,CPU~1~ 必須在讀取旗標 `x` 時使用 `smp_load_acquire(&x)`,或者在 `READ_ONCE(x)` 之後且讀取 `y` 之前插入 `smp_rmb()` (前提是 CPU~0~ 使用如 `smp_store_release(&x,1)` 或 `smp_wmb()` 來配對) 。否則觀測序列與實際記憶體中資料變動可能脫節。 ### 三層快取-不一致) 「三層快取-不一致」借用現代處理器普遍採用的 L1/L2/L3 cache 階層關係來說明,即使硬體透過 MESI 和 MOESI 一類的協定保證快取一致性 ,它也只確保在任何時間點,一個記憶體位置的資料在整個系統中只有單一的、確定的值 (對所有處理器核來說,最終會收斂到這個值)。但在多核處理器系統中,單靠硬體的快取一致性協定,仍無法讓程式開發者推斷各處理器核觀測到不同記憶體位置更新的時間順序。當程式缺乏如 `smp_mb()`, `smp_store_release()`, `smp_load_acquire()` 這些同步基本操作時,某個處理器核的寫入可能先進入其 store buffer 或 L1 cache,並對該核處理器「宣告完成」,而其他核處理器要觀察到這個寫入,則需等待該快取行傳播並使其本地快取副本失效。這段時間差內,儘管硬體最終會達成快取一致,但不同處理器核觀測到的資料狀態可能暫時「不一致」(如,旗標已更新,資料卻還是舊版) 。硬體快取一致性是記憶體模型正確性的必要基礎,但非充分條件;若想讓任何兩個處理器核對相關記憶體變動的相對可見順序保持一致,還必須在程式層級插入正確的記憶體屏障與帶有排序語意的 [atomic 操作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics),否則再多層快取也無法挽救時序的混亂。 ### 四核共享-不同步) 「四核共享-不同步」藉由 4 核處理器同時存取同一塊資料的場景,揭示在缺乏同步基本操作時,程式對共享狀態的 atomics 更新會不成立。以 4 個執行緒 (假設每個執行緒運行在不同的處理器核上) 並行遞增計數器為例: ```c /* 全域共享變數 */ int counter; /* 每個執行緒都執行下列函式 */ void worker(void) { /* 讀取-修改-寫回 (Read-Modify-Write) 操作,非 atomic */ int v = READ_ONCE(counter); /* 僅保證最小讀取 */ v = v + 1; WRITE_ONCE(counter, v); /* 僅保證最小寫回 */ } ``` 4 個處理器核各自把 `counter` 從記憶體 (或其快取) 載入、本地計算、再回寫。缺少如 `atomic_add()` 或 `atomic_cmpxchg()` (即 `cmpxchg()` 的 atomic 版本) 這類讀取-修改-寫入 (Read-Modify-Write, RMW) 操作的同步基本操作,這 3 次操作 (讀取-修改-寫入) 作為整體並非 atomic 執行。因此,4 次遞增操作彼此競爭,最壞情形下,多次更新會丟失,只留下一次增量的效果,這稱為「丟失更新」(lost update)。硬體快取協定雖確保一個記憶體位址最終持有單一值,但它不保證這 4 核處理器執行的 non-atomic「讀取-修改-寫入」序列 —— 誰先誰後,及中間狀態 —— 符合程式開發者的直觀期望;在 LKMM 眼中,這段程式對 `counter` 的並行存取存在資料競爭,其行為則未定義。 「共享」強調程式開發者期望所有處理器核能安全共用同一份資料;「不同步」則點出沒有諸如 `atomic` 操作或鎖 (lock) 等機制,就失去操作的 atomics、順序與一致性保證。最終輸出的 `counter` 可能遠小於預期的遞增總次數,顯示觀察結果與預期差異。在多核處理器系統中,只要跨越多核處理器共享並修改狀態,就必須使用正確的同步基本操作 (如 atomic RMW 操作、lock),否則即使處理器核數量不多,也可能演變成難以追蹤的時序錯亂與資料損壞。 ### 五級管線-不按序) 「五級管線-不按序」藉由經典 RISC 的五級指令管線 ── 擷取 (IF)、解碼 (ID)、執行 (EX)、存取記憶體 (MEM)、寫回 (WB) ── 來提醒:就算每道指令在同一核處理器內看似井然有序地穿過這 5 個階段,對其他處理器核來說,這些操作的副作用 (尤其是記憶體寫入) 實際對外可見的順序仍可能與程式順序不同。管線為了提高執行吞吐量,常配合諸如 data forwarding (或 bypassing) 及關鍵的 store buffer;這些硬體技巧允許寫入操作在未實際提交到共享記憶體 (如 L1D Cache 或更下層) 前就對目前處理器核「宣告完成」,而讀取操作也可能因預取 (prefetch) 等機制觀察到非預期的狀態,結果就是程式序與外界觀測序脫鉤。 想像下面這段程式碼在 4 核處理器系統中執行,硬體是標準 5 級管線,還帶有 store buffer: ```c /* CPU 0 */ data = 99; /* 寫入共享資料 */ WRITE_ONCE(flag, 1); /* 立旗:指示資料就緒。WRITE_ONCE 僅保證 flag 的最小寫入 */ /* CPU 1 */ while (READ_ONCE(flag) == 0) /* READ_ONCE 僅保證 flag 的最小讀取 */ cpu_relax(); r = data; /* 預期讀到 99,但可能因 store buffer 效應讀到舊值 */ ``` 在 CPU~0~ 內部,`data = 99` 的寫入操作可能先進入 store buffer,而後續的 `WRITE_ONCE(flag,1)` 可能更快完成其寫回快取並透過匯流排對外廣播其新值。此時,CPU~1~ 可能已「觀察」到 `flag` 為 1,但 store buffer 中的 `data=99` 尚未刷出到對 CPU~1~ 可見的共享快取層級。於是 CPU~1~ 跳出迴圈後,其讀取的 `r = data;` 可能仍是舊值。換言之,指令管線內部的「階段順序」不代表外部其他核處理器必定會按此順序「觀察」到這些寫入的結果;若 CPU~0~ 未使用如 `smp_store_release(&flag, 1)` (或 `smp_wmb()` 在 `data=99` 和 `WRITE_ONCE(flag,1)` 之間) ,且 CPU~1~ 未使用 `smp_load_acquire(&flag)` (或 `smp_rmb()` 在迴圈後讀 `data` 前) ,觀測序列就可能失序。 硬體管線的複雜性 (如管線深度、store buffer 的存在、預取機制等) 都可能導致程式順序與全局可見順序的不一致。LKMM 要求開發者在需要保證順序的關鍵路徑上插入正確的帶有釋放/取得語意的操作或相應的完整記憶體屏障,將這些微觀層級的重排序約束在宏觀的因果關係框架內,否則即使是看似簡單的指令序列,也無法保證其執行效果能「按序」對外生效。 --- ## 解構根號法則:為何少數人掌握多數功勞? 想像你在一間公司看見 100 個人同時努力,但真正締造一半成果的,往往不是 50 個人,而是大約 $\sqrt{100}=10$ 個人。這就是 [Price's Law](https://en.wikipedia.org/wiki/Price%27s_law) 的關鍵想法:在一個規模為 $N$ 的群體裡,頂尖的 $\sqrt{N}$ 名成員產生約 50% 的產出。 試想:在音樂串流平臺上,排行榜前幾首歌佔據大半播放次數,類似眾多的現象背後隱含同一種「長尾」分佈:多數人的貢獻或影響力很小,少數人卻非常突出。為何如此?一方面,每個人的能力、動機、資源原本就不完全相等;另一方面,更重要的是[馬太效應](https://en.wikipedia.org/wiki/Matthew_effect),亦即成功會吸引更多資源,讓已表現好的那群人更易再創佳績。於是,成果不斷向這些人集中,形成統計上的「平方根法則」。 探討 [Price's Law](https://en.wikipedia.org/wiki/Price%27s_law) 時,首先要區分「實際完成的工作」與「最終取得的功勞」。當獎酬機制過度傾向可見且易量化的指標,員工便把「爭取功勞」本身視為核心任務,久而久之,「約有 $\sqrt{N}$ 名員工獲得大部分認可」就會因行為模仿而自我實現,與其說是能力分布使然,不如說是制度與生存策略交互作用的結果。 Derek J. de Solla Price 觀察學術引用網路時,發現「優先連接」與「累積優勢」機制:已引用的論文更容易再獲引用,最終形成長尾度數分布。若令單篇產出影響力 $X$ 服從帕雷托分布 $$ \Pr[X>x]=\Bigl(\tfrac{x_{\min}}{x}\Bigr)^{\alpha},\quad \alpha\approx2,\;x\ge x_{\min}, $$ 則排名第一的值 $X_{(1)}$ 的期望近似 $x_{\min}N^{1/\alpha}=x_{\min}\sqrt{N}$。將 $X_{(i)}$ 依大小排序後,前 $m=\sqrt{N}$ 名的期望總和可用 $$ \operatorname{E}\!\Bigl[\sum_{i=1}^{\sqrt{N}}X_{(i)}\Bigr] \approx \int_{0}^{\sqrt{N}}\!x_{\min}(N/t)^{1/\alpha}\,dt =\tfrac{\alpha}{\alpha-1}\,x_{\min}N $$ 進一步除以 $$ \operatorname{E}[S_N]=\sum_{i=1}^{N}\operatorname{E}[X_i]=\tfrac{\alpha}{\alpha-1}\,x_{\min}N, $$ 得到前 $\sqrt{N}$ 人約佔總產出一半。若改用對數常態分布 $\log X\sim\mathcal{N}(\mu,\sigma^{2})$,只要 $\sigma^{2}$ 夠大,極值期望 $\exp(\mu+\sigma\sqrt{2\ln N})$ 同樣呈次線性增長,亦能觀察到高度集中;比例則依 $\sigma$ 而變。由此可見,根號法則是分布參數落在臨界區域時的近似,而非普適定律。 1988 年刊於《Information Processing & Management》的[研究](https://www.sciencedirect.com/science/article/abs/pii/0306457388900490)指出,Price's Law 在不同領域的擬合度差異甚大,且常與描述科學家產出分布的 [Lotka's Law](https://en.wikipedia.org/wiki/Lotka%27s_law) ($\alpha\approx2$) 混淆;僅憑產量或引用並不足以衡量影響力。歷史上牛頓與費曼的論文數量不多,卻深刻改變科學版圖,正好反證以單一量化指標評價的侷限。 在大型科技企業,績效系統會放大「功勞可見性偏差」。Google 於 2022 年推行 GRAD,為配合預設曲線把更多人排入低檔;Amazon 大量使用 PIP 作為「安靜解雇」工具。面對晉升壓力,工程師傾向挑選高曝光專案,甚至建立短期亮眼卻難以長期維護的系統,把技術債轉嫁未來。晉升階梯亦加劇集中:Microsoft 的 Principal Engineer 以上職級天然擁有更大決策範圍,可將團隊成果歸為個人成就;在 FAANG,工程師自 Staff 升至 Principal 乃至 Distinguished 後,工作重心轉向跨團隊策略,若績效仍聚焦短期個人產出,下層員工很難獲等量認可。 > 對照 [組織與企業章呈](https://elderengineer.github.io/book-sillicon-valley/32.html) 組織規模擴張造成溝通邊數級數增長。若將利潤中心視為節點、員工視為連邊,全連通網路需 $O(N^{2})$ 條邊;在複雜協作下,那些能自行拆解問題並減少協調成本的少數人,其邊際產出特別突出,呼應《人月神話》所述「新增人手可能拖慢進度」的非線性特徵。 因此,Price's Law 提供觀察產出不均的啟發,但真正決定集中程度的是激勵機制、網路效應與協作複雜度。若組織過度依賴少數英雄,制度將鼓勵追逐可見功勞而忽視長期價值。 延伸閱讀: * [Price’s Law: What It Is And Why You Should Care](https://dariusforoux.com/prices-law/) ![image](https://hackmd.io/_uploads/ByXxGhPbgg.png) > [出處](https://www.facebook.com/permalink.php?story_fbid=pfbid032dGJqv4rmG97YDiNJCdk4b2WjqcrbWf64fLKnUdXCotWsgNpSNiRBTSebdorWE32l&id=100082931152164) Microsoft 這次大規模裁員引發業界高度關注:一位在公司效力 18 年、曾讓 TypeScript 執行速度提升 10 倍的人工智慧部門主管也難逃此波人事震盪,總計全球約 6,000 名員工受影響。儘管最新財報顯示獲利亮眼、股價逼近歷史高點,Microsoft 仍宣布自 7 月 13 日起生效,裁減約 3% 員工,是繼 2023 年砍掉 1 萬名人力後的最大規模。 從華盛頓州政府公布的統計來看,Microsoft 總部有 1985 名員工被裁,包括 1510 名辦公室人員;截至 2024 年 6 月,Microsoft 全球員工總數為 228,000 人。公司發言人強調此舉屬組織調整而非績效考量,著重精簡管理階層,以回應市場需求。 外界普遍認為與 Microsoft 在人工智慧領域的鉅額投資及其折舊壓力有關。與此同時,Amazon 也曾因檢視「多餘主管階層」進行裁員,網路安全業者 [CrowdStrike 近期亦宣布縮編 5% 人力](https://www.cnbc.com/2025/05/07/crowdstrike-announces-5percent-job-cuts-says-ai-reshaping-every-industry.html),可見大型科技公司在擴張與精簡之間面臨相似挑戰。 延伸閱讀: [微軟大規模裁員 高層:「不怎麼樣」的主管太多了](https://www.cw.com.tw/article/5135369) --- ## WSL 原始程式碼發布 ![image](https://hackmd.io/_uploads/BylUwEKWgx.png =80%x) WSL (Windows Subsystem for Linux) 最初於 2016 年的 BUILD 大會宣佈,並隨 Windows 10 周年更新首次推出。當時的 WSL 採用 pico process provider [lxcore.sys](https://learn.microsoft.com/en-us/previous-versions/windows/desktop/cmdline/wsl-architectural-overview),讓 Microsoft Windows 得以原生執行 ELF 可執行檔,並在 Windows 核心中實作 Linux 系統呼叫,這就是今天所稱的 WSL 1,且至今仍受支援。隨著對原生 Linux 相容性的需求增加,Microsoft 改以 Linux 核心本身為基礎,於 2019 年發佈 WSL 2。社群規模快速成長後,WSL 又相繼加入 GPU 支援、圖形應用程式支援 (透過 wslg) 以及 systemd 支援。 如今,Microsoft 以 MIT 授權條款發布 [WSL 的原始程式碼](https://github.com/microsoft/WSL)。 --- ## NVIDIA 開放 NVLink Fusion IP NVIDIA 在 Computex 2025 宣布開放獨家的超高速互連技術 NVLink Fusion IP,允許晶片設計廠商打造半客製化的 AI 基礎架構。 雲端服務供應商 (CSP) 自行開發 [ASIC](https://en.wikipedia.org/wiki/Application-specific_integrated_circuit) (應用特定積體電路) 的動機可歸納為四項: 1. 在整體系統中減少對 NVIDIA 授權依賴 2. 降低單位晶片的成本 3. 在缺貨或硬體採購不及時時,能自行決定投片時程 4. 針對特定 AI 演算法 (例如推薦系統) 客製化 ASIC 由於 CUDA 生態無法直接移植到客製化 ASIC,因此選擇 NVLink Fusion 的供應商,既可保有與 NVIDIA GPU 的高效互連,也能在私有或混合架構中彈性部署。 黃仁勳在開幕演講中指出,NVLink Fusion 不僅能讓雲端業者結合任何 ASIC 與 NVIDIA 的機架規模系統,也能利用 NVIDIA 端對端網路平台(最高 800Gb/s 的 InfiniBand 與乙太網路解決方案) 大幅提高部署效率。 第五代 NVLink 平台已在 NVIDIA Blackwell Tensor GPU 上達成每秒 1.8 TB 的總頻寬,較 PCIe Gen5 提升超過 14 倍。GB200 NVL72 等伺服器平台透過 NVLink Switch 串聯多條 NVLink 通道,未來的 GB300 機架將配備九個交換器,骨幹頻寬可達每秒 7.2 TB,使整櫃伺服器如同一部超級電腦般運作,落實機櫃內外垂直與水平的無縫擴展。 為了鞏固生態系統,聯發科技、Marvell、世芯電子 (Alchip)、Astera Labs、Synopsys 與 Cadence 等產業領導者已採用 NVLink Fusion 技術。 延伸閱讀: * [NVIDIA 推出 NVLink Fusion, 讓業界可透過 NVIDIA 合作夥伴生態系打造半客製化 AI 基礎架構](https://ithome.com.tw/pr/169023) * [COMPUTEX: NVLink Fusion](https://hao.cnyes.com/post/171019) * [0 to ASIC](https://docs.google.com/presentation/d/14npvuiGxsS3C-yo2vOsbZpNKGehwTtIYRFN6k3ZVR4M/edit?usp=sharing) --- ## Andrewtangtang 探討 Redis 如何運用 skip list 資料結構。 ### Skip List 資料結構 Redis 作為 in-memory 的資料庫,其主要可以使用的資料結構除了 Hash 外還有 sorted set, string, list 等資料儲存型態,而 skip List 根據 [Glossary: sorted sets](https://redis.io/glossary/redis-sorted-sets/) 的說明,最主要是應用在 sorted set 這個資料型態中,不過 sorted set 在元素數量較少或元素較小時,會採用 [ziplist](https://redis.io/glossary/redis-ziplist/) 編碼以節省記憶體,當超過特定閾值時,則會轉換為由 skip list 和雜湊表組合的結構 (稱為 `OBJ_ENCODING_SKIPLIST`,見 [src/server.h](https://github.com/redis/redis/blob/unstable/src/server.h)) 。 sorted set 的主要特色,是能以有序方式儲存不重複 (unique) 的成員,且支援根據成員的分數 (score) 進行排序。以單向鏈結串列來說,若要檢查某個元素是否存在,必須線性走訪每個節點,時間複雜度為 $O(n)$;如果改用陣列 (Array) 來實作,雖然能用二分搜尋法將搜尋效率提升至 $O(\log{n})$,但在插入或刪除元素時,則需要搬動大量資料,時間複雜度最差亦為 $O(n)$。為了兼顧搜尋與插入刪除的效率,Skip List 結合鏈結串列與類似陣列快速跳躍搜尋的特性: - 它以多層級的鏈結串列設計,使搜尋、插入與刪除操作的期望時間複雜度皆為 $O(\log{n})$ - 相較於平衡樹一類的樹狀結構,skip list 的結構實作與操作相對簡單,特別適合像 sorted set 這種既要求成員有序,又需要頻繁增刪成員的應用場景 ![image](https://hackmd.io/_uploads/r1fqpvoblx.png) Skip list 包含位於最底層、完整排序的鏈結串列。在此基礎上,skip list 會額外建立多個層級的「捷徑」鏈結串列。當新成員插入時,會透過隨機過程決定是否將其提升到上層鏈結串列。由於該隨機性,層級越高的鏈結串列所包含的節點就越稀疏。 搜尋特定成員時,skip list 會從最高層的稀疏鏈結串列開始。在目前層級找到小於 (或等於,取決於搜尋目標) 目標值的最大節點後,再沿該節點的指標移動到下一層級繼續搜尋,如此逐層向下,直到在最底層找到目標成員或確定其不存在。這種多層跳躍式的查詢方式能有效減少比較次數,避免對底層鏈結串列進行線性掃描。 當我們要在 skip list 中插入成員 67,首先需要找到其合適的插入位置。其搜尋路徑如下圖所示:從最高層開始,找到小於 67 的最大節點,然後下降一層繼續搜尋,直至在最底層鏈結串列中定位到插入點。 ![image](https://hackmd.io/_uploads/SJUPn4n-xg.png) 當成員成功插入最底層的鏈結串列後,預期有 $p$ 的機率,將此新節點提升到上一層,並鏈接到該層的鏈結串列中。 ![image](https://hackmd.io/_uploads/rkvGzS3Wel.png) 新節點每成功提升一層後,都會再次以機率 $p$ 決定是否繼續向上提升。因此,一個新節點擁有至少 $i$ 層 (即其最高層級 $\ge i$,其中 Level 1 為最底層) 的機率為 $p^{i-1}$。論文〈[Skip Lists: A Probabilistic Alternative to Balanced Trees](https://epaperpress.com/sortsearch/download/skiplist.pdf)〉以 $P=1/2$ 來進行分析。 ### 預期搜尋成本分析 分析搜尋成本時,採用回溯分析法 (backward analysis) 來計算預期搜尋路徑的長度。 #### 1. 參數定義 - $n$:資料筆數 - $p$:節點「再增長一層」的機率 (實務常取 $(p=\tfrac12)$) - $L(n)$:最高層級 (定義為使得該層節點期望值**首次**小於 1 的層級,亦即 $\mathbb{E}[N_{L(n)}] < 1$ 且 $\mathbb{E}[N_{L(n)-1}] \ge 1$) 第 $k$ 層的節點期望數量: $$ \mathbb{E}[N_k] = n p^{k} $$ 因此最高層的估計可寫為: $$ n p^{L(n)} \approx 1 \quad \Longrightarrow \quad L(n) \approx \log_{1/p} n $$ #### 2. 回溯模型 ![image](https://hackmd.io/_uploads/rys0L8nbll.png) 當我們反向追溯搜尋路徑,考慮在某個節點 $x$ (位於邏輯層級 $i$) 的移動時,會遇到以下情況 (對應到下方遞迴式中的成本分析): | 情形 | 描述 | 機率 | 下一步<br>(移動與後續成本) | |------|------|------|--------| | a | $C(k)$ 的定義:距頂端尚需爬 $k$ 層的預期步數 | — | — | | b | 節點 $x$ 的最高層級為 $i$ <br>(`level(x) = i`) | $1-p$ | **向左** 1 步 (成本 1),之後仍需爬 $k$ 層 <br>成本 $C(k)$ | | c | 節點 $x$ 的層級高於 $i$ <br>(`level(x)>i`) | $p$ | **向上** 1 步 (成本 1),之後尚需爬 $k-1$ 層 <br>成本 $C(k-1)$ | 令 $C(k)$ 為「距頂端尚需上爬 $k$ 層」時,預期需要走訪鏈接 (邊) 數量。 遞迴式 $$ \begin{aligned} C(0) &= 0, \\ C(k) &= (1-p)\left[1+C(k)\right] + p\left[1+C(k-1)\right], \quad k \ge 1 \end{aligned} $$ 整理得 $$ \begin{aligned} p C(k) &= 1 + p C(k-1) \\ \Longrightarrow \quad C(k) &= \frac{1}{p} + C(k-1) \\ \Longrightarrow \quad C(k) &= \frac{k}{p} \end{aligned} $$ #### 3. 單層「水平+垂直」期望成本 取 $k=1$: $$ C(1)=\frac{1}{p} $$ 該結果可詮釋為,平均而言,為了爬升 1 個層級,預期需要移動 $\tfrac{1}{p}$ 步。其中必然有 1 步是「向上」移動,其餘的 $(\tfrac{1}{p}-1)$ 步則是「向左」移動。 #### 4. 爬到頂端的總成本 從搜尋路徑開始,預期需要自底層爬升 $L(n)$ 層: $$ \mathbb{E}[\text{cost}] = C\left(L(n)\right) = \frac{L(n)}{p} $$ #### 5. 代入原始假設的等式 已知 $$ L(n) \approx \log_{1/p} n $$ 於是,總預期成本為: $$ \mathbb{E}[\text{Cost}] = \frac{L(n)}{p} \approx \frac{\log_{1/p} n}{p} $$ 由於 $p$ 為常數,因此 $\frac{1}{p}$ 與 $\log(1/p)$ 亦為常數。注意到 $\log_{1/p} n = \frac{\log n}{\log (1/p)}$,於是 $$ \mathbb{E}[\text{Cost}] = \frac{1}{p \log(1/p)} \log n = O(\log n) $$ $p = \tfrac12$ 是個常見的理論分析值,則 $\log_{1/p} n = \log_2 n$,總預期成本為 $\frac{\log_2 n}{1/2} = 2\log_2 n$。然而,根據 Redis 原始程式碼 ([src/server.h](https://github.com/redis/redis/blob/unstable/src/server.h)),`zset` 中 `ZSKIPLIST_P` 的實際預設值是 $0.25$ (即 $p=\tfrac14$),於是: $$ \log_{1/p} n = \log_{1/(1/4)} n = \log_4 n $$ 則總預期成本為: $$ \mathbb{E}[\text{Cost}] = \frac{L(n)}{p} \approx \frac{\log_4 n}{1/4} = 4\log_4 n $$ 由於 $\log_4 n = \frac{\log_2 n}{\log_2 4} = \frac{\log_2 n}{2}$,上述成本也可表示為: $$ 4\log_4 n = 4 \left( \frac{\log_2 n}{2} \right) = 2\log_2 n $$ 儘管 Redis 使用的 $p$ 值不同,其期望搜尋成本以 $\log_2 n$ 為底表示時,結果與 $p=\tfrac12$ 的情況相同。無論 $p$ 取 $1/2$ 或 $1/4$ (或其他常數) ,skip list 在期望意義下的時間複雜度均為 $O(\log{n})$。 ### Skip list 在現代處理器架構下的性能與限制 > 參考 [What Cannot be Skipped About the Skiplist: A Survey of Skiplists and Their Applications in Big Data Systems](https://arxiv.org/html/2403.04582v2) #### 記憶體存取模式與快取效能 典型的 skip list 由多層鏈結串列組成,節點間透過指標予以連結,該資料結構的空間局部性 (spatial locality) 較差,因為走訪時常需透過指標跳躍 (skip) 到記憶體中不連續的位置。每當需要追蹤指標以存取下個節點時,便可能導致一次快取未命中 (cache miss)。因此,相較於那些在連續記憶體區塊中進行順序掃描的資料結構,skip list 可能會產生較多的隨機記憶體存取,尤其當 skip list 的每個節點只包含單一鍵值或索引項 (index entry) 時,每前進一步,幾乎都意味著需要從新的記憶體位置讀取資料,這對現代處理器的快取機制不友善。 不過近期有研究提出改良方案,例如〈[Cache-sensitive Skip List](https://www.informatik.hu-berlin.de/de/forschung/gebiete/wbi/research/publications/2016/cssl.pdf)〉使用陣列來儲存同一層級的節點,並藉由算術直接定位子節點的位置,從而消除部分指標的間接存取,並降低快取未命中的機率。針對空間局部性不佳的問題,也可用 CPU 的預取 (prefetching) 指令,例如 Intel 平台的 [`_mm_prefetch`](https://www.intel.com/content/www/us/en/docs/fortran-compiler/developer-guide-reference/2025-1/mm-prefetch.html),在走訪 skip list 的某一節點時,提前將其下一層或同一層的後續節點資料載入快取。 ![image](https://hackmd.io/_uploads/BkjW-h3Zel.png) 相較之下,在 B+ tree 中,一個節點(通常對應一個記憶體頁面的大小)內部會儲存多個鍵和指向子節點的指標。因此,搜尋時在單一節點內即可比較多個鍵,從而覆蓋較大的鍵值範圍。由於 B+ tree 節點內的鍵和指標通常以陣列等形式連續存放,因此在節點內部進行搜尋時,可連續讀取多個元素,展現出較好的空間局部性。因此一次快取行 (cache line) 的載入,便可能包含多個鍵值資料,使得 B+ tree 在利用快取階層方面表現通常更好。 即使所有資料都已載入主記憶體,B+ tree 這類針對空間局部性調整的索引結構,在實際應用中通常仍比像 skip list 這樣未特別針對此點設計的結構有著更佳的查詢性能。然而,B+ tree 在進行更新 操作時,可能會觸發節點分裂 (page split) —— 當節點填滿時必須分裂成二個或多個節點 —— 或節點合併等結構調整。這些操作不僅帶來額外開銷,還可能導致頁面碎片化 (fragmentation),從而降低有效的記憶體利用率。 #### 為什麼 Redis 使用 Skip list 根據 Redis 作者 antirez 的說法: > They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in $O(\log{N})$. It required little changes to the code. Skip List 結構相對簡單,其在延遲 (latency) 方面的優勢主要來自操作的穩定性:它不像 B+ tree 那樣可能因耗時的頁面分裂或樹重平衡 (rebalancing) 而產生顯著的延遲波動。相關論文實驗也顯示 Skip List 的尾部延遲 (tail latency) 較小,意味著極端耗時操作的發生頻率較低。然而,由於指標跳躍 (pointer skipping/chasing) 對快取存取不友善,Skip List 的單次操作平均延遲通常仍可能略高於 B+ tree 。這是因為[指標追逐](https://en.wikichip.org/wiki/pointer_chasing) (pointer chasing) 在系統執行期間會導致大量的 TLB miss 與快取未命中。其根本原因在於,處理器需不斷處理連續的「不規則記憶體存取」(irregular memory access) 指令,導致快取的空間局部性效果大幅下降,甚至可能引發快取污染 (cache pollution),進而拉高整體存取延遲。 為了凸顯 skip list 的「無需重平衡」特性,其原始論文〈[Skip Lists: A Probabilistic Alternative to Balanced Trees](https://epaperpress.com/sortsearch/download/skiplist.pdf)〉提及傳統樹形結構面臨的退化與調整問題: > Binary trees perform well when insertions are in random order. However, ordered insertions can lead to degenerate structures with poor performance. Since randomizing input is often impractical, balanced tree algorithms dynamically rearrange the structure to maintain good performance. 上述說明點出:若輸入序列特定順序 (例如已排序),普通的二元搜尋樹容易退化成鏈結串列,導致效能下降至 $O(n)$。因此,需要依賴如 AVL tree、紅黑樹或 B/B+ tree 等資料結構的「平衡」機制進行動態調整,以維持 $O(\log{n})$ 的操作效能。相對地,Skip List 透過在插入時隨機化節點的高度,從根本上避免了結構退化的問題,無需進行後續的樹旋轉或大規模節點分裂。因此,在高度並行、追求低尾部延遲的記憶體內索引 (in-memory index) 場景中,skip list 能以更簡潔的程式碼提供穩定且可預期的 $O(\log{n})$ 效能。 若考慮並行擴展性 (concurrency scalability),skip list 因其更新操作通常只涉及少量節點,使得臨界區域 (critical section) 的程式碼較短,且不同操作間的影響區域相對獨立。這使其更容易透過比較並交換 (Compare-And-Swap, CAS) 等 atomics 操作得以達成 fine-grained locking 甚至 lock-free 的設計。相較之下,B+ tree 的插入或刪除操作往往需要鎖定目標節點及其父節點;若發生節點分裂或合併並向上連鎖變動時,鎖定的範圍更可能擴大,從而導致更激烈的資源競爭。 ## 善用快取記憶體改進程式效能 中央處理器的運作速度遠超越主記憶體的存取速度。若 CPU 每次處理資料都需要直接從主記憶體讀取,那麼 CPU 的大部分時間都將花費在等待資料上,造成巨大的效能浪費。 為了緩解這個速度鴻溝,CPU 內部整合一小塊容量雖小但速度極快的儲存單元,這就是中央處理器的快取記憶體。 * 層級結構: 通常有多層快取 (L1, L2, L3) ,L1 最快且容量最小,L3 則相對較慢但容量更大。 * 工作原理: 當 CPU 需要資料時,它會首先檢查 L1 快取。 * 快取命中 (Cache Hit): 若資料在快取中,CPU 可以快速取得,效能高 * 快取失誤 (Cache Miss): 若資料不在快取中,CPU 需要從下一層快取或主記憶體中載入。這個過程會慢得多。載入時,不僅僅是所需的資料,而是包含該資料的一整塊資料 (稱作快取行或 cache line) 會被載入到快取中 有效運用快取記憶體是提升程式效能的關鍵。透過撰寫對快取友善的程式碼,我們可改進快取命中率,從而顯著減少 CPU 等待時間,提升程式執行效率。 - [ ] 快取行 快取記憶體不是以單個位元組為單位儲存資料的,而是以「快取行」為單位。當發生快取失誤時,CPU 會從主記憶體中載入一整個快取行到快取中。現代 CPU 的快取行大小通常是 64 位元組或 128 位元組。 - [ ] 區域性原理 (Principle of Locality): 程式存取記憶體的行為通常具有區域性,這是快取能夠有效運作的關鍵。 * 時間區域性 (Temporal Locality): 若一個資料項被存取,那麼它在不久的將來很可能再次被存取。例:迴圈中的計數器變數 * 空間區域性 (Spatial Locality): 若一個資料項被存取,那麼與它記憶體位址相鄰的資料項也很可能在不久的將來被存取。例:循序走訪陣列元素 當 CPU 載入一個快取行時,若程式接下來存取的資料恰好也在這個快取行內 (空間區域性) ,那麼這些後續存取都將是快速的快取命中。 考慮以下程式碼: - [ ] 緊湊型結構體 (`CompactStruct`): ```c typedef struct { int a; /* 偏移量 0 */ int b; /* 偏移量 4 */ int c; /* 偏移量 8 */ int d; /* 偏移量 12 */ char pad2[263 - 16]; /* 之後是填充 */ } __attribute__((packed)) CompactStruct; /* a, b, c, d 總共佔用 16 位元組。*/ ``` * 成員 `a`, `b`, `c`, `d` 在記憶體中是連續存放的。若一個 64 位元組或 128 位元組的快取行載入 `a`,那麼 `b`, `c`, `d` 極有可能 (幾乎肯定) 也在同一個快取行內。 - [ ] 分散型結構體 (`ScatteredStruct`): ```c typedef struct { int a; /* 偏移量 0 */ char padding1[CACHELINE_SIZE - sizeof(int) + 1]; /* 假設 CACHELINE_SIZE=128, sizeof(int)=4, padding1 大小為 125 */ int b; /* 'b' 的偏移量: 4 + 125 = 129 */ char padding2[CACHELINE_SIZE - sizeof(int) + 1]; int c; /* 'c' 的偏移量: 129 + 4 + 125 = 258 */ char padding3[CACHELINE_SIZE - sizeof(int) + 1]; int d; /* 'd' 的偏移量: 258 + 4 + 125 = 387 */ char padding4[CACHELINE_SIZE - sizeof(int) + 1]; char pad2[3]; } __attribute__((packed)) ScatteredStruct; ``` * `a`, `b`, `c`, `d` 之間插入大量的填充 (`paddingX`)。每個 `paddingX` 的大小都設計為 `CACHELINE_SIZE - sizeof(int) + 1`。這意味著: * 當存取 `a` 時,一個快取行被載入。 * 當存取 `b` 時,由於 `b` 與 `a` 的距離 (129 位元組) 遠大於一個典型的快取行大小 (例如 64 位元組) ,`b` 幾乎肯定位於不同的快取行。這將導致一次新的快取失誤。 * 對 `c` 和 `d` 的存取同理,每次都極可能導致新的快取失誤。 完整程式碼: ```c #include <stdio.h> #include <stdlib.h> #include <time.h> /* For clock_gettime */ #include <stdint.h> /* For int64_t */ #define CACHELINE_SIZE 64 #define ARRAY_SIZE 100000 typedef struct { int a; int b; int c; int d; char pad2[263 - 16]; } __attribute__((packed)) CompactStruct; typedef struct { int a; /* * Padding designed to push the next member to at least the next cache line * relative to the CACHELINE_SIZE constant. * sizeof(int) is typically 4. So, CACHELINE_SIZE - 4 + 1 = CACHELINE_SIZE - 3. * Example: if CACHELINE_SIZE is 128, padding1 is 125 bytes. * 'a' is at offset 0. 'b' is at offset 4 (sizeof(a)) + 125 = 129. * This puts 'b' into a new cache line if 'a' was at the start of one. */ char padding1[CACHELINE_SIZE - sizeof(int) + 1]; int b; char padding2[CACHELINE_SIZE - sizeof(int) + 1]; int c; char padding3[CACHELINE_SIZE - sizeof(int) + 1]; int d; char padding4[CACHELINE_SIZE - sizeof(int) + 1]; char pad2[3]; /* Some more padding to make struct size not round */ } __attribute__((packed)) ScatteredStruct; /* Helper function to get time in seconds */ double get_time_sec() { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts); return ts.tv_sec + ts.tv_nsec / 1e9; } int main() { printf("sizeof(CompactStruct): %zu bytes\n", sizeof(CompactStruct)); printf("sizeof(ScatteredStruct): %zu bytes\n", sizeof(ScatteredStruct)); printf("CACHELINE_SIZE defined as: %d bytes\n", CACHELINE_SIZE); printf("ARRAY_SIZE: %d\n\n", ARRAY_SIZE); /* Allocate memory for the arrays */ CompactStruct *arr_compact = (CompactStruct *)malloc(ARRAY_SIZE * sizeof(CompactStruct)); ScatteredStruct *arr_scattered = (ScatteredStruct *)malloc(ARRAY_SIZE * sizeof(ScatteredStruct)); if (!arr_compact || !arr_scattered) { perror("Failed to allocate memory"); if (arr_compact) free(arr_compact); if (arr_scattered) free(arr_scattered); return 1; } /* Initialize the arrays with some data */ for (int i = 0; i < ARRAY_SIZE; i++) { arr_compact[i].a = i; arr_compact[i].b = i * 2; arr_compact[i].c = i * 3; arr_compact[i].d = i * 4; arr_scattered[i].a = i; arr_scattered[i].b = i * 2; arr_scattered[i].c = i * 3; arr_scattered[i].d = i * 4; } volatile int64_t sum = 0; double start_time, end_time; /* Test CompactStruct */ sum = 0; /* Reset sum */ start_time = get_time_sec(); for (int i = 0; i < ARRAY_SIZE; i++) sum += arr_compact[i].a + arr_compact[i].b + arr_compact[i].c + arr_compact[i].d; end_time = get_time_sec(); printf("CompactStruct sum: %lld\n", (long long)sum); printf("CompactStruct time: %.6f seconds\n\n", end_time - start_time); /* Test ScatteredStruct */ sum = 0; /* Reset sum */ start_time = get_time_sec(); for (int i = 0; i < ARRAY_SIZE; i++) { sum += arr_scattered[i].a + arr_scattered[i].b + arr_scattered[i].c + arr_scattered[i].d; } end_time = get_time_sec(); printf("ScatteredStruct sum: %lld\n", (long long)sum); printf("ScatteredStruct time: %.6f seconds\n", end_time - start_time); free(arr_compact); free(arr_scattered); return 0; } ``` 編譯: ``` $ gcc -O2 -o cache-test cache-test.c -lrt ``` 預期與實際效能: * 對於 `CompactStruct` 陣列: 1. 存取 `arr[i].a`:可能快取失誤 (若 `arr[i]` 的起始位址不在快取中) 。包含 `a, b, c, d` 的快取行被載入。 2. 存取 `arr[i].b`:快取命中 3. 存取 `arr[i].c`:快取命中 4. 存取 `arr[i].d`:快取命中 每個結構體內部的存取都非常有效率。 * 對於 `ScatteredStruct` 陣列: 1. 存取 `arr[i].a`:可能快取失誤。包含 `a` 的快取行被載入。 2. 存取 `arr[i].b`:快取失誤!包含 `b` 的新快取行被載入。 3. 存取 `arr[i].c`:快取失誤!包含 `c` 的新快取行被載入。 4. 存取 `arr[i].d`:快取失誤!包含 `d` 的新快取行被載入。 每個結構體內部的存取都伴隨著多次快取失誤,導致顯著的效能下降。 在 AMD Ryzen Threadripper 2990WX 32-Core 實驗結果: ``` CompactStruct time: 0.001698 seconds ScatteredStruct time: 0.001937 seconds ``` 結果顯示 `CompactStruct` 的執行速度比 `ScatteredStruct` 快,展現將相關資料緊湊排列以利用快取空間區域性的優勢,但不顯著。 為何差異不是數倍?現代 CPU 非常複雜,擁有一些可緩解快取失誤影響的特性: * 硬體預取器 (Hardware Prefetchers): CPU 可能會偵測到記憶體存取模式 (即使是跨快取行的分散存取) ,並嘗試提前將資料載入到快取中。這可減少部分失誤的懲罰。 * 亂序執行 (Out-of-Order Execution): CPU 可以不按程式順序執行指令。當等待一個記憶體載入時,它可以先執行其他不相關的指令。 * 多層次快取: 即使 L1 快取失誤,資料也可能在 L2 或 L3 快取中找到,其存取速度仍遠快於主記憶體。 儘管有這些進階特性,遵循對快取友善的原則仍然能帶來可觀的效能提升。

Import from clipboard

Paste your markdown or webpage here...

Advanced permission required

Your current role can only read. Ask the system administrator to acquire write and comment permission.

This team is disabled

Sorry, this team is disabled. You can't edit this note.

This note is locked

Sorry, only owner can edit this note.

Reach the limit

Sorry, you've reached the max length this note can be.
Please reduce the content or divide it to more notes, thank you!

Import from Gist

Import from Snippet

or

Export to Snippet

Are you sure?

Do you really want to delete this note?
All users will lose their connection.

Create a note from template

Create a note from template

Oops...
This template has been removed or transferred.
Upgrade
All
  • All
  • Team
No template.

Create a template

Upgrade

Delete template

Do you really want to delete this template?
Turn this template into a regular note and keep its content, versions, and comments.

This page need refresh

You have an incompatible client version.
Refresh to update.
New version available!
See releases notes here
Refresh to enjoy new features.
Your user state has changed.
Refresh to load new user state.

Sign in

Forgot password

or

By clicking below, you agree to our terms of service.

Sign in via Facebook Sign in via Twitter Sign in via GitHub Sign in via Dropbox Sign in with Wallet
Wallet ( )
Connect another wallet

New to HackMD? Sign up

Help

  • English
  • 中文
  • Français
  • Deutsch
  • 日本語
  • Español
  • Català
  • Ελληνικά
  • Português
  • italiano
  • Türkçe
  • Русский
  • Nederlands
  • hrvatski jezik
  • język polski
  • Українська
  • हिन्दी
  • svenska
  • Esperanto
  • dansk

Documents

Help & Tutorial

How to use Book mode

Slide Example

API Docs

Edit in VSCode

Install browser extension

Contacts

Feedback

Discord

Send us email

Resources

Releases

Pricing

Blog

Policy

Terms

Privacy

Cheatsheet

Syntax Example Reference
# Header Header 基本排版
- Unordered List
  • Unordered List
1. Ordered List
  1. Ordered List
- [ ] Todo List
  • Todo List
> Blockquote
Blockquote
**Bold font** Bold font
*Italics font* Italics font
~~Strikethrough~~ Strikethrough
19^th^ 19th
H~2~O H2O
++Inserted text++ Inserted text
==Marked text== Marked text
[link text](https:// "title") Link
![image alt](https:// "title") Image
`Code` Code 在筆記中貼入程式碼
```javascript
var i = 0;
```
var i = 0;
:smile: :smile: Emoji list
{%youtube youtube_id %} Externals
$L^aT_eX$ LaTeX
:::info
This is a alert area.
:::

This is a alert area.

Versions and GitHub Sync
Get Full History Access

  • Edit version name
  • Delete

revision author avatar     named on  

More Less

Note content is identical to the latest version.
Compare
    Choose a version
    No search result
    Version not found
Sign in to link this note to GitHub
Learn more
This note is not linked with GitHub
 

Feedback

Submission failed, please try again

Thanks for your support.

On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?

Please give us some advice and help us improve HackMD.

 

Thanks for your feedback

Remove version name

Do you want to remove this version name and description?

Transfer ownership

Transfer to
    Warning: is a public team. If you transfer note to this team, everyone on the web can find and read this note.

      Link with GitHub

      Please authorize HackMD on GitHub
      • Please sign in to GitHub and install the HackMD app on your GitHub repo.
      • HackMD links with GitHub through a GitHub App. You can choose which repo to install our App.
      Learn more  Sign in to GitHub

      Push the note to GitHub Push to GitHub Pull a file from GitHub

        Authorize again
       

      Choose which file to push to

      Select repo
      Refresh Authorize more repos
      Select branch
      Select file
      Select branch
      Choose version(s) to push
      • Save a new version and push
      • Choose from existing versions
      Include title and tags
      Available push count

      Pull from GitHub

       
      File from GitHub
      File from HackMD

      GitHub Link Settings

      File linked

      Linked by
      File path
      Last synced branch
      Available push count

      Danger Zone

      Unlink
      You will no longer receive notification when GitHub file changes after unlink.

      Syncing

      Push failed

      Push successfully