Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912279829676032 |
|---|---|
| author | Nicaud, Cyril Pivoteau, Carine Vialette, Stéphane |
| author_facet | Nicaud, Cyril Pivoteau, Carine Vialette, Stéphane |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_13694 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms Nicaud, Cyril Pivoteau, Carine Vialette, Stéphane Data Structures and Algorithms 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. |
| title | Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.13694 |