# Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm

Cyril Nicaud, Carine Pivoteau, Stéphane Vialette

► To cite this version:

Cyril Nicaud, Carine Pivoteau, Stéphane Vialette. Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm. 2024. hal-05170281

HAL Id: hal-05170281

https://hal.science/hal-05170281v1

Preprint submitted on 18 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm

Cyril Nicaud ☐

Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France

Carine Pivoteau ☐

Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France

Stéphane Vialette ☐

Univ Gustave Eiffel, CNRS, LIGM, F-77454 Marne-la-Vallée, France

## Abstract

We revisit the classical sliding window pattern matching algorithm from a computer architecture point of view and conduct a theoretical study to answer the question: what is the impact of adding a simple branch prediction mechanism to the model of computation? Assuming that the pattern is fixed and the text is random, we give precise estimations of the number of mispredictions produced by two variants of this algorithm using local predictors. This case study introduces key tools based on automata and Markov chain theories, which are promising for the analysis of more efficient algorithms and more advanced branch prediction schemes.

**2012 ACM Subject Classification** Theory of computation → Design and analysis of algorithms

**Keywords and phrases** Pattern matching, branch prediction, transducers, average case complexity, Markov chains

**Digital Object Identifier** 10.4230/LIPIcs...

<figure><img src="image_2.png" /></figure>
XX:2 Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm

1 Introduction

Since the early ages of computers, parallelism has been used to design faster processors. We focus here on instruction level parallelism, that is, the ability to have more than one instruction executed at a time, and in particular, the use of an instruction pipeline that has been generalized in the 80s. Let us consider, for example, the classical RISC pipeline [7]: each instruction can be split into five stages that occur one after the other but are executed by different parts of the processor. For example, the instruction<fnref n="1" /> i = i + 1 will have to be fetched, then decoded, and then executed. The last two stages are memory accesses and writes into the registers. If instructions were to be executed sequentially, the part of the processor that fetches the next instruction will be idle during the last four stages of this instruction. The idea of the pipeline is that another instruction can be fetched as soon as the previous one enters the second stage, and so on for every stage, making it possible, in theory, to have five instructions being executed in parallel, for each clock cycle.

To use the pipeline at its full potential, this rate (Instructions Per Clock) has to be
maintained. Unfortunately, there are circumstances (called *hazards*) where a stage of an
instruction may depend on a stage of a previous one that has not finished yet. For example,
if the next instruction after i = i + 1 is if (i > 42), this second instruction has to wait
for the result of i = i + 1 to be written in order to execute (*data hazard*), which creates a
stall in the pipeline. The second instruction, if (i > 42), creates another kind of problem:
a *structural hazard*. Indeed, most of the time, the if instruction will be translated into a
conditional jump for the processor. It means that the result of the test is used to decide which
instruction to do next, that is whether to branch from the sequential path of instructions or
not. In other words, the first stage of the next instruction (the fetch one) needs to wait for
the result of the test to be executed. This can cause even longer stalls than a data hazard.
In order to maintain a good IPC, a technique called *branched prediction* emerged with the
first pipelines. The idea is simple: whenever a conditional jump occurs, try to predict if the
branch will be taken (when the test value is true) or not. Instead of waiting for the test
result, fetch the instruction indicated by the prediction into the pipeline. If the prediction
was correct, everything is for the better, otherwise, it is a *misprediction* and the instructions
after the jump are discarded and the other path is taken. A misprediction does not cost much
more than the stall that would have occurred without branch prediction, while a correct
prediction prevents any stall at all, which is where the bonus is. Obviously, this is even more
effective if the predictions are accurate. The first attempts were simple *static* predictors for
loops: if a branch goes back into a loop, the prediction is that it will be taken, which is
always true except the one time the program leaves the loop. For if instructions, a simple
improvement is to take past outcomes of the test into account. This is called *dynamic* branch
prediction. There are different ways to achieve this, a common one being the use of a state
automaton as the one given by Fig. 1 as a predictor. The state indicates the prediction and
the outcome of the test which edge to follow. For example, if the predictor is in the state *ν*
before the instruction if (i > 42), it predicts that the test will be false and if i is indeed
less or equal than 42, the next state will be $\bar{\nu}$ and otherwise it will be $\tau$.

If the predictor uses and predicts only the outcomes of this instruction, it's a *local* predictor associated with this instruction. This works quite well with tests that are independent from one another, but for nested instructions, such as the ones we can see in the algorithms of Fig. 2, it lacks the ability to take their correlation into account. This can be done by

<footnote n="1">¹ This may not exist as a single instruction, we use high level instruction here for the sake of simplicity.</footnote>
<figure><img src="image_3.png" /><figcaption>■ **Figure 1** The two-bit saturated predictor. The states $\bar{\nu}$ and $\nu$ predict that the branch is not taken, and the states $\tau$ and $\bar{\tau}$ predict it is taken. It is updated at each condition evaluation, using the transition labeled 0 (resp. 1) when false (resp. true). The bold edges correspond to mispredictions.</figcaption></figure>

