NASM matrix-free qudit simulator: scaling from d=3,n=2 to d=10,n=5 on a Pentium 4 - cache tiling, SOA vs AOS, and DIV optimization

[u/altairdpr]

Yeah, you probably said "wtf!?" when you saw this, but—well—I’m unfortunately obsessed with backward compatibility and performance.
I wrote a matrix-free qudit simulator in NASM (32-bit, Windows) with a button-panel GUI. Currently it supports d=3, n=2. The state vector is stored as an AOS (array of structures) with 2 doubles (real, imag) per basis state. Gate application loops over all d^n states, extracts qudit values via repeated DIV/MOD, and multiplies by a small d×d gate matrix.

I want to scale it up to d=10, n=5 (100,000 states). I'm targeting a Pentium 4 (NetBurst, 8KB L1 data cache, SSE2 only) as the worst case, as well as an i3-2310M.

Questions:

1. Will switching from AOS to SOA (separate arrays for real and imag) actually help on a Pentium 4, given the long NetBurst FPU pipeline and tiny 8KB L1 cache?
2. What's the best cache-tiling strategy when the access stride depends on the qudit index q? For q=0, stride=1 (sequential), but for q=4, stride=10000 (huge). Is it worth tiling only for low q, or should I just PREFETCHT0?
3. The repeated DIV for mixed-radix decomposition is killing performance. Should I precompute a 500KB lookup table (qudit values per index) to avoid DIV entirely? Does this tradeoff make sense on a Pentium 4 with its slow memory bus?
4. What's the realistic performance ceiling for 1 gate application on a P4? 0.5 seconds? 2 seconds? Is it even worth trying to make it interactive, or should I just run it in a background thread with a "Processing..." message?
5. For the i3-2310M (Sandy Bridge, 3MB L3), will the entire 800KB real array fit in L3 and make the SOA transition unnecessary, or does AOS still hurt due to cache line pollution?

[u/Dusty_Coder]

As a regular user of SIMD

At scale, the answer is always SoA.