Case Study 7.1: strlen() in x86-64 Assembly — Four Implementations

The classic string length function, four ways, with a performance story

Why strlen?

strlen is the "hello world" of assembly optimization. Every C programmer knows it. Every system depends on it. It has exactly one simple rule: scan bytes until you find a zero, count how many you passed. And yet the performance difference between a naive implementation and a production implementation spans an order of magnitude.

By the time you can write all four versions and explain why each is faster than the last, you understand loop mechanics, instruction selection, microarchitectural optimization, and SIMD programming — essentially all of assembly language.

The Function Contract

All four implementations share the same interface:

; strlen: compute length of null-terminated string
; Input:  rdi = pointer to null-terminated string
; Output: rax = number of bytes before the null terminator
; Preserves: all registers except rax

This matches the C library strlen: size_t strlen(const char *s).

Implementation 1: The Naive Loop

strlen_naive:
    xor     eax, eax            ; length = 0 (clears upper 32 bits too)
.loop:
    cmp     BYTE [rdi + rax], 0 ; is byte at current position null?
    je      .done               ; yes — we're done
    inc     rax                 ; no — advance length
    jmp     .loop
.done:
    ret

This is the most readable version. It does exactly what the English description says: check each byte, count until zero.

Register trace for input "hi\0" (bytes: 0x68, 0x69, 0x00):

What's slow about this: Every iteration is one byte, one comparison, one conditional branch, one unconditional jump. For a 100-byte string: 100 iterations × ~4 instructions = 400 instructions. The branch predictor learns the pattern (taken, taken, taken, not taken) and handles it reasonably well, but you're still doing a lot of work per byte.

Instruction count per byte: ~4 instructions.

Implementation 2: SCASB — The Hardware-Assisted Scan

x86 includes a string-scanning instruction, SCASB ("scan string byte"), specifically designed for this task.

strlen_scasb:
    mov     rcx, -1             ; counter = -1 (will increment past null)
    xor     eax, eax            ; search for byte value 0
    cld                         ; ensure direction flag is clear (forward scan)
    repne   scasb               ; repeat while [rdi] != al; dec rcx; inc rdi
    ; When REPNE SCASB stops: either ZF=1 (found null) or RCX=0 (counter exhausted)
    ; RCX = -(length + 2): one decrement for the null byte, plus we started at -1
    not     rcx                 ; NOT(-length - 2) = length + 1
    lea     rax, [rcx - 1]      ; subtract 1: length = rcx - 1
    ret

The REPNE SCASB instruction: - Compares [RDI] to AL - Decrements RCX - Increments RDI (since DF=0) - Repeats while ZF=0 AND RCX≠0

Why the math works: We start RCX at -1 (= 0xFFFFFFFFFFFFFFFF). Each iteration decrements RCX. When we find the null, RCX = -1 - (length + 1) = -(length + 2). NOT of -(length + 2) = length + 1. Subtracting 1 gives length.

The disappointing truth about SCASB: Despite being a "hardware string scan instruction," REPNE SCASB is implemented in microcode on modern x86 processors. It is typically slower than the naive loop for short strings and only competitive for medium-length strings. The CPU cannot effectively pipeline microcoded instructions the way it can with regular instructions. glibc's strlen does not use SCASB.

This is an important lesson: "specialized instruction" does not mean "fast instruction."

Instruction count per byte: approximately 1 SCASB iteration, but with microcode overhead.

Implementation 3: 8 Bytes at a Time — Bitmask Zero Detection

This is how production strlen implementations actually work for short-to-medium strings (up to ~16 bytes): process 8 bytes simultaneously using 64-bit arithmetic.

The key insight: given an 8-byte word, determine whether any byte in it is zero — using only integer arithmetic.