using *global* predictors that take all the conditional jump into account for their predictions. The same kind of automaton can be used, but more often, this type of predictor is based on an *k*-history table, indexed by a sequence of the last *k* outcomes of conditional jumps, keeping a two-bits saturated counter for each of them, for example. For more than 20 years, actual processors have usually been implementing a combination of both local and global prediction, with even more intricate design (see [6] for more on the subject and [?](https://en.wikipedia.org/wiki/History_table) for a complete presentation on modern computer architecture).

In this article we initiate the theoretical analysis of pattern matching algorithms in models of computation enriched with branch prediction. We estimate the number of mispredictions arising during an execution of an algorithm in addition to the classical estimation of the time and space required. This line of research was followed in the last two decades, from experimental studies on sorting algorithms and basic data structures [2], to theoretical analysis as the number of misprediction in JAVA's double-pivot quicksort [5] or the study of skewed versions of classical algorithm (binary search, exponentiation by squaring, ...) to help the predictions [1]. All these articles focused on local predictors, mostly 2-bit saturated ones as depicted in Fig. 1, which also constitutes the framework of this article.

We present results for the most elementary pattern matching algorithm: the sliding window algorithm. It will appear in the sequel that analyzing the simplest algorithm, in a model with local predictors only, already yields non-elementary statements. There are two main reasons for this. First, the worst case analysis is not relevant and we have to conduct an estimation of the number of mispredictions for random input: in our setting the pattern is fixed and the text is randomly generated. Second, the different instructions in text algorithms do have inherent correlations, depending on auto-correlations of the pattern or of its prefixes, which makes the work of predictors more complex.

This article can therefore be seen as a case study, which gives a first insight on the techniques at play and the kind of results obtained when analyzing pattern matching algorithms in enhanced models of computation that incorporate branch prediction mechanisms. This hopefully paves the way for the analysis of more relevant algorithms<fnref n="2" /> and more advanced prediction schemes in future works.

## 2 Sliding window algorithm

We study the classical sliding window algorithm that counts and outputs the number of occurrences of a pattern *X* of size *m* in a text *T* of size *n*. It is given by Fig. 2 below, along with an implementation variation. BASICWINDOW is the plain algorithm, where the pattern is checked letter by letter against the window at position *i* in the text, for each eligible position. The window loop condition is a double check on the length of the pattern

<footnote n="2">² On a side note, JAVA's `String.indexof()` does use a variation of the sliding window algorithm.</footnote>
## XX:4 Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm

and a matching of letters. Usually, this pseudo-code is sufficient to conduct an analysis. However, for the purpose of our study, we are interested in the exact branching structure of the compiled code. In particular, the condition $j < m$ and $X[j] = T[i+j]$ can be evaluated as a whole (corresponding to BASICWINDOW) or separated into two consecutive tests by splitting the test of the inner while (by testing $X[j] != T[i+j]$ inside the loop). It is easy to see that, after that change, the while condition becomes redundant with the one at Line 7, leading to the reorganization of UNRAVELEDWINDOW having one less conditional instruction. This matters here, as in our prediction model, there will be one predictor for $j < m$ and $X[j] = T[i+j]$ in BASICWINDOW and two distinct predictors for $j < m$ and $X[j] = T[i+j]$ in UNRAVELEDWINDOW.

<caption>Algorithm 1 BASICWINDOW($X, T$)</caption>

1 $m, n \leftarrow |X|, |T|$
2 $i, nb \leftarrow 0, 0$
3 **while** $i \le n - m$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;$j \leftarrow 0$
5 &nbsp;&nbsp;&nbsp;&nbsp;**while** $j < m$ and $X[j] = T[i+j]$ **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$j \leftarrow j + 1$
7 &nbsp;&nbsp;&nbsp;&nbsp;**if** $j = m$ **then** $nb \leftarrow nb + 1$
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow i + 1$
9 **return** $nb$

Figure 2 Two versions of the sliding window algorithm. BASICWINDOW is a natural way to write it and UNRAVELEDDWINDOW is a variation that splits the condition of the window loop.

<caption>Algorithm 2 UNRAVELEDWINDOW($X, T$)</caption>

1 $m, n \leftarrow |X|, |T|$
2 $i, nb \leftarrow 0, 0$
3 **while** $i \le n - m$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;$j \leftarrow 0$
5 &nbsp;&nbsp;&nbsp;&nbsp;**while** True **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\left\lfloor \text{if } j = m \text{ then } nb \leftarrow nb + 1 \text{ break } \right\rfloor$
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\left\lfloor \text{if } X[j] \neq T[i+j] \text{ then } \text{break} \text{ else } j \leftarrow j + 1 \text{ } \right\rfloor$
9 &nbsp;&nbsp;&nbsp;&nbsp;$\left\lfloor \text{i} \leftarrow \text{i} + 1 \text{ } \right\rfloor$
11 &nbsp;&nbsp;&nbsp;&nbsp;$\left\lfloor \text{return } nb \text{ } \right\rfloor$

Observe that using a language like C, the compiler will probably translate **and** conditions into two jumps since the second part should not be evaluated if the first part is false. This lazy behavior can be achieved with only one jump, using a cmov instruction, but unless forcing it to get the branch structure of BASICWINDOW, the (slightly optimized) compiled version will more likely resemble UNRAVELEDWINDOW.

## 3 Probability analysis: the average number of comparisons

In this section, we conduct a probabilistic analysis of the average number of letter comparisons performed by the two algorithms, which are exactly the same. All the results presented here are more or less folklore, we detailed them to discuss different models of random input and to introduce the key notions of probability theory that will be used in the sequel.

First, we assume that the text is made of letters chosen uniformly at random from an alphabet A. The sliding window algorithm runs in expected linear time, as stated in the following proposition which is proved by linearity of the expectation.

**Lemma 1** ([3] p.29). For any X, if the text T is taken uniformly at random, then the average number of letter comparisons performed by the two algorithms is less than $\frac{|A|}{|A|-1} |T|$.

The upper bound given by Lemma 1 is obtained by considering that the nested while, Line 5, halts only when two letters differ, i.e. by considering an infinite pattern X. We can refine the statement by adding the halting condition $j < m$ in the analysis, yielding that the expected number of letter comparisons is $\frac{|A|}{|A|-1} (n - m + 1) (1 - |A|^{-m})$. The upper bound given by Lemma 1 is sufficiently tight, except for small alphabets and very small patterns.
The next step is to allow different probabilities for the different letters: the text is generated by a so-called *memoryless source*, where each letter is taken independently from the others according to some fixed non-degenerated probability distribution $\pi: A \to (0, 1)$. It is the classical generalization of the uniform distribution where $\pi(\alpha) = \frac{1}{|A|}$ for every $\alpha \in A$.

The expected number of comparisons performed by the algorithms is still linear for a text generated by a memoryless source, but it now directly depends on the pattern: a pattern with a lot of probable letters induces more comparisons in expectation than a pattern with rare letters only. Let $\text{Pref}(X, j)$ denote the prefix of length $j$ of $X$ and consider the extension of $\pi$ to words $u = u_0 \cdots u_{\ell-1}$ defined by $\pi(u) = \pi(u_0) \cdots \pi(u_{\ell-1})$ and $\pi(\varepsilon) = 1$, we have:

**Lemma 2.** For any pattern $X$, if the text $T$ is generated by a memoryless source of probability distribution $\pi$, then the average number of letter comparisons performed by the two algorithms is $\gamma(\pi, X) (n-m+1)$, with $\gamma(\pi, X) = \sum_{j=0}^{|X|-1} \pi(\text{Pref}(X, j))$.

The next step in the analysis would be to compute the standard deviation, to study the concentration around the expected value. This computation is more involved, as there are local correlations, which depend on the pattern $X$, or more precisely of its auto-correlations. In this paper we limit ourselves to the computation of expectations.

A possible way to handle the pattern-dependent results is to also choose the pattern randomly. It is standard when analyzing text algorithms (see the analysis of KMP [8] for instance), but this is not the direction we explore in this article, where we aim at studying how the pattern influences the result. We just state the result for memoryless sources:

**Lemma 3.** If $X$ and $T$ are two random words generated by a memoryless source of probability distribution $\pi$, the average number of letter comparisons performed by the two algorithms is $\frac{1-c_2(\pi)^m}{1-c_2(\pi)} (n-m+1)$, where $c_2(\pi) = \sum_{\alpha \in A} \pi(\alpha)^2$.

To further enhance the probabilistic model, the classical next step is to introduce some dependencies. A simple way to do so is to use *Markov chains*, which, for us, are defined by a non-empty finite set $S$ of states, and a *transition matrix* $\Pi$, where, for every $x, y \in S$, $\Pi(x, y)$ is the probability to go to from state $x$ to state $y$. In particular, it requires that for all $x \in S$, $\sum_{y \in S} \Pi(x, y) = 1$. Usually, the definition is supplemented with an initial probability vector $\pi_0$ of dimension $|S|$, with non-negative coefficients that sum to 1. One can follow a (random) *trajectory* $(x_t)_{t \ge 0}$ in the Markov chain by starting at a random position following the probability $\pi_0$ for $x_0$, at time $t=0$, and then at each discrete step from time $t$ to $t+1$, go from the current state $x_t$ to $x_{t+1}$ with probability $\Pi(x_t, x_{t+1})$.

Markov chains can be used as a random source of words in several ways. For instance, fix some positive integer $k$ and use the length-$k$ words for $S = A^k$. Then for every $u = u_0 \cdots u_{k-1} \in S$ and every $\alpha \in A$, $\Pi(u, u_1 \cdots u_{k-1}\alpha)$ is the probability to generate $\alpha$ when the last $k$ generated letters are $u_0, u_1, \dots, u_{k-1}$. An example is depicted in Fig. 3.

<figure><img src="image_4.png" /><figcaption>■ **Figure 3** A Markovian source for random text, with a memory of 2 letters. If the last two generated letters are *ba*, the next letter is an *a* or a *b* with respective probabilities 1/5 and 4/5. The chain is irreducible and aperiodic. Its stationary vector is:</figcaption></figure>

$$ \hat{\pi}(aa) = \frac{3}{43} \quad \hat{\pi}(ab) = \frac{10}{43} \quad \hat{\pi}(ba) = \frac{10}{43} \quad \hat{\pi}(bb) = \frac{20}{43}. $$

We shall rely on classical results on Markov chains in the sequel, which we now introduce. A Markov chain is *irreducible* when its underlying directed graph is strongly connected, and *aperiodic* when the gcd of its cycle lengths is 1. The statement is the following [4]:
XX:6 Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm

► **Theorem 4.** If $(\Pi, \pi_0)$ is a Markov chain on $S$ that is irreducible and aperiodic, then there exists a unique probability line vector $\hat{\pi}$ on $S$, called the stationary vector, such that $\hat{\pi} \cdot \Pi = \hat{\pi}$ and if $(x_t)_{t \ge 0}$ is a trajectory then $\lim_{t \to \infty} \mathbb{P}(x_t = s) = \hat{\pi}(s)$, for all $s \in S$.

Classically, if the chain is not irreducible and has only one terminal strongly connected component $C$ that is aperiodic, Theorem 4 still applies by considering the restriction to $C$, as a random trajectory quickly ends in $C$ with high probability.

If we have a Markovian source $(\Pi, \pi_0)$ for the text, one can estimate the expected number of letter comparisons in the following way:

1. For each $s \in S$, compute the expected number of comparisons $C_{\Pi}(s, X)$ when scanning the window at position $i$ if the source is in state $s$ at time $i$: in the chain of Fig. 3, if one starts at state *ba* and $X = *aba*$, we perform one comparison with probability 4/5, two with probability 1/15, and three with probability 2/15; hence $C_{\Pi}(ba, X) = 4/3$.

2. Compute the stationary vector $\hat{\pi}$, which consists in computing the (unique) normalized eigenvector associated to the eigenvalue 1 of the transpose matrix of $\Pi$.
This allows us to compute the asymptotic estimation of the expected number of comparisons:

► **Lemma 5.** For any pattern $X$, if the text $T$ is generated by an irreducible and aperiodic Markovian source $(\Pi, \pi_0)$, then the average number of letter comparisons of the two algorithms is asymptotically equivalent to $\eta(\Pi, X) |T|$, where $\eta(\Pi, X) = \sum_{s \in S} \hat{\pi}(s) C_{\Pi}(s, X)$.

As Lemma 5 is a consequence of Theorem 4, its result is asymptotic and does not depend on $\pi_0$, which is classical for Markov chains. This whole process essentially describes an algorithm to estimate the expected number of letter comparisons. In the sequel, we will not use Markovian sources as random models for texts, but we rely on the same kind of techniques, as Markov chains naturally emerge in our analysis.

4 Analysis of the counter update in BasicWindow

We consider the probabilistic model where the pattern $X$ is of length $m \ge 2$, and the text $T$ of length $n$ is generated using a memoryless source of non-degenerated probability distribution $\pi$ on $A$. In our setting, throughout the article, $X$ is fixed and $n$ tends to infinity. Recall that $\pi$ is extended to words by $\pi(\varepsilon) = 1$ and $\pi(u_0 \cdots u_{\ell-1}) = \pi(u_0) \cdots \pi(u_{\ell-1})$.

In this section we study the number of mispredictions during the update of the variable $nb$ that counts the number of occurrences of $X$ in $T$, that is, those made by a local predictor associated with the *if* instruction in BASICWINDOW at Line 7. We establish that for any given pattern $X$, there exists a constant $\kappa_X$ such that the expected number of mispredictions caused by the update of $nb$ is asymptotically equivalent to $\kappa_X n$. The value of $\kappa_X$ is given explicitly, and its formula depends on whether $X$ contains two different letters or not.

Non-repetitive pattern.

We first consider patterns $X$ having at least two different letters, i.e. $X \neq \alpha^m$ for some $\alpha \in A$. This is the simpler case to study, and the statement is the following.

► **Lemma 6.** If the pattern $X$ contains at least two different letters, then the expected number of mispredictions induced by the updates of the counter $nb$ is asymptotically equivalent to $\pi(X)n$, as $n$ tends to infinity: $\kappa_X = \pi(X)$ in this case.

**Proof sketch.** Such a pattern $X$ cannot match at two consecutive positions. Hence, if the *if* condition is true, then it is false immediately after. This can be used to prove that, with
high probability, the predictor hits the state $\bar{\nu}$ after $O(\log n)$ steps and then stays on states $\bar{\nu}$ and $\nu$, thereby producing exactly one misprediction for each occurrence of the pattern. ◀

### Single letter pattern $X = \alpha$

In the case of a pattern of length 1, that is $X = \alpha$, the test if $j = m$ is true if and only if the current letter of $T$ is $\alpha$, which happens with probability $\pi(\alpha)$. Hence, the current state of the predictor follows a trajectory in the Markov chain obtained from its graph by changing the labels 0 and 1 into the probabilities $\bar{\pi}(\alpha) := 1 - \pi(\alpha)$ and $\pi(\alpha)$, respectively, as depicted in Fig. 4 below. Mispredictions can be read on the graph, since they happen exactly when using a transition to the right from $\bar{\nu}$ or $\nu$, or to the left from $\tau$ or $\bar{\tau}$.

<figure><img src="image_5.png" /><figcaption>**Figure 4** The Markov chain associated to $X = \alpha$. Mispredictions are indicated in bold.</figcaption></figure>

The stationary distribution of such a Markov chain was studied in a previous work on branch prediction [1], yielding the following statement.

**Lemma 7.** If the pattern $X = \alpha$ has length one, the expected number of mispredictions induced by the updates of the counter nb is asymptotically equivalent to $\kappa_{\alpha} n$, as $n$ tends to infinity, where $\kappa_{\alpha} = \mu_2(\pi(\alpha))$ and $\mu_2(p) = \frac{p(1-p)}{1-2p(1-p)}$.

### Pattern $X = \alpha\alpha$

Let $\bar{\alpha} = A \setminus \{\alpha\}$. To perform the analysis for $X = \alpha\alpha$, we see $T$ as a sequence of words of the form $\alpha^*\bar{\alpha}$ by splitting it after each letter of $\bar{\alpha}$. If the window is at position $i$ and $T[i] = \bar{\alpha}$, then the pattern is not found. Then, the window is moved one step to its right. More generally, if the suffix of $T$ starting at position $i$ starts with $\alpha^k\bar{\alpha}$, it induces a sequence of if $j = m$ instructions and one or several moves in the predictor: if $k = 0$ then we have one pattern mismatch; if $k = 1$, then we have two consecutive pattern mismatches; if $k = 2$ we have a pattern match, followed by two pattern mismatches; more generally, if $k \ge 2$, we have $k-1$ pattern matches, followed by two pattern mismatches.

We now make the following observation: if the predictor is at state $\bar{\nu}$ or $\nu$, before the algorithm reads the factor $\alpha^k\bar{\alpha}$, then immediately after, its current state is still $\bar{\nu}$ or $\nu$, as we end with two mismatches, except in the case $k = 0$, which just consists of one mismatch. Moreover, the predictor cannot be in state $\bar{\tau}$ after such a factor, and if it is in state $\tau$, it can go to $\nu$ or $\bar{\nu}$. This indicates that in the associate Markov chain on $\{\bar{\nu}, \nu, \tau, \bar{\tau}\}$, there is only one strongly connected terminal component made of the states $\bar{\nu}$ and $\nu$. Moreover, we can compute the probabilities of this part of the chain, together with the number of mispredictions induced by each factor $\alpha^k\bar{\alpha}$ as follows:

<table><thead><tr><th></th><th>k = 0</th><th>k = 1</th><th>k = 2</th><th>k = 3</th><th>k &ge; 4</th></tr></thead><tbody><tr><th>&nu;</th><td>0 misp. &rarr; &nu;</td><td>0 misp. &rarr; &nu;</td><td>1 misp. &rarr; &nu;</td><td>3 misp. &rarr; &nu;</td><td>4 misp. &rarr; &nu;</td></tr><tr><th>&nu;</th><td>0 misp. &rarr; &nu;</td><td>0 misp. &rarr; &nu;</td><td>2 misp. &rarr; &nu;</td><td>3 misp. &rarr; &nu;</td><td>3 misp. &rarr; &nu;</td></tr></tbody></table>

For instance, for $\nu$ and $k = 2$, there is one pattern match followed by two mismatches, so the path in the predictor is $\nu \xrightarrow{1} \tau \xrightarrow{0} \nu \xrightarrow{0} \bar{\nu}$, yielding two mispredictions and ending in $\bar{\nu}$.
<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /><figcaption>■ **Figure 7** On the left, the finite state automaton $A_{aba}$ that recognizes the language $A^*ab$. It is enriched on the right to form its associated transducer $T_{aba}$, which indicates the positive (using 1) or negative (using 0) evaluations of the condition $j < m$ and $T[i+j] = X[j]$ in BASICWINDOW. The red 0 indicates the only failing of the condition because $j = m$, when the pattern $X = aba$ is found.</figcaption></figure>

## 5 Mispredictions of BasicWindow

269

We complete the analysis of the total number of mispredictions of BASICWINDOW by considering the condition of the while loop of Line 5. Recall that in our model, the condition is evaluated in one block, and there is a local 2-bit saturated predictor associated with it.

270

271

272

We describe an algorithm that computes the expected number of mispredictions for the condition $j < m$ and $T[i+j] = X[j]$, for a given pattern $X = x_0 \cdots x_{m-1}$. Our results are based on the construction of two transducers $T_X$ and $P_X$: reading a word $T$ in $T_X$ outputs the sequence of true/false of the condition, while $P_X$ outputs the number of mispredictions.

273

274

275

276

If $w \in A^+$ is a non-empty word $w = w_0 \cdots w_{\ell-1}$, let $s(w) = w_1 \cdots w_{\ell-1}$ denote the word obtained from $w$ by removing its first letter, and $p(w) = w_0 \cdots w_{\ell-2}$ denote the word obtained from $w$ by removing its last letter. The first step of the algorithm consists in building the minimal finite state automaton $A_X$ that recognizes the language $A^* \cdot p(X)$. Let $\delta_X$ denote the transition function of $A_X$, which is classically extended to words. The construction is classical [3] and can be done in $O(m)$ time, making use of the following properties:

277

278

279

280

281

282

- The states $Q_X$ are the $m$ prefixes of $p(X)$, the initial state is $\varepsilon$ and the final state is $p(X)$.

283

284

- For any prefix $w$ of $p(X)$ and any letter $\alpha \in A$:

- if $w\alpha$ is a prefix of $p(X)$ then $\delta_X(w, \alpha) = w\alpha$, which is called a *forward transition*,

285

286

- else it is a *backward transition* $\delta_X(w, \alpha) = \delta_X(\varepsilon, s(w)\alpha)$ if $w \neq \varepsilon$, and $\delta_X(\varepsilon, \alpha) = \varepsilon$.

For example, the automaton $A_{aba}$ is depicted in Fig. 7, on the left.

287

When reading the path labeled by $T$ in $A_X$, after each letter of $T$ is read in the sliding window algorithm, the current state $q$ encodes the part of the sliding window which is already parsed immediately before reading the next letter of $T$, i.e. the prefix of length $j$ where $j$ is the variable of BASICWINDOW (see Fig. 8 for an illustration):

288

289

290

291

- following a forward transition $w \xrightarrow{\alpha} w\alpha$ corresponds to a match $T[i+j] = X[j]$ at Line 5, hence $j$ is incremented;

292

293

- otherwise the window is moved to the right because of a letter mismatch or because the pattern $X$ has been found, and the algorithm continues until the next letter of $T$ is queried: at this very moment, the value of $j$ is the length of the longest suffix of $w\alpha$ that is in $Q_X$, which exactly corresponds to $\delta_X(w, \alpha)$ by construction.

294

295

296

297

The second step consists in transforming the automaton $A_X$ into a transducer $T_X$ that maps a word $w \in A^*$ to a binary word of $\{0,1\}^*$. Let $\gamma_X : Q_X \times A \to \{0,1\}^*$ be the output function of $T_X$, which associates a binary word with each transition as follows:

298

299

300

1. If $w \xrightarrow{\alpha} w\alpha$ is a forward transition, then $\gamma_X(w, \alpha) = 1$.

301

2. If $w \xrightarrow{\alpha} v$ is a backward transition and $w\alpha \notin \{\varepsilon, X\}$, then $\gamma_X(w, \alpha) = 0 \cdot \gamma_X(\varepsilon, s(w)\alpha)$.

302

3. If $w\alpha = X$ then $\gamma_X(w, \alpha) = 10 \cdot \gamma_X(\varepsilon, s(w)\alpha)$, and if $|X| > 1$ and $\alpha \neq x_0$, $\gamma_X(\varepsilon, \alpha) = 0$.

303
XX:10 Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm

<figure><img src="image_8.png" /><figcaption>■ **Figure 8** The link between the sliding window algorithm for $X = aba$ and the automaton $A_X$ of Fig. 7. On the left, the prefix $ab$ has already been matched and the $a$ in red, at position $i+2$, is queried for the first time in $T$. The pattern is found and the window moves one step to the right, as depicted in the center. There is an immediate mismatch at the first position ($j=0$), thus the window moves once more to the right. On the right, the first position is a match, and we need to query the next letter of $T$ to continue. Before the red letter $a$ is read, the window matched with $ab$, which is encoded by the state $ab$ of the automaton. When the red $a$ is read, the algorithm continues until querying the unknown $T[i+3]$, and at this moment, we are in the state $a$ of $A_X$. This part of the algorithm execution corresponds to the transition $ab \xrightarrow{a} a$ in $A_X$.</figcaption></figure>

This construction can be computed in $O(m^2)$, from left to right. It is designed so that each occurrence of 1 (resp. 0) corresponds to $j < m$ and $T[i+j] = X[j]$ evaluated to true (resp. false). Indeed, one can easily check that:

- If $w \xrightarrow{\alpha} w\alpha$ is a forward transition, the interpretation is that after having matched $w$ in the window, we read $\alpha$ in $T$, which is also the next letter in $X$, so the condition is true.

- If $w \xrightarrow{\alpha} v$ is a backward transition and $w\alpha \neq X$, then we have a mismatch (producing a 0) then we move the window one step to the right, aligning it with $s(w)$ in $T$.

- If $w\alpha = X$ then we have a match (producing a 1) immediately followed by $j = m$ (producing a 0), then moving the window as in the previous case.

If $w$ is a word on $A$, let $\phi_X(w)$ denote the concatenation of the outputs produced when following the path labeled by $w$ in $T_X$. From the observation above, $\phi_X(T)$ is almost the sequence of evaluations of $j < m$ and $T[i+j] = X[j]$ when calling BASICWINDOW($X,T$), the difference being that we possibly do a few more steps in the transducer output because the algorithm halts as soon as $i > n - m$. This is formalized as follows.

**► Lemma 10.** Let $w$ be the binary sequence of the evaluations of $j < m$ and $T[i+j] = X[j]$ in BASICWINDOW($X,T$). Then $w$ is a prefix of $\phi_X(T)$ and $|\phi_X(T)| - |w| \leq |X|^2$.

Let $\xi$ denote the transition function of the predictor of Fig. 1, extended to binary words. For instance, $\xi(\nu, 00011) = \tau$. Also let $\mu(\lambda, u)$ be the number of mispredictions induced by following the path starting from $\lambda \in \{\bar{\nu}, \nu, \tau, \bar{\tau}\}$ and labeled by $u \in \{0, 1\}^*$ in this predictor.

We now build a kind of product of the transducer $T_X$ and of the automaton of the 2-bit saturated predictor. This is a transducer $P_X$, whose states are of the form $(w, \lambda)$ where $w$ is a state of $T_X$ and $\lambda \in \{\bar{\nu}, \nu, \tau, \bar{\tau}\}$. Its transition function $\zeta_X$ is defined by $\zeta_X((w, \lambda), \alpha) = (\delta_X(w, \alpha), \xi(\lambda, \gamma_X(w, \alpha)))$. In other words, the first coordinates change along with the states in $T_X$, and the second ones come from the update of the current state of the predictor according to the output of the transition in $T_X$. From the example of Fig. 7, for instance $\zeta_{aba}((ab, \bar{\tau}), a) = (a, \tau)$, as the transition in $T_{aba}$ is $ab \xrightarrow{a:1001} a$ and $\xi(\bar{\tau}, 1001) = \tau$.

The output function $\psi_X$ of $P_X$ accounts for the number of mispredictions performed during the updates. Formally, we have $\psi_X((w, \lambda), \alpha) = \mu(\lambda, \gamma_X(w, \alpha))$. To follow our example, as reading 1001 from $\bar{\tau}$ produces 3 mispredictions, we have $\psi_X((ab, \bar{\tau}), a) = 3$. Finally, we restrict the set of states of $P_X$ to those accessible from $(\varepsilon, \bar{\nu})$: we fix that the initial state of the predictor is $\bar{\nu}$ and only consider states that can be reached in $P_X$ during an execution of the algorithm BASICWINDOW. Choosing to start the predictor at $\bar{\nu}$ is arbitrary,
but does not change the asymptotic results (as Theorem 4 does not depend on the initial conditions): this makes $\mathcal{P}_X$ smaller while keeping the correct asymptotic estimate.

336

337

<figure><img src="image_9.png" /><figcaption>Figure 9 On the left, the transducer $\mathcal{P}_{aba}$. Its states encode the letters seen in the window and the state of the predictor just before each letter of $T$ is read. The output is the number of mispredictions made by BASICWINDOW when reading the letter. On the right, the matrix of the associated Markov chain, directly obtained from the probabilities of the letters labelling each transition.</figcaption></figure>

338

339

340

341

The transducer $\mathcal{P}_{aba}$ is depicted in Fig. 9. Let $\xi_X(T)$ denote the sum of the outputs produced while following the path that starts from $(\varepsilon, \bar{\nu})$ and labeled by $T$ in $\mathcal{P}_{aba}$. Then $\xi_X(T)$ gives a good estimation of the number of mispredictions produced on $T$ by BASICWINDOW, by Lemma 10 (and by Theorem 4, to ignore the predictor's starting state).

342

343

**► Proposition 11.** For a fixed pattern $X$, the expected number of mispredictions performed by BASICWINDOW at Line 5 for a random text $T$ is asymptotically equivalent to $\xi_X(T)$.

344

345

346

347

348

349

350

At this stage, one can easily conclude the computations: $\xi_X(T)$ is obtained from a long trajectory in the Markov chain $\Pi_X$ obtain from $\mathcal{T}_X$ by changing the transitions $p \xrightarrow{\alpha:t} q$ into $p \xrightarrow{\pi(\alpha)} q$, or by making the sum of the probabilities if several letters label a transition between $p$ and $q$. Computing the stationary distribution $\hat{\pi}_X$ of $\Pi_X$ gives the asymptotic number of times each state is used with high probability. This, in turn, gives the asymptotic number of times each transition is taken: a transition $p \xrightarrow{\alpha:t} q$ is typically taken $\hat{\pi}_X(p) \cdot \pi(\alpha)$ $n$ times, producing asymptotically $t \cdot \hat{\pi}_X(p) \cdot \pi(\alpha)$ $n$ mispredictions.

351

For instance, the transition matrix of $\Pi_{aba}$, given in Fig. 9, has stationary distribution $\hat{\pi}$:
$$ \hat{\pi}(\varepsilon, \bar{\nu}) = (1-p)^2; \quad \hat{\pi}(a, \nu) = (1-p)p; \quad \hat{\pi}(a, \tau) = p^2; \quad \hat{\pi}(ab, \tau) = (1-p)^2p; \quad \hat{\pi}(ab, \bar{\tau}) = (1-p)p^2, $$
where $p := \pi(a)$ is the probability of generating the letter $a$. From this, we obtain that the expected number of mispredictions is asymptotically $(p^4 - p^3 - p^2 + 3p)n$ for $A = \{a, b\}$.

352

353

354

355

356

357

358

The bottleneck for the running time of this construction is the computation of the stationary vector, which consists in solving the equation $\Pi_X^t \cdot \hat{\pi} = \hat{\pi}$. This can be done in time $O(|Q|^3)$ by Gauss elimination, or even better using more advanced computer algebra techniques. Since $|Q| \le 4m$, the following result summarizes what has been done so far.

359

360

361

**► Proposition 12.** There exists an algorithm of cost $O(|X|^3)$, which given a pattern $X$ computes the asymptotic equivalent of the expected number of mispredictions $\xi_X(T)$ performed by Line 5 of BASICWINDOW($X,T$), where $T$ is produced by a memoryless source.

362

363

The following key statement reduces the study of the number of mispredictions performed by BASICWINDOW to finitely many cases: it only depends on the first three letters of $X$.

364

365

366

**► Proposition 13.** Let $X$ be a pattern of length $m \ge 3$, and let $Y$ be its length-$3$ prefix. If the predictors of Line 5 start in the same state for both algorithms, then there are exactly the same number of mispredictions in BASICWINDOW($X,T$) and BASICWINDOW($Y,T$).
XX:12 Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm

367 **Proof sketch.** If the predictor of BASICWINDOW($X,T$) and BASICWINDOW($Y,T$) are at
368 the same state for a given position $i$ of the window, then they make the same number of
369 mispredictions while scanning the window, and their predictors end at the same state, as
370 having 3 or more matches induce the same behavior. We conclude by a direct induction. ◀

371 Using our algorithm to estimate the number of mispredictions detailed above and Pro-
372 position 13, the whole study is reduced to applying our method to a few patterns. Together
373 with Section 4, this yields our principal result for BASICWINDOW:

374 ▶ **Theorem 14.** Let $X$ be a pattern of length $m \ge 1$. As $n$ tends to infinity, the expected numbers of mispredictions produced by Line 5 and Line 7 in BASICWINDOW($X,T$) are asymptotically equivalent to $\mu_X n$ and $\kappa_X n$, respectively, when $T$ is a size-$n$ text generated by a memoryless source of probability $\pi$.

378 The value of $\mu_X$ only depends on the first three letters of $X$, and is given in the table
379 below, where $p = \pi(a)$, $q = \pi(b)$ and $r = \pi(c)$, where $r = 0$ if $A = \{a, b\}$.

<table><thead><tr><th>X</th><th>μ<sub>X</sub></th><th>X</th><th>μ<sub>X</sub></th></tr></thead><tbody><tr><td>a</td><td>p</td><td>aa</td><td><sup>p(1+3p-3p<sup>2</sup>-2p<sup>3</sup>+2p<sup>4</sup>)</sup>&frasl;<sub>1-p<sup>2</sup>+p<sup>3</sup></sub></td></tr><tr><td>ab</td><td>p(1 + 2q)</td><td>aaa</td><td><sup>p(1+3p-4p<sup>2</sup>-p<sup>3</sup>+3p<sup>4</sup>-p<sup>5</sup>)</sup>&frasl;<sub>1-p<sup>2</sup>+p<sup>3</sup></sub></td></tr><tr><td>aab</td><td><sup>p(1+3p-3p<sup>2</sup>+2p<sup>2</sup>q-2p<sup>3</sup>+2p<sup>4</sup>-p<sup>4</sup>q)</sup>&frasl;<sub>1-p<sup>2</sup>+p<sup>2</sup>q+p<sup>3</sup></sub></td><td>aba</td><td><sup>p(1+2q-p-p<sup>2</sup>-p<sup>2</sup>q-p<sup>2</sup>q<sup>2</sup>)</sup>&frasl;<sub>1-p</sub></td></tr><tr><td>abb</td><td>p(1 + q)<sup>2</sup></td><td>abc</td><td>p(1 + 2q + qr)</td></tr></tbody></table>

381 The value of $\kappa_X$ is $\pi(X)$ if $X$ is made of at least two different letters, and for $m \ge 3$:

$$
382 \kappa_a = \frac{p(1-p)}{1-2p(1-p)}, \quad \kappa_{aa} = \frac{p^2(1-p)(1+2p+p^2-p^3)}{1-p^3+p^4}, \quad \text{and} \quad \kappa_{am} = p^m(1+p-p^2+p^3).
$$

383 Applying Theorem 14 for the uniform distribution on different alphabet lengths yields the
384 following estimates for $\mu_X$:

<table><thead><tr><th>X</th><th>|A| = 2</th><th>|A| = 4</th><th>|A| = 26</th><th>X</th><th>|A| = 2</th><th>|A| = 4</th><th>|A| = 26</th></tr></thead><tbody><tr><td>a</td><td>0.5</td><td>0.25</td><td>0.038</td><td>aa</td><td>0.929</td><td>0.404</td><td>0.043</td></tr><tr><td>ab</td><td>1</td><td>0.375</td><td>0.041</td><td>aaa</td><td>0.875</td><td>0.392</td><td>0.043</td></tr><tr><td>aab</td><td>0.922</td><td>0.405</td><td>0.043</td><td>aba</td><td>1.19</td><td>0.405</td><td>0.042</td></tr><tr><td>abb</td><td>1.13</td><td>0.391</td><td>0.042</td><td>abc</td><td>1</td><td>0.391</td><td>0.042</td></tr></tbody></table>

386 Observe that when $|A| = 2$, for the patterns *aba* and *abb*, the number of mispredictions are greater than $n$, which is especially bad. Indeed, the expected number of letter comparisons being $2n$, the predictor is worse than making the predictions by flipping a coin: the 2-bit saturated predictor is fooled by the dependencies within BASICWINDOW.

390 **6 Mispredictions of UnraveledWindow**

391 In this section we analyze the mispredictions produced by the if instructions of UNRAVELED-WINDOW. The if instruction, Line 6, resembles the one of Line 7 in BASICWINDOW. However, the condition is tested at each increment of j in UNRAVELEDWINDOW, but only at each increment of i in BASICWINDOW. This makes it easier to study UNRAVELEDWINDOW: if the pattern is found at position i, this condition is false m times then true once; if not, it is false while staying in the loop (at least once). Hence, as in the proof of Lemma 6, the predictor quickly stays in {$\bar{\nu}$, $\nu$} and produces a misprediction exactly each time the pattern is found:
**► Lemma 15.** *The average number of mispredictions produced for the counter update in UNRAVELEDWINDOW is asymptotically equivalent to $\pi(X)|T|$.*

For the letter comparison condition, we can use almost identically the results of Section 5 to get an algorithm that estimates the average number of mispredictions made by UNRAVELEDWINDOW at Line 9. Indeed, the only difference is that the condition of BASICWINDOW at Line 5 is evaluated to true then false when the pattern is found: true when matching the last letter of $X$, and false as $j = m$ immediately after. The latter condition is treated separately in UNRAVELEDWINDOW, so this evaluation to false is not there anymore. Everything else remains the same. Hence we can mimic the construction of Section 5, with this modification which consists in setting $\gamma_X(w, \alpha) = 1 \cdot \gamma_X(\varepsilon, s(w)\alpha)$ instead of $\gamma_X(w, \alpha) = 10 \cdot \gamma_X(\varepsilon, s(w)\alpha)$ in Case 3 of the definition of the transducer $T_X$ in page 9 (this is exactly removing the red 0 in Fig. 7). Once this slight modification is done, one can continue by constructing the product transducer for the mispredictions, and then use the property on Markov chains to get the results for any given $X$. For the variant $\tilde{\mu}_X$ of $\mu_X$, the computations yield:

<table><thead><tr><th>X</th><th>μ̃<sub>X</sub></th><th>X</th><th>μ̃<sub>X</sub></th></tr></thead><tbody><tr><td>a</td><td>p(1-p) / (1-2p(1-p))</td><td>aa</td><td>p(1 + 2p - 2p<sup>2</sup> - 3p<sup>3</sup> + 2p<sup>4</sup>)</td></tr><tr><td>ab</td><td>p(1+2q-2p-4pq+p<sup>2</sup>-3pq<sup>2</sup>+2p<sup>2</sup>q+3p<sup>2</sup>q<sup>2</sup>+p<sup>2</sup>q<sup>3</sup>)</td><td>aaa</td><td>p(1+3p-5p<sup>2</sup>-p<sup>3</sup>+4p<sup>4</sup>-2p<sup>5</sup>)</td></tr><tr><td>aab</td><td>p(1+3p-pq-3p<sup>2</sup>+2p<sup>2</sup>q-2p<sup>3</sup>+p<sup>3</sup>q-p<sup>3</sup>q<sup>2</sup>+2p<sup>4</sup>-2p<sup>4</sup>q)</td><td>abb</td><td>p(1+2q+q<sup>2</sup>-p-3pq-2pq<sup>2</sup>-2pq<sup>3</sup>+p<sup>4</sup>)</td></tr><tr><td>aba</td><td>p((1-p)<sup>2</sup>+2q-3pq+p<sup>2</sup>q-2pq<sup>2</sup>+p<sup>2</sup>q<sup>2</sup>(p+q+pq+p<sup>2</sup>-1)) / (1-p)<sup>2</sup></td><td>abc</td><td>p(1-p+2q+qr-3pq-2pq<sup>2</sup>(1+r)-pq<sup>2</sup>r<sup>2</sup>) / (1-p-pq)</td></tr></tbody></table>

Unfortunately, we cannot limit ourselves to a finite number of cases, as Proposition 13 does not hold anymore. For instance, the computations for the uniform distribution on $\{a, b\}$ gives: $\tilde{\mu}_{aba} \approx 0.813$, $\tilde{\mu}_{abaa} \approx 0.938$ and $\tilde{\mu}_{abab} \approx 1.063$.

# 7 Conclusion

In this article, we set out a method for computing the expected number of mispredictions during an execution of the sliding window algorithm for a large text generated by a memoryless distribution, considering two branching structure variants. Recall that we studied local predictors associated with each conditional jump instruction. For BASICWINDOW we have a complete statement since the first three letters of $X$ completely determine the behavior.

The table below contains the numerical values of the ratio of mispredictions by letter of $T$ on size-3 patterns assuming the uniform distribution for $T$. It is worth noticing that UNRAVELEDWINDOW produces less mispredictions than BASICWINDOW, except for $X = abb$. Also, the number of mispredictions clearly depends on the pattern, especially for UNRAVELEDWINDOW.

<table><thead><tr><th rowspan="2">X</th><th colspan="3">BASICWINDOW</th><th colspan="3">UNRAVELEDWINDOW</th></tr><tr><th>|A| = 2</th><th>|A| = 4</th><th>|A| = 26</th><th>|A| = 2</th><th>|A| = 4</th><th>|A| = 26</th></tr></thead><tbody><tr><td>aaa</td><td>1.0156</td><td>0.4361</td><td>0.0428</td><td>0.8750</td><td>0.3921</td><td>0.0427</td></tr><tr><td>aab</td><td>1.0469</td><td>0.4206</td><td>0.0428</td><td>0.9219</td><td>0.4050</td><td>0.0428</td></tr><tr><td>aba</td><td>1.3130</td><td>0.4205</td><td>0.0416</td><td>0.9375</td><td>0.3969</td><td>0.0415</td></tr><tr><td>abb</td><td>1.2500</td><td>0.4062</td><td>0.0415</td><td>1.3130</td><td>0.4101</td><td>0.0415</td></tr></tbody></table>

The natural follow-up of our work is to proceed with the study of less naive pattern matching algorithms, such as KMP or Boyer-Moore [3]. They both have interpretations in term of automata that we should be able to exploit in a similar way. Also, to fill the gap with practical results, enhancing the model with global predictors seems mandatory since preliminary experiments suggest less mispredictions. Proving this would constitute a first
XX:14 Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm

434 theoretical result that would emphasize the value of global predictors for relevant algorithms.

435 As global predictors usually involve history tables indexing 2-bit saturated predictors, we

436 expect that what we did in the present study can be used in the process.
References

1 Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. Good predictions are worth a few comparisons. In *STACS 2016*, volume 47, pages 12:1-12:14, Orléans, France, February 2016. URL: https://hal.science/hal-01212840, doi:10.4230/LIPIcs.STACS.2016.12.

2 Gerth Stølting Brodal and Gabriel Moruz. Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms. In *Algorithms and Data Structures*, volume 3608, pages 385-395. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005.

3 M. Crochemore, C. Hancart, and T. Lecroq. *Algorithms on Strings*. Cambridge University Press, 2007. URL: https://books.google.fr/books?id=PuOOY_DR55UC.

4 David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. *Markov Chains and Mixing Times*. American Mathematical Society, 2008. URL: http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf.

5 Conrado Martínez, Markus E. Nebel, and Sebastian Wild. Analysis of branch misses in quicksort. In *Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, San Diego, CA, USA, January 4, 2015*, pages 114-128, 2015. doi:10.1137/1.9781611973761.11.

6 Sparsh Mittal. A survey of techniques for dynamic branch prediction. *Concurrency and Computation: Practice and Experience*, 31, 2018. URL: https://api.semanticscholar.org/CorpusID:4572006.

7 David A. Patterson and Carlo H. Séquin. RISC I: a reduced instruction set VLSI computation. In *International Symposium on Computer Architecture*, 1981. URL: https://api.semanticscholar.org/CorpusID:2573351.

8 Mireille Régnier. Knuth-Morris-Pratt algorithm: An analysis. In Antoni Kreczmar and Grazyna Mirkowska, editors, *Mathematical Foundations of Computer Science 1989, MFCS'89, Porabka-Kozubnik, Poland, August 28 - September 1, 1989, Proceedings*, volume 379 of Lecture Notes in Computer Science, pages 431-444. Springer, 1989.
# Appendices

## A Proofs of Section 3

463

We only prove Lemma 2, as Lemma 1 is just a corollary of this statement.

464

**Lemma 2.** For any pattern X, if the text T is generated by a memoryless source of probability distribution $\pi$, then the average number of letter comparisons performed by the two algorithms is $\gamma(\pi, X) (n - m + 1)$, with $\gamma(\pi, X) = \sum_{j=0}^{|X|-1} \pi(\text{Pref}(X, j))$.

465

466

467

**Proof.** For $i \in \{0, \dots, n-1\}$ let $C_i$ denote the number of letter comparisons performed by the algorithm when the window is at position $i$. By direct induction, for every $j < m$, the probability that the length-$j$ prefix of X matches is $\pi(\text{Pref}(X, j))$, producing at least $j+1$ comparisons. Hence

468

469

470

471

$$ \mathbb{E}[C_i] = \sum_{j=0}^{m-1} \mathbb{P}(C_i \ge j+1) = \sum_{j=0}^{m-1} \pi(\text{Pref}(X, j)). $$

472

We conclude by the linearity of the expectation.

473

<figure><img src="image_10.png" /></figure>

474

**Lemma 3.** If X and T are two random words generated by a memoryless source of probability distribution $\pi$, the average number of letter comparisons performed by the two algorithms is $\frac{1-c_2(\pi)^m}{1-c_2(\pi)} (n - m + 1)$, where $c_2(\pi) = \sum_{\alpha \in A} \pi(\alpha)^2$.

475

476

477

**Proof.** Let C denote the number of letter comparisons performed by the algorithm. From Lemma 2 we have, for any $w = w_0 w_1 \cdots w_{m-1} \in A^m$: $\mathbb{E}[C | X = w] = \sum_{j=0}^{m-1} \pi(w_0 \cdots w_{j-1})$. Hence, by the law of total probability we have:

478

479

480

$$ \mathbb{E}[C] = \sum_{w \in A^m} \sum_{j=0}^{m-1} \pi(w_0 \cdots w_{j-1}) \cdot \pi(w). $$

481

Therefore we obtain:

482

$$ \mathbb{E}[C] = \sum_{j=0}^{m-1} \sum_{u \in A^j} \sum_{v \in A^{m-j}} \pi(u)^2 \cdot \pi(v) = \sum_{j=0}^{m-1} \sum_{u \in A^j} \pi(u)^2. $$

483

Now we prove by induction on $j \ge 0$ that $\sum_{u \in A^j} \pi(u)^2 = c_2(\pi)^j$. This holds for $j = 0$. Assume it holds for some $j$, then

484

485

$$ \sum_{u \in A^{j+1}} \pi(u)^2 = \sum_{u \in A^j} \left( \pi(u)^2 \cdot \sum_{\alpha \in A} \pi(\alpha)^2 \right) = c_2(\pi)^j \cdot c_2(\pi) = c_2(\pi)^{j+1}. $$

486

This concludes the proof as $\sum_{j=0}^{m-1} c_2(\pi)^j = \frac{1-c_2(\pi)^m}{1-c_2(\pi)}$.

487

<figure><img src="image_11.png" /></figure>

## B Proofs of Section 4

488

Let $M(u, X)$ be the number of mispredictions induced by the updates of nb for the text $u$ when the initial state of the predictor is $s \in \{\bar{\nu}, \nu, \tau, \bar{\tau}\}$.

489

490
**► Lemma 6.** If the pattern X contains at least two different letters, then the expected number of mispredictions induced by the updates of the counter nb is asymptotically equivalent to $\pi(X)n$, as $n$ tends to infinity: $\kappa_X = \pi(X)$ in this case.

**Proof.** Let $\alpha$ be the first letter of X and let $\beta \neq \alpha$ be another letter. Let F be the random variable that associates with the text T the length of its smallest prefix that ends with $\beta\beta\beta$, and $+\infty$ if $\beta^3$ does not appear in T. By the law of total probability, for any $\ell \ge 1$ we have

$$ \mathbb{E}[M(T, s)] = \mathbb{E}[M(T, s) | F < \ell] \cdot \mathbb{P}(F < \ell) + \mathbb{E}[M(T, s) | F \ge \ell] \cdot \mathbb{P}(F \ge \ell). \quad (1) $$

Let $T = t_0...t_{n-1}$. Observe that if $F \ge \ell$ then for all $i < \lfloor \frac{\ell-1}{3} \rfloor$ the factor $f_i := t_{3i}t_{3i+1}t_{3i+2}$ of T is different from $\beta^3$. These factors do not overlap and hence the probability they are all different from $\beta^3$ is $(1 - \pi(\beta)^3)^{\lfloor \frac{\ell-1}{3} \rfloor}$. Therefore $\mathbb{P}(F \ge \ell) \le \lambda\gamma^\ell$, for some $\lambda > 0$ and $\gamma = (1 - \pi(\beta)^3)^{1/3}$, so that $\gamma \in (0, 1)$. We choose $\ell := \ell_n = 2^{\lfloor \log_{1/\lambda}(n) \rfloor}$, so that $\gamma^\ell = O(1/n^2)$. This yields

$$ \mathbb{E}[M(T, s) | F \ge \ell] \cdot \mathbb{P}(F \ge \ell) \le n \cdot \lambda\gamma^\ell = O\left(\frac{1}{n}\right). $$

Let $u_F$ denote the prefix of length $F(T)$ of T, and $v_F$ be the word such that $T = u_F v_F$. As observed above, we have $M(u_F v_F, s) \le M(u_F, s) + m + M(v_F, t)$, where $t$ is the state of the predictor when the window is aligned with $v_F$. By definition of $F$, $u_F$ ends with $\beta^3$ and hence $t = \bar{v}$. Moreover, as $X \neq \alpha^m$, there cannot be two consecutive occurrences of X in T. Hence, if there is a match and the predictor uses a right transition, it uses a left transition immediately after. This implies that while scanning $v_F$, the predictor only uses its states $\bar{v}$ and $\nu$: exactly one misprediction occurs each time the pattern X is found. Let $N(k, X)$ denote the number of occurrences of X in a random word of length $k$. Since there is at most one misprediction by window position, we have

$$ \mathbb{E}[N(n - i, X)] \le \mathbb{E}[M(T, s) | F = i] \le i + \mathbb{E}[N(n - i, X)] $$

As $\mathbb{E}[N(k, X)]$ is non-decreasing with $k$, this yields

$$ \mathbb{E}[N(n - \ell, X)] \le \mathbb{E}[M(T, s) | F < \ell] \le \ell + \mathbb{E}[N(n, X)]. $$

Moreover, by linearity of the expectation and since each window is a match with probability $\pi(X)$, for $k \ge m$ we have $\mathbb{E}[N(k, X)] = (k - m + 1)\pi(X)$. Therefore,

$$ (n - 2^{\lfloor \log_{1/\gamma}(n) \rfloor} - m + 1) \pi(X) \le \mathbb{E}[M(T, s) | F < \ell] \le (n - m + 1)\pi(X) + 2^{\lfloor \log_{1/\gamma}(n) \rfloor}, $$
which concludes the proof as $\mathbb{P}(F < \ell)$ tends to 1 as $n$ tends to infinity. ◀

**► Lemma 8.** If the pattern is $X = \alpha\alpha$, then the expected number of mispredictions induced by the updates of the counter nb is asymptotically equivalent to $\kappa_{\alpha\alpha} n$, where $\kappa_{\alpha\alpha} = \delta(\pi(\alpha))$ and $\delta(p) = \frac{p^2(1-p)(1+2p+p^2-p^3)}{1-p^3+p^4}$.

**Proof.** The stationary distribution of the 2-state markov chain above is $\hat{\rho}$ defined by $\hat{\pi}(\bar{v}) = \frac{1-p^3}{1-p^3+p^4}$ and $\hat{\pi}(\nu) = \frac{p^4}{1-p^3+p^4}$. If we condition to be at state $\bar{v}$ when starting a factor $\alpha^k \bar{\alpha}$, the expected number of mispredictions can be computed from the array above, and is equal to $p^2(1+p)^2$. Similarly, if we condition to be at state $\nu$, the expected number of misprediction is $p^2(2+p)$. Hence, after $t$ factors of the form $\alpha^k \bar{\alpha}$ are considered, the expected number of mispredictions is asymptotically equivalent to

$$ \left( \frac{1-p^3}{1-p^3+p^4} \times p^2(1+p)^2 + \frac{p^4}{1-p^3+p^4} \times 2p^2(1+p) \right) t = \frac{p^2(1+2p+p^2-p^3)}{1-p^3+p^4} t. $$
XX:18 Theoretical Analysis of Branch Prediction in the Sliding Window Algorithm

In our model of randomness, the expected length of a $\alpha^k \bar{\alpha}$ is $\frac{1}{1-p}$, since it is distributed as a geometric law of parameter $1-p$. Hence if we generate $t = (1-p)n$ such factors, we obtain a text $T$ of length $n+o(n)$ with high probability, by the law of large numbers. This concludes the proof. ◀

**Lemma 9.** If the pattern is $X = \alpha^m$, for $m \ge 3$, then the expected number of mispredictions induced by the updates of the counter nb is asymptotically equivalent to $\lambda(\pi(\alpha))n$, as $n$ tends to infinity, where $\lambda(p) = p^m(1+p-p^2-p^3)$.

**Proof.** The probability of generating $\alpha^k \bar{\alpha}$ is $p^k(1-p)$, with $p = \pi(\alpha)$. Observe also that the probability of generating an $\alpha^j \bar{\alpha}$ with $j \ge k$ is $p^j$. Hence, the expected number of mispredictions induced by a factor $\alpha^k \bar{\alpha}$ conditioned to be on $\bar{\nu}$ is

$$540 \qquad p^m(1-p) + 3p^{m+1}(1-p) + 4p^{m+2} = p^m(1-p + 3p(1-p) + 4p^2) = p^m(1+p)^2.$$

As in the proof of Lemma 8, they are typically $(1-p)n$ factors $\alpha^k \bar{\alpha}$ in a size-$n$ random text, concluding the proof by law of large numbers. ◀

C Proofs of Section 5

**Proposition 13.** Let $X$ be a pattern of length $m \ge 3$, and let $Y$ be its length-$3$ prefix. If the predictors of Line 5 start in the same state for both algorithms, then there are exactly the same number of mispredictions in $\text{BASICWINDOW}(X,T)$ and $\text{BASICWINDOW}(Y,T)$.

**Proof.** We prove by induction on $i \in \{0, \dots, n-m\}$ that each scan of the window when it is at position $i$ produces the same number of mispredictions, and leave the predictor in the same state. The proof is a direct consequence of the following observation:

if $Y$ is not found at position $i$ in $T$, then neither is $X$ and the window scans at position $i$ in both $\text{BASICWINDOW}(X,T)$ and $\text{BASICWINDOW}(Y,T)$ and performs exactly the same execution, making the same number of mispredictions and leaving the predictors at the same states, provided they started at the same state.

if $Y$ is found at position $i$, then the predictors are at state $\bar{\tau}$ when finding $Y$ (after comparing $T[i+2]$ and $X[2] = Y[2]$). For $\text{BASICWINDOW}(Y,T)$, it is followed by a misprediction leaving the predictor at state $\tau$ as $j=m$ is triggered; then the window moves to the right. For $\text{BASICWINDOW}(X,T)$ it continues scanning $X$, staying in $\bar{\tau}$ and producing no misprediction, until the inner while loop stops (because $X$ is found or because of a mismatch), at which time a misprediction is produced and the predictor's state changes to $\tau$; then the window moves to the right.

Thus in both cases, if the predictors start at the same state, they produce the same number of mispredictions and end at the same state. This concludes the proof by induction. ◀
D Misprediction in UnraveledWindow

The following plot depicts the variations of $\tilde{\mu}_X$ for all patterns of length 3 on a binary
alphabet.

<figure><img src="image_12.png" /><figcaption>■ **Figure 10** Variations of the first-order multi-plicative constants, depending on $\pi(\alpha)$, for the expected number of mispredictions of the letter comparison. The alphabet is $A = \{a, b\}$, and all the size-3 pattern shapes are depicted.</figcaption></figure>