Technology beats algorithms (in exact string matching)
| Autor: | Jorma Tarhio, Emanuele Giaquinta, Jan Holub |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Loop (graph theory)
Speedup Computer science Phase (waves) Commentz-Walter algorithm 020207 software engineering 0102 computer and information sciences 02 engineering and technology String searching algorithm 01 natural sciences 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Order (group theory) SIMD Algorithm Software |
| Zdroj: | Software: Practice and Experience. 47:1877-1885 |
| ISSN: | 0038-0644 |
| DOI: | 10.1002/spe.2511 |
| Popis: | Summary More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the naive 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text