perf(elf): reduce full-output build-ID hashing cost

[zackees]

Context

The latest exact-baseline Linux experiment for #74 (925e54f3be324778a9af81755cb782476df23987) preallocates large ext4 output extents and improves native reld, but it still misses the required 10% final-link gate:

Configuration	Output size	HEAD median	Compute build ID	Share of median	HEAD vs baseline
no-LTO	468,318,777 B	415.12 ms	54.88 ms	13.22%	8.16% faster
ThinLTO	392,055,327 B	378.64 ms	46.48 ms	12.28%	8.14% faster
full-LTO	373,343,543 B	368.41 ms	45.28 ms	12.29%	5.54% faster

Evidence: https://github.com/zackees/reld/actions/runs/32849407073

crates/reld-core/src/elf_writer.rs::compute_hash currently performs a second full-output BLAKE3 traversal after all ELF bytes are written. The public Rust workload uses a content-derived GNU build ID, so that 45–55 ms pass is paid in all three LTO modes and is now the clearest bounded opportunity to close #74's remaining gap.

A previous attempt to overlap buffered flushing and build-ID hashing was counterproductive: the combined phase grew to 117–156 ms and delivered only 1.04–5.23% total improvement. Hashing and output writeback compete for memory bandwidth, so simply running the existing work concurrently is not the next step. Evidence: https://github.com/zackees/reld/actions/runs/32847260751

There is also a compatibility hazard in crates/reld-core/src/args/elf.rs: bare --build-id, fast, md5, and sha1 all collapse to BuildIdOption::Fast. Any fast-path change must not silently change explicitly named md5 or sha1 behavior.

Proposal

1. Add a focused RED benchmark for the GNU build-ID phase over representative 373–468 MiB ELF outputs, while retaining the existing captured-link benchmark as the end-to-end oracle.
2. Give bare --build-id / --build-id=fast a dedicated implementation and evaluate a faster deterministic 128-bit content hash such as XXH3-128. twox-hash 2.1.2 is already present transitively in Cargo.lock, but the implementation should be selected from measured GitHub Linux results rather than dependency convenience alone.
3. Keep hashing the complete finalized output with the build-ID descriptor zeroed. Do not sample bytes, reuse stale input metadata, subtract startup, or weaken the content-sensitivity contract to improve the score.
4. Separate the parser representation for explicit md5 and sha1 before changing the fast digest. Preserve their current emitted behavior and descriptor widths in this performance change; any standards-correct algorithm migration belongs in a separately reviewed compatibility issue.
5. Retain Compute build ID as a distinct timing phase and publish exact-SHA before/after evidence for no-LTO, ThinLTO, and full-LTO.

Acceptance criteria

• RED evidence is committed first: a focused test/benchmark demonstrates the current fast build-ID phase exceeds its budget on a representative large output.
• GREEN evidence on the same GitHub Linux runner reduces Compute build ID median latency by at least 50% for representative 373–468 MiB outputs.
• The exact captured-link benchmark improves HEAD median final-link latency by at least 5% relative to 925e54f3be324778a9af81755cb782476df23987 in each of no-LTO, ThinLTO, and full-LTO.
• The paired comparison uses the same inputs, linker flags, output mode, thread count, filesystem, round-robin trial ordering, trial count, and correctness oracle; it reports raw samples, median, dispersion, output size, and phase timings.
• Published measurements remain raw final-link latency; process startup is reported separately and never subtracted.
• Repeated links of identical bytes produce identical fast build IDs, and changing any byte outside the zeroed build-ID descriptor changes the ID.
• The build-ID descriptor itself is zeroed during hashing, is written with the correct GNU note size/alignment, and is recognized by readelf -n or an equivalent ELF parser.
• Every benchmark output executes successfully and passes the existing content/layout validation oracle.
• Bare --build-id and --build-id=fast use the optimized path; explicit --build-id=md5, --build-id=sha1, none, uuid, and hexadecimal values have focused compatibility tests and are not silently routed through the new fast algorithm.
• No byte sampling, timestamp-based ID, random ID, disabled build ID, benchmark-workload reduction, or other score-only shortcut is accepted.
• Controlled ordinary small links do not regress by more than 2%.
• Linux correctness, self-hosting, and scheduled benchmark gates remain green.
• The final PR links the exact RED and GREEN workflow runs and records the algorithm, digest width, endianness, and compatibility behavior.

Decisions

• Priority: P2. The phase consumes a stable 12.3–13.2% of the measured link and is large enough to determine whether perf(elf): accelerate large retained-section output emission #74 passes, but it is not a correctness or release blocker.
• Scope: native ELF fast build IDs only. Mach-O UUID/code-signature hashing and bridge engines have different formats and are excluded.
• Target: at least 5% end-to-end in every LTO mode. Applying that gain to the current HEAD medians is sufficient to carry all three exact-baseline results beyond perf(elf): accelerate large retained-section output emission #74's 10% requirement.
• Prefer a faster full-content hash over overlap. The measured overlap experiment increased memory-bandwidth contention and failed its gate.
• Preserve explicit named-mode behavior here. Correcting the existing md5/sha1 alias semantics may be worthwhile, but coupling it to a performance change would make compatibility and benchmark attribution ambiguous.
• Keep build-ID timing visible. A distinct phase makes future output-size and algorithm regressions diagnosable.

Related issues

• perf(elf): accelerate large retained-section output emission #74 is the parent large-output optimization and supplies the exact-baseline benchmark/gate this work should use.