throughput 4a: swap RaptorQ → hand-rolled small-K Reed–Solomon FEC #50

Merged

vxfemboy merged 14 commits from feat/throughput-4a into main

2026-07-09 20:54:11 +00:00

vxfemboy commented

2026-07-09 20:18:35 +00:00

(Migrated from github.com)

What

Replaces yip's RaptorQ FEC with a hand-rolled small-K systematic Reed–Solomon codec, unlocking multi-gigabit single-core throughput while keeping proactive, zero-RTT loss recovery. This is Stage 1 of a staged FEC-codec campaign (RS → sliding-window RLC → RLNC recoding); it builds the reusable GF(256) core the later stages ride on.

Why

A profiling spike + four-track investigation established:

RaptorQ encode is ~26 µs/packet (the ~355 Mbit/s single-core ceiling). Caching its SourceBlockEncodingPlan only reaches ~12 µs — 96% of the residual is the irreducible GF(256) solve over RaptorQ's K′=10 minimum block (a 2-symbol packet does ~10 symbols of work).
That K′=10 tax exists because RaptorQ is a rateless fountain code — and yip never uses ratelessness (observe_loss clamps ratio ≤ 1.0, so repair_count ≤ source). We paid RaptorQ's biggest cost for a capability we don't use.
Small-K systematic Reed–Solomon has no such padding: measured ~0.77 µs bare-core / 1.33 µs full path, same byte overhead, no unsafe.

How

Three layers, all #![forbid(unsafe_code)]:

crates/yip-transport/src/gf256.rs — GF(256) field (poly 0x11D, primitive 2), table-based add/mul/inv/mul_slice_into.
crates/yip-transport/src/rs.rs — normative RS-v1 Cauchy generator (C[m][i] = inv((K+m) ⊕ i)), systematic encode + erasure decode (GF(256) Gauss–Jordan), gated by an exhaustive K-of-(K+R) MDS proof (K∈1..8 × R∈1..4, every erasure pattern) + a reed-solomon-erasure oracle cross-check (dev-dep).
crates/yip-transport/src/fec.rs — rewritten FecEncoder/FecReassembler: codec-tagged payload_id = [0x01, idx_hi, idx_lo, 0], systematic no-loss passthrough, repair_with_id full re-encode for ARQ, all DoS guards preserved + new ones.

raptorq dependency dropped from yip-transport and yip-bench. bin/yipd/src/wire_glue.rs and crates/yip-wire::Frame are unchanged — the wire codec change is entirely in payload_id semantics (a codec tag that pre-slots RLC as 0x02, and fails safe against RaptorQ peers).

Results

Encode: 26 µs → 1.33 µs (~95%) — now below the AEAD seal floor (~1.95 µs), so FEC is no longer the single-core bottleneck.
yip-transport 57/57, yipd 134/134, workspace clippy clean.
netns end-to-end (real sudo run): tunnel, 10%-loss recovery, L2, and ARQ integrity (99.3% delivery @5% loss, 128 retransmits) all pass.

Final whole-branch review (opus): READY TO MERGE, no Critical/Important — MDS-proven correctness, guarded DoS/ARQ/wire seams, constraints intact.

Wire compatibility

Wire-incompatible with RaptorQ peers (fails safe via the codec tag). Acceptable under the pre-release "both peers rebuild together" posture.

Deferred follow-ups (non-blocking)

Doc sweep: CLAUDE.md, README, docs/research, and a now-misleading yip-wire/src/lib.rs:17 comment still say "RaptorQ".
Trivial u8::try_from cleanup of one as cast in a gf256 test.
Optional encode micro-opt (reduce shard-split/Symbol allocations to close the 1.33 → ~0.8 µs gap; already below AEAD, so low priority).
Unrelated: yip-rendezvous-bin smoke test register_lookup_relay_over_udp_with_obf_psk is a pre-existing UDP-timeout flake (passes on re-run; no dependency on this change) — worth hardening its 2s recv timeout separately.

Design docs

Spec: docs/superpowers/specs/2026-07-09-throughput-rs-codec-4a-design.md
Plan: docs/superpowers/plans/2026-07-09-throughput-rs-codec-4a.md
The superseded plan-cached-FEC spec/plan are kept with banners as the decision trail.

🤖 Generated with Claude Code

https://claude.ai/code/session_01RVP6NnbDMAg1iTsMMTfL86

