Knowing Which Blocks Not to Open — Full Spectrum Part 3: 0.17s Against ripgrep’s 0.31s on a Plain Search, and 4% Slower for Words That Live in Every Block

Cut 3 GB of OpenStreetMap XML into 1 MB blocks and you get 2,893 of them. The word I was looking for appeared in 910.

The other 69% did not need to be opened. The trouble is that you normally learn this after opening them. What does a block have to carry so the decision can be made before it is read? And how big should a block be in the first place? Those are the two questions in this part.

The short version: 0.17 s against ripgrep’s 0.31 s on the second query, 1.67x to 2.61x with marks on versus off, and 0.96x for words that appear everywhere

Every block of a .uwvz (UwView Pro’s compression format plus index) now carries a summary of the three-byte sequences that occur inside it. I call it the block’s marks. The table is 1/512 of the block (2 KB for a 1 MB block). Split the search term into three-byte windows, check the table, and if even one window is missing, the term cannot be in that block. A set bit can be a coincidence, so blocks that pass are still opened and checked. The mechanism only ever works in the direction of skipping.

In the same release the block size changed from 4 MB to 1 MB. That change and the marks belong together, for a reason I will get to.

In the v1.9.0 suite (Mac, 3 GB, plain search, 11,274 matching lines) the second query took 0.17 s against ripgrep’s 0.31 s — 1.82x. Isolating the mechanism by turning marks off and on gives 1.67x, 2.17x and 2.61x for 東京, 大阪 and 札幌 — three city names of decreasing frequency.

Now the losses. Words that occur in every block gain nothing. highway and k="name" land at 0.96x — level (anything under 1.5x I call level), marginally slower with marks on, because checking the table is pure overhead there. The first pass is slower: with the index being built, uvp‘s cold time was 4.35 s against ripgrep’s 3.27 s (1.33x, still level). And a background process building the marks competed with the next query, pushing a 10 GB second query from 0.92 s to 1.70 s until the child was demoted in the OS scheduler.

uvf and uvp are the search commands of UwView, which I build (uvf is the free edition, uvp is UwView Pro). The figures here were measured on v1.9.0 “Full Spectrum” (released 14 October 2026, build 26.10.13.22) on a Mac (Apple M4, 10 cores, 32 GB of memory, external USB SSD) on 13 October 2026. The marks on/off ratios come from development build 1.8.3.4. v1.9 carries the pet name “Full Spectrum” because it brings Shift_JIS, EUC-JP and UTF-16 files into the index as UTF-8, so encoding and file type no longer change how fast a search runs.

The problem: narrowing the range still told me nothing about a single block

From the second query onward uvp reads the .uwvz rather than the original file. It knows which byte each line number starts at, so one pass produces numbered results (more on that single pass here).

What it did not have was a reason to leave a block closed. Once the range was settled, every block in it was decompressed and scanned as raw bytes. A word matching fewer than one line in a thousand still cost every block. Decompression runs at roughly 0.44 ms per megabyte, so the number of blocks opened is the runtime.

The goal is narrow: be able to say “the answer is not in here” before opening. Only one direction of error is acceptable. Saying “it might be here” when it is not costs a wasted read. Saying “it is not here” when it is silently drops results.

The idea: fold three-byte sequences into a small per-block table

A list of words would not work as a summary. Tokenising needs structure, and the vocabulary of a large log or XML file has no bound worth planning around. So the summary throws away position and frequency and keeps only whether a three-byte sequence occurred.

• Each run of three bytes a b c is folded through (a<<16 | b<<8 | c) * 0x9E3779B1 and the top bits index a bit in the table.
• ASCII upper case is folded to lower case before setting the bit, so a case-insensitive search can use the same table.
• The table is 1/512 of the block (2 KB for 1 MB, 8 KB for 4 MB).

A search splits its term into three-byte windows and tests them. Marks are used for:

• plain strings, case-insensitive ones included, and the required literal extracted from a case-sensitive regular expression (how that extraction works) — in both cases only when the literal is at least three bytes long;
• and not for inverted matches (-v) or case-insensitive regular expressions. An inverted match cannot skip a block for containing something; that case is handled by the line skeleton from the previous part.

Case-insensitive matching needed one piece of care. .NET’s case-insensitive comparison treats k as equal to the Kelvin sign (U+212A) and s as equal to ſ (U+017F) (the trap, in detail). So the literal is cut at every k and s, and only the remaining runs are used as evidence.

64 bytes either side of a boundary — the bug that opened 612 of 724 blocks

The first implementation was wrong about lines that straddle a block boundary. The last line of a block continues into the next one, and to check that line the code consulted the next block’s table. A term occurring anywhere in that next block was enough to pass, so a search over 3 GB opened 612 of 724 blocks when only 466 actually contained the word.

