Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.13694 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |