Tune-up for the Dead-Zone algorithm

Jorma Tarhio, Bruce Watson

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

We present a number of performance tuning techniques as applied to the Dead-Zone algorithm for exact single (keyword) pattern matching in strings in sequential processing. The tuning techniques presented here are focused on the algorithm skeleton as well as how the shifters are used, and include: removal of some redundant computation, and shifting using 2-grams, among others. Benchmarking results are given for the C implementation in a modern processor without penalties for misaligned memory access.
Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2020
EditorsJan Holub, Jan Zdarek
Place of PublicationPrague
PublisherCzech Technical University
Pages160-167
Number of pages8
ISBN (Print)978-80-01-06749-9
Publication statusPublished - 2020
MoE publication typeA4 Article in a conference publication
EventPrague Stringology Conference - Prague, Czech Republic
Duration: 31 Aug 20202 Sep 2020

Conference

ConferencePrague Stringology Conference
Abbreviated titlePSC
CountryCzech Republic
CityPrague
Period31/08/202002/09/2020

Fingerprint Dive into the research topics of 'Tune-up for the Dead-Zone algorithm'. Together they form a unique fingerprint.

Cite this