A column computed in machine words

Two cells side by side in an edit-distance table differ by at most one.

That is not in the definition and it is not obvious from it. It follows from the recurrence: the cell to the right can always be reached from this one by one insertion, so it is at most one more; and this one can be reached from it by one deletion, so it is at most one more than that. The same argument runs vertically. A diagonal neighbour differs by zero or one.

So a column of the table is not a list of numbers between zero and $n$. It is a list of differences from $\{-1, 0, +1\}$ — two bits a cell — and thirty-two of them fit in one machine register.

Why the unit has to change before anything can be said #

Counting cells is useless here, because every cell is still computed. Myers’s algorithm prunes nothing, skips nothing and approximates nothing: it produces the identical table, cell for cell, and its whole claim is that it produces a column at a time.

So the count that means anything is the number of word operations, and a word operation needs a word size to be defined. This site has made that move twice before. The machine field models a cache with a stated line size and counts misses; it models a two-bit branch predictor and counts mispredictions. Neither is a measurement of a real processor and both are exact, reproducible and machine-independent — which is what a cost model is for.

This field adds a third: a bit vector held in $w$-bit lanes, charging one operation per lane per act. Every and, or, not, shift and addition on a vector of $m$ bits costs $\lceil m/w \rceil$. The implementation of Myers’s recurrence measured here performs fifteen such acts per character of the text, so its total is $15\,n\lceil m/w\rceil$, and each of those three factors is on the plate.

What the fifteen operations are doing #

The recurrence works on two vectors: VP, whose bit $i$ is set where the vertical difference at row $i$ is $+1$, and VN, set where it is $-1$. Where neither is set the difference is zero. A third pair, HP and HN, carries the horizontal differences.

Per character of the text, the algorithm computes a mask of the positions where that character matches the pattern, combines it with the two vectors by a fixed sequence of bitwise operations, and reads the bottom bit to update a running score. Fourteen of the fifteen operations are bitwise and take no notice of their neighbours.

The fifteenth is an addition, and it is the interesting one. Addition is the only operation in the set that propagates information along the vector, because a carry moves upward through the bits — and propagating information along the column is exactly what the inner loop of the ordinary algorithm was doing. The carry chain is the loop, executed by the adder in one step. That is the whole trick, and it is why this technique appears wherever a scan-like dependency can be expressed as a carry.

What it buys, measured #

At five hundred and twelve characters each way, the plain table considers 787,456 transitions across 263,169 cells. Myers performs 122,880 word operations at $w = 32$.

The right-hand column is flat, which is the claim: the ratio is $3w/15 = 6.4$, and neither the strings nor their contents move it. Against cells rather than transitions the factor is 2.14, or $w/15$, and which of the two numbers is the honest one depends on what a cell is thought to cost — this site counts both for exactly that reason.

Reading the answer off the bottom bit #

One detail is worth following because it explains why the score is maintained rather than computed.

The vectors hold differences, so nothing in them is a distance. The distance at the bottom of the current column is kept as an ordinary integer, initialised to $m$ — the distance between the whole pattern and the empty prefix of the text — and updated by one per character according to the top bit of the horizontal difference vectors: up if that bit is set in HP, down if it is set in HN, unchanged otherwise.

So the running score is a scalar that moves by at most one per step, and the whole column’s worth of information never has to be summed. That is what makes the per-character cost a constant number of word operations rather than a constant plus a popcount, and it is also what limits the algorithm to the bottom row: any other row’s value would need the differences above it added up, which is a scan the representation deliberately does not do.

The other consequence is that the intermediate scores are available for free. The score after $j$ characters of the text is the distance between the whole pattern and the first $j$ characters of the text, so one run produces the entire last row of the table — which is exactly what the divide step of a linear-space alignment needs, and is why the two techniques compose without either of them being modified.

The crossover, which is where the honest half is #

A vector of $m$ bits occupies $\lceil m/w\rceil$ lanes, and a lane is a whole word whether or not it is full. So the cost per text character is $15\lceil m/w \rceil$ — flat in $m$ until $m$ crosses a multiple of the word size, and then it steps.

