Re: Improve the performance of Unicode Normalization Forms.

Hi hackers,

While reviewing this patch I looked into its effect on frontend
(libpq) size, and ended up laying out four ways the tables could
be arranged -- including options that bring the frontend back to,
or below, baseline size. Even if the current direction is right,
I wanted these on record, so the community isn't later left
wondering about "The Road Not Taken" -- with a nod to Frost. This
is purely an architect's-eye summary of structures and sizes; the
implementation and the decision are the author's and the
committer's.

Whichever road is taken below, two points hold. The OOB fix is a
hard requirement, assumed throughout. And while
the patch applies SHIFT=6 to both two-stage tables, the size-optimal
shift differs per table (decomposition 5, inverse 6); adopting that
mixed shift is a small, construction-independent size win I would
recommend as a baseline either way -- the figures below already use
it.

----------------------------------------------------------------------

Unicode normalization: current tables, a frontend compression
option, and four patch constructions
======================================================================

Premise: the backend keeps the unified two-stage table. This is
about the frontend (libpq) only, where normalization is reached
solely through SCRAM, so size matters more than speed. All figures
are static array bytes at the size-optimal shifts (decomposition
SHIFT=5, inverse SHIFT=6); baseline frontend is 75,576 and the patch
is 104,242.

1. Current data structures

The generated header holds nine arrays and three lookup functions.

Decomposition data:
UnicodeDecompMain[3957] (4B struct): decomposition entries,
each {comb_class, dec_size_flags, dec_index}.
UnicodeDecompCodepoints[4596] uint32: multi-codepoint
decomposition sequences.
UnicodeDecompSizes[4596] uint8: compatibility decomposition
length when it differs from the canonical one.

Recomposition data:
UnicodeDecompInverseCodes[962] uint32: composed results.
UnicodeDecompInverseSecond[6208] uint16: per first-codepoint
records, each [start_hi, start_lo, span, code_idx x (span+1)],
mapping a second codepoint in [start, start+span] to an
InverseCodes index.

Forward two-stage lookup (codepoint -> DecompMain index):
decomp_table_offset[6098] uint16
decomp_table_index[13248] uint16

Inverse two-stage lookup (first codepoint -> InverseSecond index):
inverse_table_offset[1463] uint16
inverse_table_index[3776] uint16

Lookup functions:
normalization_index(cp) -- forward two-stage
inverse_index(cp) -- inverse two-stage
normalization_inverse(first, second) -- recomposition:
inverse_index(first) gives an InverseSecond record, then the
second codepoint indexes into it for an InverseCodes result.

A two-stage lookup splits the key: offset[cp >> SHIFT] is where that
page begins in the index array, and index[offset + (cp & mask)] is
the value. Unmapped pages all share one dummy page, so most offset
entries point there -- which is why these tables are mostly empty
(exploited in section 3).

2. What the patch changes (architecture)

The patch reworks the lookup tables. The decomposition entry drops
its codepoint (8B -> 4B), which also lets entries with identical
contents merge. But once the codepoint is gone from the entry, the
two mappings it used to provide -- "codepoint -> entry" and
"pair -> composed" -- must be rebuilt as the explicit two-stage
tables above. The frontend and backend now share them; before this
patch the frontend used bsearch plus a scan and linked no lookup
table at all.

- Backend: a net win. Total tables -4.2%, and no slower: on the
thread, differences between lookup encodings (table vs branch,
big vs small table) were only 1-7%, so changing the encoding
does not move backend speed much.

- Frontend: +28,666 B (+37.9%). The data shrinks by 36,768 B
(the 4B entry plus dedup), but 65,434 B of forward and inverse
lookup tables plus the recomposition tables are added -- tables
baseline did not link at all, since it kept the codepoint and
used bsearch plus a scan. The two together net +28,666 B.

So the frontend cost is the lookup and recomposition tables that
exist only because the codepoint was removed, linked into a path
where speed is irrelevant. That makes the frontend purely a size
question.

