vectorized execution 比較快或許大概聽過幾百次，用 SIMD 加速可能也聽過一百次
但...真的是同一件事嗎？

昨天結尾把問題丟在「NULL 為什麼要用 bitmap 標」，那個詞今天還會用到，後面會補它跟 bit buffer 差在哪。
先問一個聽起來像同義詞、實際上是不同層的問題：向量化執行跟 SIMD，究竟是不是同一件事？
先講個結論：不是
搞混會出的糗事是，以為換成 vectorized engine 就自動吃到 SIMD，結果 profile 打開，一條 vmulps 都沒有～

兩個詞分別在兩個抽象層

vectorized execution 這個詞從 MonetDB/X100（CIDR 2005）那條路線來的：一次處理一批 tuple，相對於 Volcano 那種一次一列。它是執行模型的選擇，講的是「引擎每次動一步，動多少資料」。

SIMD(Single Instruction Multiple Data) 是 CPU 給的技能
一條 _mm256_mul_ps 可以把 8 個 float 同時乘起來。它是指令等級的東西，跟資料庫沒關係，Intel／ARM 就是這樣給的硬體介面。

一個講批次的資料量，一個講指令的並行度
中間沒有等號，只有可能的重疊

先看看 SIMD 的實體長什麼樣

要說清楚「vectorized 不等於 SIMD」，得先看看 SIMD 那條線到底做什麼。

現代 x86 CPU 有一組寬暫存器，普通 register 只能裝一個 64-bit 值，SIMD register 一次裝一整條：

以 AVX2 的 YMM0 為例，256 bit 被切成 8 個 lane：

YMM0:  | f32 | f32 | f32 | f32 | f32 | f32 | f32 | f32 |
        lane0 lane1 lane2 lane3 lane4 lane5 lane6 lane7

當你發一條 vmulps ymm0, ymm1, ymm2，8 個 lane 走同一條指令、同一批 pipeline stage，平行處理，不是一個 cycle 做完。主流 Intel／AMD 上這條指令 latency 大約 4 cycles，reciprocal throughput 大約 0.5。重點是一條指令做 8 件事，不是跑得快 8 倍，更不是一個 cycle 乘完。這是硬體把並行做在指令裡，不是軟體排程出來的。

這就是「Single Instruction Multiple Data」的字面意思，以前 for 迴圈裡跑八次的乘法，變成一條指令。

Lockstep：8 個 lane 必須走同一條指令

這裡就出現一個殘酷的規矩：8 個 lane 是 lockstep 的，它們必須執行同一條指令，不能各走各的。

想像這樣的情境：

for (int i = 0; i < 8; i++) {
    if (x[i] > 0) {
        y[i] = sqrt(x[i]);
    } else {
        y[i] = 0;
    }
}

如果 x = [1, -2, 3, -4, 5, -6, 7, -8]，lane0/2/4/6 該走 sqrt，lane1/3/5/7 該走 = 0，但 SIMD 沒辦法讓同一條指令在不同 lane 上做不同事。

於是編譯器要嘛放棄向量化（退回 scalar 一個一個跑），要嘛做「兩邊都跑」的 predication：8 個 lane 全部算 sqrt、8 個 lane 全部算 0，再用 mask 選擇要哪個結果。
分岔的邏輯永遠變成兩倍工
這就是為什麼迴圈裡有 branch 是 auto-vectorization 的頭號殺手，不是編譯器懶，是硬體物理上就這樣。

註：AVX-512 起 predication 才變成第一等公民——專用 mask register（k0–k7）加上 _mm512_mask_add_ps 這種全 ISA 級 masked 指令。AVX2 其實就有 vblendvps、vmaskmovps，SSE4.1 有 blendvps，所以不是「第一次有 mask」。ARM SVE 更是整個 ISA 以 predication 為底。但編譯器主動把純量 if 化成這些指令的門檻很高，需要側效應乾淨、兩支路都便宜。
實務上「資料佈局把 branch 拔掉」還是更可靠的策略。

一個栗子🌰：看得到 vs 真的用到

for (int i = 0; i < 1024; i++) {
    result[i] = price[i] * (1 - discount[i]);
}

這個迴圈是 vectorized 嗎？

• 從執行模型看：是一次處理 1024 個 tuple，不是 iterator 每次一列
• 從指令等級看：看編譯器心情，auto-vectorization 願意，就編出 vmulps；不願意，就 8 個 lane 空著、一列一列 scalar 跑。

換句話說：vectorized execution 給的是機會，SIMD 是不是真的用到，還要看下一層願不願意配合。

為什麼 null 是 SIMD 的頭號敵人

想像每列 null 都要問一次：