Holding the text at 256 characters and sweeping the pattern:

At a pattern of eight characters the word machine performs 3,840 operations where the table has 2,313 cells. It does more elementary work than the thing it replaces. The crossover in cells is between eight and sixteen characters, at $m + 1 = 15$; against transitions it is at $m + 1 = 5$, so on any pattern longer than four characters it is already ahead by the count that charges three per cell.

That shape is familiar on this site and it is the reason this essay sits in the machine field rather than in the tables field. A search with no branch to miss measured a branchless binary search doing strictly more work by every counter the site owns and existing because a mispredicted branch costs more than the work it avoids. Bit-parallel edit distance is the same argument with a different resource: it does more, in a unit that is cheaper, and the ranking flips only once the unit is stated.

The other thing two bits a cell is good for #

The delta representation is worth a paragraph on its own account, independently of the algorithm, because it is a statement about how much information a distance table contains.

A table of distances between prefixes of two strings of length $n$ holds $(n+1)^2$ numbers, each up to $n$, so writing it out costs about $n^2\log_2 n$ bits. Writing out the differences costs $2n^2$ — the first row and column, plus two bits a cell. At $n = 1{,}000$ that is a factor of ten, and the two representations are exactly interconvertible: a prefix sum recovers the table, and a difference recovers the deltas.

That is the same observation the coding field makes about a stream whose symbols are correlated — the model is the compressor — arriving here as a property of a computed object rather than of a data source. The table looks like it holds $\log n$ bits a cell and holds two, because its cells are heavily constrained by each other, and the constraint is a consequence of the recurrence rather than of anything about the strings.

Where the same trick is used #

Bit-parallelism over a dynamic programming column is one instance of a family, and the family is worth naming because the shape recurs.

Shift-Or, for exact matching. A bit vector of pattern positions, shifted left and masked by the character’s match set, one operation per text character. It is the same representation with a simpler recurrence, it predates Myers, and it is the reason the technique is sometimes called bitap.

Approximate matching with a small threshold. $k+1$ vectors, one per allowed error, each derived from the one below it. Cheaper than the full Myers recurrence when $k$ is tiny and worse when it is not, which is a crossover of the same kind as the one above.

Carry propagation as a scan. The general form: any left-to-right dependency where the state is one or two bits per position and the update is monotone can often be expressed as an addition, and then a whole word of positions advances in one step. That is what the fifteenth operation is doing here, and it is why the technique fails on recurrences whose per-cell state does not fit in a couple of bits — the affine gap model, for instance, needs three tables and the deltas stop being small.

What the model does and does not claim #

The word machine here is a model, in the exact sense the cache model and the branch predictor on this site are models, and it is worth stating what that buys and what it costs.

What it buys: an exact, reproducible, machine-independent count. Run the same pair of strings through the same code at the same word size on any host and the number of word operations is the same integer. That is the same property comparisons have, and it is why every number in this essay is a count rather than a duration.

What it costs: the model charges one for every operation on a lane, and a real processor does not. An addition with a carry chain across eight lanes is not eight independent additions — it is a dependency the hardware serialises — while eight independent ands are not, and a vector unit may do thirty-two lanes at once. So the count here is an upper bound on the parallel work and an accurate count of the scalar work, and it does not model the one thing that would make a wider register strictly better.

That is a real limitation and it is stated rather than hedged. What the model does support is the claim this essay makes: the count is proportional to $n\lceil m/w\rceil$, it is a staircase in $m$, and the crossover against a plain table is at a pattern length the model computes exactly.

The empty half of the register #

The staircase says that a pattern of nine characters costs a whole lane, of which seven-eighths is unused. That waste is not inherent, and the repair is worth stating because it applies exactly where the technique is weakest.

Nothing about the recurrence requires a lane to hold one pattern. The vectors are bitwise throughout except for the single addition, and an addition is the only operation whose effect crosses a bit boundary. So several short patterns can be packed into one register — each occupying its own field, separated by a spare bit that absorbs the carry — and advanced together on the same text character. Three nine-bit patterns and their separators fit in a thirty-two bit word, and one pass over the text then computes three distances.

