基于SWAR优化x86-64汇编strlen的提速方法探讨

以下是一个基于SWAR（SIMD Within A Register）技术实现的x86-64汇编strlen函数：该函数接收字符数组形式的字符串指针，仅使用通用寄存器实现（不依赖XMM寄存器或SSE指令）。它通过位操作(v - 0x01010101) & ~(v & 0x80808080)以8字节步长检测字符串中的零终止字节；若检测到零字节，则逐字节遍历至零字节以避免页错误。其中对齐逻辑参考GNU Libc的实现，对应的C代码如下：

for (char_ptr = str; ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0; ++char_ptr){
    if (*char_ptr == '\0'){
        return char_ptr - str;
    }
}

对应的汇编实现如下：

; rdi <- const *char
; rax <- counter + return value
; r10 <- current array for computation
; rcx,r8 <- Bitmask
; rsi <- Arr for calculation 
            
strlen:
    PUSH rbp
    SUB rsp,8
 
    XOR rax,rax    
    MOV r8,31
alignment:
    CMP byte [rdi+rax],0
    JE end
    
    MOV rsi,rdi
    ADD rsi,rax
    AND rsi,r8
    CMP rsi,0
    JE while_parallel
    INC rax
    JMP alignment       
          
while_parallel:  
    MOV rcx,0x01010101
    MOV r8,0x80808080
while_parallel_loop:  
    MOV r10,[rdi+rax]
    MOV rsi,r10
    
    NOT r10
    AND r10,r8
    SUB rsi,rcx
    AND rsi,r10
    
    CMP rsi,0
    JNE while_single
    ADD rax,8
    JMP while_parallel_loop
    
while_single:
    CMP byte [rdi+rax],0
    JE  end
    INC rax
    JMP while_single    
end:
    ADD rsp,8
    POP rbp
    RET

注：不考虑使用任何SSE指令或XMM寄存器。

可优化的方向及具体实现 #

1. 修正对齐掩码并简化对齐循环

原代码中使用31作为对齐掩码是错误的——x86-64平台下8字节对齐的掩码应为7（sizeof(longword)-1，longword为8字节）。同时可以直接计算未对齐字节的数量，一次性处理所有未对齐部分，减少循环分支次数：

strlen:
    XOR rax,rax    
    ; 计算当前地址到下一个8字节对齐边界的偏移
    MOV rsi, rdi
    AND rsi, 7
    JZ while_parallel  ; 已经对齐，直接进入并行检测
.alignment_loop:
    CMP byte [rdi+rax], 0
    JE end
    INC rax
    DEC rsi
    JNZ .alignment_loop

2. 将常量加载移出循环

原代码中每次进入while_parallel块都会重复加载0x01010101和0x80808080两个常量，可将其移到函数开头，仅加载一次：

strlen:
    ; 提前加载常量，避免重复执行
    MOV rcx, 0x01010101
    MOV r8, 0x80808080
    XOR rax,rax    
    ; ... 对齐逻辑 ...
while_parallel_loop:  
    MOV r10,[rdi+rax]
    MOV rsi,r10
    
    NOT r10
    AND r10,r8
    SUB rsi,rcx
    AND rsi,r10
    ; ... 后续检测逻辑 ...

3. 优化零字节检测的位运算依赖链

调整位运算指令的顺序，让无依赖的指令并行执行，减少CPU等待时间：

while_parallel_loop:  
    MOV r10, [rdi+rax]
    ; 并行执行无依赖的操作：NOT和SUB
    MOV rsi, r10
    NOT r10                  ; 独立于SUB操作
    SUB rsi, rcx             ; 独立于NOT操作
    AND r10, r8
    AND rsi, r10
    
    CMP rsi, 0
    JNE while_single
    ADD rax,8
    JMP while_parallel_loop

4. 利用已加载的寄存器数据优化逐字节检测

进入while_single时，r10中已经保存了当前8字节的字符串数据，无需再次访问内存，直接在寄存器中检测第一个零字节的位置，减少内存访问开销：

while_single:
    ; 检测r10中第一个零字节的位置
    TEST r10, 0x00000000000000FF
    JZ .found
    TEST r10, 0x000000000000FF00
    JZ .found1
    TEST r10, 0x0000000000FF0000
    JZ .found2
    TEST r10, 0x00000000FF000000
    JZ .found3
    TEST r10, 0x000000FF00000000
    JZ .found4
    TEST r10, 0x0000FF0000000000
    JZ .found5
    TEST r10, 0x00FF000000000000
    JZ .found6
    TEST r10, 0xFF00000000000000
    JZ .found7
    ; 理论上不会执行到此处，因为前面已检测到零字节
.found:
    JMP end
.found1:
    ADD rax, 1
    JMP end
.found2:
    ADD rax, 2
    JMP end
.found3:
    ADD rax, 3
    JMP end
.found4:
    ADD rax, 4
    JMP end
.found5:
    ADD rax, 5
    JMP end
.found6:
    ADD rax, 6
    JMP end
.found7:
    ADD rax, 7
    JMP end

5. 消除不必要的栈操作

原函数中保存和恢复rbp、调整栈指针的操作是多余的——该函数并未使用rbp作为栈帧指针，也没有需要栈对齐的内存访问，直接省略这些操作可减少4条指令的开销：

strlen:
    MOV rcx, 0x01010101
    MOV r8, 0x80808080
    XOR rax,rax    
    ; ... 对齐逻辑 ...
end:
    RET

内容的提问来源于stack exchange，提问作者HeapUnderStop