3. A frontend high-compression alternative

The frontend can link a succinct form of the same tables, without
touching the backend or the 4B struct. As noted in section 1 the
tables are mostly empty -- the offset arrays are 93% dummy, and the
InverseSecond code_idx slots are 80% zero -- so store only the
non-empty entries:

- each offset array -> a rank/select bitmap: one present bit per
block plus a per-word rank cache. The non-zero ordinals are
1,2,3,... in order, so ordinal = rank + 1 (no value array).
- each index array and the InverseSecond records -> bitfield +
dense: a mask marks the non-empty slots, and only their values
are stored, each minus a base (per page for index, per record
for recomposition).

The decision needs only the resulting size below; the mechanism is
sketched for the curious and worked in full in Appendix A, so it is
safe to skim past it without stopping here. The struct stays 4B and
shared; only the three lookup functions differ, behind #ifdef
FRONTEND.

- Frontend 64,132 B: -11,444 vs baseline, -40,110 vs the patch.
The frontend surplus turns negative -- libpq ends up below
baseline.
- Lookup is the heaviest (rank/select + several popcounts). That
is fine where speed is irrelevant, but a bsearch-vs-this speed
comparison is worth showing before adopting it.

This is the most aggressive frontend option; it is what makes
"keep the backend two-stage, compress only the frontend" reach a
size below baseline.

4. Four patch constructions

Option 1 -- As-is (the patch)
Frontend and backend share the unified two-stage table.
Frontend 104,242 B. Lookup simple (one branch, two arrays).
Single code path. Current form (plus the OOB fix).
Policy: prioritize a single code path; accept +28.7 KB in libpq.

Option 2 -- Restore the codepoint
Keep the codepoint in the entry (both sides, 8B), as before this
patch. Then the frontend needs no lookup table: bsearch
forward, recomposition by scanning the same table.
Frontend 75,576 B (= baseline). Backend data +~39 KB (8B entry,
dedup lost), but the backend is one binary where size matters
less. One data table, one struct; only the lookup differs.
Policy: keep libpq at baseline on one data table; pay with a
larger backend data table. This is the pre-patch structure.

