Implement Fast String Search Using SIMD

Topic Overview

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.

Your Task

Implement the core of a SIMD memchr: compare 16 bytes at once against the byte you're looking for, turn the 16 comparison results into a 16-bit mask (_mm_movemask_epi8), and read match positions off the mask's set bits. The bytes that don't fill a final 16-byte chunk are checked one at a time. Report every match, the mask of each chunk that matched, and how many comparisons the SIMD version needed compared with a byte-at-a-time loop.

Input

The first line is needle C, where C is a single printable character or 0xHH. Everything after that line is the text, including its newlines, except that one final newline at the very end is removed.

Algorithm

• Split the text into chunks of 16 bytes starting at offset 0. For each full chunk, compare all 16 bytes with the needle. The mask has bit k set when byte k of the chunk matches (bit 0 = the chunk's first byte).
• The remaining len mod 16 bytes are the tail, compared one by one.

Output

cCopy
Loading…

• Print a chunk line only for chunks with at least one match, with the mask as 4 lower-case hex digits.
• Print a tail line only if some tail byte matched.
• matches: N at ... lists every position, or reads matches: 0 when there are none.
• The ratio is len / (chunks + tail) with two decimals. For empty text, print text 0 bytes: nothing to search instead.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Build each chunk's mask first, then extract positions by repeatedly taking the lowest set bit (__builtin_ctz(mask), then mask &= mask - 1).
2. On the judge, SSE2 intrinsics (_mm_loadu_si128, _mm_cmpeq_epi8, _mm_movemask_epi8) are available. A plain loop that builds the same mask is also accepted.

Hidden tests cover a needle given in hex (a newline, in a text spanning several lines) and a text of exactly 32 bytes (no tail) with matches at the first and last byte of each chunk.