casei

Fast case-insensitive UTF-8 substring search for one literal or a whole set.

IndexFold returns the byte offset of one literal. A compiled Matcher returns the leftmost match from many literals in one scan. Both use Unicode simple folding, the same case relation as Go's regexp (?i) on valid UTF-8.

The result

On Intel Ice Lake and Sapphire Rapids with AVX-512F, BW, and VBMI, casei finished first on every row of its 36-row arena. Each row includes the fastest eligible result from Go regexp, PCRE2-JIT, rust/regex, Vectorscan, StringZilla, veloz, and Rust Aho-Corasick where their contracts apply.

host	rows won	worst median x_vs_best	worst sample	median speedup
Ice Lake	36/36	0.9624	0.9736	1.80×
Sapphire Rapids	36/36	0.9716	0.9799	1.56×

x_vs_best is casei time divided by the fastest other implementation on the same workload. Lower is better. Every one of the 216 measured row samples was below 1.0. Every row had 5 to 7 entrants. casei reported 512-bit dispatch, and Vectorscan reported a 512-bit VBMI database.

Rebar provides a useful independent check. It asks engines to enumerate every non-overlapping match instead of returning the first one. casei now wins all five Rebar rows that request the same Unicode folding relation on both CPUs.

Rebar selection	Ice Lake	Sapphire Rapids
same Unicode contract	5/5 wins, worst 0.8794	5/5 wins, worst 0.8999
all 18 representable stress rows	9/18 wins	9/18 wins

The other 13 Rebar rows request ASCII-only case matching. casei keeps Unicode simple-fold semantics on them, so those timings are published as stress data rather than folded into the product claim. The complete table and raw receipts are in REBAR.md.

The speed claim is for the AVX-512 implementation. The portable implementation is correct and scalar. There is no NEON kernel yet.

The idea

Most of search is proving that a match does not start here.

Imagine 64 possible starting positions in a block of text. casei checks a few useful bytes for all 64 positions at once. The result is a 64-bit mask:

possible starts      0 1 2 3 4 5 ... 63
first useful byte    0 0 1 0 0 0 ...  0
second useful byte   0 0 1 0 1 0 ...  0
                     -------------------- AND
survivors             0 0 1 0 0 0 ...  0

An empty mask skips the whole block. A surviving bit means "check this one." The exact Unicode plan checks it before casei can report a match.

Compilation builds those two parts together:

patterns
   |
   +--> conservative byte sieve --> reject impossible starts in blocks
   |
   +--> exact simple-fold plan ----> decide matches, offsets, order, and ties

That is where the advantage comes from:

1. The compiler knows the question is literal search under simple folding. It can choose byte tests that a general regex engine cannot assume.
2. One pattern and 512 patterns use one compiled plan and one traversal. The many-pattern sieve carries pattern tags, so exact replay checks only the literals that survived.
3. Unicode decoding happens at survivors instead of at every byte. Width-changing folds such as k/K/K are represented explicitly.
4. The AVX-512 kernels keep several independent blocks in flight and keep set arithmetic in mask registers. The hand-written schedule matters: a complete port to Go's experimental SIMD package stayed correct and lost the required field row it was tested on.

The one-page explanation follows this model into the actual filters, assembly, competitor implementations, and measurements.

Use it

go get github.com/tsenart/casei

// One needle.
if casei.ContainsFold(line, "payment declined") {
	alert(line)
}

// Byte offset, or -1 when absent.
at := casei.IndexFold(line, "payment declined")

// Many needles, one compiled plan. Leftmost match wins. A tie goes to the
// lowest pattern index.
m := casei.NewMatcher([]string{"fatal panic", "oom killed", "segfault"})
if match, ok := m.Find(line); ok {
	fmt.Println(m.Patterns()[match.Pattern], match.Start)
}

// Enumerate non-overlapping matches. Width is the number of source bytes
// consumed by this occurrence, which can differ across a Unicode fold orbit.
m.Each(log, func(match casei.Match, width int) bool {
	fmt.Println(match.Pattern, match.Start, width)
	return true
})

