Tune-up for the Dead-Zone algorithm

Jorma Tarhio, Bruce Watson

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


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 in Prague
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


ConferencePrague Stringology Conference
Abbreviated titlePSC
Country/TerritoryCzech Republic


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

Cite this