strlen 函數多種實現方式：從遞歸到指針運算的性能進化

前言

strlen 是 C 標準庫中最基礎的字符串函數，看似簡單，實則蘊含豐富的算法思想與工程優化技巧。本文從最直觀的遞歸寫法，進階到指針運算、標準庫優化（SIMD）、甚至無分支實現，層層剖析其性能演進邏輯。

一、基礎實現：三種經典寫法

1. 數組下標法（教科書風格）

size_t strlen_array(const char *s) {
    size_t len = 0;
    while (s[len] != '\0') len++;
    return len;
}

優點：直觀易懂。缺點：每次循環需計算 s + len 地址，編譯器優化後通常轉為指針形式。

2. 指針遍歷法（C 程序員慣用）

size_t strlen_ptr(const char *s) {
    const char *p = s;
    while (*p != '\0') p++;
    return p - s;
}

優點：避免重複加法，僅做指針遞增與解引用，編譯生成極精簡指令（典型 x86: scasb 或循環 cmp/jne）。

3. for 循環緊湊寫法

size_t strlen_for(const char *s) {
    const char *p = s;
    for (; *p; p++);
    return p - s;
}

二、進階優化：遞歸與尾調用

1. 朴素遞歸（棧溢出風險）

size_t strlen_rec(const char *s) {
    return *s ? 1 + strlen_rec(s + 1) : 0;
}

缺點：空間複雜度 O(n)，長字符串導致棧溢出，性能差。

2. 尾遞歸優化（需編譯器支持 -O2/-O3）

size_t strlen_tail(const char *s, size_t acc) {
    return *s ? strlen_tail(s + 1, acc + 1) : acc;
}
// 調用：strlen_tail(str, 0)

GCC/Clang -O2 可優化為迭代，但 C 標準不保證尾調用優化，生產環境**不推薦**。

三、標準庫級優化：SIMD 向量化與字對齊

1. glibc 實現核心思路

• 字對齊讀取：按 8 字節（64位）或 16 字節（SSE2）讀取，減少內存訪問指令數
• 零字節檢測：利用 (x - 0x0101010101010101) & ~x & 0x8080808080808080 技巧（HasZeroByte），單指令檢測 8 字節中是否含 \0
• 無分支循環：減少分支預測失敗

2. 簡化版 SIMD 風格實現（64位系統）

size_t strlen_simd(const char *s) {
    const unsigned long *p = (const unsigned long *)s;
    // 處理未對齊前綴
    while ((uintptr_t)p % sizeof(unsigned long) && *s) s++;
    // 向量化主循環
    for (; ; p++) {
        unsigned long word = *p;
        if (has_zero_byte(word)) {
            // 逐字節定位具體位置
            const char *c = (const char *)p;
            while (*c) c++;
            return c - s;
        }
    }
}

// 檢測 64 位字中是否有零字節
inline int has_zero_byte(unsigned long x) {
    return (x - 0x0101010101010101UL) & ~x & 0x8080808080808080UL;
}

3. SSE2/AVX2 實現（生產級）

現代 glibc/musl 使用 pcmpeqb (SSE2) 或 vpcmpeqb (AVX2) 指令，單周期比較 16/32 字節，配合 pmovmskb 生成掩碼，極致性能。

四、性能基準測試對比

五、工程最佳實踐

1. 永遠使用標準庫 strlen：經過數十年優化，針對目標 CPU 運行時分發最優實現
2. 避免重複計算長度：循環中緩存長度，或用 strnlen 限制最大掃描
3. 嵌入式無標準庫場景：優先用指針遍歷版，代碼體積小、無依賴、易審計
4. 編譯器內建函數：__builtin_strlen 允許編譯器常量折疊、死代碼消除

六、總結

從朴素指針遍歷到 SIMD 向量化，strlen 的演進縮影了 C 語言性能優化的歷程：算法複雜度相同時，指令級並行、內存訪問模式、分支預測友好度決定實際性能。理解這些原理，不僅能寫出更快的字符串處理代碼，更能培養系統級優化思維。