Option 3 -- Dual table (#ifdef)
Backend as in the patch (4B + two-stage); frontend baseline
(8B + bsearch); struct and lookup split by #ifdef FRONTEND.
Frontend 75,576 B. Backend small. Generator emits both.
Policy: keep libpq AND the backend small, at the cost of a dual
struct/lookup.

Option 4 -- Frontend high compression (section 3)
Backend as in the patch; frontend the succinct form; struct 4B
shared, lookup split by #ifdef.
Frontend 64,132 B (below baseline). Lookup heaviest.
Policy: push libpq below baseline, accepting a complex but
frontend-only lookup.

5. Comparison

Option Frontend Backend Lookup(front) Dual?
1 As-is (patch) 104,242 two-stage simple no
2 Restore codepoint 75,576 +39KB data bsearch no
3 Dual table 75,576 small bsearch yes
4 Frontend compress 64,132 two-stage rank/select lookup

In short: option 1 (the patch) is a net loss for the frontend --
the tables grow +28.7 KB, about 1% of libpq -- while the size gain
is on the backend. Whether even that 1% matters on modern servers,
let alone embedded or mobile, is open to doubt; this much memory is
arguably negligible today, so on size grounds option 1 may well be
enough -- which then turns on re-measuring the backend performance
win. If a frontend size win is wanted anyway, options 2/3/4 provide
it -- 2 and 3 at baseline size with a simple bsearch, 4 below
baseline with a complex lookup -- but the shared price is
complexity: a dual struct/lookup, or a complex lookup.

6. Recommendation

The premise is a backend performance win: common to all four
options (all keep the two-stage table), but it must be established
by a clear re-measurement before commit. The frontend is the SCRAM
authentication path, where size and stability -- not speed -- carry
weight, so the choice there comes in two steps.

The first choice is between options 1 and 3. If the frontend size
cost is deemed negligible today, option 1 (the patch, a single
path) is enough. If returning the frontend to baseline size is
preferred, adopt option 3 (simple bsearch, small backend) first.

If option 3 is taken and the frontend compression is confirmed to
cost no performance, option 4 can follow, pushing size below
baseline -- at the cost of a maintainability trade-off in its
complex lookup. (Option 2 also returns the frontend to baseline
but enlarges the backend data, so it loses to option 3, whose
backend stays small.)

The frontend choice is a balance of size against lookup simplicity
and maintainability; the final choice is the committer's, and the
four constructions above are laid out to make it easier.

----------------------------------------------------------------------

Appendix A. Worked compression examples

Small illustrations of the three transforms in section 3. Bit b of
a mask corresponds to slot/block b (bit 0 is lowest).

A.1 offset array -> rank/select bitmap

Suppose the offset array maps 8 blocks to page ordinals, mostly
dummy:

ordinal = [0, 0, 1, 0, 2, 0, 0, 3] (blocks 2,4,7 -> 1,2,3)

Store instead:

present = bits {2,4,7} set (one bit per block)
rank = per-word prefix count (one word here, rank[0]=0)

Pages are laid out in block order, so the k-th non-zero block gets
ordinal k+1; the ordinals run 1,2,3,... in sequence and need not be
stored -- ordinal = rank + 1.

Lookup of block 4:
present bit 4 is set -> not dummy
rank = rank[word] + popcount(present below bit 4) = 0 + 1 = 1
ordinal = rank + 1 = 2
Block 3: present bit 3 clear -> dummy, return 0.

A.2 index page -> bitfield + dense

Two pages of the index array, mostly zero (values not sorted):

page P = [0, 0, 102, 100, 0, 0, 101, 0]
page Q = [0, 202, 200, 0, 0, 0, 201, 0]

Each page stores a mask and a base; the non-zero values minus base
form a delta sequence. Identical delta sequences are shared, so a
page keeps only a seqoff into one common delta pool:

P: mask {2,3,6}, base 100, delta (2,0,1)
Q: mask {1,2,6}, base 200, delta (2,0,1) <- same sequence
delta pool = [2, 0, 1] (stored once); P.seqoff = Q.seqoff = 0

Lookup of slot 3 in page P:
mask bit 3 is set -> present
rank = popcount(mask below bit 3) = 1
value = base + delta[seqoff + rank] = 100 + delta[1] = 100
Slot 4: mask bit clear -> 0.

A.3 recomposition record -> bitfield + dense

An InverseSecond record for one first-codepoint, second range
[0x300 .. 0x30A] (span 10), code_idx mostly zero:

[hi=0, lo=0x300, span=10,
code_idx = 0,0,5,0,0,0,7,0,0,0,0]

Store:

hi=0, lo=0x300, span=10
mask = bits {2,6} set (span+1 = 11 bits)
base = 5 (min non-zero code_idx)
delta = [0, 2] (code_idx - base)

Lookup of second = 0x302 (offset 2):
mask bit 2 is set -> present
rank = popcount(mask below bit 2) = 0
result = InverseCodes[base + delta[0]] = InverseCodes[5]
second = 0x303 (offset 3): mask bit 3 clear -> 0.

A.4 Further sharing (not pursued)

The delta pool above shares only identical sequences. A sequence
that is a subsequence of another, or that overlaps it, could share
storage too:

pool so far: [2, 0, 1]
delta (0, 1) -> reuse pool at offset 1 (subsequence)
delta (1, 5) -> extend to [2, 0, 1, 5]; (1,5) sits at offset 2

This is the overlap/suffix sharing the generator already uses for
the decomposition-sequence table. Applied to these bitfield deltas
it could shrink them further, but the packing becomes a
shortest-common-superstring-like problem and gets complex, so I
did not pursue it -- noting it only as a possibility.

----------------------------------------------------------------------

Best regards,
Henson