Case Study 11.1: Implementing strlen() in Assembly — Hand-Optimized vs. Compiler Output

The Function

strlen counts bytes until the first null byte. It is one of the most-called functions in any C program that handles strings, and its performance matters. We will examine four implementations in increasing sophistication.

Version 1: Naive Byte-at-a-Time

; size_t strlen_naive(const char *s)
; RDI = s, returns count in RAX

section .text
global strlen_naive

strlen_naive:
    xor  eax, eax           ; length = 0
.loop:
    cmp  byte [rdi + rax], 0  ; is s[length] == '\0'?
    je   .done
    inc  rax
    jmp  .loop
.done:
    ret

This processes one byte per iteration. For a string of length N, it executes N+1 iterations. On modern hardware: approximately 1 byte per clock cycle (limited by the loop overhead and sequential dependency on RAX).

Version 2: Using REP SCASB (Chapter 12 preview)

; strlen using REPNE SCASB
strlen_scasb:
    xor  eax, eax
    not  rcx               ; rcx = 0xFFFFFFFFFFFFFFFF (maximum count)
    repne scasb            ; scan: decrement RCX, advance RDI, until [RDI-1] == AL (0)
    not  rcx               ; negate count
    dec  rcx               ; adjust for initial NOT
    mov  rax, rcx
    ret

REPNE SCASB processes one byte per cycle in the hardware microcode loop, but has lower overhead than a software loop. The idiom not rcx → scan → not rcx; dec rcx computes the length from the remaining count.

Version 3: Compiler Output at GCC -O2

size_t strlen(const char *s) {
    const char *p = s;
    while (*p) p++;
    return p - s;
}

GCC -O2 on x86-64 produces (with vectorization disabled):

; GCC -O2 (scalar, no auto-vectorization)
strlen_gcc_scalar:
    mov  rax, rdi              ; rax = start pointer
.loop:
    movzx ecx, byte [rax]      ; ecx = *rax (zero-extend)
    inc  rax
    test cl, cl                ; is it zero?
    jnz  .loop                 ; no: continue
    sub  rax, rdi              ; length = current - start
    dec  rax                   ; adjust (we went one past the null)
    ret

Note: GCC reorganizes the pointer instead of an integer counter to avoid the final subtract. The loop exits after incrementing past the null byte, so we subtract 1.

Version 4: GCC -O3 with Auto-Vectorization

With optimization enabled, GCC produces a significantly longer but faster function:

; Conceptual structure of GCC -O3 vectorized strlen:

strlen_vec:
    ; Phase 1: Align to 16-byte boundary
    test  rdi, 15              ; is pointer 16-byte aligned?
    jz    .aligned
    ; ... process bytes until aligned (1-15 bytes, scalar) ...

.aligned:
    ; Phase 2: SIMD loop — process 16 bytes per iteration
    ; Uses SSE2: load 16 bytes, compare with zero vector, check for any zero
    pxor  xmm0, xmm0           ; xmm0 = 0x00...00 (zero comparand)
.simd_loop:
    pcmpeqb xmm1, [rdi]        ; compare each byte of [rdi] with 0, result: 0xFF if match, 0x00 if not
    pmovmskb eax, xmm1         ; create 16-bit mask: bit i set if byte i was zero
    test  eax, eax
    jnz   .found               ; found a null byte in this block
    add   rdi, 16              ; advance by 16
    jmp   .simd_loop

.found:
    ; bsf eax, eax             ; find position of first set bit (lowest zero byte)
    ; Compute length from position
    ...
    ret

The vectorized version processes 16 bytes per iteration, achieving roughly 16× throughput compared to the byte-at-a-time version.

Performance Comparison

Measured on Intel Ice Lake, strings of varying lengths:

(cy = CPU cycles, approximate, L1-cached data)

For short strings, the overhead of alignment + vectorization setup makes the SIMD version barely faster. For long strings (thousands of bytes), it is 10-60× faster.

Register Trace: Naive strlen("Hello")

s = pointer to ['H','e','l','l','o','\0'], in RDI

Iteration 0: [rdi+0] = 'H' (0x48) ≠ 0, RAX = 0 → 1
Iteration 1: [rdi+1] = 'e' (0x65) ≠ 0, RAX = 1 → 2
Iteration 2: [rdi+2] = 'l' (0x6C) ≠ 0, RAX = 2 → 3
Iteration 3: [rdi+3] = 'l' (0x6C) ≠ 0, RAX = 3 → 4
Iteration 4: [rdi+4] = 'o' (0x6F) ≠ 0, RAX = 4 → 5
Iteration 5: [rdi+5] = '\0' (0x00) == 0, jump to .done
RAX = 5 (length of "Hello")

What the glibc Implementation Does

The glibc (GNU C Library) strlen implementation (in sysdeps/x86_64/strlen.S) uses AVX2 instructions to process 32 bytes per iteration on processors that support AVX2. The algorithm:

1. Handle unaligned bytes before the first 32-byte aligned boundary
2. Check 32 bytes at a time using VPCMPEQB (compare 32 bytes with zero simultaneously)
3. Use VPMOVMSKB to extract a 32-bit mask of zero-byte positions
4. Use TZCNT (trailing zero count) to find the first zero byte's position

This achieves throughput of approximately 32 bytes per clock in the SIMD loop — 32× faster than the naive implementation for long strings.

The Lesson

The naive byte-at-a-time implementation is correct and readable. For a bootloader or kernel initialization code where strings are short and performance is not critical, it is entirely appropriate. For a production standard library called on every string operation in every program, it is 10-60× too slow.

The progression from naive to vectorized shows the full range of optimization techniques: reducing loop overhead, using SIMD to process multiple bytes per instruction, and handling alignment edge cases correctly. The compiler (at -O3) handles the vectorization automatically for simple scalar C code. But the production glibc implementation is hand-written in assembly because compilers cannot always recognize all the alignment edge cases and choose the most aggressive instruction forms.

When writing library functions that will be called millions of times per second, assembly is still worth the investment.