Skip to content

mibz2 · Research blog

The free closure of an induction: where free steps come to rest

The steps that cost mibz2 no bookkeeping can be taken in any order and still meet at one end point, now proved to belong to the block itself.

The width of an induction, the previous post, looked at mibz2's experimental decoder for bzip2. It found that the decoder can hold about a third as much at its busiest moment if it takes its free steps first. A free step is a step of the rebuild that erases one boundary between pieces of the block and creates none. That post also reported that the free steps always reach the same end point, whatever order they run in. This post is about that end point: why the order doesn't matter, how it was proved and checked, and what it allows a decoder to do.

The recap. bzip2 sorts the rotations of each block and stores the last byte of each, the last column; each sorted rotation is a row. To decode, mibz2 follows a map called LF from row to row, reading one byte per move, which spells the block out backwards. A run is a stretch of equal bytes in the last column, and LF moves each run's rows together, as one interval. A new way back from the BWT introduced Cells, the decoder that works on those intervals instead of on rows. Each of its steps cuts some rows out of the map, and lets the interval whose rows used to land there jump straight over them. The code calls each interval a letter, and the bytes its jump reads, in text order, its word. A step happens at a coincidence: a boundary where one letter's rows end and another letter's landing place ends too. Every letter starts with a one-byte word, and when the last step is done, a word spells the whole block.

The width post in brief. The width of a rebuild is the most letters with a word longer than one byte that it holds at once. Cells always steps at the right-hand end of the map. Its width is about 0.32 r at the median on Wikidata, where r is the number of runs in the block. Taking free steps first cuts that to about 0.08–0.11 r. On every block, the peak stayed within the number of letters left once the free steps run out.

The theorem. Take free steps in any order until none is left. You always reach the same letters, with the same words, after the same number of steps. The one exception is a cycle of the map that closes completely during the free steps. It takes no further part, and two orders can leave it in different places, with its word rotated. No real block closes its cycle that early.

Why it matters. Call the state where the free steps run out the free closure. Because the order doesn't matter, it is a property of the block, not of the algorithm that found it. On the 233 large blocks of the Wikidata benchmark it leaves 0.185 r letters at the median, and takes 0.896 r steps to reach. Those are counts, and they are now facts about each block: no cleverer order of free steps can change them. The proof is by hand, and a program checked its every case on 10.7 million pairs of steps, with no exception.

What it allows, and what it doesn't yet. A decoder may take free steps in whichever order is cheapest to find. Free steps on different letters may go to different threads and still meet at the same state. So one block's rebuild can be split between threads, and it is proved to stay correct. No such decoder has been built or timed.

Section 1 works one free step on a four-byte block. Section 2 takes its two free steps in both orders. Section 3 gives the proof's shape, and section 4 the machine check. Section 5 separates what is proved from what is counted. Section 6 says what a decoder could do with it, and section 7 what is open.

1. What does one step do?

Suppose you want to compress the four bytes abac. Their four rotations, sorted, are abac, acab, baca and caba, so the last column is cbaa. It has three runs, c, b and aa, so the rebuild starts with three letters. Call them Y, Z and X:

Letter Its rows (top) LF sends them to (bottom) Word
Y, the run c row 0 row 3 c
Z, the run b row 1 row 2 b
X, the run aa rows 2–3 rows 0–1 a

The figure draws each letter twice. The top strip shows where its rows sit in the last column. The bottom strip shows where LF sends them, and the shaded band joins the two. The numbers above the strips count boundaries between rows, so boundary 4 is the end of row 3.

One free step on the column of abac

Before: X and Y end at boundary 401234topbottomY · cY · cZ · bZ · bX · aX · aAfter the step at 4: row 3 is cut01234topbottomcutcutY · acY · acZ · bZ · bX · aX · a
Computed by a program that steps the column exactly as the checker in section 4 does; not drawn by hand. Top strip: each letter’s rows. Bottom strip: where LF sends them. Each box shows the letter and its word. Grey boxes are rows the step has cut.

