Research-0055: VIF AVX-512 polynomial-log2 attempt — bit-exactness forbids¶

• Status: Active (concluded — negative result)
• Workstream: ADR-0138 (_iqa_convolve bit-exact double-precision fast path — precedent for "SIMD must match scalar bit-for-bit"), ADR-0145 (motion_v2 NEON bit-exact to scalar — same precedent on the ARM side), Research-0024 (VIF upstream divergence), Research-0053 (post-merge CPU profile, in flight on PR #333)
• Last updated: 2026-05-03

Question¶

The post-merge CPU profile (Research-0053, in flight on PR #333) attributes 13% of VIF AVX-512 samples to the first of three vpgatherdq log2 lookups in vif_statistic_8_avx512. The proposed optimisation: replace the gather-from-table with an inline 5th-order minimax polynomial. Expected end-to-end win: +3–6%.

The fork's bit-exactness contract (ADR-0138 / ADR-0140) requires every SIMD path to produce byte-identical integer outputs to the scalar reference. The scalar uses a precomputed lookup table generated by log_generate() in core/src/feature/integer_vif.c:221:

log2_table[i] = (uint16_t)round(log2f((float)i) * 2048);   // i in [32767, 65535]

So: can a 5th-order polynomial (or any polynomial of practical SIMD cost) return the same uint16 quantised value as this table at every one of the 32,768 integer inputs in the gather domain?

If yes — the AVX-512 swap is legal in isolation (AVX2 / NEON / scalar can keep their tables; the fork already accepts heterogeneous implementations as long as the output bits agree). If no — the optimisation violates ADR-0138 and cannot ship.

Sources¶

• core/src/feature/integer_vif.c:221 — log_generate() table fill.
• core/src/feature/integer_vif.h:132 — log2_32() / log2_64() scalar lookups.
• core/src/feature/x86/vif_avx512.c:101–136 — three _mm512_i32gather_epi64 calls into log2_table per 8-lane block.
• ADR-0138 — SIMD bit-exactness contract (cross-backend places=4 gate + scalar-equality requirement).
• ADR-0140 — CPU SIMD scalar-equality requirement (no cross-backend ULP drift on x86 paths).
• PR #333 profile digest (Research-0053).
• scripts/dev/vif_log2_poly_check.py — empirical prototype that drove the numbers in this digest.

Findings¶

Empirical bit-equivalence test¶

scripts/dev/vif_log2_poly_check.py fits a Chebyshev least-squares polynomial to log2(x) on x ∈ [32768, 65535], evaluates it through the same float32 → *2048 → round-to-nearest pipeline as log_generate(), and compares the uint16 output against the reference table at every integer input.

The proposed degree-5 polynomial misses 428 inputs out of 32,768 by ±1 quantisation step (each step = 1/2048 of a log2 unit). Even degree 8 still misses 2. Bit-equivalence first reaches zero mismatches at degree 10.

Why bit-equivalence is so hard here¶

The table stores 32,768 independent integer outputs. A degree-N polynomial has only N+1 free coefficients. For the polynomial to reproduce all 32,768 quantised outputs, the rounding boundaries of round(log2f(i)*2048) must align with the polynomial's curve to ULP-of-quantisation precision at every input — the function being approximated has to sit, by accident, inside the half-quantum band around a polynomial of that degree at every one of those 32,768 sample points. log2 is too curvy on this domain for any polynomial under degree 10 to satisfy that.

Cost analysis at degree 10¶

A degree-10 Horner evaluation per lane is 10 FMAs. The AVX-512 path runs 8 lanes per block, so 10 vector FMAs replace one vpgatherdq (which has ~14-cycle latency on Skylake-X, but throughput one per ~5 cycles, much of which is already hidden by surrounding work).

The 13% sample share for the first gather is dominated by L1d cache misses on the 128 KiB log2_table (65,536 × uint16 = 128 KiB; the table is too big to stay resident in L1 alongside the rest of the working set during the inner loop). A polynomial would pay 10 FMAs per lane (≈ 5 throughput-cycles on a Skylake-X Port 0/Port 5 mix), which is on the same order as the gather throughput cost without the cache pressure. At degree 5 the win would be larger but the polynomial diverges. Net: even if we lifted the bit-exact requirement, degree 10 is a wash, not a +3–6% end-to-end win.

The +3–6% estimate in PR #333's profile assumed a degree-5 polynomial. With the bit-exactness constraint it cannot ship.

What would unblock this optimisation¶

Three (mutually exclusive) paths exist, in increasing order of project disruption:

1. Tighten the table generator to a polynomial form. If we changed log_generate() itself to evaluate the same polynomial at integer inputs, the table and the SIMD polynomial would agree by construction. But that would change the table's output bits (≤ 1 quantum at 428 of 32,768 entries for degree 5) — Netflix golden-data assertions hash the final VIF score, which depends on every accumulated log2_table[] value. Forbidden by §8 / global rule #1.

2. Make the table generator higher-precision and re-fit. The table currently rounds float32 log2f(i)*2048. Switching to float64 + bigger quantum would change a small number of LSBs and might widen the polynomial fit's tolerance. Same forbidden-touches-golden problem.

3. Smaller table + interpolation. A 8 KiB table + linear interpolation would fit L1d, eliminating the cache-miss share of the gather cost, without touching the polynomial / bit-exactness question. The interpolation has to round to the same uint16 the full table produces — non-trivial but not impossible. Out of scope for this digest; tracked as a follow-up bullet below.

Alternatives explored¶

• Degree 5 minimax polynomial in AVX-512 only, table elsewhere. Tried in this digest; 428 of 32,768 inputs diverge from the table by ±1 quantum. Violates ADR-0138 / ADR-0140. Rejected.
• Degree 10 polynomial in AVX-512 only. Bit-equivalent, but 10 FMAs per lane is roughly the same throughput as the gather it replaces on Skylake-X / Ice Lake — the win evaporates. Rejected on cost grounds.
• Quantised lookup table reduced to L1d-resident size with linear interpolation. Promising — would skip the bit-exactness landmine if the interpolation is rounded the same way the full table is — but a separate piece of work, not the +3–6% drop-in PR #333 anticipated. Filed as follow-up.
• Just accept ±1 quantum drift in AVX-512. Would break Netflix golden CI (the fork's three canonical reference pairs would shift at places=4) and /cross-backend-diff. Hard rule §8 / global rule #1: forbidden.

Open questions¶

• Is a smaller (e.g. 4 KiB or 8 KiB) lookup table + linear interpolation a viable replacement that stays bit-exact and fits L1d? Worth a separate prototype.
• Does the gather hot share survive on Sapphire Rapids / Granite Rapids, where AVX-512 gather throughput is materially better than Skylake-X? If yes, the optimisation question goes away on newer hardware and only matters for the older machines on which the profile was taken.

Related¶

• ADRs: ADR-0138, ADR-0140
• Research: Research-0024, Research-0053 (post-merge CPU profile, PR #333)
• PRs: this PR (perf/vif-polynomial-log2-simd, docs-only)
• Scripts: scripts/dev/vif_log2_poly_check.py