The fix was to keep raw bytes instead of a summary: 64 bytes either side of each boundary, stored per block, so a straddling line is checked against the actual text. After the fix the count was 482 (4 MB blocks, 8 KB table). I rebuilt the same marks independently in Python and confirmed the counts fell as predicted, down to 474 with a 32 KB table.

From 4 MB blocks to 1 MB — marks alone did not get there

With marks on and 4 MB blocks, 東京 came out at 1.13x, which is level. The arithmetic explains it. Of 724 blocks, 466 (64.4%) genuinely contain the word, so perfect marks could skip 35.6% and the ceiling is about 1.55x.

Smaller blocks lower that ratio. At 1 MB it is 910 of 2,893 (31%), and for 札幌 181 (6.3%).

A bigger table reduces false positives, but the returns collapse immediately. The true count at 4 MB is 466; an 8 KB table gives 482, 16 KB gives 475, 32 KB gives 474. At 1 MB, 2 KB gives 910 and 4 KB gives 893. Four times the storage buys one or two percent, so 1/512 is where it stopped.

Smaller blocks barely change the archive itself (251.8 MB to 252.4 MB, +0.22% on 3 GB). Comparing 1 MB against 4 MB across 15 suite items with marks disabled, only two got slower — -seq by 2% and -tail by 4%, both inside 5%. With marks on, 1 MB (2 KB table) is faster than or equal to 4 MB (8 KB table) everywhere: 1.56x, 1.77x and 1.66x on three items, 1.00x to 1.09x on the rest.

Numbers: against ripgrep (v1.9.0 suite, 3 GB)

The comparison is ripgrep 15.2.0, with identical queries and match counts verified. Cold runs follow a cache purge and a 10-second wait; hot runs immediately after. uvp‘s cold time is measured with the .uwvz deleted first, so it includes building the index.

• The second query is 1.82x. Marks keep 1,983 of the 2,893 blocks closed, so under a third of the data is decompressed.
• The first pass favours ripgrep (3.27 s against 4.35 s, 1.33x, level) because the index is built in it. The free edition, which builds no index, came in at 3.06 s cold and 0.29 s hot — within 7% of ripgrep both ways.
• The harness raised no cache warning on this item: ripgrep’s 3.27 s cold against 0.31 s hot shows the cache working as intended.

Numbers: marks off against marks on

UVP_MARKS=0 searches the same .uwvz without using the marks. The table below is development build 1.8.3.4, since the v1.9.0 suite has no marks-disabled condition. 3 GB, hot cache, median of three runs, output discarded to /dev/null.

There are two groups. Terms whose matches are clustered (東京, 大阪, 札幌, Main St) gain 1.67x to 2.61x at 1 MB. Terms present in every block sit at 0.96x, marginally slower with marks on. 札幌 already gained 2.35x at 4 MB because even 4 MB blocks held it in only 121 of 724. The size of the win is a property of the data’s skew, not of the implementation.

Losses: words that are everywhere, the cold pass, and a background process stealing CPU

1. Words in every block cost 4%. For highway and k="name" nothing can be skipped, so reading and checking the table is pure overhead. At 0.96x this is level, but it is not an improvement. Measured against the previous default — 4 MB blocks with no marks — the same queries did improve, 0.336 s to 0.315 s, purely from the smaller blocks. Being cheap when it fails is what makes a mechanism safe to enable by default.

2. The cold pass does not get faster. Building the index costs what it costs. On top of that, reading the new sections with 1 MB blocks made the cold runs of the case-insensitive, regular-expression and aggregate items on 10 GB 0.15 to 0.2 s slower. The fix reads the mark tables in 8 MB runs instead of block by block and loads the skeleton and mark sections only for queries that use them — but purging the cache needs sudo, so the re-measurement is still pending and will be done in the next full suite run.

3. A background process competed with the next query. Marks and skeleton are built by a separate process after the search finishes. Measuring a 10 GB second query immediately after the first pushed it from 0.92 s to 1.70 s. The fix was to demote the child in the OS scheduler (taskpolicy -b on macOS, nice 19 plus ionice -c 3 on Linux, Idle priority on Windows). On 3 GB a second query that runs while the build is in progress now takes 0.305 s, against 0.291 s with nothing else running, and the build can use every thread without getting in the way, finishing in 27 seconds (restricting it to two threads took 54). The GUI’s background thread cannot be demoted the same way, so it stays capped at a quarter of the cores.

4. Storage grows. The .uwvz itself grows 0.22%, but the skeleton and marks live in a sibling .uwvz.x — 21.6 MB on 3 GB (15.5 MB skeleton plus 6.1 MB marks), which is +8.8% over the previous 4 MB archive, or +2.4% for the marks alone. Compact storage is part of what this tool sells, so the number belongs in the open.

