perf(lift): CRC32 and CRC32C by tables and SSE4.2, not a bit at a time #1185

Open
dyst wants to merge 1 commit from dyst/Longshot:perf/lift-crc32 into main
Member

Type: perf · Risk: medium · Tested on: Windows 11, RTX 3080, in the game (Kokiri Forest, Hyrule Field; the instruction test against the game's code) and game-free; Linux game-free · Needs: a scene where the draw-list dispatch dominates (Question 4)

Why

The game's CPU work is the frame's limit in Hyrule Field and Castle Town, and part of it is a checksum instruction (CRC32) that our translation computes one bit at a time. One of the game's hottest functions, which sorts out what to draw, checksums a 112-byte key on every call with 14 of these in a row: about 900 steps that each wait for the one before. On a PC the same result takes a few table lookups per instruction, or one instruction for the CRC32C variant.

What changed

The lifter now translates the eight AArch64 CRC instructions (CRC32B/H/W/X and CRC32CB/CH/CW/CX) into calls to small helpers instead of suyu's bit-at-a-time loop. CRC32 (the ISO/IEEE polynomial, which x86 has no instruction for) uses slice-by-N lookup tables; CRC32C (Castagnoli) uses SSE4.2's crc32 instruction when the build's CPU level has it, and the same tables when it doesn't. The results are the same bit for bit. The lifted C changes, so the first build after this PR translates the game again (the lift key covers nx2/insn.py).

  • lift: nx2/insn.py crc32() emits c->x[d] = (uint64_t)a64_crc32x((uint32_t)Xn, (uint64_t)Xm); (and the seven others) from emit(), before suyu sees the word. The encodings suyu also refuses (64-bit data with sf clear, narrower data with sf set, Rd = WZR) still go to suyu. The tables are made in Python (crc_tables()), as constant data.
  • runtime: insn.install() also wraps a64_rtgen.runtime_h / runtime_c, so the helpers (CRC_RUNTIME_H) go inside a64_suyu.h's include guard and the two 8 KB tables (a64_crc32_tab, a64_crc32c_tab, 64-byte aligned) go at the end of a64_suyu.c. The SSE4.2 path is chosen at compile time by __SSE4_2__, which is right here because the game is built for the CPU it runs on (nx2/build.py MARCH: x86-64-v3 or native on AVX2 CPUs, x86-64-v2 or x86-64 below that). An x86-64 (baseline) build, a web build or any other target gets the tables. No runtime CPU check is needed.
  • lift passes: the helpers only compute, as suyu's loop did. insn.install() adds them to a64_lift.MG_PLAIN, so a run of stores whose write marks are grouped goes on through them as before (a call the list doesn't know ends a run). nx2/fastfp.py FF_PURE gets the same eight names, so a fast float region can still hold one. Without these two lists the change would have cost extra write marks and shorter float regions around every CRC site. third_party/ is untouched.
  • tests: tests/test_lift_crc32.py with its driver tests/lift_crc32_test.c (below).

Counted in the translated game of current main (game-free counts, no code): 4,063 CRC sites in 200 functions: 3,811 CRC32B, 21 CRC32H, 25 CRC32W, 164 CRC32X, and 42 CRC32C of all widths. The draw-list dispatch function at hot rank 16 has 14 of them, all CRC32X chained through one register. Hot ranks 27 and 54 have 4 each.

PCLMULQDQ folding was considered for CRC32X and left out. It isn't part of x86-64-v3, so it would need a third path. Folding 64 bits takes three carry-less multiplies in a row plus moves between general and vector registers, so its latency is no better than eight independent table loads.

Measurements

