Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms
Cyril Nicaud, Carine Pivoteau, Stéphane Vialette · 2025
Read Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms by Cyril Nicaud, Carine Pivoteau, Stéphane Vialette (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-13694.txt.
Introduction
Cyril Nicaud, Carine Pivoteau, and Stéphane Vialette analyze, in 2025, two classic pattern-matching algorithms through the eyes of the processor. The Morris-Pratt and Knuth-Morris-Pratt methods scan text for a fixed pattern quickly, but modern chips guess which way branches will go, and wrong guesses cost time. Nobody had counted those costs for these algorithms.
Assuming a random text, the authors derive precise estimates of how many mispredictions each algorithm causes under simple local predictors. Their tools come from automata theory and Markov chains. Beyond the two algorithms, the work lays groundwork for studying other text algorithms under realistic processor models.
Catalog record
| CREATOR | Cyril Nicaud, Carine Pivoteau, Stéphane Vialette |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-13694
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms Cyril Nicaud, Carine Pivoteau, Stéphane Vialette Abstract We analyze the classical Morris-Pratt and Knuth-Morris-Pratt pattern matching algorithms through the lens of computer architecture, investigating the impact of incorporating a simple branch prediction mechanism into the model of computation. Assuming a fixed pattern and a random text, we derive precise estimates of the number of mispredictions these algorithms produce using local predictors. Our approach is based on automata theory and Markov chains, providing a foundation for the theoretical analysis of other text algorithms and more advanced branch prediction strategies. Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, [email protected] Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, [email protected] Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, [email protected] ccs Theory of computation Design and analysis of algorithms keywords Pattern matching, branch prediction, transducers, average case complexity, Markov chains † † runningtitle: Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms † † runningauthor: C. Nicaud, C. Pivoteau and S. Vialette † † copyright: Cyril Nicaud, Carine Pivoteau and Stéphane Vialette † † event-title: submitted † † event-shorttitle: submitted † † event-acronym: submitted 1 Introduction Pipelining is a fundamental technique employed in modern processors to improve performance by executing multiple instructions in parallel, rather than sequentially. Instructions execution is divided into distinct stages, enabling the simultaneous processing of multiple instructions, much like an assembly line in a factory. Today, pipelining is ubiquitous, even in low-cost processors priced under a dollar. We refer the reader to the textbook reference [ 6 ] for more details on this important architectural feature. The sequential execution model assumes that each instruction completes before the next one begins; however, this assumption does not hold in a pipelined processor. Specific conditions, known as hazards, may prevent the next instruction in the pipeline from executing during its designated clock cycle. Hazards introduce delays that undermine the performance benefits of pipelining and may stall the pipeline, thus reducing the theoretical speedup: • Structural hazards occur when resource conflicts arise, preventing the hardware from supporting all possible combinations of instructions during simultaneous executions. • Control hazards arise from the pipelining of jumps and other instructions that modify the order in which instructions are processed, by updating the Program Counter (PC). • Data hazards occur when an instruction depends on the result of a previous instruction, and this dependency is exposed by the overlap of instructions in the pipeline. To minimize stalls due to control hazards and improve execution efficiency, modern computer architectures incorporate branch predictors . A branch predictor is a digital circuit that anticipates the outcome of a branch (e.g., an if–then–else structure) before it is determined. Two-way branching is typically implemented using a conditional jump instruction, which can either be taken , updating the Program Counter to the target address specified by the jump instruction and redirecting the execution path to a different location in memory, or not taken , allowing execution to continue sequentially. The outcome of a conditional jump remains unknown until the condition is evaluated and the instruction reaches the actual execution stage in the pipeline. Without branch prediction, the processor would be forced to wait until the conditional jump instruction reaches this stage before the next instruction can enter the first stage in the pipeline. The branch predictor aims to reduce this delay by predicting whether the conditional jump is likely to be taken or not. The instruction corresponding to the predicted branch is then fetched and speculatively executed. If the prediction is later found to be incorrect (i.e., a misprediction occurs), the speculatively executed or partially executed instructions are discarded, and the pipeline is flushed and restarted with the correct branch, incurring a small delay. The effectiveness of a branch prediction scheme depends on both its accuracy and the frequency of conditional branches. Static branch prediction is the simplest technique, as it does not depend on the code execution history and, therefore, cannot adapt to program behavior. In contrast, dynamic branch prediction takes advantage of runtime information (specifically, branch execution history) to determine whether branches were taken or not, allowing it to make more informed predictions about future branches. A vast body of research is dedicated to dynamic branch prediction schemes. At the highest level, branch predictors are classified into two categories: global and local. A global branch predictor does not maintain separate history records for individual conditional jumps. Instead, it relies on a shared history of all jumps, allowing it to capture their correlations and improve prediction accuracy. In contrast, a local branch predictor maintains an independent history buffer for each conditional jump, enabling predictions based solely on the behavior of that specific branch. Since the 2000s, modern processors typically employ a combination of local and global branch prediction techniques, often incorporating even more sophisticated designs. For a deeper exploration of this topic, see [ 10 ] , and for a comprehensive discussion of modern computer architecture, refer to [ 6 ] . In this study, we focus on local branch predictors implemented with saturated counters . A 1-bit saturating counter (essentially a flip-flop) records the most recent branch outcome. Although this is the simplest form of dynamic branch prediction, it offers limited accuracy. A 2-bit saturating counter (see \cref fig:predictor), by contrast, operates as a state machine with four possible states: Strongly not taken ( \underline{\nu} ), Weakly not taken ( \nu ), Weakly taken ( \tau ), and Strongly taken ( \underline{\tau} ). When the 2-bit saturated branch predictor is in the Strongly not taken or Weakly not taken state, it predicts that the branch will not be taken and execution will proceed sequentially. Conversely, when the predictor is in the Strongly taken or Weakly taken state, it predicts that the branch will be taken, meaning execution will jump to the target address. Each time a branch is evaluated, the corresponding state machine updates its state. If the branch is not taken, the state shifts toward Strongly not taken ; if taken, it moves toward Strongly taken . A misprediction (corresponding to a bold edge in \cref fig:predictor) occurs when: • a branch is not taken, while the predictor is in either of the Taken states ( \tau or \underline{\tau} ); • a branch is taken, while the predictor is in either of the Not Taken states ( \nu or \underline{\nu} ). This mechanism gives the 2-bit saturating counter an advantage over the simpler 1-bit scheme: a branch must deviate twice from its usual behavior (i.e. a Strongly state) before the prediction changes, reducing the likelihood of mispredictions. \underline{\nu} \nu \tau \underline{\tau} N N N N T T T T Figure 1: The 2-bit saturated predictor consists of four states: \underline{\nu} and \nu predict that the branch will not be taken, while \tau and \underline{\tau} predict that it will. The predictor updates at each condition evaluation, transitioning via T when the branch is taken (i.e., the condition is true) and via N when it is not. Bold edges indicate mispredictions. This paper provides an initial theoretical exploration of the techniques and results involved in analyzing pattern matching algorithms within computational models enhanced by branch prediction mechanisms. Specifically, we examine the classical Morris-Pratt (MP) and Knuth-Morris-Pratt (KMP) algorithms [ 11