Two things end at boundary 4. In the top strip, X's rows 2–3 end there. In the bottom strip, so does Y's landing place, row 3. That makes boundary 4 a coincidence, and a step can be taken there. Y's one row lands on row 3. Row 3 belongs to X, which sends it on to row 1. So row 3 is only a stopover on Y's way. The step cuts row 3 out, and Y now jumps from row 0 straight to row 1. Its jump reads c and then a. LF runs backwards through the text, so in text order its word grows at the front: c becomes ac, which is indeed in abac. X loses the row, and keeps row 2, which still goes to row 0.

The step is free because of where Y now lands. Its new landing place starts a boundary at 1 in the bottom strip. The top strip already had a boundary at 1, between Y's row and Z's. So the step erased the boundary at 4 and created none that wasn't already there. A step that is not free, a paid step, would put a boundary at a new place, and some later step would have to remove it. A step between two letters of the same length is always free, since one letter simply takes over the other's place.

2. Does the order matter?

The column has a second free step available at the start. At boundary 2, Z's row 1 ends in the top strip. X's landing place, rows 0–1, ends there in the bottom strip. Here Z is the shorter piece, so row 1 is cut. X's row 3 used to land on row 1 and go on with Z to row 2. Now it jumps straight to row 2. That one row splits off from X and becomes Z, with the word ba.

Both steps are free, and they share a letter: X. Each one changes X's length, so neither leaves the other's starting point untouched. The figure takes them in both orders.

Two free steps, two orders, one state

Start: free steps at 2 and 401234Y·cY·cZ·bZ·bX·aX·aStep at 4 firstY·ac; X shrinks01234cutcutY·acY·acZ·bZ·bX·aX·aStep at 2 firstZ·ba; X shrinks01234cutcutY·cY·cX·aX·aZ·baZ·baEither order: one staterows 1 and 3 cut01234cutcutcutcutY·bacY·bacX·aX·astep at 4step at 2then at 2then at 4In each state: upper strip top, lower strip bottom
Computed, as in the figure above. Green lines mark the free steps available in each state. Taking the step at 4 first and then the one at 2, or the other way round, gives the same letters, places and words: X at row 2 with the word a, and Y at row 0, landing on row 2, with the word bac.

The left path makes Y's word ac first, and then the step at 2 puts b in front of it. The right path makes Z's word ba first, and then the step at 4 hands Y the whole of ba followed by its own c. Either way, Y ends with bac and X with a. In the language of rewriting systems this is a diamond, or a square. Two steps leave one state, and one step on each side brings them back together.

The tiny block goes on to its end. After the diamond, X and Y form a cycle of two letters, each landing on the other's rows, and one more free step closes it whole. A program tried every one of the twelve orders in which the free steps of cbaa can be taken. All twelve take three steps. Each ends with one letter whose word is abac, acab, baca or caba: the same cycle, read from different starting points. That is the exception in the theorem. On a four-byte block the whole text closes during the free steps. On the Wikidata blocks, where the free steps stop at about a fifth of the runs, none did. bzip2 stores with every block the row of the original rotation, which says where to start reading in any case.

3. Why does it hold for every block?

Two diamonds on one example prove nothing in general, so the proof goes through a classical result. Newman's lemma, from 1942, says that a system of rewriting steps has a single end point from every start if two things hold.

  1. Termination. No sequence of steps goes on forever. Each free step erases one boundary and creates none, and a block has only finitely many boundaries, so this holds.
  2. Local confluence. Whenever two steps are available in the same state, there is some way to continue from each of them so that both reach the same state again.

Termination is what lets the second, local condition decide the global answer. Without it, two paths could keep diverging forever, each step of the way looking reconcilable.