The gain is exactly the fraction of the register that was empty. At a pattern of nine on a thirty-two bit machine that is a factor of three; at a pattern of six it is four. The technique’s worst regime and its best opportunity for packing are the same regime, which is a pleasant symmetry and not a coincidence — both are the same statement about how much of the register the problem fills.

Two conditions, and both are checkable rather than hopeful. The separator bit must be wide enough that no carry escapes its field, which for this recurrence means one spare bit per pattern because the addition can propagate at most one position beyond the field’s top. And the running scores are per pattern, so the scalar bookkeeping is multiplied rather than shared — a small cost, since the scalars are integers and the expensive part was the vector.

Where this matters is the case the crossover section makes look bad. A spell-checker compares one mistyped word against thousands of dictionary entries, all of them short, and the plain analysis says the word machine is barely ahead of the table at those lengths. Packed, it processes several dictionary entries per pass and is ahead by the packing factor as well. The regime in which the ordinary form is unimpressive is precisely the regime that is plural, and plural is what packing is for.

The table that has to be built before the first character #

Every count in this essay is per character of the text, and there is a term that is not.

The recurrence needs, for each character of the text, a mask saying which positions of the pattern hold that character. Those masks are precomputed: one bit vector per symbol of the alphabet, each $\lceil m/w \rceil$ lanes wide, built by one pass over the pattern before the text is touched.

So the real cost is

$$\sigma \left\lceil \frac{m}{w} \right\rceil \;+\; 15\,n \left\lceil \frac{m}{w} \right\rceil$$

and the first term is invisible in every table above because those tables hold $\sigma$ at four or twenty-two while $n$ is in the hundreds. Divide through and the preprocessing is worth paying once the text is longer than about $\sigma/15$ characters — seventeen characters for a byte alphabet, which is never a consideration.

It becomes one on a wide alphabet. Over sixteen-bit characters the mask table is sixty-five thousand vectors and the break-even text is some four thousand characters long; below that, the algorithm spends most of its time preparing for a text it barely reads. And the table is rebuilt for every new pattern, so a workload of many short searches pays it many times.

The repair is the same one the multi-pattern automaton needs and arrives for the same reason. A symbol occurring nowhere in the pattern has an all-zero mask, and all such symbols are identical, so only the symbols the pattern actually contains need entries — at most $m$ of them — with everything else resolving to a shared zero vector through a small map. The preprocessing term becomes $O(m)$ rather than $O(\sigma)$, it no longer depends on the alphabet at all, and the per-character cost gains one lookup.

Which restores the property the essay’s headline claim depends on. Without it, the cost is a function of $n$, $m$, $w$ and $\sigma$, and the last of those appears in no statement of the algorithm; with it, the alphabet genuinely drops out. That is a term worth chasing down rather than absorbing into a constant, because a term that is negligible on the alphabet a paper measured and dominant on the alphabet a reader has is the exact shape of thing this collection exists to print.

What it does not do #

Three things, and all three are the reason this is a technique rather than a replacement.

It gives the distance and not the alignment. The vectors hold differences, the score is a running integer, and nothing is retained that a traceback could walk. Recovering the alignment means going back to a table — which is what the alignment that fits in one line is for, and the two techniques compose: the divide step can use the bit-parallel routine to compute the row it needs.

It computes every cell. There is no output sensitivity here at all. On two strings one edit apart it does exactly as much work as on two unrelated strings, where a band as wide as the answer does a hundredth. The two techniques attack different factors of $nm$ — one the constant, one the $n$ — and real implementations use both, running the bit-parallel recurrence inside a band.

Its constant is not small. Fifteen operations per character is what this implementation performs; published versions are nearer eleven, and a hand-tuned one fewer still. The count reported here is a count of what the measured implementation actually did, not a quotation, and it is the number the plates carry. A different implementation would move the crossover and would not move the shape.