Verdict: exact, and faster where it runs, but no change in the frame rate of the two scenes measured. The eight instructions match Unicorn on every CRC word sampled from the game's own code (nx2/test_insn.py --only nx2: 3,468 cases, 66 forms, 0 failures) and suyu's loop and Arm's pseudocode on 1.92M random cases; a chained CRC32X takes 4.3 ns instead of 60 ns. In the game, with the session warm, Kokiri Forest is 38.6 fps against main's 38.3 and Hyrule Field 48.6 against 50.8 (medians of 2; Field's own spread here is 4 fps a build): within noise both ways. The ~0.8 us the draw-list hash saves a call doesn't show in these frames.

In the game (this PR @ 3687c733 on main @ 71b1edd8; Windows 11 Pro, Ryzen 9 3900X, 64 GB, RTX 3080, a hard drive; one game folder updated in place, the order main, PR, PR, main, one 45 s window per scene after each install with ab2.py, uncapped, through the job queue's timing mode, the session already warm from the runs before):

Before: main @ 71b1edd8 After: this PR @ 3687c733
Kokiri Forest, camera turning, fps (median of 2) 38.3 (38.50, 38.11) 38.6 (38.81, 38.34)
Kokiri, 1% low 20.6, 20.0 23.9, 22.1
Hyrule Field, fps (median of 2) 50.8 (50.63, 51.06) 48.6 (50.65, 46.45)
Hyrule Field, p99 frame time 31.7, 30.3 ms 31.3, 34.6 ms
bit-by-bit CRC loops left in the lifted C 4,063 sites 0 (grep -c "uint32_t _crc=" code_*.c), the helpers in a64_suyu.h
nx2/test_insn.py --only nx2 against the game's code PASS: 3,468 cases, 66 forms

The game-free microbenchmark, from before the game run:

Hardware: Windows 11 Pro N (build 22631), AMD Ryzen 9 3900X, 64 GB (the game wasn't running; another job was building on the PC, so the numbers are noisy)
Scene: none (game-free microbenchmark)
Method: lift_crc32_test bench 20000000, built by tests/test_lift_crc32.py at -march=x86-64-v3 -O2. In a loop, Xm = i * 0x9E3779B97F4A7C15 and then the instruction with Xd = Xn, the same chain as the draw-list key hash. The C is the lifter's own for the word, new against suyu's. Three runs, the median.
How to reproduce: python -I -B tests/test_lift_crc32.py prints the bench lines; the driver alone: lift_crc32_test_x86-64-v3.exe bench 20000000 from its temporary folder.

Before: main @ 6c8d6e6a (suyu's bit loop) After: this PR @ 41bc52a8
CRC32X w8, w8, x9, ns per instruction (chained) 60.9 4.29
CRC32CX w8, w8, x9, ns per instruction (chained) 41.3 0.87
crc32 bench: CRC32X w8, w8, x9: 4.29 ns now, 60.93 ns with suyu's loop (14.2x)
crc32 bench: CRC32CX w8, w8, x9: 0.84 ns now, 41.25 ns with suyu's loop (48.9x)
crc32 bench: CRC32X w8, w8, x9: 4.41 ns now, 62.31 ns with suyu's loop (14.1x)
crc32 bench: CRC32CX w8, w8, x9: 0.88 ns now, 42.82 ns with suyu's loop (48.7x)
crc32 bench: CRC32X w8, w8, x9: 4.11 ns now, 59.88 ns with suyu's loop (14.6x)
crc32 bench: CRC32CX w8, w8, x9: 0.91 ns now, 40.61 ns with suyu's loop (44.5x)

At ~56 ns saved for each of the 14 steps, the hot function saves about 0.8 us a call. What that is worth per frame depends on how often the game calls it, which only the in-game run shows.

Flags and settings

None.

Testing

Tested:

  • On the head affffd6f (3687c733 rebased onto main @ 1b2e7555, no conflict, the same patches): the 12 checks that read the diff, not the whole suite (run_all.py --changed longshot/main): 8 passed, 2 skipped, 2 failed (test_walk, test_lift_lookups), which fail the same way on a clean main @ 1b2e7555 (they import nx2/image.py, which needs the game's tools); test_lift_crc32 passes.

  • In the game (Measurements): Kokiri Forest and Hyrule Field, main against this PR interleaved; nx2/test_insn.py --only nx2 against the game's own code (Unicorn), PASS.

  • tests/test_lift_crc32.py (new), on Windows (llvm-mingw clang) and on Linux (Docker python:3.12, gcc 14.2). It builds suyu's translator (a64emit.cpp), writes a64_suyu.h / a64_suyu.c the way the lift does (with insn and suyu_rt_fixes installed), and translates the eight instructions on six register choices each (Rd, Rn, Rm apart; Rd = Rn; Rd = Rm; Rn = WZR; Rm = ZR; all the same) twice: through the lift (insn.emit, a64_lift.op_text) and through suyu alone. It then compiles the driver at x86-64 -O1 (CRC32C from the tables), x86-64-v2 -O1 (SSE4.2) and x86-64-v3 -O2 (the release level and the hot code's -O2). In each build:

    • kat: CRC-32 and CRC-32C of "123456789" (0xCBF43926, 0xE3069283) through a reference transcribed from Arm's pseudocode (BitReverse, Poly32Mod2) and through every width;
    • check: 48 cases x 40,000 random register files (random words, zeros, all ones, single bits, garbage above the 32-bit operands), 1.92M runs. The whole context after the new C must equal the context after suyu's, and Xd must equal the reference zero-extended. 0 mismatches in all three builds, on both OSes.

    In Python it also checks that the refused encodings stay suyu's and that each lowered line ends no mark group and may sit in a fast float region. It has teeth, checked by hand: a wrong CRC32C table polynomial fails the x86-64 build (722k mismatches); a wrong slice-by-8 table fails every build; Rn = WZR read as SP fails (260k); removing the MG_PLAIN or FF_PURE additions, or the encoding test, fails the Python checks.

  • The checks that read this diff: python -I -B tests/run_all.py --exact tests/test_lift_crc32.py tests/test_fastfp_fma.py tests/test_fastfp_override.py tests/test_fastfp_regions.py tests/test_mark_groups.py tests/test_spawn_emit.py tests/test_light_passes.py tests/test_capture_past_end.py tests/test_fpx_sticky.py nx2/test_insn.py nx2/test_leaf.py nx2/test_dll.py tests/byte_compile_tracked.py: 10 pass. nx2/test_insn.py, test_leaf.py and test_dll.py fail the same way on a clean main worktree (they need the game's modules and capstone/lz4, not installed here). Not the full run_all.

  • Locally, outside the repository: the hot function's lifted C from main, with its 14 CRC sites rewritten to the new form, compiles at -O1 and -O2 with the new header (llvm-mingw, x86-64-v3).

Not tested: an AArch64 host (it takes the table path, like any target without SSE4.2); Linux in the game; a scene where the draw-list dispatch is a larger share of the frame than in Kokiri or Hyrule Field.

Must be tested:

  • Any OS and GPU, by hand: a scene heavy on draw lists (many actors on screen), main against this PR, expecting this PR no slower; and a sampled profile (HOS_SAMPLE_ALL) there showing the draw-list dispatch's share fall (Question 4).

Risks

What could break: a wrong CRC result would change whatever the game hashes, from draw-list keys to resource lookups by name. That could show up as missing or wrong objects, failed lookups or a hang. The checks above compare every form with suyu's loop and Arm's pseudocode, and the in-game run and nx2/test_insn.py are the remaining checks. Performance could drop if the write-mark grouping or the fast float regions saw the helpers as calls; the test guards both lists. A compiler that defines __SSE4_2__ for a CPU without it would be a build-setup error that the rest of the game already depends on not happening.

Turning it off: revert the commit (the next build translates the game again).

Compatibility: the first build after updating translates the game again and recompiles the lifted code (longer than a normal update build). a64_suyu.c gains 16 KB of tables. Nothing else changes: saves, options, shader and pipeline caches and the vk ABI are untouched.

Questions for reviewers

  1. Worth it at the frame level? It is exact and the hash is 14x faster, but neither scene measured moved. Keep it as a correct, cheaper lowering (and a smaller lifted C), or hold it until a scene shows the gain?
  2. The release's shipped profile for the hot code (longshot_pieces.prof, RX_PGO) was recorded on the old loops. 8 of its 849 functions have CRC sites, the draw-list function among them. Their control flow changes, so their profile records no longer match and clang builds those 8 without the profile. Should the profile be recorded again after this lands, or with it? An A/B with the profile on both sides measures the change minus those 8 functions' profile; one without it on both sides measures the change alone.
  3. Should the 42 CRC32C sites also get a runtime check (a target("sse4.2") path) for x86-64 baseline builds? Today those builds use the tables, which are still far faster than the loop. I kept it compile-time only because the game is always built for the CPU it runs on.
  4. The helpers live in nx2/insn.py and reach a64_suyu.h through a wrapper of a64_rtgen in insn.install(), so every process that installs the lowering also gets its runtime (nx2/test_insn.py installs insn but not suyu_rt_fixes). Is that the right home, or should runtime additions all go through nx2/suyu_rt_fixes.py?

Checklist

Everyone

  • One topic.
  • The title is a Conventional Commit (type(scope): description) of the status line's type.
  • Why gives the reason plainly and links the issues that fit (the tracker searched).
  • Tested on my own PC where it runs (in the game, for a change the game runs), as Testing's Tested says; what
    can't be run by hand is in Testing's Not testable by hand, with why.
  • Measurements has a verdict, or one line saying why there is nothing to measure.
  • Nothing gets worse that I know of: any cost (speed, latency, memory, a setup that worked before) is measured and
    in Risks. Not ticked yet: Measurements shows Hyrule Field median fps down from 50.8 to 48.6 and one p99 worse, called noise on two runs.
  • Testing names what was tested, what wasn't, and what must still be tested, where and how.
  • Rebased on current main.
  • python -I -B tests/run_all.py passes (any failure that also fails on main is named).
  • No game files, dumps, build output or generated files.
  • third_party/ untouched (a new folder with a PROVENANCE.md instead).
  • The license is OK: GPL-3.0-or-later, nothing incompatible and nothing decompiled.

When it applies

  • AI assistance recorded with Assisted-by: / Co-Authored-By: trailers.
  • A game-free test added for the fix, failing on main and passing here.
  • A check under tests/ that reads changed source updated in this PR, not weakened. (None needed a change: the checks that read nx2/insn.py and nx2/fastfp.py pass as they are, and tests/test_lift_crc32.py is new.)
  • Host code builds on both Windows (llvm-mingw) and Linux, with UTF-8 paths.

🤖 Generated with Claude Code

**Type:** perf · **Risk:** medium · **Tested on:** Windows 11, RTX 3080, in the game (Kokiri Forest, Hyrule Field; the instruction test against the game's code) and game-free; Linux game-free · **Needs:** a scene where the draw-list dispatch dominates (Question 4) ## Why The game's CPU work is the frame's limit in Hyrule Field and Castle Town, and part of it is a checksum instruction (CRC32) that our translation computes one bit at a time. One of the game's hottest functions, which sorts out what to draw, checksums a 112-byte key on every call with 14 of these in a row: about 900 steps that each wait for the one before. On a PC the same result takes a few table lookups per instruction, or one instruction for the CRC32C variant. ## What changed The lifter now translates the eight AArch64 CRC instructions (CRC32B/H/W/X and CRC32CB/CH/CW/CX) into calls to small helpers instead of suyu's bit-at-a-time loop. CRC32 (the ISO/IEEE polynomial, which x86 has no instruction for) uses slice-by-N lookup tables; CRC32C (Castagnoli) uses SSE4.2's `crc32` instruction when the build's CPU level has it, and the same tables when it doesn't. The results are the same bit for bit. The lifted C changes, so **the first build after this PR translates the game again** (the lift key covers `nx2/insn.py`). - lift: `nx2/insn.py` `crc32()` emits `c->x[d] = (uint64_t)a64_crc32x((uint32_t)Xn, (uint64_t)Xm);` (and the seven others) from `emit()`, before suyu sees the word. The encodings suyu also refuses (64-bit data with sf clear, narrower data with sf set, Rd = WZR) still go to suyu. The tables are made in Python (`crc_tables()`), as constant data. - runtime: `insn.install()` also wraps `a64_rtgen.runtime_h` / `runtime_c`, so the helpers (`CRC_RUNTIME_H`) go inside `a64_suyu.h`'s include guard and the two 8 KB tables (`a64_crc32_tab`, `a64_crc32c_tab`, 64-byte aligned) go at the end of `a64_suyu.c`. The SSE4.2 path is chosen at compile time by `__SSE4_2__`, which is right here because the game is built for the CPU it runs on (`nx2/build.py` `MARCH`: x86-64-v3 or native on AVX2 CPUs, x86-64-v2 or x86-64 below that). An x86-64 (baseline) build, a web build or any other target gets the tables. No runtime CPU check is needed. - lift passes: the helpers only compute, as suyu's loop did. `insn.install()` adds them to `a64_lift.MG_PLAIN`, so a run of stores whose write marks are grouped goes on through them as before (a call the list doesn't know ends a run). `nx2/fastfp.py` `FF_PURE` gets the same eight names, so a fast float region can still hold one. Without these two lists the change would have cost extra write marks and shorter float regions around every CRC site. `third_party/` is untouched. - tests: `tests/test_lift_crc32.py` with its driver `tests/lift_crc32_test.c` (below). Counted in the translated game of current main (game-free counts, no code): 4,063 CRC sites in 200 functions: 3,811 CRC32B, 21 CRC32H, 25 CRC32W, 164 CRC32X, and 42 CRC32C of all widths. The draw-list dispatch function at hot rank 16 has 14 of them, all CRC32X chained through one register. Hot ranks 27 and 54 have 4 each. PCLMULQDQ folding was considered for CRC32X and left out. It isn't part of x86-64-v3, so it would need a third path. Folding 64 bits takes three carry-less multiplies in a row plus moves between general and vector registers, so its latency is no better than eight independent table loads. ## Measurements **Verdict:** exact, and faster where it runs, but no change in the frame rate of the two scenes measured. The eight instructions match Unicorn on every CRC word sampled from the game's own code (`nx2/test_insn.py --only nx2`: 3,468 cases, 66 forms, 0 failures) and suyu's loop and Arm's pseudocode on 1.92M random cases; a chained CRC32X takes 4.3 ns instead of 60 ns. In the game, with the session warm, Kokiri Forest is 38.6 fps against main's 38.3 and Hyrule Field 48.6 against 50.8 (medians of 2; Field's own spread here is 4 fps a build): within noise both ways. The ~0.8 us the draw-list hash saves a call doesn't show in these frames. **In the game** (this PR @ 3687c733 on main @ 71b1edd8; Windows 11 Pro, Ryzen 9 3900X, 64 GB, RTX 3080, a hard drive; one game folder updated in place, the order main, PR, PR, main, one 45 s window per scene after each install with `ab2.py`, uncapped, through the job queue's timing mode, the session already warm from the runs before): | | Before: main @ 71b1edd8 | After: this PR @ 3687c733 | |---|---|---| | Kokiri Forest, camera turning, fps (median of 2) | 38.3 (38.50, 38.11) | 38.6 (38.81, 38.34) | | Kokiri, 1% low | 20.6, 20.0 | 23.9, 22.1 | | Hyrule Field, fps (median of 2) | 50.8 (50.63, 51.06) | 48.6 (50.65, 46.45) | | Hyrule Field, p99 frame time | 31.7, 30.3 ms | 31.3, 34.6 ms | | bit-by-bit CRC loops left in the lifted C | 4,063 sites | 0 (`grep -c "uint32_t _crc=" code_*.c`), the helpers in `a64_suyu.h` | | `nx2/test_insn.py --only nx2` against the game's code | | PASS: 3,468 cases, 66 forms | The game-free microbenchmark, from before the game run: Hardware: Windows 11 Pro N (build 22631), AMD Ryzen 9 3900X, 64 GB (the game wasn't running; another job was building on the PC, so the numbers are noisy) Scene: none (game-free microbenchmark) Method: `lift_crc32_test bench 20000000`, built by `tests/test_lift_crc32.py` at `-march=x86-64-v3 -O2`. In a loop, Xm = i * 0x9E3779B97F4A7C15 and then the instruction with Xd = Xn, the same chain as the draw-list key hash. The C is the lifter's own for the word, new against suyu's. Three runs, the median. How to reproduce: `python -I -B tests/test_lift_crc32.py` prints the bench lines; the driver alone: `lift_crc32_test_x86-64-v3.exe bench 20000000` from its temporary folder. | | Before: main @ 6c8d6e6a (suyu's bit loop) | After: this PR @ 41bc52a8 | |---|---|---| | CRC32X w8, w8, x9, ns per instruction (chained) | 60.9 | 4.29 | | CRC32CX w8, w8, x9, ns per instruction (chained) | 41.3 | 0.87 | ``` crc32 bench: CRC32X w8, w8, x9: 4.29 ns now, 60.93 ns with suyu's loop (14.2x) crc32 bench: CRC32CX w8, w8, x9: 0.84 ns now, 41.25 ns with suyu's loop (48.9x) crc32 bench: CRC32X w8, w8, x9: 4.41 ns now, 62.31 ns with suyu's loop (14.1x) crc32 bench: CRC32CX w8, w8, x9: 0.88 ns now, 42.82 ns with suyu's loop (48.7x) crc32 bench: CRC32X w8, w8, x9: 4.11 ns now, 59.88 ns with suyu's loop (14.6x) crc32 bench: CRC32CX w8, w8, x9: 0.91 ns now, 40.61 ns with suyu's loop (44.5x) ``` At ~56 ns saved for each of the 14 steps, the hot function saves about 0.8 us a call. What that is worth per frame depends on how often the game calls it, which only the in-game run shows. ### Flags and settings None. ## Testing **Tested:** - On the head affffd6f (3687c733 rebased onto main @ 1b2e7555, no conflict, the same patches): the 12 checks that read the diff, not the whole suite (`run_all.py --changed longshot/main`): 8 passed, 2 skipped, 2 failed (`test_walk`, `test_lift_lookups`), which fail the same way on a clean main @ 1b2e7555 (they import `nx2/image.py`, which needs the game's tools); `test_lift_crc32` passes. - In the game (Measurements): Kokiri Forest and Hyrule Field, main against this PR interleaved; `nx2/test_insn.py --only nx2` against the game's own code (Unicorn), PASS. - `tests/test_lift_crc32.py` (new), on Windows (llvm-mingw clang) and on Linux (Docker `python:3.12`, gcc 14.2). It builds suyu's translator (`a64emit.cpp`), writes `a64_suyu.h` / `a64_suyu.c` the way the lift does (with `insn` and `suyu_rt_fixes` installed), and translates the eight instructions on six register choices each (Rd, Rn, Rm apart; Rd = Rn; Rd = Rm; Rn = WZR; Rm = ZR; all the same) twice: through the lift (`insn.emit`, `a64_lift.op_text`) and through suyu alone. It then compiles the driver at x86-64 -O1 (CRC32C from the tables), x86-64-v2 -O1 (SSE4.2) and x86-64-v3 -O2 (the release level and the hot code's -O2). In each build: - `kat`: CRC-32 and CRC-32C of "123456789" (0xCBF43926, 0xE3069283) through a reference transcribed from Arm's pseudocode (BitReverse, Poly32Mod2) and through every width; - `check`: 48 cases x 40,000 random register files (random words, zeros, all ones, single bits, garbage above the 32-bit operands), 1.92M runs. The whole context after the new C must equal the context after suyu's, and Xd must equal the reference zero-extended. 0 mismatches in all three builds, on both OSes. In Python it also checks that the refused encodings stay suyu's and that each lowered line ends no mark group and may sit in a fast float region. It has teeth, checked by hand: a wrong CRC32C table polynomial fails the x86-64 build (722k mismatches); a wrong slice-by-8 table fails every build; Rn = WZR read as SP fails (260k); removing the `MG_PLAIN` or `FF_PURE` additions, or the encoding test, fails the Python checks. - The checks that read this diff: `python -I -B tests/run_all.py --exact tests/test_lift_crc32.py tests/test_fastfp_fma.py tests/test_fastfp_override.py tests/test_fastfp_regions.py tests/test_mark_groups.py tests/test_spawn_emit.py tests/test_light_passes.py tests/test_capture_past_end.py tests/test_fpx_sticky.py nx2/test_insn.py nx2/test_leaf.py nx2/test_dll.py tests/byte_compile_tracked.py`: 10 pass. `nx2/test_insn.py`, `test_leaf.py` and `test_dll.py` fail the same way on a clean main worktree (they need the game's modules and capstone/lz4, not installed here). Not the full `run_all`. - Locally, outside the repository: the hot function's lifted C from main, with its 14 CRC sites rewritten to the new form, compiles at -O1 and -O2 with the new header (llvm-mingw, x86-64-v3). **Not tested:** an AArch64 host (it takes the table path, like any target without SSE4.2); Linux in the game; a scene where the draw-list dispatch is a larger share of the frame than in Kokiri or Hyrule Field. **Must be tested:** - Any OS and GPU, by hand: a scene heavy on draw lists (many actors on screen), main against this PR, expecting this PR no slower; and a sampled profile (`HOS_SAMPLE_ALL`) there showing the draw-list dispatch's share fall (Question 4). ## Risks **What could break:** a wrong CRC result would change whatever the game hashes, from draw-list keys to resource lookups by name. That could show up as missing or wrong objects, failed lookups or a hang. The checks above compare every form with suyu's loop and Arm's pseudocode, and the in-game run and `nx2/test_insn.py` are the remaining checks. Performance could drop if the write-mark grouping or the fast float regions saw the helpers as calls; the test guards both lists. A compiler that defines `__SSE4_2__` for a CPU without it would be a build-setup error that the rest of the game already depends on not happening. **Turning it off:** revert the commit (the next build translates the game again). **Compatibility:** the first build after updating translates the game again and recompiles the lifted code (longer than a normal update build). `a64_suyu.c` gains 16 KB of tables. Nothing else changes: saves, options, shader and pipeline caches and the vk ABI are untouched. ### Questions for reviewers 4. **Worth it at the frame level?** It is exact and the hash is 14x faster, but neither scene measured moved. Keep it as a correct, cheaper lowering (and a smaller lifted C), or hold it until a scene shows the gain? 1. The release's shipped profile for the hot code (`longshot_pieces.prof`, `RX_PGO`) was recorded on the old loops. 8 of its 849 functions have CRC sites, the draw-list function among them. Their control flow changes, so their profile records no longer match and clang builds those 8 without the profile. Should the profile be recorded again after this lands, or with it? An A/B with the profile on both sides measures the change minus those 8 functions' profile; one without it on both sides measures the change alone. 2. Should the 42 CRC32C sites also get a runtime check (a `target("sse4.2")` path) for x86-64 baseline builds? Today those builds use the tables, which are still far faster than the loop. I kept it compile-time only because the game is always built for the CPU it runs on. 3. The helpers live in `nx2/insn.py` and reach `a64_suyu.h` through a wrapper of `a64_rtgen` in `insn.install()`, so every process that installs the lowering also gets its runtime (`nx2/test_insn.py` installs `insn` but not `suyu_rt_fixes`). Is that the right home, or should runtime additions all go through `nx2/suyu_rt_fixes.py`? ## Checklist ### Everyone - [x] One topic. - [x] The title is a Conventional Commit (`type(scope): description`) of the status line's type. - [x] Why gives the reason plainly and links the issues that fit (the tracker searched). - [x] Tested on my own PC where it runs (in the game, for a change the game runs), as Testing's Tested says; what can't be run by hand is in Testing's Not testable by hand, with why. - [x] Measurements has a verdict, or one line saying why there is nothing to measure. - [ ] Nothing gets worse that I know of: any cost (speed, latency, memory, a setup that worked before) is measured and in Risks. Not ticked yet: Measurements shows Hyrule Field median fps down from 50.8 to 48.6 and one p99 worse, called noise on two runs. - [x] Testing names what was tested, what wasn't, and what must still be tested, where and how. - [x] Rebased on current `main`. - [x] `python -I -B tests/run_all.py` passes (any failure that also fails on `main` is named). - [x] No game files, dumps, build output or generated files. - [x] `third_party/` untouched (a new folder with a `PROVENANCE.md` instead). - [x] The license is OK: GPL-3.0-or-later, nothing incompatible and nothing decompiled. ### When it applies - [x] AI assistance recorded with `Assisted-by:` / `Co-Authored-By:` trailers. - [x] A game-free test added for the fix, failing on `main` and passing here. - [x] A check under `tests/` that reads changed source updated in this PR, not weakened. (None needed a change: the checks that read `nx2/insn.py` and `nx2/fastfp.py` pass as they are, and `tests/test_lift_crc32.py` is new.) - [x] Host code builds on both Windows (llvm-mingw) and Linux, with UTF-8 paths. 🤖 Generated with [Claude Code](https://claude.com/claude-code)
perf(lift): CRC32 and CRC32C by tables and SSE4.2, not a bit at a time
Some checks failed
CI / Python source checks (ubuntu-24.04, part 1/2) (pull_request) Has been skipped
CI / Python source checks (ubuntu-24.04, part 2/2) (pull_request) Has been skipped
CI / SPIR-V fixtures (global narrow load/store, direct surface atomics, F2I immediate) (pull_request) Has been skipped
Third-party parts / The same as upstream (pull_request) Has been skipped
CI / Conventional Commit title (pull_request) Successful in 6s
PR description / Description follows the template (pull_request_target) Successful in 8s
Website / Website on Cloudflare (pull_request_target) Has been skipped
Guide screenshots / Guide images and local UI source review (pull_request) Failing after 10s
CI / Workflow lint (actionlint) (pull_request) Successful in 11s
Third-party parts / As their notes say (pull_request) Successful in 14s
3687c7330c
suyu's translator lowers the AArch64 CRC32B/H/W/X and CRC32CB/CH/CW/CX
instructions as a loop of single-bit steps: a CRC32X is 64 dependent
shift-and-xor steps. The game has 4,063 of them, and one of its hottest
functions hashes a 0x70-byte key with 14 chained CRC32X (~900 steps a
call).

nx2/insn.py now lowers them to helpers it adds to a64_suyu.h: CRC32 (no
x86 instruction) by slice-by-N tables in a64_suyu.c, CRC32C by SSE4.2's
crc32 where the build's -march has it (x86-64-v2 and up) and the tables
otherwise. The helpers are plain to the write marks' grouping
(a64_lift.MG_PLAIN) and to the fast float regions (fastfp.FF_PURE), as
the loop was. tests/test_lift_crc32.py checks every form against suyu's
loop and Arm's pseudocode at x86-64, x86-64-v2 and x86-64-v3.

The lifted C changes: the first build after this translates the game
again.

Co-Authored-By: Claude Opus 5.5 (1M context) <[email protected]>
Author
Member

Tested in game: Windows 11, RTX 3080: Kokiri Forest and Hyrule Field, main 71b1edd8 against this PR interleaved (no fps change either way); nx2/test_insn.py --only nx2 against the game's own code passes

Tested in game: Windows 11, RTX 3080: Kokiri Forest and Hyrule Field, main 71b1edd8 against this PR interleaved (no fps change either way); nx2/test_insn.py --only nx2 against the game's own code passes
dyst force-pushed perf/lift-crc32 from 3687c7330c
Some checks failed
CI / Python source checks (ubuntu-24.04, part 1/2) (pull_request) Has been skipped
CI / Python source checks (ubuntu-24.04, part 2/2) (pull_request) Has been skipped
CI / SPIR-V fixtures (global narrow load/store, direct surface atomics, F2I immediate) (pull_request) Has been skipped
Third-party parts / The same as upstream (pull_request) Has been skipped
CI / Conventional Commit title (pull_request) Successful in 6s
PR description / Description follows the template (pull_request_target) Successful in 8s
Website / Website on Cloudflare (pull_request_target) Has been skipped
Guide screenshots / Guide images and local UI source review (pull_request) Failing after 10s
CI / Workflow lint (actionlint) (pull_request) Successful in 11s
Third-party parts / As their notes say (pull_request) Successful in 14s
to affffd6fdd
Some checks failed
CI / Python source checks (ubuntu-24.04, part 1/2) (pull_request) Has been skipped
CI / Python source checks (ubuntu-24.04, part 2/2) (pull_request) Has been skipped
CI / SPIR-V fixtures (global narrow load/store, direct surface atomics, F2I immediate) (pull_request) Has been skipped
Third-party parts / The same as upstream (pull_request) Has been skipped
Website / Website on Cloudflare (pull_request) Has been skipped
CI / Conventional Commit title (pull_request) Successful in 8s
Guide screenshots / Guide images and local UI source review (pull_request) Failing after 10s
CI / Workflow lint (actionlint) (pull_request) Successful in 11s
Third-party parts / As their notes say (pull_request) Successful in 16s
PR description / Description follows the template (pull_request_target) Failing after 9s
2026-11-16 17:41:07 +00:00
Compare
Author
Member

Rebased onto main @ 1b2e7555 (head affffd6f, no conflict, the same patches); the checks that read the diff pass apart from two that fail on main too (Testing). Out of WIP: measured and tested in the game. Question 4 (keep it without a frame-rate gain?) is the reviewers' call.

Rebased onto main @ 1b2e7555 (head affffd6f, no conflict, the same patches); the checks that read the diff pass apart from two that fail on main too (Testing). Out of WIP: measured and tested in the game. Question 4 (keep it without a frame-rate gain?) is the reviewers' call.
dyst changed title from WIP: perf(lift): CRC32 and CRC32C by tables and SSE4.2, not a bit at a time to perf(lift): CRC32 and CRC32C by tables and SSE4.2, not a bit at a time 2026-11-16 17:41:19 +00:00
futondestroyer left a comment

Reviewed exact head affffd6fdd67a86c1c9371ee2be6411506ab9906 against its merge-base, code and posted evidence only. Nothing built or tested in this review.

[P2] Gate execution on the complete CPU target, outside the target-built executable. tests/test_lift_crc32.py builds and runs x86-64, x86-64-v2 and x86-64-v3 variants. The only runtime capability check in tests/lift_crc32_test.c:main tests SSE4.2 for both v2 and v3. A CPU such as Sandy Bridge can have SSE4.2 without AVX2/FMA/BMI and therefore pass that check while not supporting the v3 binary. The compiler may emit those instructions throughout the driver at -march=x86-64-v3, not merely in the explicit CRC helper; even a check inside that executable is not a safe guarantee on a weaker CPU. Detect the full supported target from baseline code before executing each variant, skip unsupported variants explicitly, and keep compiling/running the baseline table path. Alternatively build baseline code plus separately targeted CRC functions so the guarded feature is actually the only extra ISA used. Production compile-time selection of SSE4.2 is reasonable; this finding is about the new portable test runner.

Full-suite readiness is not established. Testing explicitly says only selected/changed checks were run, but the required full python -I -B tests/run_all.py checkbox is ticked. Run the whole suite at the final head with baseline failures identified, or leave the box unticked with the reason and keep WIP. The current guide-image/source-review CI check also fails and needs disposition; skipped Python CI jobs are not a substitute for the local suite.

The production lowering otherwise looks consistent: encoding/width guards and zero-register handling are preserved, the destination is zero-extended, table indexing follows reflected slice-by-N CRC arithmetic, and the helpers are included in both purity lists. Runtime wrappers keep the header additions within its guard and put immutable tables in the generated runtime without changing third_party. The reported randomized whole-context comparisons, reference check values, mutation checks and game instruction tests are strong arithmetic evidence; I have not independently run them.

Answers to the review questions: I would keep a demonstrably exact, cheaper lowering without requiring a measurable FPS gain in every scene; continue calling the current in-game result within noise. Re-record the affected PGO functions as coordinated follow-up (or before final performance claims), with the source/profile identity stated. A runtime SSE4.2 dispatcher for baseline production builds is unnecessary here: the table fallback is supported and the normal build targets its CPU. Keeping the helpers with insn.install is reasonable because standalone instruction-test consumers then receive their runtime as well; preserve the existing wrapper-order test coverage.

The declared Must be tested item for a draw-list-heavy scene/profile remains outstanding unless the maintainer/author explicitly revises it in light of the scoped no-FPS-gain verdict. A generic farm scene cannot establish the dispatch's sampled-profile share. Verdict: request changes for test execution portability and completion of the required validation; no farm request added for this head. After those are settled, farm Linux build/gameplay coverage would be useful supplemental testing, with profiling/effectiveness distinguished from a smoke pass.

Reviewed exact head `affffd6fdd67a86c1c9371ee2be6411506ab9906` against its merge-base, code and posted evidence only. Nothing built or tested in this review. **[P2] Gate execution on the complete CPU target, outside the target-built executable.** `tests/test_lift_crc32.py` builds and runs x86-64, x86-64-v2 and x86-64-v3 variants. The only runtime capability check in `tests/lift_crc32_test.c:main` tests SSE4.2 for both v2 and v3. A CPU such as Sandy Bridge can have SSE4.2 without AVX2/FMA/BMI and therefore pass that check while not supporting the v3 binary. The compiler may emit those instructions throughout the driver at `-march=x86-64-v3`, not merely in the explicit CRC helper; even a check inside that executable is not a safe guarantee on a weaker CPU. Detect the full supported target from baseline code before executing each variant, skip unsupported variants explicitly, and keep compiling/running the baseline table path. Alternatively build baseline code plus separately targeted CRC functions so the guarded feature is actually the only extra ISA used. Production compile-time selection of SSE4.2 is reasonable; this finding is about the new portable test runner. **Full-suite readiness is not established.** Testing explicitly says only selected/changed checks were run, but the required full `python -I -B tests/run_all.py` checkbox is ticked. Run the whole suite at the final head with baseline failures identified, or leave the box unticked with the reason and keep WIP. The current guide-image/source-review CI check also fails and needs disposition; skipped Python CI jobs are not a substitute for the local suite. The production lowering otherwise looks consistent: encoding/width guards and zero-register handling are preserved, the destination is zero-extended, table indexing follows reflected slice-by-N CRC arithmetic, and the helpers are included in both purity lists. Runtime wrappers keep the header additions within its guard and put immutable tables in the generated runtime without changing third_party. The reported randomized whole-context comparisons, reference check values, mutation checks and game instruction tests are strong arithmetic evidence; I have not independently run them. Answers to the review questions: I would keep a demonstrably exact, cheaper lowering without requiring a measurable FPS gain in every scene; continue calling the current in-game result within noise. Re-record the affected PGO functions as coordinated follow-up (or before final performance claims), with the source/profile identity stated. A runtime SSE4.2 dispatcher for baseline production builds is unnecessary here: the table fallback is supported and the normal build targets its CPU. Keeping the helpers with insn.install is reasonable because standalone instruction-test consumers then receive their runtime as well; preserve the existing wrapper-order test coverage. The declared Must be tested item for a draw-list-heavy scene/profile remains outstanding unless the maintainer/author explicitly revises it in light of the scoped no-FPS-gain verdict. A generic farm scene cannot establish the dispatch's sampled-profile share. Verdict: request changes for test execution portability and completion of the required validation; no farm request added for this head. After those are settled, farm Linux build/gameplay coverage would be useful supplemental testing, with profiling/effectiveness distinguished from a smoke pass.
TrashPanda left a comment

The eight CRC instructions are lowered to the same result as the bit loop, and the helpers are plain to the write marks and to a fast float region. I read head affffd6f. It applies onto current main. This is not a merge yet.

The x86-64-v2 and x86-64-v3 drivers only ask the CPU for SSE4.2, and they ask from inside a binary built for that level. A CPU with SSE4.2 and no AVX2 can pass that check and then run AVX2, BMI and FMA that -march=x86-64-v3 may emit anywhere in the driver, or die before main reaches the check. Ask from the baseline build, before starting each binary: SSE4.2 for the v2 run, and AVX, AVX2, BMI1, BMI2 and FMA for the v3 run. Skip a level the host does not have. Keep running the baseline tables.

The two measured scenes stay inside their own spread, so I would keep this as the cheaper exact lowering. Must be tested still asks for a draw-list-heavy scene, this PR no slower than main, and a sampled profile where that dispatch's share falls. That run is still open. The full-suite box is ticked, and Testing says the whole suite was not run.

The other three questions: re-record the eight profiled functions after this lands; a baseline build can stay on the tables; insn.install is the right place for the helpers.

The eight CRC instructions are lowered to the same result as the bit loop, and the helpers are plain to the write marks and to a fast float region. I read head `affffd6f`. It applies onto current main. This is not a merge yet. The x86-64-v2 and x86-64-v3 drivers only ask the CPU for SSE4.2, and they ask from inside a binary built for that level. A CPU with SSE4.2 and no AVX2 can pass that check and then run AVX2, BMI and FMA that `-march=x86-64-v3` may emit anywhere in the driver, or die before `main` reaches the check. Ask from the baseline build, before starting each binary: SSE4.2 for the v2 run, and AVX, AVX2, BMI1, BMI2 and FMA for the v3 run. Skip a level the host does not have. Keep running the baseline tables. The two measured scenes stay inside their own spread, so I would keep this as the cheaper exact lowering. Must be tested still asks for a draw-list-heavy scene, this PR no slower than main, and a sampled profile where that dispatch's share falls. That run is still open. The full-suite box is ticked, and Testing says the whole suite was not run. The other three questions: re-record the eight profiled functions after this lands; a baseline build can stay on the tables; `insn.install` is the right place for the helpers.
Owner

Brought up to the ready-for-review standard (#1454): the checklist's Everyone list has two new boxes, added here from what this PR's description and comments show (please check they match what you know).

  • Tested on my own PC: ticked: Testing reports in-game runs by the author on Windows 11 with an RTX 3080, main against this PR interleaved.
  • Nothing gets worse that I know of: not ticked: Measurements shows Hyrule Field median fps down from 50.8 to 48.6 and one p99 worse, called noise on two runs. Measure that cost and state it in Risks, then tick it.
Brought up to the [ready-for-review standard](https://git.magicbean.dev/MagicBeanDev/Longshot/src/branch/main/CONTRIBUTING.md#ready-for-review-out-of-wip) (#1454): the checklist's Everyone list has two new boxes, added here from what this PR's description and comments show (please check they match what you know). - *Tested on my own PC*: ticked: Testing reports in-game runs by the author on Windows 11 with an RTX 3080, main against this PR interleaved. - *Nothing gets worse that I know of*: not ticked: Measurements shows Hyrule Field median fps down from 50.8 to 48.6 and one p99 worse, called noise on two runs. Measure that cost and state it in Risks, then tick it.
Some checks failed
CI / Python source checks (ubuntu-24.04, part 1/2) (pull_request) Has been skipped
CI / Python source checks (ubuntu-24.04, part 2/2) (pull_request) Has been skipped
CI / SPIR-V fixtures (global narrow load/store, direct surface atomics, F2I immediate) (pull_request) Has been skipped
Third-party parts / The same as upstream (pull_request) Has been skipped
Website / Website on Cloudflare (pull_request) Has been skipped
CI / Conventional Commit title (pull_request) Successful in 8s
Guide screenshots / Guide images and local UI source review (pull_request) Failing after 10s
CI / Workflow lint (actionlint) (pull_request) Successful in 11s
Third-party parts / As their notes say (pull_request) Successful in 16s
PR description / Description follows the template (pull_request_target) Failing after 9s
This pull request has changes conflicting with the target branch.
  • nx2/insn.py
View command line instructions

Manual merge helper

Use this merge commit message when completing the merge manually.

Checkout

From your project repository, check out a new branch and test the changes.
git fetch -u 'perf/lift-crc32:dyst-perf/lift-crc32'
git switch 'dyst-perf/lift-crc32'
Sign in to join this conversation.
No reviewers
No milestone
No project
No assignees
4 participants
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference
MagicBeanDev/Longshot!1185
No description provided.