So the proof takes any two free steps available together, at boundaries c₁ and c₂, and shows that they can be brought back together. It rests on two facts. First, a free step touches only its own two letters, and removes no boundary but its own. Second, the place where a free step's shorter letter lands always lies strictly inside the longer letter's interval, so it can never be the other step's coincidence. Then two steps relate in exactly one of four ways:

  1. No letter in common. Neither step changes anything the other reads, so each stays free after the other, and the two orders give the same state.
  2. One shared letter X, whose rows end at c₁ and whose landing place ends at c₂. This is the case of abac, and the hard one. Each step can be one of three kinds: the letter above wins (it is longer), the letter below wins, or the two are equal. That gives nine combinations of kinds for the pair. The table below shows which can happen.
  3. One shared letter, the other way round. This is case 2 with the steps' names swapped.
  4. Both letters shared. The two letters form a cycle of two, and either step closes it. The two results differ only in where the closed letter lies and in which rotation of its word it holds. That is where the theorem's exception comes from.

In case 2, X is the upper letter at c₁, over Y, and the lower letter at c₂, under Z. Rows compare X with Y at c₁, and columns compare X with Z at c₂:

At c₁ ↓ / at c₂ → Z longer X longer equal
X longer than Y impossible square; Y and Z equal impossible
Y longer than X square impossible square
equal square impossible square

The four impossible combinations fail for one reason. For both steps to be free, one of them would have to land strictly inside a letter's interval in the other strip, where no boundary can be. The five squares are each written out in both orders in the proof, and each reaches the same letters, places and words. abac is the square in the top row. X has two rows, so it is longer than Y and longer than Z. Y and Z have one row each, as forced.

A last detail settles the step count. Every square closes with one step on each side, and the closing cycles of case 4 need none. So any two complete paths of free steps have the same length, not only the same end point.

4. How was it checked?

The proof was checked against a program that steps every short column exhaustively. It covers every column over 2 letters up to length 14, and likewise over 3, 4 and 5 letters up to lengths 9, 7 and 6. On each column it follows three random complete paths of free steps. At every state along every path, it takes every ordered pair of free steps available, classifies it by case and kinds, and runs both orders. It checks that the two orders reach the same state. In case 4 it checks instead that one step closes a cycle, and that the two agree up to its rotation.

The results, over 10.7 million ordered pairs. Same state counts the pairs whose two orders reach the same state, and closed cycle the case 4 pairs that agree up to rotation:

Alphabet, longest Pairs Same state Closed cycle (case 4) Exceptions
2 letters, 14 4,322,196 4,042,698 279,498 0
3 letters, 9 3,434,430 3,129,050 305,380 0
4 letters, 7 1,741,700 1,531,570 210,130 0
5 letters, 6 1,164,480 991,358 173,122 0

In every alphabet, the combinations of kinds that occur are exactly the ones the proof allows. Case 2 shows its five squares, and case 3 their mirror images. Case 4 shows only the three combinations that close a cycle. None of the four impossible combinations was ever seen. Rerun for this post, the program gives the same counts.

Before the proof, a separate count had run the free steps to the end under different orders and compared the results directly. No two orders ever disagreed, on 404,677 short columns under ten orders each, or on the 233 Wikidata blocks and four blocks of prose. On every real block the results were equal exactly, with no closed cycle to allow for.

5. What is proved and what is counted

The research record labels each statement as proved by hand, or counted (exact for the data it ran on, but no more). For this result:

  • Proved: free steps in any order reach one end point, up to closed cycles. A program checked every case on 10.7 million pairs of steps.
  • Proved: every complete path of free steps has the same number of steps.
  • Proved: after the free closure, no step adds a letter.
  • Counted, on all 233 Wikidata blocks under three orders: before reaching the closure, free-first orders never held more long words than the closure has letters.
  • Counted, on all 233 Wikidata blocks: the closure leaves 0.185 r letters and takes 0.896 r steps, at the median.

The two counted figures are now properties of each block, so their spread across blocks is a spread across text, not across algorithms. The Wikidata corpus is an extract of a Wikidata dump. Its blocks here are the 233 with at least 65,536 rows, and each figure is divided by that block's own r.

The free closure of each of the 233 Wikidata blocks

