Why Wirefilter Needed Faster Substring Searches

Cloudflare's Firewall Rules product is built on Wirefilter, an engine that evaluates customer-written boolean expressions against incoming requests. It's already used at scale across the edge, and with more products like the Web Application Firewall expected to run on the same engine, reducing CPU consumption has become a priority. The work involved both building a reliable benchmark system and then applying the insights from that system to optimize the hottest code paths.

Measuring Performance the Hard Way

Time-based measurements are too volatile in Cloudflare's distributed environment. The team turned to hardware counters instead, using Linux's perf_event_open API to record counters from inside the binary. This gives per-stage data for parsing, compilation, analysis, and execution—stages that external profilers can't easily isolate. JSON Lines output makes the data easy to ingest and store for visualization. In addition to CPU counters, getrusage and clear_refs track maximum resident set size (RSS) to understand memory impact.

The benchmark results pointed to a clear conclusion: dynamic dispatch, which Wirefilter was previously engineered to minimize, is not the main bottleneck. Roughly 65% of execution time goes to operations like comparisons and substring searches. The remaining 35% mostly involves reading request field memory, not resolving function calls.

Benchmarking as a Service

Building a useful benchmark system at Cloudflare's scale required solving some practical problems. Standard CI agents use virtualization and sandboxing, which blocks access to hardware counters. Running benchmarks on a dedicated machine solves that. But the bigger issue was volume: the full filter set was too large to run routinely, making the benchmark suite itself too slow for regular regression testing.

Three tricks brought a full run down to roughly 20 minutes:

  • Deduplication. Wirefilter can serialize filters to JSON, which revealed that only about a third are structurally unique. Dropping duplicates cut significant time.
  • Sampling. Random sampling reduced the filter count further, with a fixed seed to preserve reproducibility across runs.
  • Partitioning. Grouping filters by Wirefilter language feature before sampling ensures broad coverage and surfaces exactly which feature areas are affected by a performance change.

The framework now runs a full benchmark before each release to catch performance regressions early.

Why Regex Was Beating the contains Operator

The contains operator checks whether a substring—the "needle"—appears in a field value, the "haystack." Wirefilter supports raw byte expressions that don't conform to UTF-8, so it couldn't use Rust's String::contains. The engine used the memmem crate, which implements a two-way substring search on raw bytes.

It worked, but rewrites of contains filters using regular expressions were often faster for identical matches:

http.host matches "example"

Specialized substring search should beat a general regex engine. The explanation: Rust's regex library ships a whole collection of dedicated matchers for simple expressions. Tools like ripgrep use this same approach for fixed-string patterns. But Wirefilter couldn't easily reuse that machinery—since it dispatches cases at the interpreter level, matching on an enum deep inside the regex crate at execution time isn't clean.

Algorithm 1: First and Last Bytes

Wirefilter integrated a SIMD-based substring search based on Wojciech Muła's prior work. The algorithm works roughly like this:

  1. Fill a SIMD register with the needle's first byte, repeated.
  2. Load a chunk of the haystack into a register and perform a bitwise equality with the first register.
  3. Any position with a zero can't be a match start—it doesn't share the needle's first byte.
  4. Repeat with the needle's last byte, offsetting the haystack to rule out bad end positions.
  5. AND the two masks together, drastically narrowing candidate positions.
  6. Verify each remaining candidate with memcmp; the first match ends the search.
  7. If no match, advance to the next haystack chunk.

Instruction-count benchmarks showed significant improvement over the memmem crate.

A naive SIMD implementation reads past the end of the haystack to keep registers full, masking out false positives from that overread region. Cloudflare's security requirements ruled out that approach entirely. The team ported Muła's library to Rust and open-sourced it as the sliceslice crate, applying an overlapping-registers technique. On a 4-byte SIMD system scanning the string "abcdefghij," the modified version repeats tail bytes of one register as head bytes of the next, so no out-of-bounds reads occur.

Repeating bytes in adjacent registers doesn't change the result, but it does require bitmasking to avoid duplicated checks in the final register and minimize memcmp calls. For very short haystacks that fit in a single register, overlapping isn't possible at all. The implementation falls back to smaller SIMD register sizes—but no lower than SSE2—and beyond that uses a Rabin-Karp search implementation.

Resisting Worst-Case Attacks

Muła's algorithm has a known worst case. Given a needle like /wp-admin/ and a haystack of thousands of / characters, both chosen bytes match everywhere, turning the search into a slow bruteforce. For a security product, that's not acceptable—an adversary could intentionally trigger it.

The fix is randomized selection. Wirefilter keeps the first byte for its SIMD-friendly properties but picks the second byte at random. An attacker can't predict which byte will need to match, so they can't reliably construct a pathological input. The randomized version is slower than Muła's original but still shows a strong improvement over both memmem and the regex crate in instruction count.

The crate is available on crates.io as sliceslice, and the work will inform further optimizations to Wirefilter's execution engine.