for (int i = 0; i < 1024; i++) {
    if (!is_null[i]) {                        // 每列一個 branch
        result[i] = price[i] * (1 - discount[i]);
    }
}

for 迴圈裡多了一個 branch，is_null[i] 又要從另一塊記憶體讀
這個 branch 直接把 lane 並行機會鎖死

要讓 vectorized execution 真的踩到 SIMD 的油門，三個條件同時要成立：

回頭看：Arrow bitmap 怎麼變成一次 SIMD 動作

先把昨天丟出來的那個詞講清楚。Arrow 一個 array 不是「一堆值」這麼簡單，它是幾塊連續記憶體拼起來的，規格叫 buffer。依型別，最多三塊：

• validity buffer：這列是不是 NULL
• data buffer：真正的值（price、discount）
• offset buffer：變長型別才有（字串每個值從哪裡開始、多長）

primitive 型別只有 validity + data 兩塊；第三塊是變長型別才出現。

validity 那塊不是一列一個 byte，而是 bitmap：一列只佔 1 bit，8 列塞進 1 byte。這塊用來裝 packed bits 的記憶體，程式碼裡常叫 validity buffer 或 bit buffer
兩個詞差在層次：bitmap 是格式，bit buffer 是放這個格式的那塊記憶體

Arrow 還規定了 polarity：1 = 有值、0 = NULL，而且從每個 byte 的最低位開始排，第一個 byte 的 bit 0 是第 0 列，單一系統用 0 還是 1 都沒差，兩個系統要交換資料才會差。
欄位確定沒有 NULL 時，這塊 buffer 可以整塊省略，後面思考題會繞回來。

把 SIMD 這一層攤開後，這個決定就有機械式的答案了。

如果 validity 用 per-row byte flag（byte 標一列），8 列 validity 佔 8 byte，data 佔 32 byte（假設 float32）。
迴圈就是：

for (int i = 0; i < 8; i++) {
    if (flag[i]) result[i] = ...    // 每列 branch
}

不能向量化。

用 bitmap（一 bit 一列），8 列 validity 只佔 1 byte。
上圖 Byte 0 就是 0b11011010（從右邊 lane 0 讀起：NULL、有值、NULL、有值、有值、NULL、有值、有值）。

這 1 byte 在 AVX-512 可以丟進 k register（k0–k7 是 AVX-512 才有的架構暫存器）。AVX2 沒有 mask register。展開 bitmap 的標準做法是：把這個 byte broadcast 進 ymm，跟一組 per-lane 選位常數 [1, 2, 4, 8, 16, 32, 64, 128] 做 AND，再 compare。少掉中間那步 AND，光 broadcast + compare 做不出各位元。展開後每個 bit 變成 32-bit 的全 0 或全 1。順序跟前面 YMM 圖一樣，lane 0 在左邊：

mask_ymm (lane0 → lane7) =
[0x00000000, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF,
 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF]

NULL 在 row 0、2、5，對應三個 0x00000000。接著用 _mm256_and_ps(data_ymm, mask_ps) 把這些位置歸零——mask_ps 是把上面那個整數 mask _mm256_castsi256_ps 過來的。_mm256_and_si256 收的是 __m256i，float 的 data_ymm 直接丟進去編不過。8 列的 NULL 過濾變成 SIMD 指令，branch 完全消失。

Arrow spec 那個看起來無關緊要的細節，真實作用其實是，讓上層的 vectorized execution 有機會真的踩到 SIMD 那顆油門。抽象層之間的合作，就靠這種規格層的一個決定。

今日思考題

如果一欄 99% non-null、另一欄 99% NULL，用 bitmap 的成本會一樣嗎？

提示三個方向：

• branch predictor（分佈極端會不會反而好猜？）
• compressed bitmap（Roaring 這類壓縮結構怎麼處理稀疏／密集？）
• all-null / no-null 極端 fast path 該不該做？

沒有標準答案，但答案應該會影響你怎麼設計一張欄位分佈長尾的表。

明天預告

今天我們把 SIMD 那顆油門解剖了一遍，但踩油門需要有大小合適的油門踏板，一批到底該裝幾列？

明天要看另一個被硬體決定的神奇數字，batch size 為什麼是 8192？不是 100，也不是 100 萬？順便會把batch 的概念再看一次：資料結構層 v.s 時間軸層

那就明天見～

Reference:
https://arrow.apache.org/docs/format/Columnar.html
https://weedge.github.io/perf-book-cn/zh/chapters/3-CPU-Microarchitecture/3-4_SIMD_cn.html
https://vutr.substack.com/p/apache-arrow-for-data-engineers
https://openproceedings.org/2026/conf/edbt/paper-163.pdf