Letters left at the free closureblock 145: 0.075 rblock 26: 0.131 rblock 151: 0.131 rblock 27: 0.134 rblock 153: 0.139 rblock 152: 0.140 rblock 36: 0.142 rblock 70: 0.150 rblock 28: 0.150 rblock 147: 0.150 rblock 17: 0.150 rblock 82: 0.154 rblock 84: 0.154 rblock 16: 0.155 rblock 96: 0.156 rblock 197: 0.156 rblock 98: 0.157 rblock 35: 0.157 rblock 100: 0.157 rblock 92: 0.158 rblock 22: 0.158 rblock 138: 0.159 rblock 181: 0.159 rblock 109: 0.159 rblock 106: 0.160 rblock 79: 0.160 rblock 108: 0.160 rblock 116: 0.160 rblock 67: 0.161 rblock 137: 0.161 rblock 192: 0.161 rblock 114: 0.161 rblock 115: 0.162 rblock 103: 0.162 rblock 146: 0.162 rblock 111: 0.162 rblock 10: 0.163 rblock 97: 0.163 rblock 91: 0.164 rblock 105: 0.164 rblock 142: 0.164 rblock 75: 0.165 rblock 101: 0.165 rblock 210: 0.166 rblock 104: 0.166 rblock 62: 0.166 rblock 107: 0.166 rblock 77: 0.166 rblock 99: 0.166 rblock 88: 0.167 rblock 126: 0.167 rblock 95: 0.167 rblock 13: 0.167 rblock 74: 0.167 rblock 139: 0.168 rblock 59: 0.168 rblock 110: 0.168 rblock 193: 0.169 rblock 0: 0.169 rblock 65: 0.169 rblock 112: 0.169 rblock 144: 0.169 rblock 135: 0.169 rblock 172: 0.170 rblock 87: 0.170 rblock 83: 0.170 rblock 148: 0.170 rblock 30: 0.170 rblock 78: 0.171 rblock 60: 0.171 rblock 9: 0.171 rblock 76: 0.172 rblock 150: 0.172 rblock 113: 0.172 rblock 102: 0.172 rblock 6: 0.172 rblock 129: 0.172 rblock 133: 0.172 rblock 187: 0.173 rblock 69: 0.174 rblock 131: 0.174 rblock 72: 0.175 rblock 188: 0.175 rblock 189: 0.175 rblock 125: 0.175 rblock 71: 0.175 rblock 120: 0.176 rblock 228: 0.177 rblock 118: 0.177 rblock 85: 0.178 rblock 11: 0.178 rblock 66: 0.178 rblock 202: 0.178 rblock 80: 0.178 rblock 81: 0.178 rblock 124: 0.178 rblock 199: 0.179 rblock 163: 0.179 rblock 63: 0.179 rblock 25: 0.180 rblock 141: 0.180 rblock 73: 0.180 rblock 159: 0.180 rblock 180: 0.181 rblock 182: 0.182 rblock 157: 0.182 rblock 162: 0.182 rblock 68: 0.182 rblock 132: 0.182 rblock 31: 0.183 rblock 89: 0.183 rblock 168: 0.183 rblock 130: 0.183 rblock 5: 0.183 rblock 184: 0.184 rblock 174: 0.184 rblock 224: 0.185 rblock 175: 0.185 rblock 169: 0.185 rblock 196: 0.185 rblock 117: 0.185 rblock 128: 0.186 rblock 198: 0.186 rblock 216: 0.186 rblock 123: 0.186 rblock 179: 0.187 rblock 58: 0.187 rblock 140: 0.187 rblock 7: 0.187 rblock 61: 0.187 rblock 161: 0.187 rblock 64: 0.188 rblock 229: 0.188 rblock 176: 0.188 rblock 8: 0.188 rblock 33: 0.188 rblock 219: 0.189 rblock 190: 0.189 rblock 173: 0.189 rblock 178: 0.189 rblock 231: 0.190 rblock 14: 0.190 rblock 208: 0.190 rblock 156: 0.190 rblock 217: 0.190 rblock 158: 0.191 rblock 167: 0.191 rblock 32: 0.191 rblock 37: 0.191 rblock 222: 0.191 rblock 226: 0.191 rblock 121: 0.191 rblock 47: 0.192 rblock 136: 0.192 rblock 164: 0.192 rblock 15: 0.192 rblock 194: 0.192 rblock 200: 0.192 rblock 183: 0.192 rblock 154: 0.192 rblock 155: 0.192 rblock 52: 0.193 rblock 227: 0.193 rblock 205: 0.193 rblock 127: 0.193 rblock 39: 0.193 rblock 171: 0.193 rblock 38: 0.194 rblock 185: 0.194 rblock 134: 0.194 rblock 49: 0.194 rblock 48: 0.194 rblock 46: 0.194 rblock 165: 0.194 rblock 160: 0.194 rblock 42: 0.194 rblock 43: 0.195 rblock 53: 0.195 rblock 213: 0.195 rblock 19: 0.195 rblock 122: 0.196 rblock 170: 0.196 rblock 195: 0.196 rblock 12: 0.196 rblock 186: 0.196 rblock 54: 0.196 rblock 209: 0.196 rblock 45: 0.196 rblock 57: 0.196 rblock 221: 0.197 rblock 93: 0.197 rblock 90: 0.197 rblock 215: 0.197 rblock 191: 0.198 rblock 119: 0.198 rblock 166: 0.198 rblock 18: 0.198 rblock 56: 0.198 rblock 149: 0.199 rblock 21: 0.199 rblock 86: 0.200 rblock 207: 0.200 rblock 44: 0.200 rblock 204: 0.200 rblock 4: 0.201 rblock 223: 0.201 rblock 220: 0.202 rblock 211: 0.202 rblock 51: 0.202 rblock 41: 0.202 rblock 225: 0.203 rblock 230: 0.203 rblock 218: 0.203 rblock 1: 0.204 rblock 214: 0.205 rblock 55: 0.206 rblock 232: 0.208 rblock 24: 0.209 rblock 2: 0.209 rblock 94: 0.211 rblock 177: 0.211 rblock 50: 0.212 rblock 201: 0.214 rblock 20: 0.216 rblock 3: 0.220 rblock 40: 0.220 rblock 23: 0.221 rblock 29: 0.225 rblock 143: 0.226 rblock 34: 0.243 rblock 203: 0.251 rblock 212: 0.262 rblock 206: 0.281 r0.050.10.150.20.250.3median 0.185 rletters ÷ the block's runs rFree steps taken to reach itblock 206: 0.794 rblock 212: 0.815 rblock 203: 0.827 rblock 34: 0.833 rblock 29: 0.852 rblock 143: 0.853 rblock 40: 0.854 rblock 3: 0.856 rblock 23: 0.856 rblock 50: 0.862 rblock 94: 0.862 rblock 55: 0.865 rblock 20: 0.866 rblock 201: 0.869 rblock 177: 0.869 rblock 232: 0.870 rblock 214: 0.870 rblock 41: 0.870 rblock 24: 0.871 rblock 51: 0.872 rblock 44: 0.873 rblock 2: 0.873 rblock 56: 0.874 rblock 220: 0.875 rblock 1: 0.875 rblock 218: 0.875 rblock 45: 0.876 rblock 42: 0.877 rblock 149: 0.877 rblock 54: 0.877 rblock 21: 0.877 rblock 225: 0.877 rblock 204: 0.877 rblock 230: 0.877 rblock 57: 0.877 rblock 48: 0.878 rblock 43: 0.878 rblock 53: 0.878 rblock 39: 0.878 rblock 46: 0.879 rblock 52: 0.879 rblock 38: 0.879 rblock 209: 0.879 rblock 166: 0.879 rblock 49: 0.880 rblock 223: 0.880 rblock 93: 0.880 rblock 90: 0.881 rblock 86: 0.881 rblock 211: 0.881 rblock 215: 0.882 rblock 37: 0.882 rblock 213: 0.882 rblock 47: 0.882 rblock 160: 0.883 rblock 4: 0.883 rblock 170: 0.883 rblock 18: 0.884 rblock 165: 0.884 rblock 191: 0.884 rblock 12: 0.885 rblock 221: 0.885 rblock 164: 0.885 rblock 227: 0.885 rblock 122: 0.886 rblock 205: 0.886 rblock 195: 0.886 rblock 217: 0.886 rblock 207: 0.887 rblock 155: 0.887 rblock 119: 0.887 rblock 185: 0.887 rblock 226: 0.888 rblock 167: 0.888 rblock 134: 0.888 rblock 171: 0.888 rblock 219: 0.888 rblock 154: 0.888 rblock 121: 0.889 rblock 32: 0.889 rblock 194: 0.889 rblock 186: 0.889 rblock 231: 0.890 rblock 158: 0.890 rblock 19: 0.890 rblock 156: 0.890 rblock 33: 0.890 rblock 229: 0.890 rblock 173: 0.891 rblock 200: 0.891 rblock 216: 0.891 rblock 8: 0.891 rblock 222: 0.891 rblock 208: 0.892 rblock 136: 0.892 rblock 183: 0.892 rblock 161: 0.892 rblock 14: 0.892 rblock 178: 0.893 rblock 169: 0.893 rblock 140: 0.893 rblock 127: 0.893 rblock 117: 0.893 rblock 190: 0.893 rblock 176: 0.894 rblock 179: 0.894 rblock 31: 0.894 rblock 15: 0.894 rblock 224: 0.895 rblock 58: 0.895 rblock 198: 0.895 rblock 174: 0.896 rblock 64: 0.896 rblock 184: 0.896 rblock 157: 0.896 rblock 175: 0.896 rblock 61: 0.896 rblock 123: 0.897 rblock 128: 0.897 rblock 7: 0.897 rblock 162: 0.898 rblock 25: 0.898 rblock 159: 0.898 rblock 196: 0.898 rblock 168: 0.898 rblock 89: 0.898 rblock 5: 0.899 rblock 132: 0.900 rblock 113: 0.900 rblock 130: 0.900 rblock 163: 0.901 rblock 182: 0.902 rblock 228: 0.902 rblock 199: 0.902 rblock 68: 0.902 rblock 85: 0.903 rblock 180: 0.903 rblock 148: 0.903 rblock 141: 0.903 rblock 202: 0.903 rblock 73: 0.904 rblock 80: 0.905 rblock 102: 0.905 rblock 81: 0.905 rblock 95: 0.906 rblock 124: 0.906 rblock 66: 0.906 rblock 110: 0.906 rblock 30: 0.907 rblock 63: 0.907 rblock 11: 0.908 rblock 71: 0.908 rblock 189: 0.908 rblock 131: 0.908 rblock 112: 0.909 rblock 107: 0.909 rblock 104: 0.909 rblock 118: 0.909 rblock 188: 0.909 rblock 187: 0.909 rblock 133: 0.910 rblock 99: 0.911 rblock 72: 0.911 rblock 150: 0.911 rblock 120: 0.911 rblock 6: 0.912 rblock 87: 0.912 rblock 101: 0.912 rblock 144: 0.912 rblock 69: 0.912 rblock 105: 0.912 rblock 83: 0.912 rblock 129: 0.913 rblock 125: 0.913 rblock 103: 0.913 rblock 172: 0.914 rblock 114: 0.914 rblock 193: 0.914 rblock 0: 0.914 rblock 9: 0.914 rblock 78: 0.915 rblock 142: 0.915 rblock 97: 0.915 rblock 135: 0.915 rblock 88: 0.915 rblock 126: 0.916 rblock 59: 0.916 rblock 60: 0.916 rblock 76: 0.916 rblock 111: 0.916 rblock 139: 0.917 rblock 77: 0.917 rblock 210: 0.917 rblock 108: 0.917 rblock 115: 0.918 rblock 65: 0.918 rblock 106: 0.918 rblock 74: 0.919 rblock 116: 0.919 rblock 109: 0.919 rblock 100: 0.920 rblock 13: 0.920 rblock 75: 0.920 rblock 62: 0.921 rblock 98: 0.922 rblock 96: 0.922 rblock 146: 0.922 rblock 91: 0.923 rblock 192: 0.923 rblock 10: 0.923 rblock 35: 0.925 rblock 138: 0.925 rblock 67: 0.925 rblock 181: 0.925 rblock 92: 0.925 rblock 79: 0.926 rblock 137: 0.926 rblock 22: 0.928 rblock 197: 0.930 rblock 16: 0.930 rblock 84: 0.931 rblock 147: 0.932 rblock 153: 0.932 rblock 82: 0.932 rblock 28: 0.932 rblock 70: 0.936 rblock 17: 0.937 rblock 152: 0.939 rblock 36: 0.940 rblock 27: 0.950 rblock 26: 0.952 rblock 151: 0.960 rblock 145: 0.994 r0.750.80.850.90.951median 0.896 rsteps ÷ the block's runs r
Counted, not timed. Each dot is one block, stacked where values coincide; hover a dot for its block and value. Upper: letters left when no free step remains, as a share of the block’s runs, from 0.075 r to 0.281 r. Lower: the free steps taken to get there, from 0.79 r to 0.99 r. Each block gave the same two numbers under every order tried, as the theorem says it must.