NewMatcher compiles once. Reuse the matcher across searches. Find is safe for concurrent use. Search is allocation-free on the published paths after compilation. A generic plan with a longest pattern above the 256-entry inline ring may allocate an offset ring during search.

The library requires Go 1.22 or newer. Rebuilding the native benchmark field requires Go 1.24 or newer.

Semantics

On valid UTF-8, matching follows Unicode simple folding:

• k, K, and Kelvin sign K match.
• s, S, and long s ſ match.
• σ, ς, and Σ match.
• ß and ẞ match. ß and ss do not.

Invalid UTF-8 bytes are opaque one-byte units. Results use source byte offsets. Matcher.Find returns the leftmost start, with ties resolved by the lowest pattern index. Matcher.Each emits non-overlapping matches in that order and returns the exact source width of each occurrence.

Correctness is checked against Go regexp (?i) by deterministic differential tests and two fuzz targets. The portable path, AVX2 path, and AVX-512 path run the same contract suite. Filter tests include exhaustive byte-pair projections, randomized tails, malformed input, width-changing folds, and ordering ties.

How the field was measured

The arena builds every native entrant from pinned source. It rejects an entrant that silently dispatches below the width promised for that tier. Each row reports active entrants and their observed vector widths.

BenchmarkBar measures casei beside each eligible competitor six times. The order alternates, so each operation goes first in three pairs. The median paired ratio is computed for each competitor, and the largest ratio names the fastest field result. The checked-in acceptance run repeats the complete board three times on each host, pinned to one core.

The current raw transcripts are here:

• Ice Lake BenchmarkBar
• Sapphire Rapids BenchmarkBar
• Receipt verifier and summary

The repository also keeps the earlier sequential-window runs that exposed measurement drift near parity. They failed the publication bar and are part of the methodology record.

To rebuild the field and rerun all 36 rows on a qualifying Linux host:

./scripts/reproduce.sh

The script requires x86-64 with AVX2 and AVX-512F/BW/VBMI. It builds PCRE2, Vectorscan, rust/regex, Rust Aho-Corasick, and StringZilla from their pinned sources before it runs the board.

What changed after Rebar found the gap

The original arena covered first-match search and single-needle counting. It did not contain multi-pattern enumeration or the two focused shapes that made Rebar's Russian rows hard. Perfloop optimized the board it was given. Rebar showed what the board had omitted.

The follow-up added three focused arena rows and kept the Rebar rows as an external gate. The surviving construction combines:

• tagged interior anchors for several Unicode literals;
• raw confirmation that follows one-, two-, and three-byte fold spellings and returns the source width it proved;
• an exact common-byte origin gate for eligible multi-pattern plans; and
• wider assembly schedules that scan several cache lines before testing masks.

The result closes all five same-contract Rebar rows while preserving all 36 arena wins. REBAR.md contains the before/after account and every external row.

Perfloop record

I built casei as a hard, self-contained test for Perfloop. I supplied the problem, field, and constraints. Perfloop proposed implementations, measured them against the field, and sent survivors to an independent verifier.

• Original full-engine Case
• Shared interior-anchor Case
• Dispersed Unicode-probe Case
• Raw-confirmation Case
• Complete Go SIMD backend, rejected

The public Cases are the experiment log. NOVELTY.md records the constructions that failed on paper or in measurements. Negative results stay in the repo so the next attempt starts from evidence.

Limits

• Published speed numbers cover x86-64 AVX-512F/BW/VBMI on Intel Ice Lake and Sapphire Rapids.
• The portable path is scalar. ARM64 is correct, with no NEON speed claim.
• The API searches literals and finite literal sets.
• Folding is Unicode simple folding. Full-fold expansions such as ß -> ss are outside the contract.
• Plan compilation has a cost. Cache a matcher for repeated searches.
• The 36-row arena belongs to this repository. Its sources, field, dispatch, failed measurements, and verifier are open and pinned. Rebar is the external cross-check.

Read next

• How it works
• Direct Rebar audit
• Known field and prior art
• Novelty and negative results
• Current acceptance receipts
• Rebar receipts