Correctness: byte-identical output across 15 queries, and the archive never changes

A mechanism that decides not to read something will drop answers silently if the decision is ever wrong.

• Byte-identical output: marks on against marks off, across 15 queries (plain strings, case-insensitive, regular expressions, alternation, $, -w), with terms deliberately straddling block boundaries, lines over 64 KB and mixed CRLF. Both output paths were checked — streaming while scanning, and collecting first (--csv).
• Independent rebuild: the same marks were rebuilt in Python and the resulting block counts matched the predictions.
• The original index is untouched: marks go into the sibling .uwvz.x, and the .uwvz was verified byte-for-byte unchanged. Searching the same archive while the build is running returns identical results (checked three times concurrently), and an interrupted build leaves nothing that blocks the next one. A .uwvz.x whose validation key (original length, block size and count, hash of the block table) does not match is ignored.
• Test suite: 1,054 core tests, 372 GUI tests and 167 editor tests passed.

The general lesson: check the chunk size before improving the summary

A summary that can say “not here” is a broadly useful tool. Building one, there seem to be three things worth thinking about.

Granularity decides the outcome. The same marks give 1.13x at 4 MB and 1.67x at 1 MB. Revisiting the chunk size can beat improving the summary, and the ceiling is computable in advance: the fraction of chunks that genuinely contain the answer gives you the best a perfect summary could do (64.4% at 4 MB, so about 1.55x). That estimate is available before writing any code.

Count what the trade is paid in. Quadrupling the table removes one or two percent of the false positives. Shrinking the chunks raises the skip rate but fragments reads and slows the first pass, which then had to be clawed back with batched reads. Both knobs work; both charge somewhere else.

Measure the cost of failing first. For words that appear everywhere this mechanism is useless. It can still ship enabled by default because being useless costs 4%. The worst case when it does nothing matters more than the best case when it works for deciding whether something can be a default.

How to write it with uvp

uvp japan.osm 東京                        # plain search, where marks help
uvp japan.osm 'Main St' -i                # marks are used case-insensitively (cut at k and s)
uvp japan.osm '="' -v                     # inverted match: marks are not used
uvp japan.osm.uwvz --build-extra          # add the skeleton and marks to an existing .uwvz
uvp japan.osm.uwvz --extra-status         # check whether the sections exist or are being built
UVP_MARKS=0 uvp japan.osm 東京            # neither build nor use marks (verification, benchmarking)
UVP_EXTRA=sync uvp japan.osm 東京         # build in-process and report how long it took
UVP_EXTRA=0 uvp japan.osm 東京            # build and use neither skeleton nor marks
uvf japan.osm 東京                        # the free edition builds no index and reads each time

Block size is set with UVP_BLOCK_SIZE and the mark table size with UVP_MARK_BYTES (both for measurement). Exit codes follow grep: 0 for matches, 1 for none, 2 for an error or an incomplete result. The free edition is on GitHub Releases (brew install --cask amru195704/uwview/uwview on macOS, Scoop on Windows, Snap on Linux).

Links

• Full Spectrum Part 1 — bringing Shift-JIS, EUC-JP and UTF-16 into the index as UTF-8: https://uvp.y42u.net/en/blog/uwview-fs01-sjis-utf8-index-en/
• The v1.9.0 “Full Spectrum” release post (what the whole version changed): https://uvp.y42u.net/en/blog/uwview-v190-full-spectrum-en/
• Extracting a required literal from a regular expression: https://uvp.y42u.net/en/blog/uwview-fl04-regex-required-literal-en/
• Why case-insensitive matching has to think about the Kelvin sign: https://uvp.y42u.net/en/blog/uwview-fl03-ignorecase-u212a-en/
• Producing numbered results in a single pass over the file: https://uvp.y42u.net/en/blog/uwview-fl02-one-pass-rawgrep-en/
• Where ripgrep wins, collected in one place: https://uvp.y42u.net/en/blog/uwview-wf14-where-ripgrep-wins-en/
• The newline counting that took 40% of the second query: https://uvp.y42u.net/en/blog/uwview-wf12-newline-hot-en/
• The previous series, wrapped up (multiple files, seven compression formats, zip, pbf): https://uvp.y42u.net/en/blog/uwview-wf15-wide-field-recap-en/
• Every measurement, in one table: https://uvp.y42u.net/en/benchmarks-en/
• Source code on GitHub: https://github.com/amru195704/UwView

And if you keep searching the same huge logs for the same handful of terms, UwView Pro makes the second query a step faster — a persistent index, search inside the compressed cache, and roughly a ninth of the storage (every OS, one-time purchase or monthly subscription, 14-day free trial; see the pricing page).

From the developer: my apps, Kindle books and public projects are listed at GitHub: amru195704.