Implement Fast String Search Using SIMD

Vectorized Character Compare

Scanning for a byte in a buffer is memory-bound scalar work until SIMD compares 16 or 32 bytes per instruction. PCMPEQB marks equal bytes; movemask compresses the mask to a bitmask you scan with ctz.

cCopy
Loading…

libc and Production

glibc memchr and hyperscan use similar wide compares. Alignment prologue handles unaligned start; epilogue handles tail bytes.

For example, searching 1 KiB for '\n' might test 64 SIMD chunks instead of 1024 scalar comparisons.

For this exercise, you will implement find_byte_simd and benchmark against memchr. This task asks you to handle the final partial vector without reading past buffer end (use masked load or scalar tail).

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.