Jul 12, 2026 · Accepted · result-transfer-shape

Experiment 225: 12-bit LUT for json_write_base64

Date: 2026-07-12

Status: Accepted

Direction:result-transfer-shape

Benchmark Run: none — focused

benchmark/experiments/select_bytes_blob_base64.dart;

three order-flipped passes recorded in

benchmark/results/2026-07-12T11-16-37Z-exp225-base64-lut12.md.

No release-suite run because no current release lane isolates BLOB base64

encoding wall time — the focused harness is the durable gate.

Problem

The BLOB arm of write_json_to_buf calls

json_write_base64 once per BLOB cell. On a 4 KB

BLOB that inner loop encodes ≈ 1,365 24-bit triplets per cell; on a 10k × 4 ×

128 B row set it emits ≈ 1.7 million triplets per query.

Per triplet the current encoder does:

 *out++ = b64_table[(v >> 18) & 0x3F]; *out++ = b64_table[(v >> 12) & 0x3F]; *out++ = b64_table[(v >>  6) & 0x3F]; *out++ = b64_table[ v        & 0x3F]; 

Four 6-bit table lookups and four 8-bit stores. Loop control was collapsed by

exp 216 (4×-unrolled outer loop) and

exp 218 confirmed a wider unroll no longer helps —

the ceiling is not loop-control, it is per-triplet work. signals.json

records that future BLOB work needs a different mechanism, not another

scalar-unroll variant.

Hypothesis

Widening the lookup table from 6 bits to 12 bits collapses the four

per-triplet accesses into two. Each 12-bit LUT entry stores two encoded

base64 chars, so one triplet becomes:

 unsigned int v = ((data[i] << 16) | (data[i+1] << 8) | data[i+2]); memcpy(out,     b64_pair_table[(v >> 12) & 0xFFF], 2); memcpy(out + 2, b64_pair_table[ v        & 0xFFF], 2); out += 4; 

Two 2-byte loads + two 2-byte stores instead of four 1-byte loads + four

1-byte stores. The output is bit-identical to the current encoder — the

table is derived from the same b64_table[] string — so no correctness

change is possible on the fast path. Table cost is 4,096 × 2 B = 8 KiB in

.bss, sitting beside the 64-byte scalar table which is still used by the

1–2 byte padded tail.

Accept if the two medium/large BLOB lanes (4 × 128 B and 2 × 4 KB) reproduce

≥ 3 % candidate-faster across an order-flipped pair. Reject if the 3 B

tiny-cell guards reproduce a ≥ 2 % regression (only the padded tail runs

there — the LUT should not touch them) or if the 4 KB lane flips sign

across the pair.

Approach

Only native/resqlite.c changes:

• Add static unsigned char b64_pair_table[4096][2] (8 KiB .bss).

Each row holds the two base64 chars for the 12-bit index — [0] from

bits 11–6, [1] from bits 5–0. Byte-array (not uint16_t) so the write

order is byte-order independent.

• Add init_b64_pair_table() that fills the table from the existing

b64_table string, and a one-time flag b64_pair_table_initialized.

• Guard the first call: json_write_base64 runs init_b64_pair_table()

under RESQLITE_UNLIKELY(!b64_pair_table_initialized). Every subsequent

call takes a perfectly-predicted no-op branch.

• Rewrite RESQLITE_WRITE_B64_TRIPLET to use the pair table. Exp 216's

4×-unrolled outer loop and the singleton i <= len - 3 loop stay

intact — they now dispatch through the shorter body. The 1/2-byte

padded tail still uses the scalar b64_table (only 3–4 output bytes

per query max; not worth a special case).

Correctness rests on b64_pair_table[i] being defined as

{b64_table[(i>>6)&0x3F], b64_table[i&0x3F]} — the two halves of the

existing lookup, in the same order the old encoder wrote them. The

selectBytes encodes blobs as base64 test and every other database and

stream test passes on the candidate.

Results

Full raw tables:

benchmark/results/2026-07-12T11-16-37Z-exp225-base64-lut12.md.

Decision-relevant medians in microseconds per query:

The two decision lanes — 4 × 128 B (≈ 1.7 M triplets per query) and 2 × 4 KB

(≈ 2.7 M triplets per query) — reproduce ≥ 17 % candidate-faster across all

three passes, roughly 1.3–1.5× faster BLOB base64 encoding for medium

and large payloads. The 4 KB baseline drifted between 4,201 and 4,487 µs

across passes while the candidate held at 3,056–3,086 µs, so the delta size

varies with baseline drift but the sign is stable.

The 3 B and 3 B × 20 lanes (single-triplet cells with no unrolled iterations)

stay inside the noise floor across all three passes — the LUT changes the

inner body they hit, but per-cell wall is dominated by other per-call cost

(JSON row framing, buf capacity checks, cell dispatch), so the encoder

saving is invisible there. The mixed lane trends candidate-faster on 2/3

passes but stays within ±5 %; only ~1/8 of its cells are BLOBs, and half the

BLOB payload lives in single-triplet cells.

Decision

Accepted. Medium and large selectBytes() BLOB workloads encode

~1.3–1.5× faster with no observable regression on tiny-BLOB guards or the

mixed row shape. The 8 KiB .bss table has no per-call cost after the

first json_write_base64 invocation.

The result was the mechanism-change signals.json named as the requirement

for further BLOB work after exp 218 closed loop-unroll variants. Future

BLOB encode experiments in this direction should try a different mechanism

again (SIMD _mm_shuffle_epi8, base64 SIMD kernels, or a compiler-flag

change), not a wider LUT — the byte body itself is now two lookups per

four output bytes, which is at or below the memcpy cost.

The prototype ships on the branch; there is no archive tag because the

candidate is the merged form. The 1/2-byte padded tail intentionally stays

on the scalar b64_table: at most 3–4 output bytes per query max, well

below the extra branch it would take to route through the pair table

correctly.

Validation

• dart analyze --fatal-infos native/resqlite.c lib/ test/database_test.dart
• dart test test/database_test.dart -j 1 (53/53 pass, including

Database selectBytes encodes blobs as base64, `preserves embedded-NUL

text, and the selectBytes matches jsonEncode of select` round-trip)

• Three order-flipped focused A/B passes of

benchmark/experiments/select_bytes_blob_base64.dart

• git diff --check