strlen_8bytes:
    mov     rcx, rdi            ; save original pointer
    ; Align pointer down to 8-byte boundary
    and     rdi, -8             ; rdi = rdi & ~7

    ; Read the first aligned qword (may include bytes before our string)
    ; We mask out bytes before the string start using a computed mask
    mov     rax, [rdi]          ; load aligned qword

    ; Compute how many bytes to skip at the start
    and     rcx, 7              ; rcx = offset of string start within qword (0-7)

    ; Mask out the pre-string bytes (fill them with non-zero so they don't trigger)
    ; Shift in 0xFF bytes for positions before our string
    mov     r8, rcx
    shl     r8, 3               ; r8 = bit offset = byte_offset * 8
    mov     rdx, -1             ; rdx = 0xFFFFFFFFFFFFFFFF
    shl     rdx, r8             ; rdx = mask: 0xFF... in valid bytes, 0x00 in pre-string
    or      rax, rdx            ; fill pre-string bytes with 0xFF (they won't be zero)

.scan_qwords:
    ; Zero-byte detection: does this qword contain any zero byte?
    ; Algorithm (Hacker's Delight technique):
    ;   t = qword - 0x0101010101010101
    ;   If any byte was 0x00, subtracting 0x01 borrows from the next byte,
    ;   setting bit 7 of that byte position to 1.
    ;   We AND with ~qword to only keep high bits from bytes that were zero
    ;   (borrowed), not from bytes that were already 0x80-0xFF.
    mov     rdx, rax
    mov     r8, rax
    sub     rdx, 0x0101010101010101
    not     r8
    and     rdx, r8
    and     rdx, 0x8080808080808080  ; isolate high bits only
    jnz     .found_null         ; at least one zero byte exists in this qword

    ; No zero byte — advance to next qword
    add     rdi, 8
    mov     rax, [rdi]
    jmp     .scan_qwords

.found_null:
    ; rdx has a set bit at position (byte_offset * 8 + 7) for each zero byte
    ; Find the least significant set bit to find the first zero byte
    bsf     rdx, rdx            ; bit scan forward: rdx = index of lowest set bit
    shr     rdx, 3              ; divide by 8 to get byte offset within qword

    ; total length = (aligned pointer + byte offset) - original pointer
    add     rdi, rdx
    sub     rdi, rcx            ; subtract original byte offset we saved
    ; wait — rcx was the byte offset within qword, not original pointer
    ; let's use the original approach: length = end_ptr - start_ptr

    ; Recalculate: actual length = (rdi + byte_offset) - original_start
    ; original_start was in rcx (we need to recover it)
    ; Correct implementation: save original pointer separately
    ret

The above is intentionally left slightly incomplete to show the complexity. A complete, correct 8-bytes-at-a-time strlen:

strlen_8bytes_correct:
    mov     r8, rdi             ; r8 = original pointer (saved)
    and     rdi, ~7             ; align down to 8-byte boundary

    ; Mask pre-string bytes in first qword
    mov     rax, [rdi]
    mov     rcx, r8
    and     rcx, 7              ; byte offset of start within first qword
    neg     rcx
    and     rcx, 7              ; bytes from start of qword to string start
    ; Fill those bytes with 0xFF so they don't trigger zero detection
    mov     rdx, rcx
    shl     rdx, 3
    mov     r9, -1
    shl     r9, rdx             ; shift: 0xFF in valid positions
    or      rax, r9

.qword_loop:
    ; Hacker's Delight zero-byte detection
    mov     rdx, rax
    mov     r9, rax
    sub     rdx, 0x0101010101010101
    not     r9
    and     rdx, r9
    and     rdx, 0x8080808080808080
    jnz     .found_zero_byte

    add     rdi, 8
    mov     rax, [rdi]
    jmp     .qword_loop

.found_zero_byte:
    bsf     rdx, rdx            ; find lowest zero byte bit position
    shr     rdx, 3              ; convert bit to byte offset
    add     rdi, rdx            ; rdi now points to the null byte
    sub     rdi, r8             ; subtract original pointer
    mov     rax, rdi            ; rax = length
    ret

What's fast about this: For a 100-byte string, the scan loop runs ~13 times (100 / 8 = 12.5, rounded up) instead of 100 times. The inner loop is approximately 9 instructions for 8 bytes checked, versus 4 instructions for 1 byte in the naive version. That's a ~3x speedup from fewer iterations, and the branch predictor works better too (the loop iterates many times before the exit is taken).

Instruction count per 8 bytes: ~9 instructions = ~1.1 instructions per byte.

Implementation 4: AVX2 SIMD — 32 Bytes at a Time

For longer strings, the winning implementation uses SIMD (Single Instruction, Multiple Data) vector instructions to check 32 bytes simultaneously:

strlen_avx2:
    vpxor   ymm0, ymm0, ymm0    ; ymm0 = 32 zero bytes (our search pattern)
    mov     rax, rdi            ; save original pointer

.avx_loop:
    vmovdqu ymm1, [rdi]         ; load 32 bytes (unaligned is OK with AVX2)
    vpcmpeqb ymm2, ymm1, ymm0  ; compare each byte with 0; result: 0xFF where byte=0
    vpmovmskb ecx, ymm2         ; extract high bit of each comparison byte → 32-bit mask
    test    ecx, ecx            ; any bits set? (any zero bytes found?)
    jnz     .found_null_avx     ; yes — found at least one null

    add     rdi, 32             ; advance 32 bytes
    jmp     .avx_loop

.found_null_avx:
    bsf     ecx, ecx            ; find first set bit (first zero byte position)
    add     rdi, rcx            ; rdi points to null byte
    sub     rdi, rax            ; length = null_ptr - original_ptr
    mov     rax, rdi
    vzeroupper                  ; required before mixing YMM with SSE (transition penalty)
    ret

The key instructions: - vpxor ymm0, ymm0, ymm0: zero all 32 bytes of YMM0 (our comparison target) - vmovdqu ymm1, [rdi]: load 32 unaligned bytes from memory into YMM1 - vpcmpeqb ymm2, ymm1, ymm0: compare each of the 32 bytes against zero; each result byte is 0xFF (match) or 0x00 (no match) - vpmovmskb ecx, ymm2: extract the most significant bit of each of the 32 result bytes into a 32-bit integer — a 1 bit means that byte was zero - bsf ecx, ecx: find the position of the first 1 bit (first zero byte)

Register trace for a 2-byte string "hi\0" (padded with garbage):

The 32-byte load at [rdi] reads: 0x68 0x69 0x00 [garbage 29 bytes]

After vpcmpeqb: byte 0 = 0x00 (not equal), byte 1 = 0x00, byte 2 = 0xFF (null found), bytes 3-31 = 0x00 or 0xFF (garbage)

After vpmovmskb: ECX has bit 2 set (and possibly others from garbage)

After bsf ecx, ecx: ECX = 2 (position of first set bit)

Result: rdi + 2 - rax = 2. Correct.

Note about the garbage: The vpcmpeqb will also set bits for any zero bytes in the 29 unread bytes. But bsf finds the first (lowest) set bit, which is the first zero byte — the null terminator. The garbage beyond it doesn't matter.

Instruction count per 32 bytes: ~7 instructions = 0.22 instructions per byte.

Performance Comparison

On a modern x86-64 (Zen 4, Alder Lake) for a 512-byte string:

The glibc strlen on Linux uses an AVX2 or SSE2 implementation selected at runtime via IFUNC (indirect function dispatch based on CPUID). For very short strings (0-8 bytes), the overhead of setting up SIMD may exceed the benefit, so production implementations include a fast path for short strings.

The Real Lesson

The four strlen implementations illustrate the fundamental trade-off in assembly optimization:

1. Correctness first — the naive loop is obviously correct; the AVX2 version requires careful thought about alignment, garbage bytes, and VZEROUPPER.

2. Abstraction cost — SCASB looks like the right tool but is slower due to microcode overhead. Specialized instructions are not always the fastest path.

3. Throughput thinking — the shift from "instructions per byte" to "bytes per instruction" (or per clock) is the key mental model shift. The goal is to do more bytes per unit of work, not fewer instructions per byte.

4. Hardware knowledge required — knowing that SCASB is microcoded, that YMM registers can process 32 bytes, and that bsf finds the first set bit in one clock cycle — all of this comes from reading CPU documentation, not from the C specification.

This is what makes assembly programming non-trivially harder than C: correctness is achievable in an afternoon, but understanding why one correct implementation is 8× faster than another requires architecture knowledge that no higher-level language exposes.