6. What could a decoder do with it?

Everything in this section is a consequence of the theorem, not a measurement.

Any order is correct. The cost of a free-first decoder is in finding its free steps. It needs a worklist of ready steps. An earlier count priced that worklist at about 150 instructions a run on one thread, against 115 for Cells' sweep from the right-hand end. The theorem says a decoder may take its free steps in whatever order its worklist yields them: a stack, a sweep, or batches. The end point, the step count and the bound on width hold for all of them. So a worklist can be designed for speed alone.

Splitting one block between threads. Two free steps on different letters commute. So free steps can be handed to different threads, and they reach the same state as on one thread. The condition is that each thread's step writes only its own two letters' records. That is a way to split one block's rebuild that is proved correct, which matters for how mibz2 uses many cores. It decodes blocks in parallel either with each thread on a block of its own, or with teams of threads sharing a block. On a 10-core Intel desktop at ten threads, a block per thread took 1.040 times the teams' wall time in the latest run. Its 95% interval is 1.019 to 1.061 (the run's report). The working explanation, not yet measured directly, is that each thread's live state competes for the shared cache. A smaller live state, and a proved way to share one block's free steps, both bear on that.

A bound fixed by the block. After the closure, no step adds a letter. So from the closure on, a decoder that takes free steps first never needs more live letters than the closure has. That is about 0.19 r on Wikidata, against the r slots Cells reserves today. Before the closure, the bound held on every block counted.

No free-first decoder has been built. A first decoder that keeps the untouched one-byte letters implicit, and writes a letter only when its word first grows, has been built with Cells' right-end order and is being measured. None of it has been timed yet.

7. What is still open?

Which steps does the closure leave? Only equal steps remove letters, and a block's rebuild makes exactly r − 1 of them. So the closure's letter count is 1 plus the number of equal steps that can only become ready after a paid step. Saying which equal steps those are, from the block's runs, would describe the closure without running it. That is the next question.

One block on many cores, by rounds. A different route also reaches the end of a rebuild: repeatedly cut the map down to the rows where runs branch, all at once. It collapses a whole Wikidata block to between 2 and 560 letters in 5 to 18 such rounds, and the work within a round is independent. Cells' right-end order, by contrast, has a chain of 93 dependent rounds at the median. As counted, though, each round walks every row it removes, so its work grows with the rows rather than the runs, which is the cost Cells exists to avoid. Whether a round can be computed on letters and their words alone has not been tested.

Is width a cutwidth? The width post links width to the cutwidth of a graph: line up its vertices, cut between any two, and count the edges that cross. Whether the width of a rebuild is exactly a cutwidth of the block's cycle of rows, bundled by runs, is a conjecture.

The record of the rounds count is #440.


Research records: