Performance

A throughput figure on its own says little: it depends on the text, on how many patterns there are and how often they hit, and on whether the implementation being compared did the same work. So these measurements follow the discipline of the Rust crate's rebar suite. The corpora are rebar's own, fetched from a pinned commit and checked against their SHA-256. Every implementation runs the same pattern set over the same bytes in the same search mode. And every row carries the number of matches found, which must agree between all the implementations on that row and, where rebar records a count for that pattern set and haystack, must reproduce it. A benchmark whose counts differ is measuring different work, and the report script fails on it.

The search modes are the ones on the compatibility page: overlapping is find_all and find_overlapping_iter; overlapping_iter is find_iter, consumed lazily; standard is Stream.feed_nonoverlapping over the whole input and Rust's default find_iter; leftmost_longest and replace are the leftmost-longest search and replace_all; and the _stream modes feed the input in 4 KiB chunks. The Python columns time the call from Python, Python objects per match included, which is what a Python caller pays. Each cell is the median of at least three runs and at least one second of running, on one core, after building the automaton once.

Results

Generated by bench/report.py from one run of bench/run.sh; the environment is listed first. The machine is a shared cloud VM, so treat the figures as order-of-magnitude comparisons between columns, not as absolute numbers for your hardware. Reading the results below says what to make of them.

• date: 2026-09-04T15:01:52Z
• cpu: Intel(R) Xeon(R) Processor @ 2.80GHz x4
• os: Linux 6.18.44-fc-v24 x86_64
• ocaml: 5.3.0
• rust: rustc 1.94.1 (e408947bf 2026-03-25) / aho-corasick 1.1.5
• python: 3.11.15
• pyahocorasick: 2.3.1
• ahocorasick_rs: 1.0.3
• seconds per measurement: 1

Reading the results

Ordinary text, few patterns

On English text where matches are rare — the Sherlock and OpenSubtitles name workloads — this library scans at 170 to 200 MB/s, within fifteen percent of the Rust crate's bare NFA and close to pyahocorasick's C engine. The Rust crate's default configuration is up to sixty times faster on the two- and three-pattern rows because it is not running an automaton at all: its Teddy prefilter looks for candidate bytes with SIMD instructions and only confirms hits with the automaton. That is the gap between a dependency-free OCaml automaton and a vectorised scanner, and it narrows as soon as the prefilter stops paying off: with seven names the default engine is at about 530 MB/s, and with 5 000 or 15 000 words under 100.

Dictionaries

With thousands of patterns the automaton is large and the prefilter is gone, so every engine is bounded by how fast it walks the trie. This library reaches 46 MB/s on 15 000 words and 82 to 86 MB/s on the 2 663 long words of dictionary-15: level with or ahead of the Rust NFA, and between half and nine tenths of the Rust default. The first 4096 nodes in breadth-first order have dense rows; beyond them a sorted-children lookup and failure links take over, which is where the remaining gap sits. Construction is where the library is clearly slower: about 100 ms for 15 000 words against the crate's 19, spent filling the dense rows and building the trie through a hash table. It happens once.

Match-dense inputs

When almost every byte ends a match, reporting dominates scanning. find_all returns a list of records, so on dense/abc-1m, with three matches per byte, it keeps three million records live and the garbage collector's work shows: 2.5 MB/s, against 27 MB/s for find_iter, whose records die young, and 43 MB/s for the Rust crate, which allocates nothing. The API page's advice stands: consume dense matches lazily. The leftmost-longest selection no longer pays that cost at all; at 16 MB/s on the same input it is ahead of the Rust NFA's 10, and its streamed form reaches 37 MB/s, a mode the Rust crate does not offer on streams. The pathological row, twenty nested patterns over a run of the same byte, is the same story at twenty matches per byte.

Streams

Feeding the input in 4 KiB chunks costs this library nothing: Stream.feed_nonoverlapping runs at 190 to 200 MB/s on the name workloads, the same as the whole-input search, and faster on dense inputs, where each chunk's result list is short-lived. The Rust crate's stream_find_iter reads through a buffer and runs at 250 to 290 MB/s however fast its whole-input search is, so on streams the two are within a factor of two everywhere and level on the dictionary rows.

Linear time

The scaling rows run the same 39 patterns over 64 KiB to 4 MiB of the same random text. find_iter holds at 26 to 27 MB/s across the four sizes: the automaton's cost per byte is constant, as the amortised argument says it must be. The list-returning modes slow down as the input grows — find_all from 304 to 679 nanoseconds per byte — because their result grows with it and a larger live heap makes each collection dearer. That is the price of the result, not of the scan.

Before and after

The first run of this suite was against the version of the library that stored transitions in a hash table and selected leftmost-longest matches by materialising every overlapping match and sorting. Those numbers are the reason the transition table and the selection were rewritten (the cost section of the API page describes what the library does now); the semantics did not change, which the differential test confirmed byte for byte before and after.

What is not measured

Memory

Automaton size and peak allocation during a scan are not recorded. The dense transition rows cost 2 KiB per node for up to 4096 nodes; a 15 000-word automaton is a few megabytes.

Latency

Streamed modes are timed for throughput over 4 KiB chunks, not for the delay between a byte arriving and a match being reported, which the semantics page bounds rather than measures.

Small inputs

Every haystack is at least 200 KB, so per-call overhead — the cost of find_all on a 40-byte log line — does not show.

Other implementations

Hyperscan, daachorse and the Go and Java libraries are not in the table. The drivers speak the format described in bench/README.md; adding one is a matter of writing a driver.

./bench/run.sh reproduces everything on this page, and bench/README.md documents the workloads and the method. Back to correctness, or on to compatibility.