Technology beats algorithms (in exact string matching)
Loading...
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Date
2017
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
SOFTWARE-PRACTICE AND EXPERIENCE
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.Description
Keywords
AVX2, Exact string matching, SIMD instructions, SSE2
Other note
Citation
Tarhio , J , Holub , J & Giaquinta , E 2017 , ' Technology beats algorithms (in exact string matching) ' , SOFTWARE-PRACTICE AND EXPERIENCE , vol. 47 , no. 12 , pp. 1877–1885 . https://doi.org/10.1002/spe.2511
