2026 年 7 月 12 日

前幾天我在最佳化一個特定領域的壓縮器，如同往常一樣。

其中一個重要的問題是將輸入字串分塊，並為每個區塊選擇最佳的壓縮編碼（不同的編碼對不同字元壓縮效果較好，因此如何分割並不明顯）。前一篇文章描述了這個演算法，如果你有興趣可以參考，但基本上就是尋找網格上的最短路徑。對於每個儲存格，演算法會計算接下來的最佳儲存格。從第一個儲存格依序參照到最後一個，就能得到最佳的編碼順序。

uint8_t next_j[n_symbols][8]; // references to the next cell

// The core of the algorithm populating `next_j`.
// Don't worry too much about understanding it, it's just here for completeness.
__m128i best_path_length = _mm_setzero_epi16();
for (int i = n_symbols - 1; i >= 0; i--) {
    __m128i tmp = _mm_add_epi16(cost[i], best_path_length);
    __m128i minpos = _mm_minpos_epu16(tmp);
    __m128i cost_without_switching = _mm_sub_epi16(tmp, _mm_broadcastw_epi16(minpos));
    __m128i cost_with_switching = _mm_set1_epi16(switch_cost);
    best_path_length = _mm_min_epu16(cost_without_switching, cost_with_switching);
    __m128i choice = _mm_blendv_epi8(
        _mm_set1_epi16(_mm_extract_epi16(minpos, 1)),
        _mm_set_epi16(7, 6, 5, 4, 3, 2, 1, 0),
        _mm_cmpeq_epi16(best_path_length, cost_without_switching)
    );
    _mm_storeu_si64(&next_j[i], _mm_packs_epi16(choice, choice));
}

// Find the optimal encoding for each symbol.
// Chunk boundaries are located where encodings change.
uint8_t encoding[n_symbols];
uint8_t j = 0; // always start with encoding 0 for simplicity
for (int i = 0; i  n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}

那個長迴圈不是這篇文章的主題，它已經經過良好最佳化。我們要討論的是第二個迴圈，乍看之下簡單許多。

延遲

排除寫入操作，迴圈主體僅有 j = next_j[i][j]，編譯後只會產生一條 mov 指令。這怎麼可能還不夠最佳？

如果我們在 1984 年寫程式，這確實就足夠了，但現代處理器具備指令層級平行能力——也就是它們可以同時執行多條指令。這甚至能跨迴圈迭代運作，也是我們通常在評估迴圈效能時，不會特別在意 i n_symbols 與 i++ 指令的原因——它們通常不會阻礙 CPU 執行更多工作。

不過，關鍵在於你無法同時執行兩條相依的指令。在我們的案例中，每一次迴圈迭代必須等到前一次結束才能開始，因為 j 會在迴圈中被傳遞，所以我們受到記憶體存取延遲的限制，即使有快取也相當明顯。

這能改善嗎？在這個特定案例中，是可以的！我們預期不會有太多區塊，因此 next_j[i][j] 很有可能就等於 j。如果我們能讓 CPU 預測 j 保持不變，這個迴圈就會從延遲導向轉為吞吐量導向。

雖然我們無法直接控制位址預測，但我們可以用分支預測來模擬：

for (int i = 0; i  n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}

如果 CPU 預測 if 主體不太可能發生，它就會忽略它，因此不會看到不同迭代之間的相依性。當條件最終評估為 true 時，分支預測錯誤處理機制會啟動，撤銷錯誤的推測寫入，並以正確的 j 重新開始。這正是我們想要的結果！

對編譯器說謊

唯一的問題是，從編譯器的角度來看，這個 if 完全是無用的。如果 j 是在記憶體中，它會避免可能寫入唯讀記憶體，但它是在暫存器中。與我們通常使用編譯器提示的大多數情況不同，我們想把無分支程式碼轉換成分支程式碼，而不是反過來——而且沒有任何編譯器支援這種做法，尤其是這種任何CSE pass 都會毫不猶豫地移除的程式碼！愚蠢的編譯器不了解整數有硬體來源。

我所知道的唯一實現方式，就是透過轉型為 volatile，讓條件判斷與指派看起來像是獨立的：

for (int i = 0; i  n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}

在合成基準測試中，這個改變將迴圈從 320 微秒加快到 80 微秒（在我的資料上）。（這看起來不多，但這個迴圈在壓縮過程中會執行多次，所以累積起來很可觀。）

在更實際的實驗中，我只觀察到 2 倍的提升，很可能是因為 LLVM 的程式碼生成次佳。不過還是值得的！

附註

有趣的是，在這個特定演算法中，每個 next_j[i][j] 只能是兩個值之一——要麼是 j（最常見），要麼是某個只依賴 i、而不依賴 j 的值。因此我可以用該值搭配位元遮罩來取代每個 8 元素陣列 next_j[i]，這樣會自動讓 if 在語意上變得重要，也就不需要 volatile 的把戲了。但這可能會讓程式變慢，因為測試變數位元比起比較運算更慢（至少在 x86 上是如此）。