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

    89 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 Dive into the research topics of 'On compile time Knuth-Morris-Pratt precomputation'. Together they form a unique fingerprint.

    Cite this