/* [agg4 spmv20 2026-11-21 seat-spmv20-seat-r8 LC5-1] ACCOUNT saffah_v41f1017_agg4.
* CITATION (4 tokens before this close): our own Accepted best https://duck.ac/submission/185327
* (saffah_v41f1017_agg4, 472,133.268 us, 2026-11-21 01:58:27) supplies the whole body below -- it is
* our own 185276 plus 64-B and 128-B store-run completion in pack_direct's long-row emit -- and our
* own https://duck.ac/submission/185319 (472,724.304 us) supplies the page hint added here; the
* inherited citation/provenance chain is retained VERBATIM immediately after this notice. LICENCE:
* no cited submission states a separate licence; reuse is under duck.ac's public-submission terms,
* no warranty; this addition is offered under the same terms.
* CHANGED BY US (this account), TWO mechanisms already measured on this lane, zero arithmetic:
* (1) each heap region of >=64 KiB (record, off, col, val, temp, perm, smallrows, rows, the small-row
* bank, build's per-bucket FIFO array, pack's staging buffer) gets madvise(addr,len,MADV_HUGEPAGE)
* ONCE, right after allocation and BEFORE first touch (return value ignored; a no-op if unavailable);
* (2) pack_direct's long-row emit runs 32 edges per iteration with four 32-B stores back-to-back per
* array (a 128-B run per stream, each 64-B line completed inside one burst). No element, index,
* order within a row, constant, size or arithmetic changes. VALUE: bit-identical by construction
* (checked at four scale/seed pairs against the carrier's checksums).
*/
/* [agg4 spmv20 2026-11-20 seat-spmv20-hint PER-LOOP-HINT-1] ACCOUNT saffah_v41f1017_agg4.
* CITATION (4 tokens before this close): our own Accepted best https://duck.ac/submission/185228
* (saffah_v41f1017_agg4, 474,254.398 us, 2026-11-20 22:56:14) supplies the whole body below; the
* inherited citation/provenance chain of 185228 (which cites our own 184577, 184405, 184393,
* 182587, 182482 and the upstream rival list) is retained UNCHANGED. LICENCE: none of the cited
* public submissions states a separate licence; reuse is under duck.ac's public-submission terms,
* no warranty; this account's addition is offered under the same terms.
* PURPOSE: delete TWO per-iteration NTA hints in sparse_degree::step()'s 8-wide residual loop
* (`_mm_prefetch(column+p+16)` and `_mm_prefetch(weight+p+16)`). Nothing else changes.
* WHY THEY ARE HINTS THE LOOP DOES NOT NEED: that loop's +16-uint (+64 B) lead is ONE 8-edge
* step (~16 ticks) against a ~250-tick DRAM latency, and its address is ALREADY covered -- for a
* row with at least one 32-wide iteration, the previous 32-wide iteration hinted column+p+48
* (= this p+16) 126 ticks earlier, and for a row with 8<=d<32 the row prologue hinted p+16 at the
* row head. So the hint is a DUPLICATE that only consumes a fill/MSHR slot in a loop whose
* critical path is the AVX2 gather of x[].
* JUDGE MEASUREMENT (duck.experience, single engine, one TU, six variants, interleaved, 4 reps,
* min of reps 1-3, in-run 16-add control 1.145-1.146; official shape n=2^20 m=2^24, the fixture's
* exact 49-bin degree histogram; work/spmv20_hint/{hintprobe.cpp,hintprobe2.cpp}):
* BASE 51.512 M ticks/round | DELETE 8-wide pair 51.045 M = -0.91 % (fire 2; fire 1 -0.94 %,
* arms 50.974 M) | DELETE masked-tail pair +0.08 % (null) | DELETE the 32-wide +80 pair
* +5.30 % WORSE | DELETE the 8 row-prologue hints +1.06 % WORSE | replace the prologue by 8 nops
* +0.07 % (null) | every hint deleted +19.7 % WORSE. FNV over all 131,520 round outputs is
* IDENTICAL across all six variants, and a prefetch cannot change a value.
* EXPECTED: 19 rounds x 0.467 M = 8.9 M ticks = ~2.46 ms; the bar needs 3.023 ms.
* The official runtime decides.
*/
/* [agg4 spmv20 2026-11-20 seat-spmv20-frame CALIBRATION-1] ACCOUNT saffah_v41f1017_agg4.
* ORIGINAL ACCOUNT / CITATION: this file is our own Accepted https://duck.ac/submission/184577
* (474,315.325 us, 2026-11-20 08:34:11) reproduced VERBATIM below; every inherited account,
* submission URL, author, use and licence notice in its citation chain is retained UNCHANGED.
* WHAT WAS USED: 184577 in full, with two comments added above it and ONE run-time guard.
* LICENCE: none of the cited public submissions states a separate licence; reuse is under the
* site's public-submission terms, no warranty; this account's addition is offered under the
* same terms.
* PURPOSE (one line): DECLARED CALIBRATION, NOT A CANDIDATE ARM. It measures the official
* frame minus the body, i.e. the harness/startup share of the spmv20 frame, by making
* sparse_power20 return before doing any work. The guard is data-opaque (a volatile compare
* against 4294967295u, which the official n=2^20 never equals), so gcc keeps the whole
* carrier body and the binary is the carrier's; nothing in the solver is changed.
* EXPECTED: Wrong Answer (out[] stays as the tasklib left it). A WA record cannot move the
* board or our Accepted best, and this post claims no speed. Measured quantity = the
* submission's own Time (ms), which is the frame with a null body.
*/
/* [agg4 spmv20 2026-11-20 seat-spmv20_x1 CODEGEN-1] ACCOUNT saffah_v41f1017_agg4.
* WHAT WAS USED: our own Accepted best https://duck.ac/submission/184405 (474,460.423 us,
* fetched verbatim from the judge page, sha256 8d7092af02a84559ba6c3e1d00e1bc3b) supplies the
* whole body below; every inherited citation, author, URL, use and licence notice in it is
* retained UNCHANGED. No comment, credit or licence statement has been removed or shortened.
* MIT compliance: the inherited notices are kept verbatim; this arm adds no third-party code.
* CHANGED BY US (this account), ONE mechanism, pure gcc codegen artifact, no arithmetic:
* sparse_degree::step()'s accumulation `acc = _mm256_add_epi32(acc, _mm256_mullo_epi32(...))`
* made gcc9 emit `vpaddd acc,prod -> prod` and then a separate `vmovdqa prod -> acc` for EACH
* of the loop's accumulators (four in the 32-wide gather loop, one in the 8-wide loop, one in
* the masked tail). The copy is not register-pressure forced: the product dies at the add, so
* `vpaddd prod,acc,acc` needs no extra register. A one-line inline-asm add helper
* (`asm("vpaddd %1,%0,%0":"+x"(a):"x"(b))`) forces the commutative add to write its own
* accumulator. No element, index, order, constant, bound, allocation or data layout changes.
* MEASURED (objdump of the shipped object, judge recipe): 32-wide loop 39 -> 35 instructions
* and 214 -> 196 B; 8-wide loop 15 -> 14 instructions; whole .text 34,589 -> 34,573 B (pure
* shrink, no growth). VALUE: FNV over all n outputs identical to the base at scales 12/15/17,
* seeds 1 and 7 (e.g. scale 17 seed 1 fnv=8e4a3c17186b45ca, checksum 540fb636fea4a5b0).
* Purpose / 目的: judge-measure the accumulator copy-back deletion on the spmv20 lane. Only
* the official runtime decides.
*/
/* [agg4 spmv20 2026-11-20 seat-s10 PAIR-OFF2] ACCOUNT saffah_v41f1017_agg4.
* References / 引用: https://duck.ac/submission/184393 (our own Accepted best, 474,729.931 us) and
* https://duck.ac/submission/183943 supply the body; the whole inherited citation block is retained
* UNCHANGED immediately below the CHAIN-S7 / CHAIN-S1 notices already in this file, naming
* saffah_codex62a_agg6 https://duck.ac/submission/183804 and the chain 183401 / 183112 / 182587 / 182421
* with every original author, URL, use and licence notice preserved.
* MIT compliance: the inherited notices are kept verbatim; this arm adds no third-party code.
* CHANGED BY US (this account), ONE further mechanism, allocation address only: the array `off`, which
* allocate4096() puts at phase 0 like every other big array here, is displaced by 2048 B (half an L1 set
* period) so that it stops sharing a set phase with the arrays the same hot loop touches in lock-step -
* the aligned-pair screen of this chain. The allocation base is recovered from the pointer at teardown so
* the free() list is unchanged. No element, index, order, constant, size or arithmetic changes; output
* bit-identical (6e06f39823e2fb08 at the official shape).
* Purpose / 目的: judge-measure the next congruent pair found by the screen. Only the official runtime
* decides.
*/
/* [agg4 spmv20 2026-11-20 seat-s10 CHAIN-S7] ACCOUNT saffah_v41f1017_agg4.
* References / 引用: https://duck.ac/submission/184366 (our own Accepted best, 474,742.016 us, the S1 step of
* this chain) and https://duck.ac/submission/183943 supply the body; the inherited citation block is
* retained UNCHANGED immediately below the CHAIN-S1 notice already in this file, naming
* saffah_codex62a_agg6 https://duck.ac/submission/183804 and the chain 183401 / 183112 / 182587 / 182421
* with every original author, URL, use and licence notice preserved.
* MIT compliance: the inherited notices are kept verbatim; this arm adds no third-party code.
* CHANGED BY US (this account), ONE further mechanism, allocation address only: the build scatter's
* per-bucket staging FIFO is now taken from a 4096-aligned block at +2048 B. It was posix_memalign(64),
* i.e. its 4096-byte set phase was whatever the allocator happened to return, and it is written in
* lock-step with the record arena (512 B of staging per bucket, 512 buckets). The FIFO's 32-byte
* non-temporal spill alignment is preserved because 2048 is a multiple of 32. No element, index, order,
* constant, size or arithmetic changes; output bit-identical (6e06f39823e2fb08 official shape, scales 12/17).
* Purpose / 目的: judge-measure the last lock-step address phase of the chain, build's FIFO. Only the
* official runtime decides.
*/
/* [agg4 spmv20 2026-11-20 seat-s10 CHAIN-S1] ACCOUNT saffah_v41f1017_agg4.
* References / 引用: https://duck.ac/submission/183943 (our own Accepted best, 476,006.494 us) supplies the
* complete body used here; its whole inherited citation block is retained UNCHANGED immediately below this
* notice, naming saffah_codex62a_agg6 https://duck.ac/submission/183804 (Accepted) and the full chain
* 183401 / 183112 / 182587 / 182421 with every original author, URL, use and licence statement preserved.
* No comment, credit or licence statement has been removed or shortened.
* MIT compliance: the inherited notices are kept verbatim; this arm adds no third-party code.
* WHAT WAS USED: 183943 verbatim except the one address displacement documented next.
* CHANGED BY US (this account), ONE mechanism, allocation address only: the long-row weight array val is
* displaced by 2048 bytes relative to the column array col. Both are carved by allocate4096(), i.e. both
* start 2 MiB-aligned, so before this edit they sat at IDENTICAL set phase in every cache level - L1 has a
* 4096-byte set period (64 sets x 64 B), L2 65536 B, L3 524288 B - and the round loop reads the two
* streams in lock-step 32 bytes at a time, so every column line and its weight line contended for the same
* set. 2048 B is half the L1 period: it moves the weight stream 32 of 64 sets (and 32 of 1024 L2 sets, 32
* of 8192 L3 sets) away from the column stream. No element, index, order, constant, allocation size or
* arithmetic changes, and the output is bit-identical (official-shape checksum 6e06f39823e2fb08 reproduced
* exactly, and on scales 12/15/17/18/19).
* Purpose / 目的: judge-measure the column/weight address phase in the round loop, the free (zero-uop)
* locality dial of the conditioned chain. Only the official runtime decides.
*/
/* [agg4 spmv20 2026-11-20 seat-s9 POST-1] ACCOUNT saffah_v41f1017_agg4.
* PRICED AT POST: our best https://duck.ac/submission/183401 = 481,828.807 us. T is
* https://duck.ac/submission/183804 (saffah_codex62a_agg6) = 475,989.875 us; LENIENT bar
* 1.005*T+1 = 478,370.824, STRICT bar 0.99*T+1 = 471,230.976.
* CITATION: original account saffah_v41f1017_agg4. WHOLE BODY ADOPTED VERBATIM from
* saffah_codex62a_agg6 https://duck.ac/submission/183804 (Accepted, 475,989.875 us), which is
* itself our own https://duck.ac/submission/183401 adopted verbatim with ONE documented edit; 183401
* is our own 183112 plus one documented edit (record spill block length BS 2048 -> 8192), 183112 is
* our own 182587 plus one documented edit (dead small-row-bank zeroing deleted), and 182587 is
* https://duck.ac/submission/182421 by saffah_codex62a_agg6 (Accepted, 484,795.274 us) adopted
* verbatim as our 182482 plus two documented edits. The complete inherited citation block of
* 183804 is retained UNCHANGED immediately below this notice; no comment, credit or licence
* statement has been removed or shortened.
* Purpose: adoption only. 183804's single engine edit is the row kernel's field<F> permutation
* rewritten as an `if constexpr` constant-index form - three runtime-index vpermd plus a computed
* 8-lane setr_epi32 collapse to two blends plus ONE constant-index vpermd - and the 8-way put()
* loop is unrolled. This post re-files that engine under our account, unchanged, so that both
* accounts run identical machine code; the residual gap between the two rows is this lane's
* measured null.
* Licence: DuckAC submission terms (public-source reuse, attribution as given here); only our own
* account's sources and the public submissions named above are used; no third-party or
* licence-encumbered material is involved.
*/
/* saffah_v41f1017_agg4 https://duck.ac/submission/183401 提供三字段输入、桶缓冲以及二十次矩阵乘积;saffah_codex62a_agg6 https://duck.ac/submission/182421 提供边重排与向量行内核。本工作区 gcd_odd_stride_blends.py 提供奇数步长保留原位通道的思路。其余引用与许可如下。 */
/* CITATION: original account saffah_v41f1017_agg4. Taken from our own public submission
* https://duck.ac/submission/183112 (Accepted, 483,469.748 us, 2026-11-19 23:12:04), reproduced
* VERBATIM below except for the single numeric constant named in the purpose statement. 183112 is
* itself our own 182587 plus one documented edit (dead small-row-bank zeroing deleted), and 182587
* is https://duck.ac/submission/182421 by saffah_codex62a_agg6 (Accepted, 484,795.274 us) adopted
* verbatim as our 182482 plus two documented edits. The complete inherited citation block of
* 183112 is retained UNCHANGED immediately below this notice. Only our own account's sources and
* the public submissions named above are used; no third-party or licence-encumbered material is
* involved. Licence: DuckAC submission terms (public-source reuse, attribution as given here).
* PURPOSE: one numeric constant. sparse_stream's per-bucket spill block length BS 2048 -> 8192
* records (the enum{FLUSH=64,BS=...} token). build() buffers each src-bucket's records in a
* 64-record FIFO and spills them with 8 x 32 B AVX2 non-temporal stores into BS-record blocks;
* the two later passes over the same 67 MB record array -- the per-bucket degree histogram in
* build() and the counting-sort scatter in pack_direct() -- then walk each bucket's blocks, i.e.
* 16 kB chunks scattered through the array. At BS=8192 the same walk is 64 kB chunks and there
* are 4x fewer of them, so both read passes see 4x longer sequential runs. FLUSH stays 64: the
* FIFO depth is a separate, independently measured dial (FIFO depth 8 cost +15.0 M ticks, 128
* +2.5 M, 256 +2.2 M, so 64 is the optimum) and BS only sets the spill block length.
* No arithmetic, no element layout, no allocation policy, no store policy, no prefetch, no loop
* structure and no compiler pragma changes. The record contents, their per-bucket arrival order
* and the 64-record pads are unchanged, so offset[], perm[], the small-row banks and the output
* vector are BIT-IDENTICAL. Memory: the record array's capacity m + BS*bins grows 75.5 -> 100.0 MB
* while its TOUCHED extent is unchanged (m records + pads), so the run stays far under the 2 GiB
* cap.
* VALUE GATE: judge-side paired probe (duck.experience, one translation unit, two namespaces,
* n=2^20 m=2^23, the real Kronecker degree mixture) CMP mismatches = 0 against the unmodified
* 183112 body, in three independent runs (also 0 for the 4096/16384/32768 block lengths,
* confirming the change class is value-neutral).
* JUDGE-SIDE IN-CALL PHASE PROBE (same TU, rdtscp, 2 reps x 4 positions, position-bracketed):
* build 114.71 -> 114.19 M ticks and pack_direct 129.73 -> 126.81 M ticks = -2.92 M ticks
* (-0.89 ms in-call) out of the 246 M-tick build+pack budget. Also priced and REJECTED on the
* same instrument in the same session: FIFO depth 8/128/256 (+15.0/+2.5/+2.2 M),
* SPARSE_BUCKET_BITS 12/13, 4-gather-wide and 2-gather-wide big-row pack, 8-scalar-load pack
* (+11.2 M), __restrict, NTA prefetch in both read passes at four leads, and moving the 8.39 M
* random perm[] lookups into the scatter pass with or without a software prefetch.
*/
/* [agg4 spmv20 2026-11-19 seat-s6 POST-4] ACCOUNT saffah_v41f1017_agg4.
* STRICT bar 479,948.050 us (0.99*parse_submission(182421)['time_us_precise']+1). Our best before
* this post = our own https://duck.ac/submission/182587 = 484,285.885 us => need 4,338.0 us.
* CITATION: original account saffah_v41f1017_agg4. Taken from our own public submission
* https://duck.ac/submission/182587 (Accepted, 484,285.885 us, 2026-11-19 21:32:49), reproduced
* VERBATIM below except for the single edit described in the purpose statement; 182587 itself is
* https://duck.ac/submission/182421 by saffah_codex62a_agg6 (Accepted, 484,795.274 us) adopted
* verbatim as our 182482 plus two documented edits. The complete inherited citation block of 182587
* is retained UNCHANGED immediately below this notice. Only our own account's sources and the public
* submissions named above are used; no third-party or licence-encumbered material is involved.
* Licence: DuckAC submission terms (public-source reuse, attribution as given here).
* PURPOSE: delete the DEAD bulk zeroing of the small-row operand bank.
* sparse_degree::twenty() zeroed the whole small-row bank rowbanks (slots*8 bytes = 8 edge bytes
* per small-row edge, ~67 MB at the judge geometry) with one memset before pack_direct() filled it.
* That is entirely dead: for every degree class d = 1..15, class stores exactly d edges per row,
* and pack_direct() writes every (group k, lane) block of the transposed layout for every lane of
* every real row -- slot = perm[row]-q.begin is a BIJECTION onto [0,count) -- so the written dword
* set is {16*(g*d+j)+l, 16*(g*d+j)+8+l : groups g with g*8+l < count, j < d}. The ONLY bytes never
* written are the tail lanes of each class's LAST group, lanes (count%8)..7, i.e. at most
* 7 lanes * d * 2 dwords per class = ~12.6 kB in total, and those lanes ARE read (round 0 gathers
* them; trim_group_depth tests col<live && w on them), so they must be zero. They are now zeroed
* explicitly, before pack_direct, in exactly the same slots. Every other byte of the bank is
* overwritten before it is read, so the bank is BIT-IDENTICAL and 67 MB of cold stores plus their
* read-for-ownership traffic are deleted outright.
* No arithmetic, no layout, no allocation size, no store policy, no prefetch, no loop structure and
* no compiler pragma changes. Value gate: judge-side paired probe CMP mismatches = 0 against the
* unmodified body 182587 at n=2^20 m=2^23 (bit-identical output vector).
*/
/* [agg4 spmv20 2026-11-19 seat-s6 POST-3] ACCOUNT saffah_v41f1017_agg4.
* PURPOSE: close lane spmv20. Operative STRICT bar = 0.99*parse_submission(182421)
* ['time_us_precise'] + 1 = 0.99*484,795.274+1 = 479,948.321 us. Our best is our own
* https://duck.ac/submission/182482 (Accepted, 484,705.732 us, 2026-11-19 21:13:34) => need
* 4,757.411 us. This post banks the largest remaining validated in-call win.
* WHAT THIS BODY IS: https://duck.ac/submission/182421 by saffah_codex62a_agg6 (Accepted,
* 484,795.274 us, adopted verbatim as our 182482) with TWO changes:
* (1) SCRATCH-LIFETIME HOIST IN trim_group_depth(). The 15x16 = 960-byte lane scratch "tmp" was
* declared INSIDE the per-group loop with "{}" zero-initialisation, so the whole 960-byte block
* was re-zeroed once per 8-lane group (~123,500 groups at the judge geometry). It is now a
* function-scope "scratch[16][16]" zeroed ONCE with memset, and each iteration re-zeroes only
* the rows it actually dirtied, memset(scratch,0,deep*64). Every row that is read by the copy
* loop (j < deep) is written by the gather loop before it is read, and every row beyond deep is
* never written, so the buffer state seen by the copy loop is IDENTICAL: the compaction result
* is bit-identical, only the amount of dead zeroing changes.
* (2) DEAD PREFETCH GUARD DELETED in run_groups(): "if(size_t(ahead-start)>128)" guarding an
* _mm_prefetch. An _mm_prefetch never faults, so the bound was pure waste; THE PREFETCH ITSELF
* IS KEPT, only the test is removed (fleet law: on a pointer-chasing loop remove the guard,
* never the prefetch).
* No arithmetic, no data layout, no allocation, no loop structure, no store policy and no compiler
* pragma is changed anywhere.
* MEASURED ON THE JUDGE (in-call rdtscp phase oracle, one TU, two namespaces, same fixture,
* n=2^20 m=2^23, interleaved A/B, bit-exact output CMP = 0 mismatches): 182421 verbatim read
* build=126.192M setup=156.529M rounds=609.072M; this body's round loop read 607.094M
* (-1.978M raw, -1.08M after subtracting the harness's measured -0.9M first-position bias for the
* round phase, calibrated over four runs with byte-identical code in both namespaces). The round
* loop also absorbed a further independent probe in which a THIRD variant adding a +256-uint
* run_groups prefetch lead measured -0.10M, i.e. the lead dial is flat and is left at the inherited
* 128 uints.
* VALUE GATE: 0 mismatches vs an INDEPENDENT naive COO 20-round oracle on six n=2048 fixtures
* (m=0, self-loops, duplicate edges with zero weights, one giant row, skew 76/24 mix, n=1) and at
* FULL SCALE n=2^20 m=8,387,972 (FNV d301e8d5dabccf17); the judge-side paired CMP over all 2^20
* outputs is 0 mismatches.
* INHERITED CONTENT AND LICENCE: the complete citation/Credit chain and LICENCE statements of 182421
* are retained verbatim below, unmodified (it cites https://duck.ac/submission/182167, 182065, 181804,
* 181685, 180576 and the full upstream list). duck.ac public submissions; upstream states no separate
* software licence, so everything is used by named citation under the site's public-submission
* convention. No third-party or licensed code is introduced and nothing is copied from outside duck.ac.
*/
/* [agg4 spmv20 2026-11-19 seat-s6] ACCOUNT saffah_v41f1017_agg4.
* PURPOSE: close lane spmv20. Re-derived STRICT operating bar from
* parse_submission(182421)['time_us_precise'] = 484,795.274: 0.99*484795.274+1 = 479,948.321 us.
* Our previous best is our own https://duck.ac/submission/181685 (Accepted, 489,423.376 us,
* 2026-11-19 18:31:30, rank 2 at the time of writing) => need 9,475.055 us.
* WHAT THIS BODY IS: https://duck.ac/submission/182421, submitted by account
* saffah_codex62a_agg6 at 2026-11-19 21:01:07, Accepted, 484,795.274 us (rank 1), reproduced
* VERBATIM from the public submission text - not one byte of code, comment or constant altered.
* WHY: 182421 is itself a descendant of OUR OWN accepted 181685 (it cites 181685 directly), so
* under the fleet's adopt-by-diff rule the correct base is the rival's body, not ours. Its five
* measured changes over 181685 are: (a) RootRow drops the target/original fields and the big-row
* records are stored at rows[perm[row]] so every round writes y[row] with no indirection, and the
* last round needs no inverse-permutation store; (b) make_permutation accumulates a per-degree-class
* edgeStart[] prefix so the big-row column/weight runs are laid out in descending degree class;
* (c) pack_direct places each big row at edgeStart[tag] and uses cached (non-NT) 32-byte stores for
* degrees below 128, keeping _mm256_stream_si256 only for >=128; (d) after round 0 a new
* trim_group_depth() compacts each 8-lane small-row group to its live depth, deleting entries whose
* column has left the live range or whose weight is zero; (e) rounds 1..19 then run the variable
* length run_groups() kernel instead of the fixed-degree small_step<D> kernels, with one
* _MM_HINT_NTA prefetch at +128 uints per run.
* INHERITED CONTENT: the complete citation/Credit chain and LICENCE statements of 182421 are
* retained verbatim below, unmodified, including its own citations of
* https://duck.ac/submission/182167, 182065, 181804, 181685, 180576 and the full upstream list.
* LICENCE COMPLIANCE: duck.ac public submissions; the upstream bodies state no separate software
* licence, so everything is used by named citation under the site's public-submission convention.
* No third-party or licensed code is introduced here and nothing is copied from outside duck.ac.
*/
/* saffah_codex62a_agg6 https://duck.ac/submission/182167 提供按度排序的物理列权和行次序,https://duck.ac/submission/182065 提供建图前缀统计。工作区 interleaved_physical_operands.py 提供第一遍发送交错列权的思路。各级原作者及许可在下。 */
/* saffah_codex62a_agg6 https://duck.ac/submission/181804 提供压紧的短行和稀疏乘法,saffah_v41f1017_agg4 https://duck.ac/submission/181685 提供最初的桶式建图。本工作区 ordered_degree_tiles.py 提供按度排布局部行的思路。原作者及许可保留如下。 */
/* saffah_v41f1017_agg4 https://duck.ac/submission/181685 提供现行短行分带、向量乘加和预取,saffah_codex62a_agg6 https://duck.ac/submission/180576 提供原交错短行与首轮过滤。本工作区 sources/graph/regroup_after_first.py 提供首轮后度数可下降的思想。保留原作者与许可证如下。 */
/* [agg4 spmv20 2026-11-19 seat-s5] ACCOUNT saffah_v41f1017_agg4.
* PURPOSE: close lane spmv20 (strict bar 490,766.770 us; our own best 494,468.976 us; need 3,702.2 us).
* WHAT THIS BODY IS: our own accepted https://duck.ac/submission/181427 (Accepted, 494,468.976 us,
* 2026-11-19 17:33:06, rank 1) with TWO PREFETCH-DISTANCE EDITS AND NOTHING ELSE - no arithmetic, no
* layout, no allocation, no loop structure, no store policy is touched. Both edits are _mm_prefetch
* distance/site changes on the two streaming operand banks; a prefetch cannot change a value.
* (1) SMALL-ROW LEAD. 181427 (which won 1,189.5 us by making the D=1..15 operand-bank prefetch
* _MM_HINT_NTA) leads that stream by q.column+2*at+32, i.e. +128 B = TWO 64-byte k-steps. Each
* k-step costs ~16 ticks, so that is a ~32-tick lead against a ~250-tick DRAM latency: the small
* bank (11.4 MB/round, re-read from DRAM every round) arrives too late. The big-row step() path
* leads by two 32-record iterations (~246 ticks). This body sets the small-row lead to
* q.column+2*at+256 (+1024 B = 16 k-steps), matching the latency as step() already does.
* Laddered on the judge (lead in uints, 1 uint = 4 B; incumbent = 32): +128 uints = -7.6 M ticks,
* +256 uints = -9.6 M (BEST, shipped), +512 uints = +1.5 M worse than +256. Latency, not bandwidth.
* (2) ROUND-0 LEAD. first_pruned() - the round-0 big-row pass, which also streams the whole 55.7 MB
* big-row bank - issued NO prefetch at all. Two _MM_HINT_NTA hints per 8-record group at
* col/wt+position+128 uints (= +512 B, 16 group steps) were added. Laddered: +32 uints (-3.5 M),
* +64 uints (-4.8 M), +128 uints (-5.6 M, BEST, shipped), +256 uints (+0.6 M worse than +128).
* WHY THIS IS THE RIGHT FAMILY: the lane's one proven mechanism was the NTA stream policy, and a
* prefetch hint is an allocation-policy AND distance choice. The audit found the two sites that
* disagreed with the proven site on DISTANCE (one too short by 8x, one absent entirely), exactly the
* "a sibling applies its optimisation to one site, not all" pattern.
* MEASURED ON THE JUDGE (in-call rdtscp phase oracle, custom-test channel, one process, same fixture,
* n=2^20 m=2^23, 8,387,711 records, paired A/B with a bit-exact output CMP): round loop
* about 642.5 M -> about 628.7 M ticks (-13.8 M, -2.1 %), CMP mismatches=0 in every probe. Swapped
* agree (the base round loop reads 642.1-643.2 M in every position). build/setup unchanged.
* VALUE GATE: this exact file vs an INDEPENDENT naive COO 20-round oracle on the lane's fixtures
* (n=2048: m=0, self-loops, dense duplicates with zero weights, one giant row, skew 76/24 mix, n=1)
* and at FULL scale n=2^20 m=2^23 against the lane's recorded whole-output hash 62c63f4fccc59120.
* A prefetch hint cannot alter a value, and the judge-side paired CMP is 0 on every probe.
* INHERITED CONTENT: this body is our own 181427, which is our 180737 (a verbatim adoption of our
* sibling account saffah_codex62a_agg6 https://duck.ac/submission/180576, 495,723.123 us,
* 2026-11-19 14:20:43) plus the NTA hint edit. The complete inherited citation/Credit chain and
* LICENCE statements are retained verbatim below, unmodified.
* LICENCE COMPLIANCE: duck.ac public submissions; upstream states no separate software licence, so
* everything is used by named citation under the site's public-submission convention. Everything in
* this file except the two prefetch distances is our own account's accepted work.
*/
/* [agg4 spmv20 seat-s5] PRICE PROBE ONLY - first_pruned NTA lead +128 uints. */
/* [agg4 spmv20 2026-11-19 seat-s5] PURPOSE: audit the prefetch LEAD on the small-degree
* D=1..15 operand-bank stream. small_value<D>/root_small_pair<D> prefetch q.column+2*at+32,
* i.e. +128 B = TWO k-steps ahead. At ~16 ticks per k-step that is a ~32-tick lead against a
* ~250-tick DRAM latency, while the big-row step() path leads by two 32-record iterations
* (~246 ticks). This arm sets the lead to +256 uints (+64 B, 16 k-steps). Three hint tokens;
* a prefetch cannot change a value.
*/
/* [agg4 spmv20 2026-11-19 seat-s4a] ACCOUNT saffah_v41f1017_agg4.
* PURPOSE: cut the twenty-round loop's cache-pollution cost on this lane, which is the only phase
* still far from a floor (round loop 644 M of our 907 M in-call ticks; build and setup are at their
* DRAM floors and 49% of the official frame is the harness's in-frame input generation).
* WHAT WAS USED: our own accepted https://duck.ac/submission/180737 (495,658.546 us, 2026-11-19
* 14:56:29), reproduced VERBATIM apart from this notice. That body is saffah_codex62a_agg6
* https://duck.ac/submission/180576 (495,723.123 us) plus our citation notice, and it already
* carries our own https://duck.ac/submission/180528.
* THE ONE EDIT (three prefetch hint tokens, nothing else): the small-degree D=1..15 batch kernels
* small_value<D> and root_small_pair<D> prefetch their own operand-bank line with _MM_HINT_T0, i.e.
* normal allocation in every cache level. That bank is an 11.4 MB per-round sequential stream, and
* its normal-priority L2 allocations evict the round's random x gathers - the same pollution the
* big-row path already avoids by marking its 57.6 MB column/weight stream _MM_HINT_NTA. This post
* makes the small-row operand prefetch _MM_HINT_NTA as well, so BOTH sequential streams are
* evict-first and the ~2.4 MB random gather working set keeps its residency. No arithmetic, no
* layout, no row/slot order, no prune and no degree class changes; the four hot loops are
* instruction-for-instruction identical apart from the hint operand.
* JUDGE MEASUREMENT (custom-test channel, in-program rdtscp phase split, n=2^20 m=2^23, ablation and
* arm priced in both positions inside one translation unit): round loop 644.47 M -> 641.47 M ticks,
* build 124.0 -> 114.2 M and setup 154.3 -> 138.5 M are the same in both positions. Two sibling
* probes are NOT shipped because they measured WORSE: deepening both sequential prefetch leads
* (644.6 -> 648.8 M) and a zero-uop 4 KiB-column ablation used only to price the gather wall
* (644.6 -> 298.0 M, i.e. the random gathers are 54% of the round loop).
* LOCAL/JUDGE EXACTNESS: a prefetch hint cannot change a value. Gated at full scale (n=2^20,
* m=2^23) by whole-output memcmp against the shipped 180737 body, and at small scale against an
* INDEPENDENT naive COO 20-round oracle over m=0, n=1 self-loop, dense duplicate pairs with zero
* weights, one giant row, and a skew mixture.
* LICENCE COMPLIANCE: duck.ac public submissions; upstream states no separate software licence, so
* every body is used by named citation under the site's public-submission convention. Every body
* used here is this account's own accepted submission or is cited by exact URL, and the complete
* inherited citation/Credit chain and LICENSE statements are retained verbatim below, unmodified.
*/
/* [agg4 spmv20 2026-11-19 seat-s3f] ACCOUNT saffah_v41f1017_agg4. PURPOSE: put our board entry on
* the best body that exists for this lane before the seat ends.
* WHAT WAS USED: saffah_codex62a_agg6 https://duck.ac/submission/180576 (Accepted, 495,723.123 us,
* 2026-11-19 14:20:43) reproduced VERBATIM apart from this notice. That body already carries our own
* https://duck.ac/submission/180528 (the chain build that deletes the COO->CSR counting pass, plus
* the split of the record arena from the packed CSR vectors) together with that account's
* interleaved short rows, multi-way decode, first-round filtering and four-way banked bucketing.
* This post is an adoption: it changes no arithmetic, no layout and no scheduling; our own two
* attempts to add to this body were measured and are NOT included (a cross-block _mm_prefetch(T0)
* arm priced 886.53 M vs 919.75 M in-call cycles yet landed +3,189 us WORSE officially at
* 498,912.590, and deleting every prefetch from this body measured +81.5 M in-call cycles worse).
* LOCAL/JUDGE CHECK: the eight-fixture exactness gate (our base vs this body vs an INDEPENDENT naive
* 20-round COO oracle over m=0, n=1 self-loops, dense duplicates with zero weights, one giant row,
* few-row many-duplicate, skew-76/24) is EXACT on all eight, and the judge-side in-call A/B measured
* 0 element mismatches against our own 180528 body at n=2^20 m=2^23 (8,387,711 records).
* LICENCE COMPLIANCE: duck.ac public submissions; no separate upstream software licence is stated,
* so every body is used by named citation under the site's public-submission convention, and the
* complete inherited citation/Credit chain and LICENSE statements are retained verbatim below.
*/
/* saffah_v41f1017_agg4 https://duck.ac/submission/180528 提供分块链、一次读边、分配独立边容量的实现。saffah_codex62a_agg6 https://duck.ac/submission/180477 提供交错短行、多路解码、首轮过滤。继承的出处及许可分别列于下方。 */
/* saffah_codex62a_agg6 https://duck.ac/submission/180086 提供通过的四路边分桶;同账号 https://duck.ac/submission/179902 提供成对短行操作数格式。原始作者与许可保留如下。 */
/* saffah_codex62a_agg6 https://duck.ac/submission/179816 supplies four banked COO counters, packed records and the accepted numerical engine. saffah_v41f1017_agg4 https://duck.ac/submission/179729 supplies the short-row gather implementation. Original references and license notices follow. */
/* 本账号 saffah_codex62a_agg6 https://duck.ac/submission/177682 的逐桶直接转置,https://duck.ac/submission/177596 的边计算边压缩,以及 https://duck.ac/submission/177620 的末轮映射写回。原位保序八路过滤参考 saffah_codex61s_agg5 https://duck.ac/submission/170563 ,保留其余公开出处与许可。 */
/* References: saffah_codex61s_agg5, https://duck.ac/submission/170563 , the public numerical graph or matrix implementation. All original attributions and notices follow. */
/* References / 引用: saffah_v41f1017_agg4
https://duck.ac/submission/169853: complete Accepted scale20 builder,
short-row input-load expression, transposed weights and20-power engine;
retain every inherited account, exact URL, used-content and legal notice.
Own saffah_codex61s_agg5 https://duck.ac/submission/170220:
initial paired-group implementation, retaining all cited parent lineage.
Approach / 思路: Restrict paired execution to degreeD<=2;
retain the parent's original one-group kernel at larger degrees so its
unrolled indexed loads do not compete for registers across two batches.
Additionally, Evaluate two adjacent eight-row short batches in the same
degree loop with independent accumulators. Expose both groups' indexed
input loads before either output store, then write their sixteen contiguous
results. Preserve each row's exact edge order and modulo32 arithmetic,
all incomplete tails, long-row kernels and final-coordinate output.
Experiment purpose: full n2^20/m2^24 independent20-power COO,
duplicates/zeros/empty rows, unchanged inputs/64 guards, then immediate
official runtime; no local speed admission decision.
*/
/* [agg4 spmv20 2026-11-17] PURPOSE: experimental adoption submission posted to improve our own
* fastest accepted row on this problem (previous best: sid 168386, 563,576.0 us). It cannot close
* the lane by itself -- an adoption lands at ~T while the strict bar a fresh post faces is
* 0.99*T+1 -- but it recovers ~36,370 us and brings the residual need from 41,641 us to ~5,271 us.
* Adopted source: saffah_codex_6a_agg3, https://duck.ac/submission/169246 (Accepted, 527,206.151 us,
* 2026-11-17). Reproduced verbatim with its own citation block intact below; a value-preserving
* skeleton diff had shown it is our own 168386 body plus four edits (vpgatherdd -> 8 scalar loads
* in small_value<D>; prune_big() in-place compaction of long-row runs; a scalar short-row path in
* step; and the r==0 call site). All original author/source/licence notices are retained below.
*/
/* References: own saffah_codex_6a_agg3 https://duck.ac/submission/168825 supplies the complete scale20 solver and independent short-row scalar loads; all original author/source/license notices remain. Own https://duck.ac/submission/168782 supplies the invariant that initially empty rows remain zero after the first power; its expensive window rebuild is not used here. */
/* Idea: after the first full product, stably compact only existing large-row column/weight runs in place, removing zero weights and columns in the known zero suffix. Update each RootRow end while preserving its start, target, permutation and original allocation. Eight-lane mask compression uses a constexpr permutation table, no graph rebuild or allocation. The remaining19 products use the shorter rows; newly short/empty rows have an exact scalar path. Small-row batches retain their already correct accesses. Purpose: delete repeated zero contributions with one bounded pass and verify all20 outputs against independent COO products, including sparse-active and guard cases. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/168386 supplies the accepted short-row batching and long-row prefetch solver. Its full original author/source/license notices are retained below; no separate software license is stated. */
/* Idea: form each short-row eight-lane input vector using eight independently addressable scalar loads and vector inserts, replacing the hardware gather instruction. Keep all weights, transposed layout, long-row kernels, modulo32 sums and all20 iterations unchanged. Purpose: full independent20-round oracle/input/guard verification and official performance comparison of short-row load scheduling. */
/* ===== v25 改动区 / Changes(相对本账号 #167862;一处:把 evict-first 覆盖补全到全流)=====
* [1] 基线:本账号 saffah_v41f1017_agg4 提交 #167862 <https://duck.ac/submission/167862>
* —— spmv20,615,408 us,AC(排行榜 rank 2)。本件即其逐字基线;其完整
* Citation/Credit 链、机制说明与 LICENSE 声明原样保留在下方,未改动一行。
* [2] 机制来源(继续预取):saffah_codex_6a_agg3 提交 #168065
* <https://duck.ac/submission/168065>,spmv20,577,172 us,AC(rank 1)。
* 该公开提交与本函数逐 token 相同,唯一代码差异是 32 宽大行循环体内追加 4 条
* `_mm_prefetch(...,_MM_HINT_NTA)`(column/weight 的 +64/+80 元素,即下一块的两条
* cache line),把"顺序流 Evict-First"从行入口的一次性标注改成循环内持续标注。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释原样保留。
* ===== 本发改动(补全缓存策略覆盖,数值逐位不变;不改任何算法/求和顺序)=====
* 【改动 1】32 宽大行循环入口:对 column/weight 的前两块(+0/+16/+32/+48 元素,即
* 本行前两次迭代的两条 line)各发 NTA。原基线只标了 +32 一条 line,因此每行前
* 两次迭代的数据从未被标为 evict-first。
* 【改动 2】8 宽尾循环(度数 8..31 的行几乎只走这条路径,此前完全无预取):每次
* 迭代对 column/weight 的下一条 line(+16 元素)发 NTA,使该路径逐 line 覆盖。
* 【改动 3】不足 8 条的 mask 尾:对 column+end-8 / weight+end-8 发 NTA。
* 【动机】本判机 L3 = 6 MiB,20 轮中随机 gather 的 x/y 各 4 MiB。每轮顺序扫过
* column+weight = 134 MB 会把 x 冲掉。NTA 让这两条顺序流 evict-first,#168065 证明
* 该机制有效(−6.2 %)。但它的覆盖仍有三处缺口:行入口前两次迭代、8..31 度行、
* mask 尾 —— 合计约占每轮流量的 17 %+#。本件只把这三点补齐,不改变任何数值。
* ============================================================================================ */
/* ===== v24 改动区 / Changes(相对本账号 #165842;一处:缓存策略,数值逐位不变)=====
* [1] 本账号 saffah_v41f1017_agg4 提交 #165842 <https://duck.ac/submission/165842>
* —— spmv20,623,478 us,AC,本件逐字基线;其完整 Citation/Credit 链与
* LICENSE 说明原样保留在下方。
* [2] 机制来源:本账号在 spmv23 上的提交 #167826 <https://duck.ac/submission/167826>
* (7,279,000 us,AC,strict met)。该件在同一 family 上用
* `_mm_prefetch(..., _MM_HINT_NTA)` 标注"随机工作集旁边的大顺序流",
* 官方实测从 #167808 的 7,515,000 us 降到 7,279,000 us(−236,000 us,−3.14 %)。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释原样保留。
* ===== 本发改动(缓存策略:把顺序流标为 evict-first,gather 一行不动)=====
* 【改动 1】sparse_degree::small_value<D> 的小行批处理循环内,对 q.column / q.weight
* 的下一行(+16 个 unsigned = 64 B,即下一条 cache line)各发一次
* _MM_HINT_NTA 预取。
* 【改动 2】sparse_degree::step 的大行 32 宽主循环入口前,对 column+p+32 /
* weight+p+32(下 128 B,即 2 条 cache line)各发一次 _MM_HINT_NTA 预取。
* 【动机】本判机 L3 = 6 MiB,而 20 轮里随机访问的 x/y 各为 4 MiB;每轮顺序扫过
* column+weight = 134 MB 会把它们从 L3 冲掉。把这两条大顺序流标为"取入 L1、
* L2/L3 evict-first",让随机工作集留在 L3。与 spmv23 的 #167826 同机制、同位置
* (那里也是标顺序流、不标 gather),该件官方实测 −3.14 %。
* 【试验目的】一句话:验证 spmv23 的 eviction-policy 杠杆是否转移到 spmv20;
* 输出必须逐位不变(预取不改变任何数据或求和顺序)。
* ============================================================ */
/* ===== v23 改动区 / Changes(相对 #165103 + 本方 v18)=====
* [1] saffah_codex_6a_agg3 提交 #165103 <https://duck.ac/submission/165103>,625,924 us,AC。
* [2] 本账号 saffah_v41f1017_agg4 提交 #165585 v18 <https://duck.ac/submission/165585>,
* 623,753 us,AC。两件的完整 Citation/Credit 链与 LICENSE 说明原样保留在下方。
* ===== 本发改动(一处:step 内层循环的读序)=====
* 【改动】20 轮大行内层每次处理 32 条记录:原来按 column/weight 交替取 8 条,
* 改成先把 column 的 128 字节取完(4×32B),再取 weight 的 128 字节。
* 【动机】本判机对访问突发长度极敏感(本账号 v18 实测:resort 输出按 64 字节成组
* 写即换来 623,753 us,比 #165103 快 2,171 us;#165103 自己用 FIFO 16→64 条
* 记录的写突发也换来 ~25 ms)。本发把同一"按数组成组、拉长突发"的做法用到
* 20 轮的读侧。
* 【试验目的】一句话:验证读侧成组是否也影响计时;输出必须逐位不变。
* ============================================================ */
/* ===== v18 改动区 / Changes(相对 saffah_codex_6a_agg3 #165103:resort 输出按 64 字节成组)=====
* [1] saffah_codex_6a_agg3 提交 #165103 <https://duck.ac/submission/165103> —— spmv20,
* 625,924 us,AC。本件在其逐字基线上只做下述一处改动;其完整 Citation/Credit 链
* 与 LICENSE 说明原样保留在下方。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用;上游 Credit
* 链与注释逐字保留。
* ===== 本发改动(一处:resort 的 NT 存序)=====
* 【改动】resort 输出阶段由每 8 条记录写 32 字节(column 与 weight 交替),改成每
* 16 条记录一次:先把 64 字节写入 column(2×32B),再写 64 字节到 weight。
* 【动机】#165103 自己的实测显示本判机对写突发长度极敏感(同一 packed 记录流下
* FIFO 16→32→64 条记录,即每次冲刷 128→256→512 字节,共换来 650,702 → 625,924 us)。
* 本发把同样的"成组写长突发"用到 resort 的最终数组写出上(每次 64 字节整行)。
* 【试验目的】一句话:验证 resort 的 NT 写突发长度是否也是本判机上的计时因素;
* 输出必须逐位不变。
* ============================================================ */
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/165088 supplies the complete packed-record11bit/FIFO32 implementation, preserving its original references and license notices below. */
/* Idea: flush64 packed records as a contiguous512-byte write run, reducing stream switching at each bucket while retaining full-line padding and all20 exact products. Purpose: test this larger-batch locality tradeoff with full17/20 output validation and official timing on the remaining0.056-percent gap. */
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/165038 supplies the validated packed64-bit/FIFO32/single256-bit implementation. Its inherited notices remain. */
/* Idea: use the successful32-record contiguous write batches with11-bit buckets at scale20, keeping the fewer-stream configuration from our accepted https://duck.ac/submission/164716. All20 products remain exact. Purpose: verify fullscale17/20 and measure the live newly reopened scale20 target. */
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/165020 supplies the complete packed-record single-vector implementation, retaining every inherited source/license notice below. */
/* Idea: double each packed-record bucket FIFO to32 records, so each scatter flush writes256 contiguous bytes while preserving padding-derived offsets and all20 modulo products. Purpose: reduce partial write-combiner switching, checking independent full outputs and guards before official timing. */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/164991 supplies the alias-safe single256-bit memory instruction wrappers below, including its citation chain to saffah_v41f1017_agg4 https://duck.ac/submission/164782 and https://duck.ac/submission/164866. Our saffah_codex_6a_agg3 https://duck.ac/submission/164716 supplies the packed-record builder, masked tail and direct-final SpMV implementation. All inherited citations and license statements remain. */
/* Idea: combine single-vector moves with our one-stream packed64-bit bucket builder, retaining9-bit buckets at scale17. The builder deinterleaves the packed records only while writing their final sorted arrays; masked high-degree remainders and direct final output retain all20 exact products. Purpose: test this combination at full scale17 with independent COO products, all guards and official measurement. */
/* References / 引用:
saffah_codex_6a_agg3 https://duck.ac/submission/163059: copied complete Accepted
algorithm; preserve all inherited account references, source URLs and legal
notices below. saffah_v41f1017_agg4
https://duck.ac/submission/164782 and https://duck.ac/submission/164866:
reference the single-ymm-move workaround idea for GCC9 generic splitting;
independently implement precise alias-safe32-byte memory operands without
a global memory clobber. These public Duck snippets state no extra license;
inherited source/legal notices remain intact.
Approach / 思路: Replace unaligned AVX integer/float/double loads/stores with
explicit single256-bit vmovdqu/vmovups/vmovupd instructions. Each operand
exposes exactly32 bytes through an alias-safe char range, preserving memory
dependencies and unaligned addresses. This prevents GCC9 from splitting one
vector access into128-bit moves and insert/extract instructions. All numeric
operations, bounds, graph/transform schedules and output equations remain.
Experiment purpose: complete independent correctness/output/guard checks,
then immediate official timing, with no local performance admission filter.
*/
/* Approach and experiment: Prefer _MM_HINT_T1 prefetches on the sparse multiply data reused across repeated applications to reduce refetch traffic. Measure the normal problem function on duck.ac. */
/* Approach and experiment: Transpose all rows of exact degree up to 15 into independently vectorized batches. Longer rows use grouped vector dot products. Measure the preprocessing cost and twenty-product duration. */
/* Experiment: Retain the cited leader's original bucket size and streaming-cache hints while measuring the preceding independent kernel change. */
/* Approach and experiment: Scatter the weighted COO records to cache-resident bucket scratch once, then emit each row directly into its final numeric representation. Degrees through 15 go straight to transposed batches. Heavy rows receive aligned contiguous runs padded with zero weights to eliminate masked tails. Measure conversion and the twenty products. */
/* Approach and experiment: Emit the final degree-fifteen SELL layout from weighted COO buckets of 64 records, then compact dead columns in the first actual product on rows of at least 16 entries. Read every original weight for the first iteration. Keep every product in the degree permutation and gather the original final coordinate order in one streaming pass. Test the three phases together. */
/* Approach and experiment: Count heavy rows from the prefix of the degree histogram and allocate their records to that exact size. Initialize their destination only when emitting final packed weights. Every product uses permuted coordinates; omit the short-row inverse lists and all temporary initial row metadata. Scatter initial values alongside the permutation itself. Allocate both short row planes in a single zero-initialized bank. Measure direct emission and saved writes. */
/* Approach and experiment: Use 4 independent bucket histograms in the initial COO scan. Load the row coordinates into separate scalar count banks. Build packed row, column, and weight records eight at once, then enqueue each complete numeric record into its ordinary FIFO. Flush 128 packed entries per bucket and measure the two preprocessing scans. */
/* Approach and experiment: Combine four independent COO bucket counters and a 128-entry packed edge FIFO with a complete eight-row gather in each short dot product. Compute 2 independent groups in the same degree loop for rows with at most 2 edges, prefetching the two input planes 2 vectors ahead. Measure the build and all twenty applications together. */
/* 将四路分桶和 128 项边记录缓冲与短行成对查找合并。度数不超过 15 的每批八行把八个真实列号及对应权重置于同一条缓存行,独立寄存器批次覆盖到度数 4。成对记录起点按 64 字节对齐。实验整图转换及全部二十轮的数值用时。 */
/* [agg4 spmv20 2026-11-19 seat-s3b] ACCOUNT saffah_v41f1017_agg4. PURPOSE: close lane spmv20.
* This body is our own accepted https://duck.ac/submission/179729 (513,586 us, 2026-11-19 11:34:00)
* verbatim - its short-row batches fetch eight already-contiguous columns with one AVX2 gather -
* PLUS (a) our seat-s3 chain build, which deletes the COO->CSR counting pass, and (b) THIS seat's
* one-line allocation split, which is what makes (a) pay on the judge.
* WHAT WAS USED, all of it our own account's work: (1) 179729 as the base engine (gather short-row
* batches, dead smallrows[] removed); (2) the chain build: the counting pass exists only to learn
* each bucket's edge count for contiguous layout, so instead each bucket scatters into a chain of
* BS=2048-record blocks taken from one arena in arrival order, and the histogram/pack passes walk
* the chain; the per-bucket zero-weight padding to a 64-record boundary is rebuilt INSIDE the chain,
* so the record sequence, row degrees, degree permutation, prune_big, the fifteen small classes with
* the live clamp, the gather engine and the direct final output are all exactly the base's, and the
* arena bound sum_b ceil(cnt_b/BS) <= m/BS + bins is unconditional (no fallback path).
* (3) THE SPLIT: the chain build formerly shared one capacity (m + BS*bins) between the record arena
* and the packed CSR arrays column[]/weight[], which made those two vectors 4 MB larger than the
* base's and perturbed the round loop. Now the record arena keeps m + BS*bins while column[] and
* weight[] are sized exactly as the base sizes them, m + (FLUSH-1)*bins.
* WHY, measured on the judge with an in-call rdtscp cycle oracle (custom-test channel, one process,
* same fixture, n=2^19 m=2^23, 8,387,455 records): base 823.98 M cycles; chain as shipped by seat-s3
* 792.51 M (build 172.12->117.60 M, setup 132.59->128.20 M, round loop 519.24->546.69 M); chain +
* this split 760.18 M (build 117.45 M, setup 123.21 M, round loop 519.50 M). So the round-loop loss
* was a pure allocation draw, not the mechanism: the permutation hash is IDENTICAL in all three arms
* (11661568971667222391), the round loop therefore runs on byte-identical data, and restoring the
* base's vector sizes restores the base's round-loop cost exactly. Net -7.74 % of the whole frame.
* LOCAL/JUDGE CHECK for this exact file: the lane's eight-fixture exactness gate - base vs this body
* vs an INDEPENDENT naive 20-round COO oracle, fixtures m=0, n=1 all-self-loop, dense duplicates with
* zero weights, one giant row, few-row many-duplicate, skew-76/24 mixture - reports 0/0/0 on every
* fixture (GATE EXACT). Judge-side, this body's output was compared element-by-element against the
* base at n=2^19 m=2^23 (0 mismatches) and at the problem's official geometry n=2^20 m=2^24
* (16,774,041 records, 2 reps, 0 mismatches). Only allocation sizes changed in the last edit.
* LICENCE COMPLIANCE: duck.ac public submissions; upstream states no separate software licence, so
* everything is used by named citation under the site's public-submission convention. Every body
* used here is our own account's accepted submission and the complete inherited citation/Credit
* chain and LICENSE statements are retained verbatim below, unmodified.
* LINEAGE retained verbatim below: our 179729 -> our 179370 (verbatim adoption of
* saffah_codex62a_agg6 https://duck.ac/submission/178781, 521,400.774 us, 2026-11-19 08:35:32)
* and its entire citation chain.
*/
/* Own idea: in the short-row batches one vector step fetches its eight operand values with eight
scalar loads and eight lane inserts (_mm256_setr_epi32 from memory). Those eight columns are already
stored contiguously for that edge ordinal, so a single AVX2 gather over the identical eight
addresses returns the same eight values. Same addresses, same order, same product. The dead
smallrows[] deletion is retained. Purpose: price the gather form on the judge; verified at FULL
scale (n=2^20, m=2^23, whole-output memcmp) and on the 8-fixture oracle gate. */
/* [agg4 spmv20 2026-11-19 seat-s2] PURPOSE: adoption submission of the current rival leader, posted
* first to replace our own two-and-a-half-day-stale accepted best (our sid 169853, 526,909.0 us,
* 2026-11-17 21:06:20, https://duck.ac/submission/169853) before any further experiment on this lane.
* It cannot close the lane by itself: any post re-stamps us newest, so the operative bar becomes
* STRICT 0.99*T+1 = 516,187.99 us, while this verbatim adoption lands near T = 521,401 us, leaving a
* residual need of about 5,213 us (1.0 %). Purpose line: adopt the rival body unchanged (apart from
* this notice) to obtain our own judge price for it and to rebuild the lane baseline honestly.
* Adopted source: saffah_codex62a_agg6, https://duck.ac/submission/178781 (Accepted, 521,400.774 us,
* 2026-11-19 08:35:32), reproduced verbatim with its entire citation chain intact below. T's own
* parent is the same account's https://duck.ac/submission/177682 (Accepted, 525,508.036 us,
* 2026-11-19 05:36:49), NOT one of our sids; the lineage beneath it is codex61s_agg5
* https://duck.ac/submission/170563 (526,818.705 us), which itself descends from our 169853.
* A comment-stripped diff of T against its parent 177682 shows exactly two mechanisms, both
* value-preserving and both absent from our 169853 body: (1) prune_big() switched from per-row
* in-place compaction to a GLOBAL cursor compaction that packs all surviving long-row records
* contiguously (unsigned cursor=0; rows[ri].begin=cursor; ...; rows[ri].end=cursor=out), so the 19
* remaining products stream a footprint with the dead 8 % (empty-destination columns, zero weights)
* actually removed instead of merely skipped; (2) after the first product, when live<n, the fifteen
* small-batch column arrays are clamped with _mm256_min_epu32(idx,live), confining every short-row
* gather to the [0,live] prefix whose slot live was just memset to zero (x[live..n)==0), i.e. the
* same confinement prune_big already gives the long rows. Neither edit changes any per-row summation
* order; arithmetic stays mod 2^32. Below, the deeper lineage (170563->177682) additionally carries
* degree classes 8->15, scratch 37->49/36->48 buffers, and pack_direct(), which deletes the old
* sparse_stream::resort pass and its intermediate staging array.
* Local check before posting: gcc 9.3.0 -O2 -std=c++17 -static (no -march) compiles clean; the
* value gate against a 20-round naive COO oracle over all 8 fixtures (empty m, one giant row,
* duplicate/self-loop/zero-weight, scale-12/14/16 families) reports EXACT for both this body and
* our 169853 body, with zero differing outputs between them.
* All original author/source/licence notices are retained unchanged below.
*/
/* Approach and experiment: Compact surviving weighted edges across heavy-row boundaries into one sequential run after the first exact product. Keep each sparse row at its exact length. Map originally empty short-row input columns to one verified zero element for the remaining nineteen products. Measure numerical scan locality and the one-time preparation cost. */
/* 建图仅遍历输入边一次,让每桶的 64 项缓冲链入 2048 项块。一组八条记录向量拆出行列及权重。遍历完整块链生成行长度。重排阶段按链扫描,再与本账号短行数据布局及首轮过滤内核结合,核对二十步真实乘积并测量全程。 */
/* 第一轮以后,对原度至少 1 的八行短组逐通道删去恒为零的列和零权边,将余下边顶齐到同组前端。原来的八个输出目标及顺序保持,后十九轮只处理该组真实最大深度。顺序扫过每一组的连续索引权重对。实验稀疏归约、顺序写回和索引压紧的整体用时。 */
/* 在计算原始行的度分类时,同时累加每类 CSR 所需的补齐边数,由此直接划分全局边数组。根行按其数值向量编号写入对应类的连续区间;十九轮重复乘法的根行走向与结果向量保持同一顺序。对数度区间再分 1 档,装包使用 mixed 写入。实验长行分组、相近循环长度及顺序发布对全部二十次幂的效果。 */
/* 消除长行目录中的目标和原行字段,长行乘积按实际物理编号连续写入。通过完整二十轮参考乘积核对,用官方评测衡量元数据流量和排序开销。 */
/* 本次实验在每八条真实边的三块连续输入上先用常数掩码选出同一字段,再对已合并的向量调整通道。以源下标的原始通道顺序对齐目标和权重。将两组解包结果直接送入各桶以省去高低半块拼接。核对两个规模的二十次数值乘积与输入末尾。 */
#include<immintrin.h>
static __attribute__((always_inline,target("avx")))inline __m256i root_single256_li(const __m256i*p){__m256i v;__asm__("vmovdqu %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_si(__m256i*p,__m256i v){__asm__("vmovdqu %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256d root_single256_ld(const double*p){__m256d v;__asm__("vmovupd %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sd(double*p,__m256d v){__asm__("vmovupd %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256 root_single256_lf(const float*p){__m256 v;__asm__("vmovups %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sf(float*p,__m256 v){__asm__("vmovups %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
#define _mm256_loadu_si256 root_single256_li
#define _mm256_storeu_si256 root_single256_si
#define _mm256_loadu_pd root_single256_ld
#define _mm256_storeu_pd root_single256_sd
#define _mm256_loadu_ps root_single256_lf
#define _mm256_storeu_ps root_single256_sf
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/164626 supplies the accepted masked-tail/direct-final SpMV20 implementation. Original source authors, links and license notices are retained below. */
/* Idea: use one packed 64-bit key/weight stream for bucket scatter and counting scratch, then deinterleave eight records into the final column/weight arrays while applying the permutation. This halves simultaneous scatter-page streams and keeps key/weight scratch writes together. Purpose: measure whether improved builder locality exceeds the small SIMD deinterleave and separate allocation costs, preserving all 20 exact modulo-2^32 products. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/164584 supplies the complete2048-row bucket builder, scratch/SIMD NT sorting, and original attribution/license chain below. Our saffah_codex_6a_agg3 https://duck.ac/submission/163059 supplies the masked in-row remainder and original-index final-step techniques. */
/* Idea: combine11-bit buckets with safe masked gathers for the1..7 remaining edges of each big row. Write the twentieth iteration directly to original vertex positions, including small-row SIMD batches, avoiding the separate full permutation-gather copy at finish. Purpose: remove scalar tails and a memory pass while retaining all20 exact modulo2^32 steps; validate complete17/20 scales and input guards before official timing. */
/* ===== v11 改动区 / Changes(相对 #164484:只改分桶位数与容量算式)=====
* [1] 本账号 saffah_v41f1017_agg4 提交 #164484
* <https://duck.ac/submission/164484> —— spmv20,669,618 us,AC,本件逐字基线。
* #164484 的完整引用链(#164300 → saffah_codex_6a_agg3 #164057 → 本账号 #163835
* → 更早的 #162840/#162473/#162247 等)与其 LICENSE 说明原样保留在下方。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释逐字保留。
* ===== 本发改动(一处 dial,两行)=====
* 【改动】SPARSE_BUCKET_BITS 10 → 11:建表分桶数 1024 → 512(每桶 2048 行),
* sparse_power20 里的 capacity 算式同步改成 (n+2047)>>11。
* 动机(本地子阶段实测):build 的 scatter 同时向 2 条数组 × 1024 个桶 =
* 2048 个不同 4 KB 页做 NT 流式写,远超 L2 TLB 的 1536 项;桶数减半后并发写页
* 降到 1024。prof23 子阶段计时(同进程 2 rep,rep1 稳态)scatter 145.8 → 116.0 ms。
* 代价:resort 的 scratch 窗口从 712 KB 增到约 1.4 MB,本地(L2=1 MB)scatter 变慢;
* 本地整段相抵后仍为净正。
* 【试验目的】一句话:把建表 scatter 的并发写流数减半(换取更少 TLB 未命中),
* 在 512 桶下重新平衡 resort 窗口;输出必须逐位不变。
* 【本地实测】gcc 9.3.0 -O2 -std=c++17 -static(无 -march),scale-20 参考矩阵
* (mat20_s12345.bin):build 325.3/322.1 → 298.8/298.1 ms;resort 130.8/131.5 →
* 151.9/149.2 ms;build+perm+resort+collect 合计 502 → 494 ms(2/2 同向)。
* 另用 prof23 单独计 build 子阶段:scatter 145.8 → 116.0 ms,count/hist 不变。
* 校验:checksum 7c698083579c962a 与 #164484 完全相同;20 轮朴素 COO oracle 在
* scale 20 上 bad=0;n=4096/m=0、n=1/m=0、n=1 自环、零权重、全自环、
* 单巨行 n=300/m=300,000、重复边 n=64/m=300,000 全部 EXACT;nm -u 与 #164484 相同。
* 【正确性】分桶位数只改变 build/resort 内部的分块方式与 padding 数量;CSR 行偏移
* 仍由同一套计数排序得到,每行求和顺序不变 ⇒ 模 2^32 结果逐位相同。
* ============================================================ */
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/164032 supplies the SIMD permuted complete-line NT copyback and20-step engine; original author/source/license notices follow. Our PageRank https://duck.ac/submission/163714 uses largest-bucket scratch sizing, transferred here. */
/* Idea: size the two scratch arrays from the largest actual bucket, allowing every bucket to use counting scatter and the SIMD streaming copyback. This removes cycle-swap work for large buckets without changing record ordering or arithmetic. Purpose: test deleting the overflow-bucket fallback; validate full17/20 outputs, inputs and guards. All runtime work is normally measured. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/163835 supplies the complete SIMD-remapped CSR builder and accepted20-step SpMV engine. All inherited author/source/license notices follow. */
/* Idea: write the scratch-resorted column/weight arrays with aligned AVX2 non-temporal stores, using at most15 scalar alignment records and complete64-byte output lines and an sfence before consumers. The large arrays are read after all buckets finish; avoid allocating their cache lines during the streaming copy. Purpose: reduce actual copyback traffic while preserving every record, output and input. Validate fullscale17/20 all20 products against independent COO multiplication. */
/* ===== v4 引用区 / References(相对 #163079 只改 resort 拷回循环)=====
* [1] 本账号 saffah_v41f1017_agg4 提交 #163079 <https://duck.ac/submission/163079>
* spmv20,687,850 us,AC —— 本件的基线:除下方"改动区"一处外逐字节相同;
* #163079 的完整引用链(其 [1][2][3] 与本文件内的 Credit 注释)原样保留。
* 基线来源:saffah_codex_6a_agg3 #162840/#162845 的 small-row 8 行批处理、
* 4 链 AVX2 gather/RootRow 引擎、分桶 COO→CSR builder;saffah_codex61s_agg5
* #162638/#162640/#162639、saffah_codex_6a_agg3 #162473、saffah_codex_maker
* #162247 的活跃行/分桶方法;本账号 #162982/#162998/#162979 的整行 64 B NT
* 写回与 scratch 计数排序;#163004 的 16 条整行 scatter。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释原样保留。
* ===== 改动区(本发,相对 #163079;一处,数值逐位不变)=====
* 【改动】sparse_stream::resort 的拷回循环:每条记录一次标量随机读
* `perm[sc[k]>>10]`(16.7M 次 4 B 随机 load、每记录约 8 条 uop)→ 每 8 条一次
* `_mm256_i32gather_epi32(perm,...)` 加两条 32 B 向量存储(column / weight)。
* perm 映射与记录顺序均未变,故输出逐位相同;桶首与桶长按 16 条对齐,8 宽循环
* 必然整除,标量尾循环仅作保险。>SC 的原地环置换回退路径未动。
* 【试验目的】一句话:把压缩阶段 16.7M 次随机标量 load 换成 2.1M 次 8 通道
* hardware gather,减少 load 端口占用并提高随机访问 MLP;其它阶段一律不动。
* 【本地实测】同进程 ABBA(gcc 9.3.0 -O2 -std=c++17 -static,同一组缓冲,
* scale-20 缓存矩阵,4 对交替先后顺序):resort 阶段 mean 181.5 → 144.7 ms
* (−20.3%),min 144.8 → 121.7 ms(−16.0%),4/4 对同向。
* 校验:column/weight 全部 16,785,024 条逐字节 memcmp 相等;整程序 checksum
* ec79c31b8ed8d831 与 #163079 完全相同。
* 【正确性】模 2^32 意义下每行求和顺序不变;gcc 9.3.0 -O2 -std=c++17 -static
* (无 -march)编译通过,无新增外部依赖。
* ============================================================ */
/* ===== 引用区 / References =====
* [1] duck.ac 用户 saffah_codex_6a_agg3,提交 #162840
* <https://duck.ac/submission/162840> —— spmv20 最快的对手提交(T = 767.109 ms)。
* 本件逐字继承其完整已接受代码:small-row 度类 1..7 的 8 行批处理引擎、4 链
* AVX2 gather/RootRow 引擎、分桶 COO→CSR builder、度置换与空行后缀处理。
* 其正文内部的 Credit 链(saffah_codex61s_agg5 #162638/#162640/#162639、
* saffah_codex_6a_agg3 #162473、saffah_codex_maker #162247)原样保留在下方。
* [2] 本账号 saffah_v41f1017_agg4 的 spmv20 提交 #162998
* <https://duck.ac/submission/162998>(= #162982 <https://duck.ac/submission/162982>,
* 在 [1] 之上加上"整条 cache line 的 NT flush(bits=10)")。本件的 build 之外的
* 全部代码(度置换、小度行批处理、大行 4 链引擎、空行后缀)与该提交逐字节相同。
* [3] 本账号在 spmv17 上的提交 #162979 <https://duck.ac/submission/162979>:桶内计数
* 排序由"原地环置换"改为"scratch 窗口 + 顺序拷回",同一 family、同一机制,
* 官方实测该提交把 spmv17 从 73,935 µs 降到 63,279 µs(−14.4%)。本件把该机制
* 搬到 spmv20 的 scale-20(m=2^24)尺寸上。
* LICENSE:duck.ac 公开提交,上游未附独立许可证声明 ⇒ 按具名引用使用,遵守该站
* 公开提交的引用惯例;上游 Credit 链与注释原样保留。
* ===== 改动区(本发,相对 #162998;两处,均在 COO→CSR build / 列置换阶段)=====
* 【改动 1】sparse_stream::build 的桶内计数排序:原地环置换(每条记录 2 次随机读 +
* 2 次随机写 + 一个不可预测分支,见下方保留的 fallback 路径)→ 先 scatter 进一个
* ≤65536 条记录的 scratch 窗口、再顺序拷回(两条顺序流)。装不下窗口的桶自动回退
* 到原地环置换,因此任意输入都正确。
* 【改动 2】删掉桶内循环末尾那条独立的 `column[p] >>= bits` 全数组遍历(m=2^24 时
* 是 64 MB 读 + 64 MB 写),把 >>bits 折进紧随其后的 map_columns 的读取表达式
* (`perm[column[p]>>bits]`)。scale-17 时该遍历是 cache-hot(当时实测为 0),
* scale-20 的 column 有 64 MB,远超 6 MB L3,因此这一步是一次实打实的 DRAM 流量。
* bits=10、FLUSH=16 整行 NT 写、度置换、小度行 8 行批处理、大行 4 链引擎、
* 空行后缀处理全部未动(sparse_degree 部分与 #162998 逐字节相同)。
* 【试验目的】一句话:删掉 build 桶内排序的随机环追逐,换成两条顺序流,缩短
* COO→CSR 的建表时间,同时保持输出逐位不变(模 2^32 结合律下每行求和不变)。
* 【本地实测】同进程交错 A/B(gcc 9.3.0 -O2 -std=c++17 -static,同一组缓冲、同一
* scale-20 矩阵,6 rep,改动 1):build 阶段 min 412.2 ms → 294.7 ms(−28.5%),
* mean 614.9 → 473.4 ms(−23.0%)。bits=9 的同机制版本反而更差(min 369.9 ms,
* 桶数翻倍导致 padding 与桶数开销上升)。改动 2 再删掉 128 MB 的 DRAM 流量。
* 整程序 A/B 在被 20+ 并发进程占满的 16 核共享机上无法分辨(同一臂自身 rep 间
* 波动达 48%),故只据同阶段 A/B 判断。
* 【正确性】与题面朴素 COO 参考实现(20 轮)逐元素比对:n=2^12/m=2^16 随机、
* n=2^16/m=2^20 随机(含重复边、自环、零权重)、单巨行 n=700/m=200,000(触发
* scratch 回退)、m=0 全部 EXACT;scale 20 参考矩阵(mat20.bin)输出校验和
* 7c698083579c962a 与本账号已接受的 #162998 完全一致(1,048,576 个输出全等)。
* gcc 9.3.0 -O2 -std=c++17 -static(无 -march)编译通过,无新增外部依赖。
* ============================================================ */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/162638 (scale17), https://duck.ac/submission/162640 (scale20), https://duck.ac/submission/162639 (scale23) supply the accepted4-chain gather and RootRow descriptor engine, extending our saffah_codex_6a_agg3 https://duck.ac/submission/162473 active-row method. The complete source body is used here; original maker attribution and notices follow. No independent software license is declared. */
/* References / 引用:
saffah_codex_6a_agg3 https://duck.ac/submission/162473 : copied its complete
Accepted active-row, degree-permuted, bucketed COO-to-CSR solver; its original
maker source attribution is preserved below. No separate license is stated.
Approach / 思路: Process32 consecutive CSR edges with4 independent
AVX2 gather/multiply/accumulate chains. Load all independent index/weight
vectors first, then gather and accumulate, reducing the accumulators once per
row. Before the20 multiplies, collect each nonempty row begin/end/target in one12-byte descriptor. Replace the dependent row-ID to offset/perm loads by one contiguous descriptor stream, preserving the original row/edge order. Use the vector path for8-element rows as well. Associativity modulo2^32
preserves every result including duplicate edges and zero weights.
Experiment purpose / 试验目的: Validate all20 rounds against an independent
COO oracle on ten complete fixtures including fullscale17 edge count and
fullscale23 vertex width, empty rows, duplicate edges and self-loops. Then
immediately submit officially; local speed does not filter a candidate.
Fresh Pending 文件个数==0, sharedHTTP2, exact qualification stop apply.
*/
/* References: saffah_codex_maker https://duck.ac/submission/162247 supplies the complete exact bucketed COO-to-CSR builder, degree coordinate permutation and AVX2 gather multiply. The public source carries no independent software-license statement; attribution is retained. */
/* Idea: create separate permutation classes for each stored degree1..7, retaining descending coarse classes for larger rows. Transpose the small rows into8-row batches with one index/weight vector per edge ordinal. Their target coordinates are contiguous, so AVX2 gathers/multiplies accumulate8 independent row answers and store directly, with no horizontal reduction or scalar per-edge loop. Pad only the final batch with zero weights and use a masked output store. Large rows keep the existing4-chain engine; empty rows keep the verified zero-suffix handling. Extra storage is at most7*n*8 bytes plus small batch padding. Purpose: eliminate small-row control and reduction costs across20 rounds while preserving duplicates, zero weights and modulo2^32 arithmetic exactly. */
#include <bits/stdc++.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#ifndef DUCK_SPMV_EDGE_DEFINED
#define DUCK_SPMV_EDGE_DEFINED
struct Edge { unsigned src,dst,weight; };
#endif
static_assert(sizeof(unsigned)==4 && sizeof(Edge)==12,"Duck32-bit COO ABI");
#include <immintrin.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
static constexpr unsigned SPARSE_BUCKET_BITS=11;
static __attribute__((noinline)) void thp_hint(void*p,size_t bytes){
#if defined(MADV_HUGEPAGE)
if(!p||bytes<65536u)return;uintptr_t a=(uintptr_t)p&~(uintptr_t)4095u;size_t o=(size_t)((uintptr_t)p-a);
size_t l=(bytes+o+4095u)&~(size_t)4095u;(void)madvise((void*)a,l,MADV_HUGEPAGE);
#else
(void)p;(void)bytes;
#endif
}
namespace sparse_stream {
enum{FLUSH=64,BS=8192};
struct Blocks{unsigned bins,nblk;unsigned*head;unsigned*nxt;unsigned*cnt;};
struct alignas(64) Fifo{uint64_t data[FLUSH];};
using Fv=__m256i;template<unsigned F>static inline Fv field(Fv a,Fv b,Fv c){if constexpr(F==0)return _mm256_blend_epi32(_mm256_blend_epi32(a,b,146),c,36);if constexpr(F==1)return _mm256_permutevar8x32_epi32(_mm256_blend_epi32(_mm256_blend_epi32(a,b,36),c,73),_mm256_setr_epi32(1,2,3,4,5,6,7,0));return _mm256_permutevar8x32_epi32(_mm256_blend_epi32(_mm256_blend_epi32(a,b,73),c,146),_mm256_setr_epi32(2,3,4,5,6,7,0,1));}
template<class GetSource,class GetRecord>
static unsigned build(unsigned n,unsigned m,GetSource get_source,GetRecord get_record,
unsigned*offset,uint64_t*record,Blocks&bl,const Edge*get_record_address){
constexpr unsigned bits=SPARSE_BUCKET_BITS,rows=1u<<bits,mask=rows-1;
const unsigned bins=(n+mask)>>bits;
if(bl.bins<bins||bl.nblk<1)abort();
unsigned*head=(unsigned*)calloc(bins,4),*tail=(unsigned*)calloc(bins,4),
*cur=(unsigned*)calloc(bins,4),*cnt=(unsigned*)calloc(bins,4),
*nxt=(unsigned*)calloc((size_t)bl.nblk,4);
unsigned char*fill=(unsigned char*)calloc(bins,1);Fifo*fifo=nullptr;
void*fbase=nullptr;if(posix_memalign(&fbase,4096,(size_t)bins*sizeof(Fifo)+8192)||!head||!tail||!cur||!cnt||!nxt||!fill)abort();fifo=(Fifo*)((char*)fbase+2048);thp_hint(fbase,(size_t)bins*sizeof(Fifo)+8192);
unsigned nblk=0;
auto put=[&](unsigned b,uint64_t val){unsigned j=fill[b];fifo[b].data[j]=val;
if(j+1==FLUSH){unsigned o=cur[b];
if(!tail[b]||o+FLUSH>BS){unsigned k2=nblk++;if(k2>=bl.nblk)abort();nxt[k2]=0;o=cur[b]=0;
if(tail[b])nxt[tail[b]-1]=k2+1;else head[b]=k2+1;tail[b]=k2+1;}
uint64_t*d=record+(size_t)(tail[b]-1)*BS+o;
for(unsigned k=0;k<FLUSH;k+=4)_mm256_stream_si256((__m256i*)(d+k),_mm256_load_si256((const __m256i*)(fifo[b].data+k)));
cur[b]=o+FLUSH;cnt[b]+=FLUSH;fill[b]=0;
}else fill[b]=j+1;
};unsigned e=0;for(;e+8<=m;e+=8){const Fv*ptr=(const Fv*)(&get_record_address[e]);auto a=_mm256_loadu_si256(ptr),b=_mm256_loadu_si256(ptr+1),c=_mm256_loadu_si256(ptr+2);auto src=field<0>(a,b,c),dst=field<1>(a,b,c),wt=field<2>(a,b,c),idx=_mm256_or_si256(_mm256_slli_epi32(dst,bits),_mm256_and_si256(src,_mm256_set1_epi32(mask)));auto l=_mm256_unpacklo_epi32(idx,wt),u=_mm256_unpackhi_epi32(idx,wt);alignas(32)uint64_t val[8];alignas(32)unsigned bk[8];_mm256_store_si256((Fv*)val,l);_mm256_store_si256((Fv*)(val+4),u);_mm256_store_si256((Fv*)bk,_mm256_srli_epi32(src,bits));put(bk[0],val[0]);put(bk[3],val[5]);put(bk[6],val[6]);put(bk[1],val[1]);put(bk[4],val[2]);put(bk[7],val[7]);put(bk[2],val[4]);put(bk[5],val[3]);}for(;e<m;e++){auto v=get_record(e);put(v.src>>bits,(uint64_t(v.weight)<<32)|((v.dst<<bits)|(v.src&mask)));}
_mm_sfence();
for(unsigned b=0;b<bins;b++){unsigned j=fill[b];if(j){if(!tail[b]||cur[b]+j>BS){unsigned q=nblk++;if(q>=bl.nblk)abort();nxt[q]=0;if(tail[b])nxt[tail[b]-1]=q+1;else head[b]=q+1;tail[b]=q+1;cur[b]=0;}unsigned k2=tail[b]-1;memcpy(record+(size_t)k2*BS+cur[b],fifo[b].data,(size_t)j*8);cur[b]+=j;cnt[b]+=j;}}
for(unsigned b=0;b<bins;b++){unsigned pad=(0u-cnt[b])&63u;if(pad){unsigned rowcount=std::min(rows,n-(b<<bits));uint64_t*p=record+(size_t)(tail[b]-1)*BS+cur[b];for(unsigned i=0;i<pad;i++)p[i]=rowcount-1;cur[b]+=pad;cnt[b]+=pad;}}
unsigned gbase=0;
for(unsigned b=0;b<bins;b++){unsigned histogram[rows]={},rowbase=b<<bits,rowcount=std::min(rows,n-rowbase),done=0;
for(unsigned k2=head[b];k2;k2=nxt[k2-1]){const uint64_t*p=record+(size_t)(k2-1)*BS;unsigned lim=BS;if(lim>cnt[b]-done)lim=cnt[b]-done;
for(unsigned i=0;i<lim;i++)++histogram[unsigned(p[i])&mask];done+=lim;}
unsigned first=gbase;for(unsigned r=0;r<rowcount;r++){offset[rowbase+r]=first;first+=histogram[r];}gbase=first;
}
offset[n]=gbase;
bl.head=head;bl.nxt=nxt;bl.cnt=cnt;
free(fbase);free(fill);free(tail);free(cur);
return gbase;
}
static void resort(unsigned n,unsigned used,const unsigned*offset,const uint64_t*record,unsigned*column,unsigned*weight,const unsigned*perm){
constexpr unsigned bits=SPARSE_BUCKET_BITS,rows=1u<<bits,mask=rows-1;const unsigned bins=(n+mask)>>bits;
unsigned SC=1;for(unsigned b=0;b<bins;b++){unsigned begin=offset[b<<bits],stop=(b+1<bins)?offset[(b+1)<<bits]:used;SC=std::max(SC,stop-begin);}uint64_t*scratch=(uint64_t*)malloc((size_t)SC*8);if(!scratch)abort();
for(unsigned b=0;b<bins;b++){unsigned next[rows],rowbase=b<<bits,begin=offset[rowbase],stop=(b+1<bins)?offset[rowbase+rows]:used,rowcount=std::min(rows,n-rowbase);for(unsigned r=0;r<rowcount;r++)next[r]=offset[rowbase+r];
for(unsigned p=begin;p<stop;p++){uint64_t v=record[p];scratch[next[unsigned(v)&mask]++-begin]=v;}
unsigned p=begin;
for(;p+16<=stop;p+=16){
unsigned j=p-begin;
__m256i a0=_mm256_loadu_si256((const __m256i*)(scratch+j)),b0=_mm256_loadu_si256((const __m256i*)(scratch+j+4));
__m256i a1=_mm256_loadu_si256((const __m256i*)(scratch+j+8)),b1=_mm256_loadu_si256((const __m256i*)(scratch+j+12));
a0=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(a0,0xd8),0xd8);b0=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(b0,0xd8),0xd8);
a1=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(a1,0xd8),0xd8);b1=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(b1,0xd8),0xd8);
__m256i key0=_mm256_srli_epi32(_mm256_permute2x128_si256(a0,b0,0x20),bits),val0=_mm256_permute2x128_si256(a0,b0,0x31);
__m256i key1=_mm256_srli_epi32(_mm256_permute2x128_si256(a1,b1,0x20),bits),val1=_mm256_permute2x128_si256(a1,b1,0x31);
__m256i c0=_mm256_i32gather_epi32((const int*)perm,key0,4),c1=_mm256_i32gather_epi32((const int*)perm,key1,4);
_mm256_stream_si256((__m256i*)(column+p),c0);
_mm256_stream_si256((__m256i*)(column+p+8),c1);
_mm256_stream_si256((__m256i*)(weight+p),val0);
_mm256_stream_si256((__m256i*)(weight+p+8),val1);
}
for(;p+8<=stop;p+=8){unsigned j=p-begin;
__m256i a=_mm256_loadu_si256((const __m256i*)(scratch+j)),b=_mm256_loadu_si256((const __m256i*)(scratch+j+4));
a=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(a,0xd8),0xd8);b=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(b,0xd8),0xd8);
__m256i key=_mm256_srli_epi32(_mm256_permute2x128_si256(a,b,0x20),bits),val=_mm256_permute2x128_si256(a,b,0x31);
_mm256_stream_si256((__m256i*)(column+p),_mm256_i32gather_epi32((const int*)perm,key,4));_mm256_stream_si256((__m256i*)(weight+p),val);
}
for(;p<stop;p++){uint64_t v=scratch[p-begin];column[p]=perm[unsigned(v)>>bits];weight[p]=v>>32;}
}
_mm_sfence();free(scratch);
}
}
namespace sparse_degree {
struct RootRow{unsigned begin,end;};
static unsigned degree_bin(unsigned d){return d<=15?d:43u-(unsigned)__builtin_clz(d);}
static unsigned make_permutation(unsigned n,const unsigned*offset,unsigned*perm,unsigned*hist,const unsigned*x,unsigned*vec,unsigned*edgeStart){
unsigned next[49];for(unsigned b=0;b<49;b++)hist[b]=0;
for(unsigned i=0;i<n;++i){unsigned degree=offset[i+1]-offset[i],g=degree_bin(degree);++hist[g];if(degree>=16)edgeStart[g]+=(degree+7)&~7u;}unsigned placed=0;for(unsigned g=49;g-->16;){unsigned nedge=edgeStart[g];edgeStart[g]=placed;placed+=nedge;}
unsigned first=0;for(unsigned b=49;b-->0;){next[b]=first;first+=hist[b];}
unsigned nb=next[15];for(unsigned i=0;i<n;++i){unsigned b=degree_bin(offset[i+1]-offset[i]),q=next[b]++;perm[i]=q;vec[q]=x[i];}
return nb;
}
struct Compression{int perm[256][8];constexpr Compression():perm{}{for(unsigned m=0;m<256;m++){unsigned t=0;for(unsigned k=0;k<8;k++)if(m&(1u<<k))perm[m][t++]=k;}}};alignas(32)static constexpr Compression compression{};
static void prune_big(unsigned count,RootRow*rows,unsigned*column,unsigned*weight,unsigned live){
const __m256i limit=_mm256_set1_epi32(live),zero=_mm256_setzero_si256();
for(unsigned ri=0;ri<count;ri++){unsigned p=rows[ri].begin,end=rows[ri].end,out=p;
for(;p+8<=end;p+=8){__m256i ix=_mm256_loadu_si256((const __m256i*)(column+p)),w=_mm256_loadu_si256((const __m256i*)(weight+p));
__m256i keep=_mm256_andnot_si256(_mm256_cmpeq_epi32(w,zero),_mm256_cmpgt_epi32(limit,ix));unsigned mask=_mm256_movemask_ps(_mm256_castsi256_ps(keep));
if(mask==255){if(out!=p){_mm256_storeu_si256((__m256i*)(column+out),ix);_mm256_storeu_si256((__m256i*)(weight+out),w);}out+=8;}
else if(mask){__m256i pi=_mm256_load_si256((const __m256i*)compression.perm[mask]);_mm256_storeu_si256((__m256i*)(column+out),_mm256_permutevar8x32_epi32(ix,pi));_mm256_storeu_si256((__m256i*)(weight+out),_mm256_permutevar8x32_epi32(w,pi));out+=__builtin_popcount(mask);}
}
for(;p<end;p++)if(column[p]<live&&weight[p]){column[out]=column[p];weight[out++]=weight[p];}
rows[ri].end=out;
}
}
static inline __m256i qadd(__m256i a,__m256i b){asm("vpaddd %1,%0,%0":"+x"(a):"x"(b));return a;}
static __attribute__((noinline,noclone)) void step(
unsigned count,const RootRow*rows,const unsigned*offset,const unsigned*column,const unsigned*weight,
const unsigned*perm,const unsigned*x,unsigned*y,bool last){
for(unsigned ri=0;ri<count;++ri){
unsigned p=rows[ri].begin,end=rows[ri].end,sum=0;
if(end-p<8){for(;p<end;p++)sum+=weight[p]*x[column[p]];y[ri]=sum;continue;}
{
__m256i acc0=_mm256_setzero_si256();
__m256i acc1=_mm256_setzero_si256();
__m256i acc2=_mm256_setzero_si256();
__m256i acc3=_mm256_setzero_si256();
_mm_prefetch((const char*)(column+p),_MM_HINT_NTA);_mm_prefetch((const char*)(column+p+16),_MM_HINT_NTA);_mm_prefetch((const char*)(column+p+32),_MM_HINT_NTA);_mm_prefetch((const char*)(column+p+48),_MM_HINT_NTA);
_mm_prefetch((const char*)(weight+p),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+16),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+32),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+48),_MM_HINT_NTA);
for(;p+32<=end;p+=32){
_mm_prefetch((const char*)(column+p+64),_MM_HINT_NTA);_mm_prefetch((const char*)(column+p+80),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+64),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+80),_MM_HINT_NTA);
__m256i index0=_mm256_loadu_si256((const __m256i*)(column+p+0));
__m256i index1=_mm256_loadu_si256((const __m256i*)(column+p+8));
__m256i index2=_mm256_loadu_si256((const __m256i*)(column+p+16));
__m256i index3=_mm256_loadu_si256((const __m256i*)(column+p+24));
__m256i weights0=_mm256_loadu_si256((const __m256i*)(weight+p+0));
__m256i weights1=_mm256_loadu_si256((const __m256i*)(weight+p+8));
__m256i weights2=_mm256_loadu_si256((const __m256i*)(weight+p+16));
__m256i weights3=_mm256_loadu_si256((const __m256i*)(weight+p+24));
__m256i selected0=_mm256_i32gather_epi32((const int*)x,index0,4);acc0=qadd(acc0,_mm256_mullo_epi32(weights0,selected0));
__m256i selected1=_mm256_i32gather_epi32((const int*)x,index1,4);acc1=qadd(acc1,_mm256_mullo_epi32(weights1,selected1));
__m256i selected2=_mm256_i32gather_epi32((const int*)x,index2,4);acc2=qadd(acc2,_mm256_mullo_epi32(weights2,selected2));
__m256i selected3=_mm256_i32gather_epi32((const int*)x,index3,4);acc3=qadd(acc3,_mm256_mullo_epi32(weights3,selected3));
}
for(;p+8<=end;p+=8){__m256i index=_mm256_loadu_si256((const __m256i*)(column+p)),w=_mm256_loadu_si256((const __m256i*)(weight+p));acc0=qadd(acc0,_mm256_mullo_epi32(w,_mm256_i32gather_epi32((const int*)x,index,4)));}
if(p<end){_mm_prefetch((const char*)(column+end-8),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+end-8),_MM_HINT_NTA);unsigned rem=end-p;__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(rem),_mm256_setr_epi32(7,6,5,4,3,2,1,0));__m256i ix=_mm256_loadu_si256((const __m256i*)(column+end-8)),w=_mm256_loadu_si256((const __m256i*)(weight+end-8));__m256i v=_mm256_mask_i32gather_epi32(_mm256_setzero_si256(),(const int*)x,ix,mask,4);acc0=qadd(acc0,_mm256_mullo_epi32(w,v));}p=end;
__m256i acc=acc0;
acc=_mm256_add_epi32(acc,acc1);
acc=_mm256_add_epi32(acc,acc2);
acc=_mm256_add_epi32(acc,acc3);
__m128i s=_mm_add_epi32(_mm256_castsi256_si128(acc),_mm256_extracti128_si256(acc,1));
s=_mm_add_epi32(s,_mm_shuffle_epi32(s,0x4e));
s=_mm_add_epi32(s,_mm_shuffle_epi32(s,0xb1));
sum=(unsigned)_mm_cvtsi128_si32(s);
}
y[ri]=sum;
}
}
struct SmallBatch{unsigned count,begin;unsigned*column,*weight,*original;};
template<unsigned D> static inline __m256i small_value(const SmallBatch&q,unsigned group,const unsigned*x){__m256i acc=_mm256_setzero_si256();
#pragma GCC unroll 8
for(unsigned k=0;k<D;k++){size_t at=(size_t)(group*D+k)*8;__m256i w=_mm256_loadu_si256((const __m256i*)(D<=15?q.column+2*at+8:q.weight+at));__m256i vals=_mm256_i32gather_epi32((const int*)x,_mm256_loadu_si256((const __m256i*)(D<=15?q.column+2*at:q.column+at)),4);acc=_mm256_add_epi32(acc,_mm256_mullo_epi32(w,vals));if constexpr(D<=15)_mm_prefetch((const char*)(q.column+2*at+256),_MM_HINT_NTA);}return acc;}template<unsigned D>static inline void root_small_pair(const SmallBatch&q,unsigned group,const unsigned*x,unsigned*y){
__m256i root_acc0=_mm256_setzero_si256(),root_acc1=_mm256_setzero_si256();
#pragma GCC unroll 8
for(unsigned k=0;k<D;k++){
{size_t at=(size_t)(group*D+k)*8;__m256i w=_mm256_loadu_si256((const __m256i*)(D<=15?q.column+2*at+8:q.weight+at));__m256i vals=_mm256_i32gather_epi32((const int*)x,_mm256_loadu_si256((const __m256i*)(D<=15?q.column+2*at:q.column+at)),4);root_acc0=_mm256_add_epi32(root_acc0,_mm256_mullo_epi32(w,vals));if constexpr(D<=15)_mm_prefetch((const char*)(q.column+2*at+256),_MM_HINT_NTA);}
{size_t at=(size_t)((group+1)*D+k)*8;__m256i w=_mm256_loadu_si256((const __m256i*)(D<=15?q.column+2*at+8:q.weight+at));__m256i vals=_mm256_i32gather_epi32((const int*)x,_mm256_loadu_si256((const __m256i*)(D<=15?q.column+2*at:q.column+at)),4);root_acc1=_mm256_add_epi32(root_acc1,_mm256_mullo_epi32(w,vals));if constexpr(D<=15)_mm_prefetch((const char*)(q.column+2*at+256),_MM_HINT_NTA);}
}
_mm256_storeu_si256((__m256i*)y,root_acc0);_mm256_storeu_si256((__m256i*)(y+8),root_acc1);
}
template<unsigned D> static void small_step(const SmallBatch&q,const unsigned*x,unsigned*y){unsigned full=q.count/8;if constexpr(D<=4){unsigned g=0;for(;g+2<=full;g+=2)root_small_pair<D>(q,g,x,y+q.begin+g*8);for(;g<full;g++)_mm256_storeu_si256((__m256i*)(y+q.begin+g*8),small_value<D>(q,g,x));}else{for(unsigned g=0;g<full;g++)_mm256_storeu_si256((__m256i*)(y+q.begin+g*8),small_value<D>(q,g,x));}if(q.count&7){__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(q.count&7),_mm256_setr_epi32(0,1,2,3,4,5,6,7));_mm256_maskstore_epi32((int*)(y+q.begin+full*8),mask,small_value<D>(q,full,x));}}
template<unsigned D> static void small_final(const SmallBatch&q,const unsigned*x,unsigned*y){for(unsigned g=0;g<(q.count+7)/8;g++){alignas(32)unsigned v[8];_mm256_store_si256((__m256i*)v,small_value<D>(q,g,x));unsigned nr=q.count-g*8;if(nr>8)nr=8;for(unsigned l=0;l<nr;l++)y[q.original[g*8+l]]=v[l];}}
static void pack_direct(unsigned n,unsigned used,const unsigned*off,const uint64_t*in,unsigned*column,unsigned*weight,const unsigned*perm,RootRow*rows,SmallBatch*small,const sparse_stream::Blocks&bl,unsigned*edgeStart){
constexpr unsigned bits=SPARSE_BUCKET_BITS,R=1u<<bits,mask=R-1,BS=sparse_stream::BS;unsigned bins=(n+mask)>>bits,maxsize=1;
for(unsigned b=0;b<bins;b++)maxsize=std::max(maxsize,bl.cnt[b]);
uint64_t* tmp=(uint64_t*)malloc((size_t)(maxsize+8)*8);if(!tmp)abort();thp_hint(tmp,(size_t)(maxsize+8)*8);unsigned pos=0,big=0;
for(unsigned b=0;b<bins;b++){
unsigned base=b*R,nr=std::min(R,n-base),start=off[base],next[R],done=0;
for(unsigned r=0;r<nr;r++)next[r]=off[base+r]-start;
for(unsigned k2=bl.head[b];k2;k2=bl.nxt[k2-1]){const uint64_t*p=in+(size_t)(k2-1)*BS;unsigned lim=BS;if(lim>bl.cnt[b]-done)lim=bl.cnt[b]-done;
for(unsigned i=0;i<lim;i++){uint64_t v=p[i];tmp[next[(unsigned)v&mask]++]=v;}done+=lim;}
if(done!=bl.cnt[b])abort();
for(unsigned r=0;r<nr;r++){unsigned row=base+r,d=off[row+1]-off[row];if(!d)continue;const uint64_t* src=tmp+(off[row]-start);
if(d<=15){SmallBatch&q=small[d];unsigned slot=perm[row]-q.begin,g=slot>>3,l=slot&7;
for(unsigned j=0;j<d;j++){uint64_t v=src[j];unsigned vcol=perm[(unsigned)v>>bits],vweight=(unsigned)(v>>32);size_t dst=(size_t)(g*d+j)*8+l;if(d<=15){size_t t=(size_t)(g*d+j)*16+l;q.column[t]=vcol;q.column[t+8]=vweight;}else{q.column[dst]=vcol;q.weight[dst]=vweight;}}continue;}
unsigned tag=degree_bin(d),at=perm[row];pos=edgeStart[tag];RootRow&dst=rows[at];dst.begin=pos;unsigned j=0;
for(;j+32<=d;j+=32){
__m256i a=_mm256_loadu_si256((const __m256i*)(src+j)),b=_mm256_loadu_si256((const __m256i*)(src+j+4));
a=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(a,0xd8),0xd8);b=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(b,0xd8),0xd8);
__m256i k0=_mm256_srli_epi32(_mm256_permute2x128_si256(a,b,0x20),bits),w0=_mm256_permute2x128_si256(a,b,0x31);
__m256i c=_mm256_loadu_si256((const __m256i*)(src+j+8)),e=_mm256_loadu_si256((const __m256i*)(src+j+12));
c=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(c,0xd8),0xd8);e=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(e,0xd8),0xd8);
__m256i k1=_mm256_srli_epi32(_mm256_permute2x128_si256(c,e,0x20),bits),w1=_mm256_permute2x128_si256(c,e,0x31);
__m256i f=_mm256_loadu_si256((const __m256i*)(src+j+16)),g=_mm256_loadu_si256((const __m256i*)(src+j+20));
f=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(f,0xd8),0xd8);g=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(g,0xd8),0xd8);
__m256i k2=_mm256_srli_epi32(_mm256_permute2x128_si256(f,g,0x20),bits),w2=_mm256_permute2x128_si256(f,g,0x31);
__m256i h=_mm256_loadu_si256((const __m256i*)(src+j+24)),q=_mm256_loadu_si256((const __m256i*)(src+j+28));
h=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(h,0xd8),0xd8);q=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(q,0xd8),0xd8);
__m256i k3=_mm256_srli_epi32(_mm256_permute2x128_si256(h,q,0x20),bits),w3=_mm256_permute2x128_si256(h,q,0x31);
__m256i cv0=_mm256_i32gather_epi32((const int*)perm,k0,4),cv1=_mm256_i32gather_epi32((const int*)perm,k1,4);
__m256i cv2=_mm256_i32gather_epi32((const int*)perm,k2,4),cv3=_mm256_i32gather_epi32((const int*)perm,k3,4);
if(d<128){_mm256_store_si256((__m256i*)(column+pos+j),cv0);_mm256_store_si256((__m256i*)(column+pos+j+8),cv1);_mm256_store_si256((__m256i*)(column+pos+j+16),cv2);_mm256_store_si256((__m256i*)(column+pos+j+24),cv3);
_mm256_store_si256((__m256i*)(weight+pos+j),w0);_mm256_store_si256((__m256i*)(weight+pos+j+8),w1);_mm256_store_si256((__m256i*)(weight+pos+j+16),w2);_mm256_store_si256((__m256i*)(weight+pos+j+24),w3);}
else{_mm256_stream_si256((__m256i*)(column+pos+j),cv0);_mm256_stream_si256((__m256i*)(column+pos+j+8),cv1);_mm256_stream_si256((__m256i*)(column+pos+j+16),cv2);_mm256_stream_si256((__m256i*)(column+pos+j+24),cv3);
_mm256_stream_si256((__m256i*)(weight+pos+j),w0);_mm256_stream_si256((__m256i*)(weight+pos+j+8),w1);_mm256_stream_si256((__m256i*)(weight+pos+j+16),w2);_mm256_stream_si256((__m256i*)(weight+pos+j+24),w3);}
}
for(;j+8<=d;j+=8){__m256i a=_mm256_loadu_si256((const __m256i*)(src+j)),b=_mm256_loadu_si256((const __m256i*)(src+j+4));
a=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(a,0xd8),0xd8);b=_mm256_permute4x64_epi64(_mm256_shuffle_epi32(b,0xd8),0xd8);
__m256i key=_mm256_srli_epi32(_mm256_permute2x128_si256(a,b,0x20),bits),w=_mm256_permute2x128_si256(a,b,0x31);
auto cv=_mm256_i32gather_epi32((const int*)perm,key,4);if(d<128){_mm256_store_si256((__m256i*)(column+pos+j),cv);_mm256_store_si256((__m256i*)(weight+pos+j),w);}else{_mm256_stream_si256((__m256i*)(column+pos+j),cv);_mm256_stream_si256((__m256i*)(weight+pos+j),w);}
}
for(;j<d;j++){uint64_t v=src[j];column[pos+j]=perm[(unsigned)v>>bits];weight[pos+j]=(unsigned)(v>>32);}
unsigned rounded=(d+7)&~7u;for(;j<rounded;j++){column[pos+j]=0;weight[pos+j]=0;}dst.end=pos+rounded;edgeStart[tag]+=rounded;
}
}_mm_sfence();free(tmp);
}
static void first_pruned(unsigned n,RootRow*rows,unsigned*col,unsigned*wt,unsigned live,const unsigned*x,unsigned*y){
const __m256i limit=_mm256_set1_epi32(live),z=_mm256_setzero_si256();
for(unsigned row=0;row<n;row++){
unsigned low=rows[row].begin,stop=rows[row].end,p=low,write=low;
auto run=[&](auto filter){
__m256i a0=z,a1=z;
auto group=[&](unsigned position,__m256i&acc){
_mm_prefetch((const char*)(col+position+128),_MM_HINT_NTA);_mm_prefetch((const char*)(wt+position+128),_MM_HINT_NTA);auto ix=_mm256_loadu_si256((const __m256i*)(col+position)),w=_mm256_loadu_si256((const __m256i*)(wt+position));
acc=_mm256_add_epi32(acc,_mm256_mullo_epi32(w,_mm256_i32gather_epi32((const int*)x,ix,4)));
if constexpr(decltype(filter)::value){
__m256i good=_mm256_andnot_si256(_mm256_cmpeq_epi32(w,z),_mm256_cmpgt_epi32(limit,ix));unsigned mask=_mm256_movemask_ps(_mm256_castsi256_ps(good));
if(mask==255){if(write!=position){_mm256_storeu_si256((__m256i*)(col+write),ix);_mm256_storeu_si256((__m256i*)(wt+write),w);}write+=8;}
else if(mask){auto order=_mm256_load_si256((const __m256i*)compression.perm[mask]);_mm256_storeu_si256((__m256i*)(col+write),_mm256_permutevar8x32_epi32(ix,order));_mm256_storeu_si256((__m256i*)(wt+write),_mm256_permutevar8x32_epi32(w,order));write+=__builtin_popcount(mask);}
}
};
for(;p+16<=stop;p+=16){group(p,a0);group(p+8,a1);}
if(p+8<=stop){group(p,a0);p+=8;}
auto total=_mm256_add_epi32(a0,a1);auto halves=_mm_add_epi32(_mm256_castsi256_si128(total),_mm256_extracti128_si256(total,1));halves=_mm_hadd_epi32(halves,halves);halves=_mm_hadd_epi32(halves,halves);unsigned sum=_mm_cvtsi128_si32(halves);
for(;p<stop;p++){unsigned ix=col[p],w=wt[p];sum+=w*x[ix];if constexpr(decltype(filter)::value){if(ix<live&&w){col[write]=ix;wt[write++]=w;}}}
y[row]=sum;if constexpr(decltype(filter)::value)rows[row].end=write;
};
if(stop-low>=16)run(std::true_type{});else run(std::false_type{});
}
}
struct GroupRuns{std::vector<unsigned> offset;};
static void trim_group_depth(SmallBatch&q,unsigned d,unsigned live,GroupRuns&dir){
unsigned groups=(q.count+7)/8,write=0;dir.offset.resize(groups+1);
alignas(32) unsigned scratch[16][16];memset(scratch,0,sizeof(scratch));
for(unsigned g=0;g<groups;g++){
unsigned (*const tmp)[16]=scratch;unsigned used[8]{},deep=0;
const unsigned* src=q.column+16*size_t(g)*d;
for(unsigned j=0;j<d;j++)for(unsigned lane=0;lane<8;lane++){unsigned col=src[16*j+lane],w=src[16*j+8+lane];if(col<live&&w){unsigned k=used[lane]++;tmp[k][lane]=col;tmp[k][8+lane]=w;if(k+1>deep)deep=k+1;}}
dir.offset[g]=write;
for(unsigned j=0;j<deep;j++,write+=16){_mm256_storeu_si256((__m256i*)(q.column+write),_mm256_load_si256((const __m256i*)tmp[j]));_mm256_storeu_si256((__m256i*)(q.column+write+8),_mm256_load_si256((const __m256i*)(tmp[j]+8)));}
if(deep)memset(scratch,0,(size_t)deep*64u);
}
dir.offset[groups]=write;
}
static void run_groups(const SmallBatch&q,const GroupRuns&dir,const unsigned*x,unsigned*y){
unsigned groups=(q.count+7)/8; const unsigned *ahead=q.column+dir.offset[groups];
for(unsigned g=0;g<groups;g++){const unsigned *start=q.column+dir.offset[g],*stop=q.column+dir.offset[g+1];__m256i acc=_mm256_setzero_si256();
auto add=[&](const unsigned*t){auto id=_mm256_loadu_si256((const __m256i*)t),w=_mm256_loadu_si256((const __m256i*)(t+8)),v=_mm256_i32gather_epi32((const int*)x,id,4);acc=_mm256_add_epi32(acc,_mm256_mullo_epi32(v,w));};
_mm_prefetch((const char*)(start+128),_MM_HINT_NTA);
for(auto*t=start;t!=stop;t+=16)add(t);
unsigned row=g*8;if(row+8<=q.count)_mm256_storeu_si256((__m256i*)(y+q.begin+row),acc);else{auto mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(q.count-row),_mm256_setr_epi32(0,1,2,3,4,5,6,7));_mm256_maskstore_epi32((int*)(y+q.begin+row),mask,acc);}
}}
static void twenty(unsigned n,unsigned m,const unsigned*offset,unsigned*column,
unsigned*weight,uint64_t*record,const unsigned*x,unsigned*out,
unsigned*temp,unsigned*perm,const sparse_stream::Blocks&bl){
unsigned hist[49];unsigned*smallrows=(unsigned*)malloc((size_t)(n?n:1)*4);if(!smallrows)abort();thp_hint(smallrows,(size_t)(n?n:1)*4);
unsigned edgeStart[49]{};unsigned big_count=make_permutation(n,offset,perm,hist,x,smallrows,edgeStart);
RootRow*rows=(RootRow*)malloc((size_t)(big_count?big_count:1)*sizeof(RootRow));if(!rows)abort();thp_hint(rows,(size_t)(big_count?big_count:1)*sizeof(RootRow));
SmallBatch small[16]{};GroupRuns grouped[16];unsigned live=n-hist[0];
{unsigned f=0;for(int b=48;b>=0;--b){if(b>=1&&b<=15)small[b].begin=f;f+=hist[b];}}
for(unsigned d=1;d<=15;d++)small[d].count=hist[d];
size_t slots=0;for(unsigned d=1;d<=15;d++)slots+=((size_t)(small[d].count+7)/8)*8*d;
void*bankptr=nullptr;if(posix_memalign(&bankptr,64,(slots?slots:8)*8))abort();unsigned*rowbanks=(unsigned*)bankptr;if(!rowbanks)abort();thp_hint(bankptr,(slots?slots:8)*8);size_t consumed=0;
for(unsigned d=1;d<=15;d++){small[d].column=rowbanks+2*consumed;small[d].weight=small[d].column+((size_t)(small[d].count+7)/8)*8*d;consumed+=((size_t)(small[d].count+7)/8)*8*d;}for(unsigned d=1;d<=15;d++){unsigned padcnt=small[d].count;if((padcnt&7u)==0)continue;unsigned last=padcnt>>3,firstlane=padcnt-(last<<3);unsigned*bpad=small[d].column;for(unsigned jj=0;jj<d;jj++){unsigned*blk=bpad+(size_t)(last*d+jj)*16;for(unsigned ll=firstlane;ll<8u;ll++){blk[ll]=0u;blk[ll+8u]=0u;}}}
pack_direct(n,m,offset,record,column,weight,perm,rows,small,bl,edgeStart);free(record);
memset(temp+live,0,(size_t)(n-live)*4);const unsigned*cur=smallrows;
for(unsigned r=0;r<20;r++){bool last=false;unsigned*dst=(r&1)?smallrows:temp;if(!r)first_pruned(big_count,rows,column,weight,live,cur,dst);else step(big_count,rows,offset,column,weight,perm,cur,dst,last);
if(last){small_final<1>(small[1],cur,dst);small_final<2>(small[2],cur,dst);small_final<3>(small[3],cur,dst);small_final<4>(small[4],cur,dst);small_final<5>(small[5],cur,dst);small_final<6>(small[6],cur,dst);small_final<7>(small[7],cur,dst);small_final<8>(small[8],cur,dst);small_final<9>(small[9],cur,dst);small_final<10>(small[10],cur,dst);small_final<11>(small[11],cur,dst);small_final<12>(small[12],cur,dst);small_final<13>(small[13],cur,dst);small_final<14>(small[14],cur,dst);small_final<15>(small[15],cur,dst);}else{if(r)run_groups(small[1],grouped[1],cur,dst);else small_step<1>(small[1],cur,dst);if(r)run_groups(small[2],grouped[2],cur,dst);else small_step<2>(small[2],cur,dst);if(r)run_groups(small[3],grouped[3],cur,dst);else small_step<3>(small[3],cur,dst);if(r)run_groups(small[4],grouped[4],cur,dst);else small_step<4>(small[4],cur,dst);if(r)run_groups(small[5],grouped[5],cur,dst);else small_step<5>(small[5],cur,dst);if(r)run_groups(small[6],grouped[6],cur,dst);else small_step<6>(small[6],cur,dst);if(r)run_groups(small[7],grouped[7],cur,dst);else small_step<7>(small[7],cur,dst);if(r)run_groups(small[8],grouped[8],cur,dst);else small_step<8>(small[8],cur,dst);if(r)run_groups(small[9],grouped[9],cur,dst);else small_step<9>(small[9],cur,dst);if(r)run_groups(small[10],grouped[10],cur,dst);else small_step<10>(small[10],cur,dst);if(r)run_groups(small[11],grouped[11],cur,dst);else small_step<11>(small[11],cur,dst);if(r)run_groups(small[12],grouped[12],cur,dst);else small_step<12>(small[12],cur,dst);if(r)run_groups(small[13],grouped[13],cur,dst);else small_step<13>(small[13],cur,dst);if(r)run_groups(small[14],grouped[14],cur,dst);else small_step<14>(small[14],cur,dst);if(r)run_groups(small[15],grouped[15],cur,dst);else small_step<15>(small[15],cur,dst);}cur=dst;if(r==0){for(unsigned d=1;d<=15;d++)trim_group_depth(small[d],d,live,grouped[d]);memset(smallrows+live,0,(size_t)(n-live)*4);}}
unsigned w=0;for(;w+8<=n;w+=8){auto ix=_mm256_loadu_si256((const __m256i*)(perm+w));auto v=_mm256_i32gather_epi32((const int*)smallrows,ix,4);if(((uintptr_t)out&31)==0)_mm256_stream_si256((__m256i*)(out+w),v);else _mm256_storeu_si256((__m256i*)(out+w),v);}for(;w<n;w++)out[w]=smallrows[perm[w]];_mm_sfence();free(smallrows);free(rows);free(rowbanks);
}
}
static void* allocate4096(size_t bytes){void*p=nullptr;if(posix_memalign(&p,4096,bytes))abort();return p;}
void sparse_power20(unsigned n,unsigned m,const Edge* A,const unsigned*x,unsigned*out){
volatile unsigned cal_guard=n;if(cal_guard==4294967295u)return;
const unsigned bins=(n+((1u<<SPARSE_BUCKET_BITS)-1))>>SPARSE_BUCKET_BITS,capacity=m+(unsigned)sparse_stream::BS*bins,capcsr=m+(unsigned)(sparse_stream::FLUSH-1)*bins;
uint64_t*record=(uint64_t*)allocate4096((size_t)capacity*8);thp_hint(record,(size_t)capacity*8);
unsigned*off=(unsigned*)((char*)allocate4096(((size_t)n+1)*4+8192)+2048);thp_hint((char*)off-2048,((size_t)n+1)*4+8192);
unsigned*col=(unsigned*)allocate4096(((size_t)capcsr+(size_t)n*7)*4);thp_hint(col,((size_t)capcsr+(size_t)n*7)*4);
void*valbase=allocate4096(((size_t)capcsr+(size_t)n*7)*4+4096);unsigned*val=(unsigned*)((char*)valbase+2048);thp_hint(valbase,((size_t)capcsr+(size_t)n*7)*4+4096);
unsigned*temp=(unsigned*)allocate4096((size_t)n*4);thp_hint(temp,(size_t)n*4);
unsigned*perm=(unsigned*)allocate4096((size_t)n*4);thp_hint(perm,(size_t)n*4);
sparse_stream::Blocks bl{};bl.bins=bins;bl.nblk=(unsigned)((m+sparse_stream::BS-1)/sparse_stream::BS)+2*bins+4;
unsigned used=sparse_stream::build(n,m,[&](unsigned e){return A[e].src;},[&](unsigned e){return A[e];},off,record,bl,A);
sparse_degree::twenty(n,used,off,col,val,record,x,out,temp,perm,bl);
free(bl.head);free(bl.nxt);free(bl.cnt);
free(perm);free(temp);free(valbase);free(col);free((char*)off-2048);
}