GLIBC strlen 源碼深度解析：位級並行檢測與對齊優化的極致效能

前言

標準庫 `strlen` 效能遠超朴素逐字節循環。GLIBC 採用**字長級並行檢測**（一次檢查 4/8 字節），結合**記憶體對齊預處理**、**魔數位運算**，實現 O(N/word_size) 掃描。本文逐行解析 GLIBC 2.x `strlen.c` 核心邏輯，揭示其高效原理。

核心算法思想

1. 對齊預處理：逐字節檢查直到地址對齊到 `sizeof(long)` 邊界。
2. 字長加載：每次載入一個 `unsigned long` (4/8 字節)。
3. 零字節檢測**：利用魔數 `0x01010101` / `0x80808080`，一次判斷 4/8 字節中是否含 `\0`。
4. 精確定位**：字長級命中後，退回逐字節定位具體位置。

魔數原理推導 (32 位為例)

設 `lomagic = 0x01010101`，`himagic = 0x80808080`。
對任意字長 `x`，計算 `((x - lomagic) & ~x) & himagic`：

• 若某字節 = 0：減法產生借位，該字節最高位置 1，`~x` 該字節最高位也為 1，`& himagic` 保留 → **非零**。
• 若某字節 > 0：減法不借位/借位被 `~x` 抵消 → 最高位 0。
• 若某字節 = 0x80：減法借位但 `~x` 最高位 0 → 結果 0 (誤報)，需逐字節複查。

**結論**：表達式非零 ⇒ **至少一個字節為 0** (或 0x80 誤報)。

GLIBC 核心代碼逐行註解

size_t strlen(const char *str) {
    const char *char_ptr = str;
    const unsigned long *longword_ptr;
    unsigned long longword, himagic, lomagic;

    // 1. 對齊預處理：逐字節直到地址 % sizeof(long) == 0
    for (; ((unsigned long)char_ptr & (sizeof(longword) - 1)) != 0; ++char_ptr)
        if (*char_ptr == '\0') return char_ptr - str;

    // 2. 設置魔數
    longword_ptr = (const unsigned long*)char_ptr;
    himagic = 0x80808080L;
    lomagic = 0x01010101L;
    if (sizeof(longword) > 4) {  // 64 位擴展
        himagic = (himagic << 32) | himagic;
        lomagic = (lomagic << 32) | lomagic;
    }

    // 3. 主循環：字長級掃描
    for (;;) {
        longword = *longword_ptr++;  // 載入 4/8 字節

        // 4. 零字節檢測
        if ((((longword - lomagic) & ~longword) & himagic) != 0) {
            // 5. 命中：退回逐字節精確定位
            const char *cp = (const char*)(longword_ptr - 1);
            if (cp[0] == 0) return cp - str;
            if (cp[1] == 0) return cp - str + 1;
            if (cp[2] == 0) return cp - str + 2;
            if (cp[3] == 0) return cp - str + 3;
            if (sizeof(longword) > 4) {
                if (cp[4] == 0) return cp - str + 4;
                if (cp[5] == 0) return cp - str + 5;
                if (cp[6] == 0) return cp - str + 6;
                if (cp[7] == 0) return cp - str + 7;
            }
        }
    }
}

效能對比 (作者實測 Solaris)

**關鍵觀察**：GLIBC 耗時隨長度增長極緩慢（主要耗在對齊預處理），朴素實現線性增長。

架構相關優化

• x86-64 (SSE2/AVX2)：`pcmpeqb` / `vpcmpeqb` 向量指令一次比較 16/32 字節，`pmovmskb` 獲取掩碼，`tzcnt` 定位首零 — **更快**。
• ARM64 (NEON)：`cmeq` + `umaxv` 類似向量化路徑。
• PowerPC (VSX)：`vcmpequb` 向量比較。

GLIBC 會在編譯時根據目標架構選擇最優實現（`sysdeps/x86_64/strlen.S` 等）。

工程啟示

1. 標準庫極致優化：不要重複造輪子，除非有極特殊需求（如已知極短字符串、特定編碼）。
2. 對齊訪問至關重要**：非對齊載入在某些架構觸發 SIGBUS 或劇烈降速。
3. 位運算技巧通用性**：`has_zero_byte` 邏輯廣泛用於 `strcpy`、`strchr`、`memchr` 等。
4. 讀取超前安全性**：字長讀取可能跨頁訪問不可讀頁面 → GLIBC 依賴「字符串後必有可讀頁」或在頁邊界回退逐字節。

參考資源

• GLIBC 源碼：`string/strlen.c`、`sysdeps/x86_64/strlen.S`
• Henry S. Warren, *Hacker's Delight*, Ch. 6 (Zero Byte Detection)
• Agner Fog, *Optimizing Software in C++*, Ch. 21 (String Functions)