## What Replaces yip's RaptorQ FEC with a hand-rolled **small-K systematic Reed–Solomon** codec, unlocking multi-gigabit single-core throughput while keeping proactive, zero-RTT loss recovery. This is **Stage 1** of a staged FEC-codec campaign (RS → sliding-window RLC → RLNC recoding); it builds the reusable GF(256) core the later stages ride on. ## Why A profiling spike + four-track investigation established: - RaptorQ encode is ~26 µs/packet (the ~355 Mbit/s single-core ceiling). Caching its `SourceBlockEncodingPlan` only reaches ~12 µs — 96% of the residual is the irreducible GF(256) solve over RaptorQ's **K′=10 minimum block** (a 2-symbol packet does ~10 symbols of work). - That K′=10 tax exists because RaptorQ is a rateless fountain code — and yip **never uses ratelessness** (`observe_loss` clamps `ratio ≤ 1.0`, so `repair_count ≤ source`). We paid RaptorQ's biggest cost for a capability we don't use. - Small-K systematic Reed–Solomon has no such padding: measured ~0.77 µs bare-core / **1.33 µs full path**, same byte overhead, no `unsafe`. ## How Three layers, all `#![forbid(unsafe_code)]`: - `crates/yip-transport/src/gf256.rs` — GF(256) field (poly 0x11D, primitive 2), table-based `add`/`mul`/`inv`/`mul_slice_into`. - `crates/yip-transport/src/rs.rs` — normative RS-v1 **Cauchy** generator (`C[m][i] = inv((K+m) ⊕ i)`), systematic encode + erasure decode (GF(256) Gauss–Jordan), gated by an **exhaustive K-of-(K+R) MDS proof** (K∈1..8 × R∈1..4, every erasure pattern) + a `reed-solomon-erasure` oracle cross-check (dev-dep). - `crates/yip-transport/src/fec.rs` — rewritten `FecEncoder`/`FecReassembler`: codec-tagged `payload_id = [0x01, idx_hi, idx_lo, 0]`, systematic no-loss passthrough, `repair_with_id` full re-encode for ARQ, all DoS guards preserved + new ones. `raptorq` dependency dropped from `yip-transport` and `yip-bench`. `bin/yipd/src/wire_glue.rs` and `crates/yip-wire::Frame` are unchanged — the wire codec change is entirely in `payload_id` semantics (a codec tag that pre-slots RLC as `0x02`, and fails safe against RaptorQ peers). ## Results - **Encode: 26 µs → 1.33 µs (~95%)** — now *below* the AEAD seal floor (~1.95 µs), so FEC is no longer the single-core bottleneck. - `yip-transport` 57/57, `yipd` 134/134, workspace clippy clean. - netns end-to-end (real sudo run): tunnel, 10%-loss recovery, L2, and ARQ integrity (99.3% delivery @5% loss, 128 retransmits) all pass. Final whole-branch review (opus): **READY TO MERGE**, no Critical/Important — MDS-proven correctness, guarded DoS/ARQ/wire seams, constraints intact. ## Wire compatibility Wire-incompatible with RaptorQ peers (fails safe via the codec tag). Acceptable under the pre-release "both peers rebuild together" posture. ## Deferred follow-ups (non-blocking) - Doc sweep: `CLAUDE.md`, `README`, `docs/research`, and a now-misleading `yip-wire/src/lib.rs:17` comment still say "RaptorQ". - Trivial `u8::try_from` cleanup of one `as` cast in a `gf256` test. - Optional encode micro-opt (reduce shard-split/Symbol allocations to close the 1.33 → ~0.8 µs gap; already below AEAD, so low priority). - Unrelated: `yip-rendezvous-bin` smoke test `register_lookup_relay_over_udp_with_obf_psk` is a pre-existing UDP-timeout flake (passes on re-run; no dependency on this change) — worth hardening its 2s recv timeout separately. ## Design docs - Spec: `docs/superpowers/specs/2026-07-09-throughput-rs-codec-4a-design.md` - Plan: `docs/superpowers/plans/2026-07-09-throughput-rs-codec-4a.md` - The superseded plan-cached-FEC spec/plan are kept with banners as the decision trail. 🤖 Generated with [Claude Code](https://claude.com/claude-code) https://claude.ai/code/session_01RVP6NnbDMAg1iTsMMTfL86