Performance Comparison - daac-tools/daachorse GitHub Wiki

This wiki shows the experimental results of time and memory for daachorse and other pattern-matching libraries.

Experimental Setup

Datasets

We used the following two types of datasets for our experiments:

Implementations

We compared the following Aho-Corasick implementations:

  • aho-corasick (v1.1.4)
    • NFA (.kind(None))
    • DFA (.kind(Some(AhoCorasickKind::DFA)))
  • daachorse (v5.0.0, this library)
    • bytewise
    • charwise

In addition, we compared the following pattern matching implementations:

Machine

The following is the specification of the used machine:

  • CPU: 12th Gen Intel® Core™ i7-1270P × 16
  • Memory: 32GiB
  • OS: Ubuntu 26.04

To avoid CPU frequency fluctuations caused by heat and to ensure stable evaluation, we conducted the experiments in power-saving mode.

Experimental Result

The benchmark code can be found here.

Overlapping Match

We measured the execution time [ms] of the find_overlapping() function provided by each Aho-Corasick implementation. For fst and yada, we performed common prefix searches from all positions in the target text.

Library Word100 Word5K Word15K Word100K cl100k_base o200k_base UniDic
daachorse/bytewise 1.12 2.08 2.08 8.00 11.63 12.46 22.49
daachorse/charwise 1.25 2.01 1.83 5.28 N/A N/A 12.44
aho_corasick/nfa 2.01 9.34 9.74 12.04 29.86 33.72 40.72
aho_corasick/dfa 2.01 4.16 5.21 9.05 20.26 23.13 43.85
yada 6.97 9.81 10.20 11.08 N/A N/A 22.53
crawdad/trie 8.10 10.10 10.20 10.35 N/A N/A 12.22
fst/map 42.71 57.32 63.54 82.09 113.31 132.90 138.63
  • Since cl100k_base and o200k_base contain non-Unicode, some libraries do not support them.

Non-Overlapping Shortest Match

We measured the execution time [ms] of the find_iter() function provided by each Aho-Corasick implementation.

Library Word100 Word5K Word15K Word100K cl100k_base o200k_base UniDic
daachorse/bytewise 1.07 2.04 2.00 6.92 2.06 2.07 2.39
daachorse/charwise 1.36 2.08 1.96 5.08 N/A N/A 2.00
aho_corasick/nfa 1.50 8.64 9.20 10.91 33.05 33.27 18.06
aho_corasick/dfa 1.50 3.15 4.12 7.17 37.11 37.11 20.23

Non-Overlapping Leftmost-Longest Match

We measured the execution time [ms] of the leftmost_find_iter() function (resp. find_iter()) with the MatchKind::LeftmostLongest specification provided by daachorse (resp. aho-corasick).

Library Word100 Word5K Word15K Word100K cl100k_base o200k_base UniDic
daachorse/bytewise 0.72 1.44 1.42 8.40 9.36 9.72 16.04
daachorse/charwise 0.79 1.52 1.46 5.73 N/A N/A 10.67
aho_corasick/nfa 1.53 8.61 9.25 12.37 22.09 22.58 34.06
aho_corasick/dfa 1.53 3.23 4.24 8.88 20.71 21.57 40.58

Non-Overlapping Leftmost-First Match

We measured the execution time [ms] of the leftmost_find_iter() function (resp. find_iter()) with the MatchKind::LeftmostFirst specification provided by daachorse (resp. aho-corasick).

Library Word100 Word5K Word15K Word100K cl100k_base o200k_base UniDic
daachorse/bytewise 0.69 1.41 1.37 7.44 8.02 8.03 5.31
daachorse/charwise 0.81 1.56 1.48 5.66 N/A N/A 4.17
aho_corasick/nfa 1.54 8.65 9.28 11.61 35.00 34.80 17.11
aho_corasick/dfa 1.53 3.24 4.22 8.11 37.23 37.26 18.51

Memory usage

We measured the memory usage [MiB] reported by heap_bytes() provided by the Aho-Corasick implementations. For fst and yada, we measured the data buffer size obtained by their constructors.

Library Word100 Word5K Word15K Word100K cl100k_base o200k_base UniDic
aho-corasick (NFA) 0.228 0.507 1.1 9.7 11.7 18.9 38.5
aho-corasick (DFA) 0.228 15.871 37.3 637.5 220.2 427.7 1775.3
daachorse (bytewise) 0.077 0.509 1.2 8.7 4.0 7.9 30.7
daachorse (charwise) 0.078 0.612 1.4 11.2 N/A N/A 24.0
fst 0.001 0.109 0.1 1.0 0.5 1.1 2.8
yada 0.005 0.346 0.3 2.9 N/A N/A 9.4

Summary

These experimental results show that daachorse operates more efficiently than other libraries. Although experimental results may vary depending on the execution environment, this characteristic is supported by verification from multiple users.