Technology beats algorithms (in exact string matching)

Jorma Tarhio, Jan Holub*, Emanuele Giaquinta

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
155 Downloads (Pure)

Abstract

More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the naïve algorithm exploiting SIMD instructions of modern CPUs (with symbols compared in a special order) is the fastest one for patterns of length up to about 50 symbols and extremely good for longer patterns and small alphabets. The algorithm compares 16 or 32 characters in parallel by applying SSE2 or AVX2 instructions, respectively. Moreover, it uses loop peeling to further speed up the searching phase. We tried several orders for comparisons of pattern symbols, and the increasing order of their probabilities in the text was the best.

Original languageEnglish
Pages (from-to)1877–1885
JournalSOFTWARE-PRACTICE AND EXPERIENCE
Volume47
Issue number12
Early online date2017
DOIs
Publication statusPublished - 2017
MoE publication typeA1 Journal article-refereed

Keywords

  • AVX2
  • Exact string matching
  • SIMD instructions
  • SSE2

Fingerprint Dive into the research topics of 'Technology beats algorithms (in exact string matching)'. Together they form a unique fingerprint.

Cite this