Technology beats algorithms (in exact string matching). (1st August 2017)
- Record Type:
- Journal Article
- Title:
- Technology beats algorithms (in exact string matching). (1st August 2017)
- Main Title:
- Technology beats algorithms (in exact string matching)
- Authors:
- Tarhio, Jorma
Holub, Jan
Giaquinta, Emanuele - Abstract:
- Summary: 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.
- Is Part Of:
- Software, practice & experience. Volume 47:Number 12(2017)
- Journal:
- Software, practice & experience
- Issue:
- Volume 47:Number 12(2017)
- Issue Display:
- Volume 47, Issue 12 (2017)
- Year:
- 2017
- Volume:
- 47
- Issue:
- 12
- Issue Sort Value:
- 2017-0047-0012-0000
- Page Start:
- 1877
- Page End:
- 1885
- Publication Date:
- 2017-08-01
- Subjects:
- AVX2 -- exact string matching -- SIMD instructions -- SSE2
Computer software -- Periodicals
Computer programming -- Periodicals
Computer programs -- Periodicals
005.3 - Journal URLs:
- http://onlinelibrary.wiley.com/ ↗
- DOI:
- 10.1002/spe.2511 ↗
- Languages:
- English
- ISSNs:
- 0038-0644
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 8321.453000
British Library DSC - BLDSS-3PM
British Library STI - ELD Digital store - Ingest File:
- 5314.xml