On compile time Knuth-Morris-Pratt precomputation

J. Kourie, L.G.W.A. Cleophas, B.W. Watson

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

77 Downloads (Pure)

Abstract

Many keyword pattern matching algorithms use precomputation subroutines to produce lookup tables, which in turn are used to improve performance during the search phase. If the keywords to be matched are known at compile time, the precomputation subroutines can be implemented to be evaluated at compile time versus at run time. This will provide a performance boost to run time operations. We have started an investigation into the use of metaprogramming techniques to implement such compile time evaluation, initially for the Knuth-Morris-Pratt (KMP) algorithm. We present an initial experimental comparison of the performance of the traditional KMP algorithm to that of an optimised version that uses compile time precomputation. During implementation and benchmarking, it was discovered that C++ is not well suited to metaprogramming when dealing with strings, while the related D language is. We therefore ported our implementation to the latter and performed the benchmarking with that version. We discuss the design of the benchmarks, the experience in implementing the benchmarks in C++ and D, and the results of the D benchmarks. The results show that under certain circumstances, the use of compile time precomputation may significantly improve performance of the KMP algorithm.
Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2011 (PSC'11, Prague, Czech Republic, August 29-31, 2011)
EditorsJ. Holub, J. Zdanek
Place of PublicationPrague
PublisherCzech Technical University in Prague
Pages15-29
ISBN (Print)978-80-01-04870-2
Publication statusPublished - 2011

    Fingerprint

Cite this

Kourie, J., Cleophas, L. G. W. A., & Watson, B. W. (2011). On compile time Knuth-Morris-Pratt precomputation. In J. Holub, & J. Zdanek (Eds.), Proceedings of the Prague Stringology Conference 2011 (PSC'11, Prague, Czech Republic, August 29-31, 2011) (pp. 15-29). Prague: Czech Technical University in Prague.