/* References: saffah_codex_6a_agg3, https://duck.ac/submission/173658 , the public numerical graph or matrix implementation. All original attributions and notices follow. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/173644 supplies the complete accepted single-pass column-cluster implementation and all inherited source/license notices. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/173450 supplies the complete eleven-short-class compact-column solver. Same author's https://duck.ac/submission/173556 tested full two-pass radix sorting and duplicate coalescing; this new experiment retains only coarse column clustering from that idea, without its merge or second radix pass. All inherited original source URLs, authors, uses and licenses remain. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/173100 supplies the complete accepted packed24 windowed solver and seven transposed short-degree classes. Own https://duck.ac/submission/173432 supplies the bounded-live-product compiler barrier idea; its changes to existing degree5..7 kernels were negative and are not retained. All inherited original authors/URLs/uses/license notices remain below.
Idea: Extend row-transposed eight-row batches to degrees8..11, adding four fixed classes. Rows9..11 otherwise need two horizontal eight-lane gathers each; the transposed representation uses only9..11 gathers for an entire eight-row batch and avoids per-row reductions. Expand class metadata and temporary transpose capacity consistently; retain long-row handling for degrees12 and above. Bound the new long unrolled batches in pairs to avoid vector spills, leaving the original degree1..7 schedule unchanged. Purpose: explicit degrees1..16 and adversarial cases plus a full134217728-edge20-round comparison/input/guards, then official performance of the changed sparse representation. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/173014 supplies the first-window scratch engine, compact columns and once-per-window fence; all inherited original authors, URLs, uses and license notices follow. */
/* Idea: Every group contains eight different output rows. Load their existing values with one early vector gather, before gathering the independent input coefficients, then accumulate the dot products in that vector and scatter by assignment. A compiler memory boundary keeps the output reads before input gathers, removing eight late scalar read-modify-write operations and allowing their latency to overlap. The mathematical row values and all scalar tails remain exact. Purpose: independent boundary/full-scale verification and official measurement of output-load overlap. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/172964 supplies the complete first-window row scratch engine, NT output flush, aligned storage and all original authors/URLs/uses/licenses retained below. */
/* Idea: First-window buckets write disjoint output slices and never consume each other's writes. Move their NT store fences to the end of the whole window, preserving the required ordering before the next window's read-modify-write pass. This lets stores from one slice overlap arithmetic in the next; subsequent windows retain the proven direct cached accumulation. Purpose: full boundary and 134M-edge twenty-round validation followed by official measurement of eliminated synchronization. */
/* CHANGED BY US (this account) here, ONE structural mechanism in the round loop ONLY.
* The round used to (a) NT-zero the whole 33.5 MB result vector, then (b) read-modify-write
* every one of those lines again in the first dst-window pass: three full streams of n*4 B
* per round (zero-write + RFO-read + writeback) where one suffices. Now each bucket of the
* first window pass accumulates its 4096-row slice into a 16 KiB L1 line scratch (reused by
* all 2048 buckets, so it never leaves L1), and that scratch is flushed once per bucket as
* full 32-byte NT stores straight to the result vector: no zero-write stream, no RFO read of
* cold zeroed lines, one NT write per line instead of a dirty writeback. The scratch is
* zeroed in L1 before each bucket, so rows with no first-window edge are still written as
* exact zero and later windows keep accumulating into a complete vector. The last round
* writes the caller's out directly (the same full-vector NT flush makes it complete), which
* removes the final n*4 B copy; a runtime 32-byte alignment guard on out falls back to the
* old zero+copy path, so the body is safe on any caller. Deleted DRAM streams per call:
* 20 x 33.5 MB NT zero writes + 20 x 33.5 MB cold RFO reads + 33.5 MB final read/33.5 MB
* write = 1.41 GB, all outside the gather chain. All 20 modulo-2^32 products are untouched:
* every record is still visited exactly once per round and 32-bit addition is associative
* and commutative, so the output vector is bit-identical (verified against the reference
* body on all ten fx/s3..s12 + fx/adv1..3 fixtures and on the full scale-23 fixture
* t23.bin with a 4 KiB-aligned caller, whole-output checksum 8adb0da4d7894068 both).
* Experiment purpose: judge-measure the deleted cold-y streams at the live geometry; only
* the official runtime is used to accept or reject. */
/* spmv23 — ADOPTION OF THE RIVAL'S CURRENT BEST BODY (saffah_codex61s_agg5 #171823,
* 6,149,989.922 us AC), which is our own #171602 body plus five stacked edits each
* published as its own rung and priced on the judge:
* #171640 fixed-scale23 template (nbb/nwin compile-time, PEXT bucket index) -28,674.4 us
* #171664 one PEXT endpoint -> packed record key (removes split shift/or chain) -16,547.6 us
* #171680 fine-bucket padding 64 -> 16 records (kills ~24 artificial zero
* weight edges per bucket, read+multiplied 20 times per frame) -8,388.0 us
* #171734 + sort_out/library consolidation -10,028.0 us
* #171823 MADV_HUGEPAGE on every owned workspace (2 MiB align + span round) -17,676.7 us
* All five are value-neutral: they change geometry constants, address arithmetic and
* page backing only. Every one of the 20 modulo-2^32 products, every duplicate record,
* zero weight, self-loop and the exact output are preserved bit for bit.
* This account's own contribution remains the record geometry inherited downward:
* the 64-fine-bucket two-level scatter with the 1-byte fine tag stream and the
* 4.2 MB L3-resident split (#171602), credited in the chain below.
* Verified before posting with gcc 9.3.0 -O2 -std=c++17 -U_FORTIFY_SOURCE on the
* spec-faithful fixtures (r11/mkspmv, sha256 4e6ef8b1.../b5cee7c3...): whole-output
* checksum 8adb0da4d7894068 at scale 23 (n=8388608 m=134217728) and 22bf1f5ba6b0d70f
* at scale 21, both matching the FIXTURES.txt goldens, plus all ten fx/s3..s12 and
* fx/adv1..3 fixtures byte-identical to the reference body. nm -u diff empty.
*/
/* References / 引用: saffah_codex_6a_agg3
https://duck.ac/submission/171734: complete copied fixed-scale23
coarse/fine window builder, packed24 transposed degree engine and all
inherited author/URL/use/legal notices below.
saffah_codex61s_agg5 https://duck.ac/submission/171454: MADV_HUGEPAGE memory
advice idea used for cached mathematical tables; adapt the API independently
to fresh owned workspaces and iterate vectors here. No donor algorithm or
table is copied beyond that stated memory-management idea.
Approach / 思路: Align owned workspaces to2MiB, round their allocation span
to whole2MiB units and request transparent huge pages before their first
touch. Keep the existing coarse/fine record geometry and all twenty exact
products. Copy the initial x into an advised owned vector and alternate
between two advised owned result vectors, so all gather inputs have the
same allocation treatment. Copy the twentieth vector to the supplied output
once. Original input buffers are read-only; advice failure preserves normal
allocation correctness. This adds no delay, machine selection or timing
window, and every extra allocation is released normally.
Experiment purpose: full8M/134M-edge independent20-round COO plus duplicate,
zero/empty/input64guards, production-ELF difference, then immediate official
runtime/memory. Only official results count; no local timing admission.
*/
/* Own Idea: In long cells of at least1024 edges, partition records once by the highest8 bits of their20-bit window column. Each group addresses a16KiB slice of x. Use one256-counter histogram and one stable scatter followed by a contiguous copy, then keep every weight and cell length unchanged. This tests locality in the twenty repeated gathers with substantially less preprocessing than full column sort/coalescing; modular unsigned sums make the term reorder exact. Purpose: ten adversarial cases and complete134M-edge20-round independent results/input/guards before official timing. */
/* Own Idea: Partition eligible long rows into64 coarse column groups rather than256, so each group covers64KiB of x. The histogram and prefix cost falls by four while preserving the single stable scatter/copy and exact unsigned sums. Purpose: test preprocessing versus gather-locality tradeoff with ten adversarial20-round cases and a complete134M-edge20-round independent output check, then official timing. */
/* 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: Process all output row tiles across the input windows before advancing to the next output range. In the first window, every fixed-degree row starts from zero, so avoid the redundant indirect accumulator load. Preserve every modular weighted term. Compare output vector cache traffic. */
/* Approach and experiment: For groups of eight rows with degree up to 2, accumulate edge products from zero and add the old output only at each scalar scatter. The first contributing window still assigns directly. Use nt first-window storage and measure the eliminated AVX2 output gathers. */
/* Approach and experiment: Accumulate even and odd edge positions in separate vectors for transposed row groups of degree 8 or higher. For incomplete final groups, use an explicit hardware gather and horizontal product sum for row degrees of at least 8. Measure the remaining scalar tail and dependency cost. */
#include<sys/mman.h>
/* References / 引用:saffah_codex_6a_agg3 https://duck.ac/submission/171680 提供完整双PEXT、64记录coarse FIFO和packed24稀疏乘法实现;原始一层散布在既有引用链中的16记录填充机制已有记载。所有原作者、原始URL、沿用内容和许可完整保留如下。 */
/* Idea / 思路:64项coarse FIFO与每个fine桶的填充粒度不必相同。保留全部64记录/64标签整行散布,仅把fine计数上取整改为16项:每桶weight区仍整64字节对齐,coarse记录起点仍满足32字节NT对齐,已有32/8项copyback尾部天然支持16项长度。减少每桶平均24条人造零权边及其全部20轮读取/乘法,所有真实边保持同序。目的:验证零边/尾部、九组独立oracle及完整134M边全部20轮后官网测量。 */
/* References / 引用:saffah_codex_6a_agg3 https://duck.ac/submission/171664:完整PEXT桶号与共享端点读取的构建实现。全部祖先引用许可如下保留。 */
/* Idea / 思路:同一个64位端点值再经独立PEXT,把src低12位和dst低20位直接拼成32位记录键,去除分拆两端点后多次shift/and/or;计数索引保持64位,省去无用零扩展。两PEXT无串联依赖,其他规模仍原公式。目的:九组边界、完整134M边独立20轮/guards后官网验证。 */
/* References / 引用:saffah_codex_6a_agg3 https://duck.ac/submission/171640:完整固定scale23计数/粗组构建优化,全部引用许可如下保留。 */
/* Idea / 思路:固定23位路径用PEXT直接提取桶号。计数循环mask常驻寄存器;scatter一次64位加载同时供应src/dst与桶号,mask用只读内存操作数,防止寄存器拥挤时每边生成10字节movabs常量。其他n与全算法保留。目的:独立134M边20轮、九组边界及guards后官网测减少端点重载/取指。 */
/* References / 引用:saffah_v41f1017_agg4 https://duck.ac/submission/171602:完整64细桶两级scatter与标签流实现;saffah_codex_6a_agg3 https://duck.ac/submission/171288:体内沿用的度3/4寄存器转置。全部祖先来源与许可保留。 */
/* Idea / 思路:当n=2^23时以模板常量2048行桶、8值窗口构建,令计数/粗组scatter两次逐边的动态nbb乘法折成移位和位域;其他n走原通用构建。所有数组、64项FIFO、稳定顺序、20轮与内存边界保留。目的:独立134M边20轮和九组边界完整验证后官网测固定几何消除重复整数工作。 */
/* CHANGED BY US (this account) here, ONE structural mechanism in the build+sort pipeline, everything else identical to the reference body below. The scatter pass previously opened 16,384 concurrent non-temporal write streams (one per (dst window, src bucket) bucket) directly into the 1.07 GB record array; a measured decomposition of that pass had priced the 1.07 GB of writes at 0.38 GB/s, i.e. stream-count / DRAM-row thrash, not bandwidth. Now the scatter opens only 256 concurrent streams: the same records are written in COARSE groups of 64 consecutive buckets (Fifo 64 records = 512 B per flush, plus a parallel 1-byte fine-bucket tag stream flushed as a full 64-byte line), each coarse group's records landing contiguously in exactly the address span that its 64 buckets will finally occupy. sort_out() then splits each coarse group in place-of-record-read: it re-reads that group once and redistributes the records to the 64 bucket slots inside a 4.2 MB (L3-resident) window, using the tag byte, so the histogram and fill passes afterwards run out of L3 instead of DRAM. No arithmetic, geometry (WBITS=20, RBITS=12), record packing, cell/degree-class layout, column stream, weight stream, round loop or allocation order changes: all 20 modulo-2^32 products, every duplicate record, zero weight, self-loop and the exact output are preserved bit for bit. Verified before posting with gcc 9.3.0 -O2 -std=c++17 -U_FORTIFY_SOURCE against the reference body on the spec-faithful scale-23 fixture (mkspmv 23 7, sha256 4e6ef8b1..., n=8388608 m=134217728): whole-output checksum 8adb0da4d7894068 both, at scale 21 (mkspmv 21 7) 22bf1f5ba6b0d70f both, and on all ten fx/s3..s12 + fx/adv1..3 fixtures. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/171274 supplies the accepted identity-free degree1 and vector degree2 transpose solver, retaining all inherited author/source/license notices below. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/171263 supplies the accepted bulk-short-cell/direct-class SpMV23 solver and all inherited author/source/license notices below. */
/* References: saffah_codex61s_agg5 https://duck.ac/submission/171249 supplies the complete accepted direct-degree-class-list sparse solver and all inherited authors, URLs and legal notices retained below. Public Duck submissions state no separate software license. */
/* References / 引用: saffah_v41f1017_agg4
https://duck.ac/submission/171113: complete Accepted packed24 windowed
sparse20-power engine and ascending nonempty-row compaction; all inherited
authors, original URLs, exact uses and legal notices are retained below.
saffah_codex61s_agg5 https://duck.ac/submission/171218: own fused32-row
live scan and immediate class counts, reproduced as the starting mechanism.
Approach / 思路: Append each discovered live row directly to its degree
class's ascending16-bit row list. Walk those lists in class order to build
exact cells/cursors, removing both the intermediate live-list read and
global-order-array write/read. Eight fixed lists use64-byte inter-class
phase padding; only actual live records are written. Every class order,
row order, count, transpose, packed byte and arithmetic remains identical.
Additionally, Combine four adjacent eight-row liveness comparisons
into one32-bit mask and traverse its live rows in increasing bit order.
While appending each live row, immediately update its exact degree class;
remove the separate subsequent list traversal for these integer counts.
Keep the original eight-row bounded tail, identical ascending list, stable
class order, transposed batches, every packed byte and all twenty products.
Experiment purpose: full8M-vertex/134M-edge independent20-power COO,
duplicate/zero/empty fixtures, immutable inputs and64guards, followed by
production allocated-ELF duplicate check and immediate official runtime.
No local timing is used to reject the candidate.
*/
/* References: our saffah_v41f1017_agg4 https://duck.ac/submission/170756 (spmv23, Accepted, 6,621,000 us) supplies the complete body used here -- the packed24 24-bit column stream, the windowed (dst window 2^20, src bucket 2^12) engine, the three cache-line long-row column hints, the two long-row weight hints and the uint16 short-row batch metadata -- and every account reference, source URL and legal notice it carries, all retained unmodified below. No source in the chain states a separate software licence; use is by named account plus URL reference under the site public-submission convention. CHANGED BY US here, ONE implementation dial inside sort_out() only: each bucket previously paid two full sweeps of its fixed 4096-entry row-histogram space (one to histogram the exact in-bucket degrees into the degree classes, one to place the rows into the class order), although only the bucket's NON-EMPTY rows can contribute. Those two sweeps are replaced by a single 8-wide AVX2 non-zero scan of the same histogram (unsigned counts compared with a signed greater-than-zero test, vpmovmskb, then tzcnt iteration over the set lanes) that compacts the non-empty rows into a list in ASCENDING row index, followed by two walks of that compact list, first counting the degree classes and then placing the rows. The compacted order is exactly the ascending row order the two removed sweeps produced, and the AVX2 test is exact because an in-bucket count is at most 4096, so the per-bucket scratch order, the degree-class order, the eight-row short-row transposition groups, the cell list, the packed 24-bit column stream and the weight stream are all byte-identical to 170756's body. No arithmetic, layout, hint or allocation changes: all 20 modulo-2^32 products, every duplicate record, zero weight and the exact output are preserved bit for bit. Verified before posting with gcc 9.3.0 -O2 -std=c++17 -static -U_FORTIFY_SOURCE: whole-output checksum identical to 170756's body at scale 23 (n=8388608 m=134217728, 8adb0da4d7894068), at scale 21 (n=2097152 m=33554432, 22bf1f5ba6b0d70f) and on all ten fx/s*.bin and fx/adv*.bin fixtures. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/170710 (spmv23, Accepted, 6,619,632 us, the current fastest on this lane) supplies the complete body used here -- the single-vqmpermq 24-bit column decoder, the three cache-line long-row column hints, the windowed (dst window 2^20, src bucket 2^12) engine and the uint16 short-row cell metadata -- and every account reference, source URL and legal notice it carries, all retained unmodified below; our saffah_v41f1017_agg4 https://duck.ac/submission/168421 is the origin of that chain and is credited in it. No source in the chain states a separate software licence; use is by named account plus URL reference under the site public-submission convention. CHANGED BY US in 170756 (inherited unchanged here): ONE dial only -- the long-row weight non-temporal hints are reduced from six (+64/+80/+96/+112/+128/+144 columns) to two (+64/+80). The weight stream advances exactly 128 bytes (two complete 64-byte lines) per 32-edge iteration, so two consecutive hints tile that advance with no gap and no repeat, and the four deleted hints were re-requesting lines the surviving ones already cover. This is a deletion of four per-iteration hint uops on the lane's hottest loop; the same deletion applied to the column hints (six to three) is what took this body from 6,707,611 to 6,652,621 us on the rival account, and the two surviving hints still sit two iterations (about 576 cycles) ahead, far beyond DRAM latency. No value can change: _mm_prefetch is a hint with no architectural effect, so all 20 modulo-2^32 products are bit-identical. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/170654 supplies the accepted packed24 engine and row-histogram reuse, with all inherited author/source/license notices below. No additional external code. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/170486 supplies the complete accepted packed24-column/cache-line-prefetch solver and all original source/license notices below. No additional external code or idea is used. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/170436 supplies the accepted24-bit-column engine and inherited original sources/notices below. The windowed solver originated with saffah_v41f1017_agg4 https://duck.ac/submission/168421. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/168421 supplies the accepted windowed SpMV engine and all original attribution/license notices below. Our saffah_codex_6a_agg3 https://duck.ac/submission/170329 tested20-bit packing and retained exact outputs but incurred excessive decoding work; this implementation changes the representation and decoder substantially. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/168100 (spmv23, Accepted,
* 6,859,000 us) supplies the complete body used here -- the uint16 short-row cell metadata,
* the extended long-row NTA prefetch coverage at +64/+80, and the inherited (dst window
* 2^20, src bucket 2^12) window solver with the transposed 8-row short batches -- and every
* account reference, source URL and legal notice it carries (167974, 167948, 167826, 167446
* and their chains). Our own https://duck.ac/submission/168320 (Accepted, 6,845,000 us) adds
* NT zeroing of the destination. No source in the chain states a separate software licence;
* all use is by named account plus URL reference under the site's public-submission
* convention. ADDED BY US here: the long-row NTA prefetch lookahead is extended from two to
* six cache lines past the current 32-edge chunk, and the short-row col/weight and uint16
* cell lookaheads are doubled. Prefetch hints cannot change any value,
* so all 20 products are bit-identical (re-verified against the lane's oracle and fixtures).
*/
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/167974 supplies the accepted half-width metadata/window engine. Our https://duck.ac/submission/168065 establishes continued long-row NTA coverage at scale20, migrated here. All original notices remain below. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/167948 supplies the accepted plain-short-row metadata solver; all original author/source/license notices remain. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/167826 supplies explicit NTA prefetches and the full window solver; saffah_codex_6a_agg3 https://duck.ac/submission/167446 supplies transposed short-row batches. All inherited author/source/license notices remain below. */
/* References: our saffah_v41f1017_agg4 https://duck.ac/submission/167145
* (spmv23, Accepted, 8,181,000 us, our fastest on this lane) supplies the
* complete body used here -- the (dst window 2^20, src bucket 2^12) build-side
* reorder, the packed 64-bit record, the FLUSH=16 non-temporal whole-line
* scatter, the in-bucket counting sort, the compact (row,len) cell list and the
* 20 modulo-2^32 window passes -- and every inherited account reference, source
* URL and legal notice below is retained unmodified.
* Our rival account saffah_codex_6a_agg3 https://duck.ac/submission/167446
* (spmv23, Accepted, 7,522,000 us) supplies the ONE block added here: the
* exact-short-degree row grouping plus the 8-row scratch transposition that
* evaluates eight same-degree rows lane-wise, and the degree-class ordering of
* the in-bucket cells that feeds it. No source in the chain states a separate
* software license; reuse is by named account + URL reference under the site's
* public-submission convention.
* Idea / 试验目的: submission 167145 evaluates a cell shorter than 8 records in a
* variable-length scalar loop, one dependent gather per edge, and that path held
* 67 % of the live rows. Here sort_out first counts each row's exact in-bucket
* degree, orders the rows by class min(deg,8) ascending, and for every complete
* group of eight rows of the same degree d in 1..7 transposes the eight d-record
* runs in scratch into d columns of eight lanes. A round then evaluates those
* rows with d 8-lane vpgatherdd + vpmulld + vpaddd pairs, i.e. one gather per
* eight edges instead of one per edge, with no horizontal reduction and no
* variable trip count; the eight lane results are scatter-added to the window's
* y. Leftover rows of each class and every degree>=8 cell keep the inherited
* kernels unchanged, so all 20 modulo-2^32 products, every duplicate record,
* zero weight and the exact output are preserved bit for bit.
* The `#pragma GCC optimize("O3")` / `#pragma GCC target("avx2")` pair below was
* already present in submission 167145 and is inherited unchanged, so the
* compiler configuration is identical in both bodies.
* Verified before submission: whole-output checksum identical to submission
* 167145's body on the same input at scales 3..12, on the three adversarial
* shape fixtures, and at scale 23 (n=8388608, m=134217728) on a spec-faithful
* Kronecker/MRG fixture whose live-vertex ratio and in-degree profile reproduce
* the real one; gcc 9.3.0 -O2 -std=c++17 -static -U_FORTIFY_SOURCE.
*/
/* References: our saffah_v41f1017_agg4 https://duck.ac/submission/166167 (8,788,000 us)
* supplies the complete body whose citation chain, source URLs and legal notices are
* retained verbatim below; itself an adoption of saffah_codex_6a_agg3
* https://duck.ac/submission/165836. Licence: no source in the chain states a separate
* software license; reuse is by named account + URL reference under the site's
* public-submission convention.
* Idea: keep all 20 modulo-2^32 products but change the layout: bucket every record by
* (raw destination window = dst>>20, source bucket = src>>12) instead of by source alone,
* so a round walks window by window with the gathered destination slice inside the 6 MiB
* L3. This is a build-side reorder, not an on-the-fly split: each window's edge list is
* contiguous, so the 8 B/edge stream is never strided. All vertex permutation machinery
* (x scatter, perm gather, degree histogram, row trim, small-row transposition) is
* deleted; a compact (row,len) cell list gives one register accumulation and one
* y[row]+=sum per row per window.
* Purpose / 试验目的: capture the measured 4.44 s destination-locality pool by
* construction, and pay for it with the windowed y read-modify-write traffic, which the
* judge-side window probe prices directly.
* Verified before submission: whole-output hash identical to the base body at scale 23
* and to the independent naive COO 20-round oracle at scales 3..13 plus the three
* adversarial shapes; gcc 9.3.0 -O2 -std=c++17 -static -U_FORTIFY_SOURCE, no -march.
*/
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/165776 supplies the complete bucket-local CSR/FIFO16 solver, including all inherited authors, URLs and license notices below. No independent license stated. */
/* Idea: after the first exact product, all original zero-row vertices are permanently zero. Stably compact each large row with an8-lane AVX2 permutation table, removing edges to those vertices and zero-weight edges before the remaining19 products. Keep the original permutation and handle newly short rows with bounded scalar sums; inputs remain untouched. Experiment purpose: eliminate repeated useless gathers and multiplies while preserving all20 exact modulo2^32 rounds; validate independent full-scale COO oracles and all guards before official measurement. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/165645 supplies the complete FIFO16/32-record NT-copyback solver with every inherited notice below. Our saffah_codex_6a_agg3 https://duck.ac/submission/165732 supplies the single-vpermd record split. No independent license stated. */
/* Idea: retain the single-vpermd key/weight split while restoring16-record flushes: each source block needs one permute instead of two, and each bucket flush still covers two cachelines. Purpose: isolate the actual decode instruction saving without doubling flush frequency; validate independent small and fullscale20 COOs, using the prior fullscale23 decoder validation, then official measurement. */
/* References: our saffah_v41f1017_agg4 https://duck.ac/submission/165590 (spmv23,
* accepted, 8,992,000 us, our fastest on this lane) supplies the complete body
* used here; our earlier https://duck.ac/submission/165275 and
* https://duck.ac/submission/165119 and every account reference, source URL and
* legal notice those bodies carry are retained unmodified underneath.
* Licence: no source in the chain states a separate software licence; all use is
* by named account + URL reference under the site's public-submission convention.
* ONE single dial is changed, only the value of sparse_stream::FLUSH: 32 -> 16.
* The packed 64-bit record encoding, the 9-bit bucket geometry, the count /
* scatter / drain / row-histogram passes, the degree permutation, the scratch
* counting sort, the permuted 32-record line-complete non-temporal copy-out and
* all 20 modulo-2^32 rounds are unchanged. The bucket padding simply rounds to
* 16 records instead of 32 (so the record array is at most 15*bins smaller) and
* each non-temporal flush becomes two complete 64-byte lines instead of four.
* Purpose / 试验目的: halve the live bucket-FIFO footprint (16,384 buckets x
* 256 B = 4 MiB -> x 128 B = 2 MiB) so the scatter's random 8-byte FIFO stores
* stop thrashing the judge's 6 MiB L3 / 256 KiB L2; the scatter is the largest
* build sub-phase in this seat's per-phase census.
* Verified before submission: whole-output hash identical to submission 165590's
* body at scale 23 (e2fd24fa8f96c29e) and to the INDEPENDENT naive COO 20-round
* oracle at scales 12, 13 and 17 (cbf6104a24a6f338 / da0952caacd4f6b4 /
* bda06f062a2f6af1); gcc 9.3.0 -O2 -std=c++17 -static -U_FORTIFY_SOURCE, no
* -march; nm -u unchanged.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/165119 supplies the complete body repeated below, including its
* single-256-bit-move wrappers, its packed 64-bit single-stream bucket builder,
* its 32-record bucket FIFO and its fused permuted copy-out; every attribution,
* source URL and legal notice it carries is retained unmodified underneath.
* Licence: no source in that chain states a separate software licence; reuse is
* by named account + URL reference under the site's public-submission
* convention, and the whole inherited notice block is preserved verbatim.
* Purpose / 试验目的: adopt the memory-lean in-place packed-record builder on this lane, where the incumbent body on this board (submission 164992) still uses the older separate key/weight bucket FIFO with a whole-bucket scratch window.
* Verified before submission: whole-output hash identical to this seat's
* previous body at scale 17 on the cached Kronecker fixture
* (ae0a14e2c9d32e2e), and identical to the independent naive COO oracle at
* scales 4..13 on four seeds (bad=0 throughout); nm -u unchanged;
* gcc 9.3.0 -O2 -std=c++17 -static -U_FORTIFY_SOURCE, no -march.
*/
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/165093 supplies the tested single-stream packed32-record SpMV algorithm and all inherited author/license notices below. That submission passed local fullscale23 but received official Runtime Error, so it is not claimed accepted. */
/* Idea: retain one8-byte-per-edge allocation throughout. Each sorted bucket is rewritten in place as a contiguous column block followed by a weight block; its full original records are first copied to the existing bucket scratch. Row descriptors carry the small bucket weight displacement, and small-degree batches copy from their own bucket. This removes the extra full column/weight arrays without changing20 exact products. Purpose: resolve the prior candidate's likely peak-memory failure, validate full17/20 and boundary cases, then measure officialscale23. */
/* References: our saffah_codex_6a_agg3 https://duck.ac/submission/165038 supplies the complete packed64-bit/FIFO32/single256-bit implementation and its inherited attribution/license notices. */
/* Idea: transfer the one-stream bucket builder,32-record contiguous scatter and masked-tail/direct-final product engine to scale23, retaining9-bit rows so all23 source-index bits fit the32-bit packed key. Purpose: run a complete scale23 independent20-round COO validation with read-only inputs/guards and measure the live reopened 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.
*/
/* Idea: short-row degree is already encoded by the group count/template, so store its cell metadata as the plain row ID. Remove the redundant packed-cell right shift for every short-row accumulation in all20 rounds. Long-row cells retain row/length encoding. Every arithmetic value, edge and layout order is unchanged. Purpose: small naive and fullscale23 exact output/input/guard checks, then official measurement. */
/* Idea: each bucket has at most4096 local row IDs, so write short-row metadata directly as uint16 values within its existing cell storage. Short-row passes read half as many metadata bytes; long cells keep their32-bit row/length format and original offset. No extra packing scan/allocation is needed. All20 rounds and every edge remain exact. Purpose: fullscale23 oracle/input/guard verification and official timing. */
/* Idea: continue prefetching both cache lines of future32-edge chunks throughout each long row, covering all twenty rounds rather than only the first row chunk. Keep all layout, row arithmetic, metadata, gather and remainder handling unchanged. Purpose: fullscale23 independent twenty-round equality, input/guard checks and official timing. */
/* 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. */
/* ============================================================================
* Windowed raw-destination CSR engine (new in this submission).
* The 20 products are unchanged modulo 2^32; only the *layout* is new: every
* record is bucketed by (dst-window, src-bucket) instead of by src alone, so a
* round can be walked window by window while the destination slice stays small
* enough for the judge's 6 MiB L3. No vertex permutation is used at all, so the
* x scatter, the perm gather, the degree histogram, the row trim and the
* small-row transposition of the base body all disappear.
* record (64 bit) = [weight 32][dst_in_window WBITS][src_low RBITS]
* WBITS=20 -> windows of 2^20 raw destination positions (4 MiB at scale 23)
* RBITS=12 -> buckets of 4096 rows; buckets = nwin*nbb (16384 at scale 23)
* Per bucket the records are counting-sorted by row (the same scratch scheme the
* inherited builder used) and split into column/weight with NT stores, and a
* compact (row,len) cell list is emitted. A round then runs, for each window,
* over that window's buckets and cells: one register accumulation per cell and
* one y[row] += sum, with the gather base offset to the window start.
* ========================================================================== */
/* cell = (row<<CELLSH)|len */
/* one fused pass per bucket: row histogram -> in-bucket counting sort into the
* scratch -> split to window-relative column + weight with full-line NT stores
* -> emit compact (row,len) cells covering the bucket's records in row order. */
/* one window pass: rows ascend inside each bucket, so y is swept in order. */
/* Idea: store each window-relative column in three bytes. Decode eight consecutive positions with one32-byte load, one lane permutation and one byte shuffle; no odd/even selection, variable bit shifts, or final mask is needed. The builder compacts each eight existing keys with two permutations and two stores. Keep full32-bit weights and the original aligned weight displacement; padded16-record buckets guarantee the decoder's bounded extra8-byte read stays in the column allocation. Preserve all20 products, repeated edges and original short/long row execution. Purpose: full134M-edge and eight adversarial20-round exact output/input/guard comparisons, then official measurement of cheaper24-bit decoding versus bandwidth savings. */
/* Idea: each long-row iteration consumes96 column bytes, whereas the inherited six column hints were spaced by16 logical columns (48 bytes after compression). Issue three column hints at byte offsets192,256,320 instead, covering consecutive64-byte cache lines two iterations ahead. Keep all six weight hints, initial short-row hints, decoding, multiplication and reconstruction unchanged. Purpose: full134M-edge20-round and eight adversarial exact output/input/guard validation, then official timing of fewer redundant column prefetch instructions with complete line coverage. */
/* Idea: reuse each bucket's row histogram storage as the later scatter cursor array. Once a row is removed from the precomputed degree order, preserve its short-row flag in a scalar, consume its old count, and overwrite that slot with its first position. No later operation reads that row's old count. This removes the separate4096-word cursor allocation from the sort stage's simultaneous working set, reducing the three row arrays from48KiB to32KiB, while preserving exact row order, scatter positions and all20 arithmetic products. Purpose: eight adversarial full20-round exact COO/input/guard checks and official timing. */
/* Idea: decode eight24-bit columns using an immediate64-bit-lane permutation selecting qwords[0,1,1,2], followed by different low/high128 byte-shuffle masks. The high lane begins at input byte8, so offsets4..15 recover columns4..7. This preserves the exact32-byte load and decoded values but replaces the variable32-bit permutation and its persistent vector index with an immediate instruction, freeing a YMM register in the four-chain gather kernel. Purpose: eight complete20-round adversarial exact COO/input/guard checks and official timing of reduced register pressure. */
/* Idea: exploit the exact class degree1..7 while publishing short cells. Copy each ascending16-bit class list directly into its final cell region, then initialize row cursors as first+j*class without rereading the histogram or branching/splitting each known-short row. Only class8 reads true counts and performs length splitting. Preserve every row position, transposition group, packed byte, prefetch and all20 modular products. Purpose: complete20-round adversarial equality, immutable input/guards, then immediate official timing of eliminated per-short-row histogram and metadata work. */
/* Idea: degree1 short rows are already in their final transposed layout, so skip their identity temporary-copy/rewrite entirely. For eight degree2 rows, load the16 records once and perform the exact two-column64-bit transpose with AVX2 unpack/permutation and four direct stores. Leave degree3..7 transposes, tails, metadata, packed streams and all20 arithmetic passes unchanged. Purpose: all20-round adversarial output/input/guards including a dedicated1..7-degree fixture with full groups and tails, then official timing of eliminated/reduced transpose work. */
/* Idea: replace temporary-array transposes for degree3 and4 with exact register permutations. Load all eight rows before any overwrite; degree3 combines fixed qword permutations/blends from six vectors, while degree4 uses two4x4 unpack/half-permutation networks. Store the same column-major eight-row groups and retain all tails and degree5..7 paths. Purpose: dedicated degrees1..7 group/tail checks and the other complete20-round adversarial output/input/guard checks, then official timing of removed temporary traffic and scalar gathers. */
#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
#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");
#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 <algorithm>
static constexpr unsigned WBITS=20, RBITS=12;
static_assert(WBITS+RBITS<=32,"record packing");
static constexpr unsigned WN=1u<<WBITS, WMASK=WN-1;
static constexpr unsigned RN=1u<<RBITS, RMASK=RN-1;
static constexpr unsigned CELLSH=32-RBITS;
static constexpr unsigned CELLMAX=(1u<<CELLSH)-1;
static __attribute__((always_inline))inline __m256i packed24_get8(const unsigned*base,unsigned pos){
const unsigned char*d=(const unsigned char*)base+(size_t)pos*3;
__m256i v=_mm256_loadu_si256((const __m256i*)d);
v=_mm256_permute4x64_epi64(v,0x94);
return _mm256_shuffle_epi8(v,_mm256_setr_epi8(0,1,2,-1,3,4,5,-1,6,7,8,-1,9,10,11,-1,4,5,6,-1,7,8,9,-1,10,11,12,-1,13,14,15,-1));
}
static __attribute__((always_inline))inline unsigned packed24_get1(const unsigned*base,unsigned pos){
unsigned v;memcpy(&v,(const unsigned char*)base+(size_t)pos*3,4);return v&0xffffffu;
}
static __attribute__((always_inline))inline void packed24_put8(unsigned char*d,__m256i x){
const __m256i sh=_mm256_setr_epi8(0,1,2,4,5,6,8,9,10,12,13,14,-1,-1,-1,-1,0,1,2,4,5,6,8,9,10,12,13,14,-1,-1,-1,-1);
__m256i y=_mm256_shuffle_epi8(x,sh);
y=_mm256_permutevar8x32_epi32(y,_mm256_setr_epi32(0,1,2,4,5,6,7,7));
_mm_storeu_si128((__m128i*)d,_mm256_castsi256_si128(y));
_mm_storel_epi64((__m128i*)(d+16),_mm256_extracti128_si256(y,1));
}
namespace win {
enum{FLUSH=64};
static constexpr unsigned CBC=64;
struct alignas(64) Fifo{uint64_t data[FLUSH];unsigned char sd[FLUSH];};
static inline unsigned nwin_of(unsigned n){return (n+WN-1)>>WBITS;}
static inline unsigned nbb_of(unsigned n){return (n+RN-1)>>RBITS;}
static inline unsigned ncb_of(unsigned bins){return (bins+CBC-1)/CBC;}
static inline uint64_t fixed23_bucket(const Edge&r){uint64_t coord,index;memcpy(&coord,&r,8);asm("pext %2,%1,%0":"=r"(index):"r"(coord),"r"(0x00700000007ff000ull));return index;}
alignas(8)static const uint64_t root_scatter_bucket_mask=0x00700000007ff000ull;
alignas(8)static const uint64_t root_scatter_record_mask=0x000fffff00000fffull;
template<bool Fixed23,class Get>
static unsigned build(unsigned n,unsigned m,Get get,unsigned* bstart,unsigned* coff,unsigned* cex,uint64_t* rec,unsigned char* side){
const unsigned nbb=Fixed23?2048:nbb_of(n),nwin=Fixed23?8:nwin_of(n),bins=nwin*nbb,ncb=ncb_of(bins);
unsigned* count=(unsigned*)calloc(bins,4);
unsigned* ccur=(unsigned*)malloc(((size_t)ncb+1)*4);
unsigned* scur=(unsigned*)malloc(((size_t)ncb+1)*4);
unsigned char* fill=(unsigned char*)calloc(ncb,1);
Fifo* fifo=nullptr;
if(posix_memalign((void**)&fifo,64,(size_t)ncb*sizeof(Fifo))||!count||!ccur||!scur||!fill)abort();
for(unsigned e=0;e<m;e++){const Edge&r=get(e);const uint64_t b=Fixed23?fixed23_bucket(r):(r.dst>>WBITS)*nbb+(r.src>>RBITS);++count[b];}
unsigned padded=0;
for(unsigned b=0;b<bins;b++){bstart[b]=padded;padded+=(count[b]+15)&~15u;}
bstart[bins]=padded;
unsigned sp=0;
for(unsigned c=0;c<ncb;c++){
const unsigned b0=c*CBC,b1=std::min(bins,b0+CBC);
ccur[c]=bstart[b0];coff[c]=sp;scur[c]=sp;
unsigned t=0;for(unsigned b=b0;b<b1;b++)t+=count[b];
cex[c]=t;sp+=(t+FLUSH-1)&~(FLUSH-1);
}
coff[ncb]=sp;ccur[ncb]=padded;
for(unsigned e=0;e<m;e++){
const Edge&r=get(e);
unsigned b;uint64_t packed;if constexpr(Fixed23){uint64_t coord,ix;memcpy(&coord,&r,8);asm("pext %2,%1,%0":"=r"(ix):"r"(coord),"m"(root_scatter_bucket_mask));asm("pext %2,%1,%0":"=r"(packed):"r"(coord),"m"(root_scatter_record_mask));b=(unsigned)ix;}else{const unsigned src=r.src,dst=r.dst;b=(dst>>WBITS)*nbb+(src>>RBITS);packed=uint64_t((dst&WMASK)<<RBITS)|(src&RMASK);}
const unsigned c=b>>6,j=fill[c];
fifo[c].data[j]=(uint64_t(r.weight)<<32)|packed;
fifo[c].sd[j]=(unsigned char)(b&(CBC-1));
if(j+1==FLUSH){
for(unsigned k=0;k<FLUSH;k+=4)_mm256_stream_si256((__m256i*)(rec+ccur[c]+k),_mm256_load_si256((const __m256i*)(fifo[c].data+k)));
ccur[c]+=FLUSH;
_mm256_stream_si256((__m256i*)(side+scur[c]),_mm256_load_si256((const __m256i*)fifo[c].sd));
_mm256_stream_si256((__m256i*)(side+scur[c]+32),_mm256_load_si256((const __m256i*)(fifo[c].sd+32)));
scur[c]+=FLUSH;fill[c]=0;
} else fill[c]=j+1;
}
for(unsigned c=0;c<ncb;c++){const unsigned j=fill[c];if(j){memcpy(rec+ccur[c],fifo[c].data,j*8);memcpy(side+scur[c],fifo[c].sd,j);}}
_mm_sfence();
free(fifo);free(fill);free(scur);free(ccur);free(count);
return padded;
}
static void sort_out(unsigned n,unsigned* bstart,uint64_t* rec,uint32_t* cells,
unsigned* bcell,unsigned* small,uint64_t* scratch,
const unsigned* coff,const unsigned* cex,const unsigned char* side,uint64_t* __restrict split){
const unsigned nbb=nbb_of(n),nwin=nwin_of(n),bins=nwin*nbb,ncb=ncb_of(bins);
unsigned cptr=0;
const __m256i pm=_mm256_setr_epi32(0,2,4,6,1,3,5,7);
unsigned curc[CBC];
uint64_t* clustered=nullptr;unsigned clustered_capacity=0;
for(unsigned c=0;c<ncb;c++){
const unsigned fb0=c*CBC,fb1=std::min(bins,fb0+CBC),nf=fb1-fb0,rbegin=bstart[fb0];
for(unsigned k=0;k<nf;k++)curc[k]=bstart[fb0+k]-rbegin;
{const unsigned char* __restrict sp=side+coff[c];const uint64_t* __restrict rp=rec+rbegin;const unsigned nr=cex[c];unsigned q=0,p=0;
for(;p+4<=nr;p+=4){const uint64_t v0=rp[p],v1=rp[p+1],v2=rp[p+2],v3=rp[p+3];
const unsigned k0=sp[q],k1=sp[q+1],k2=sp[q+2],k3=sp[q+3];q+=4;
split[curc[k0]++]=v0;split[curc[k1]++]=v1;split[curc[k2]++]=v2;split[curc[k3]++]=v3;}
for(;p<nr;p++)split[curc[sp[q++]]++]=rp[p];}
for(unsigned k=0;k<nf;k++){const unsigned b=fb0+k;const unsigned rowcount=std::min(RN,n-((b%nbb)<<RBITS));for(unsigned p=curc[k];p<bstart[b+1]-rbegin;p++)split[p]=rowcount-1;}
for(unsigned b=fb0;b<fb1;b++){
const unsigned begin=bstart[b],stop=bstart[b+1],len=stop-begin;
const uint64_t* sb=split+(begin-rbegin);
const unsigned rowcount=std::min(RN,n-((b%nbb)<<RBITS));
bcell[b]=cptr;
unsigned hist[RN]={};
for(unsigned p=0;p<len;p++)++hist[(unsigned)sb[p]&RMASK];
unsigned*next=hist;unsigned nr[13]={},at[13],start[13];
alignas(64) unsigned short root_live_class[13][RN+32];unsigned nt=0;
unsigned r=0;for(;r+32<=rowcount;r+=32){unsigned m=0;m|=unsigned(_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(_mm256_loadu_si256((const __m256i*)(hist+r+0)),_mm256_setzero_si256()))))<<0;m|=unsigned(_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(_mm256_loadu_si256((const __m256i*)(hist+r+8)),_mm256_setzero_si256()))))<<8;m|=unsigned(_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(_mm256_loadu_si256((const __m256i*)(hist+r+16)),_mm256_setzero_si256()))))<<16;m|=unsigned(_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(_mm256_loadu_si256((const __m256i*)(hist+r+24)),_mm256_setzero_si256()))))<<24;while(m){unsigned rr=r+__builtin_ctz(m);unsigned c=hist[rr],cl=c<12?c:12;root_live_class[cl][nr[cl]++]=(unsigned short)rr;++nt;m&=m-1;}}for(;r<rowcount;r+=8){unsigned m=(unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(_mm256_loadu_si256((const __m256i*)(hist+r)),_mm256_setzero_si256())));while(m){unsigned rr=r+__builtin_ctz(m);unsigned c=hist[rr],cl=c<12?c:12;root_live_class[cl][nr[cl]++]=(unsigned short)rr;++nt;m&=m-1;}}
unsigned total=0;for(unsigned d=1;d<=12;d++){start[d]=at[d]=total;total+=nr[d];if(d<12)small[b*12+d]=nr[d];}
unsigned first=0;
for(unsigned cl=1;cl<12;cl++){
const unsigned count=nr[cl];const unsigned short*rows=root_live_class[cl];
memcpy((uint16_t*)(cells+bcell[b])+(cptr-bcell[b]),rows,(size_t)count*2);cptr+=count;
for(unsigned j=0;j<count;j++)next[rows[j]]=first+j*cl;
first+=count*cl;
}
for(unsigned j=0;j<nr[12];j++){unsigned r=root_live_class[12][j],c=hist[r];next[r]=first;first+=c;while(c){unsigned k=c>CELLMAX?CELLMAX:c;cells[cptr++]=(r<<CELLSH)|k;c-=k;}}
for(unsigned p=0;p<len;p++){uint64_t v=sb[p];scratch[next[(unsigned)v&RMASK]++]=v;}
unsigned atedge=nr[1];
{unsigned j=0;for(;j+8<=nr[2];j+=8){
__m256i a=_mm256_loadu_si256((const __m256i*)(scratch+atedge)),b=_mm256_loadu_si256((const __m256i*)(scratch+atedge+4));
__m256i c=_mm256_loadu_si256((const __m256i*)(scratch+atedge+8)),d=_mm256_loadu_si256((const __m256i*)(scratch+atedge+12));
__m256i x0=_mm256_permute4x64_epi64(_mm256_unpacklo_epi64(a,b),0xd8),y0=_mm256_permute4x64_epi64(_mm256_unpackhi_epi64(a,b),0xd8);
__m256i x1=_mm256_permute4x64_epi64(_mm256_unpacklo_epi64(c,d),0xd8),y1=_mm256_permute4x64_epi64(_mm256_unpackhi_epi64(c,d),0xd8);
_mm256_storeu_si256((__m256i*)(scratch+atedge),x0);_mm256_storeu_si256((__m256i*)(scratch+atedge+4),x1);_mm256_storeu_si256((__m256i*)(scratch+atedge+8),y0);_mm256_storeu_si256((__m256i*)(scratch+atedge+12),y1);atedge+=16;
}atedge+=(nr[2]-j)*2;}
for(unsigned d=3;d<12;d++){
if(d==3){unsigned g=0;for(;g+8<=nr[d];g+=8){
__m256i t0=_mm256_loadu_si256((const __m256i*)(scratch+atedge+0));
__m256i t1=_mm256_loadu_si256((const __m256i*)(scratch+atedge+4));
__m256i t2=_mm256_loadu_si256((const __m256i*)(scratch+atedge+8));
__m256i t3=_mm256_loadu_si256((const __m256i*)(scratch+atedge+12));
__m256i t4=_mm256_loadu_si256((const __m256i*)(scratch+atedge+16));
__m256i t5=_mm256_loadu_si256((const __m256i*)(scratch+atedge+20));
__m256i z0_0=_mm256_blend_epi32(_mm256_blend_epi32(_mm256_permute4x64_epi64(t0,12),_mm256_permute4x64_epi64(t1,32),48),_mm256_permute4x64_epi64(t2,64),192);
__m256i z0_1=_mm256_blend_epi32(_mm256_blend_epi32(_mm256_permute4x64_epi64(t0,1),_mm256_permute4x64_epi64(t1,48),60),_mm256_permute4x64_epi64(t2,128),192);
__m256i z0_2=_mm256_blend_epi32(_mm256_blend_epi32(_mm256_permute4x64_epi64(t0,2),_mm256_permute4x64_epi64(t1,4),12),_mm256_permute4x64_epi64(t2,192),240);
__m256i z1_0=_mm256_blend_epi32(_mm256_blend_epi32(_mm256_permute4x64_epi64(t3,12),_mm256_permute4x64_epi64(t4,32),48),_mm256_permute4x64_epi64(t5,64),192);
__m256i z1_1=_mm256_blend_epi32(_mm256_blend_epi32(_mm256_permute4x64_epi64(t3,1),_mm256_permute4x64_epi64(t4,48),60),_mm256_permute4x64_epi64(t5,128),192);
__m256i z1_2=_mm256_blend_epi32(_mm256_blend_epi32(_mm256_permute4x64_epi64(t3,2),_mm256_permute4x64_epi64(t4,4),12),_mm256_permute4x64_epi64(t5,192),240);
_mm256_storeu_si256((__m256i*)(scratch+atedge+0),z0_0);
_mm256_storeu_si256((__m256i*)(scratch+atedge+8),z0_1);
_mm256_storeu_si256((__m256i*)(scratch+atedge+16),z0_2);
_mm256_storeu_si256((__m256i*)(scratch+atedge+4),z1_0);
_mm256_storeu_si256((__m256i*)(scratch+atedge+12),z1_1);
_mm256_storeu_si256((__m256i*)(scratch+atedge+20),z1_2);
atedge+=24;}atedge+=(nr[d]-g)*3;continue;}
if(d==4){unsigned g=0;for(;g+8<=nr[d];g+=8){
__m256i t0=_mm256_loadu_si256((const __m256i*)(scratch+atedge+0));
__m256i t1=_mm256_loadu_si256((const __m256i*)(scratch+atedge+4));
__m256i t2=_mm256_loadu_si256((const __m256i*)(scratch+atedge+8));
__m256i t3=_mm256_loadu_si256((const __m256i*)(scratch+atedge+12));
__m256i t4=_mm256_loadu_si256((const __m256i*)(scratch+atedge+16));
__m256i t5=_mm256_loadu_si256((const __m256i*)(scratch+atedge+20));
__m256i t6=_mm256_loadu_si256((const __m256i*)(scratch+atedge+24));
__m256i t7=_mm256_loadu_si256((const __m256i*)(scratch+atedge+28));
__m256i u0_0=_mm256_unpacklo_epi64(t0,t1);
__m256i u0_1=_mm256_unpackhi_epi64(t0,t1);
__m256i u0_2=_mm256_unpacklo_epi64(t2,t3);
__m256i u0_3=_mm256_unpackhi_epi64(t2,t3);
_mm256_storeu_si256((__m256i*)(scratch+atedge+0),_mm256_permute2x128_si256(u0_0,u0_2,32));
_mm256_storeu_si256((__m256i*)(scratch+atedge+8),_mm256_permute2x128_si256(u0_1,u0_3,32));
_mm256_storeu_si256((__m256i*)(scratch+atedge+16),_mm256_permute2x128_si256(u0_0,u0_2,49));
_mm256_storeu_si256((__m256i*)(scratch+atedge+24),_mm256_permute2x128_si256(u0_1,u0_3,49));
__m256i u1_0=_mm256_unpacklo_epi64(t4,t5);
__m256i u1_1=_mm256_unpackhi_epi64(t4,t5);
__m256i u1_2=_mm256_unpacklo_epi64(t6,t7);
__m256i u1_3=_mm256_unpackhi_epi64(t6,t7);
_mm256_storeu_si256((__m256i*)(scratch+atedge+4),_mm256_permute2x128_si256(u1_0,u1_2,32));
_mm256_storeu_si256((__m256i*)(scratch+atedge+12),_mm256_permute2x128_si256(u1_1,u1_3,32));
_mm256_storeu_si256((__m256i*)(scratch+atedge+20),_mm256_permute2x128_si256(u1_0,u1_2,49));
_mm256_storeu_si256((__m256i*)(scratch+atedge+28),_mm256_permute2x128_si256(u1_1,u1_3,49));
atedge+=32;}atedge+=(nr[d]-g)*4;continue;}
unsigned g=0;for(;g+8<=nr[d];g+=8){uint64_t t[88];memcpy(t,scratch+atedge,d*64);for(unsigned k=0;k<d;k++)for(unsigned lane=0;lane<8;lane++)scratch[atedge+k*8+lane]=t[lane*d+k];atedge+=d*8;}
atedge+=(nr[d]-g)*d;
}
unsigned firstlong=bcell[b];for(unsigned d=1;d<12;d++)firstlong+=nr[d];
unsigned in=atedge;
for(unsigned cell=firstlong;cell<cptr;cell++){
const unsigned old=cells[cell]&CELLMAX;
if(old>=1024){
if(old>clustered_capacity){free(clustered);clustered_capacity=old;clustered=(uint64_t*)malloc((size_t)(old+32)*8);if(!clustered)abort();}
unsigned pos[64]={};
for(unsigned k=0;k<old;k++)++pos[unsigned(scratch[in+k])>>26];
unsigned next=0;for(unsigned j=0;j<64;j++){unsigned v=pos[j];pos[j]=next;next+=v;}
for(unsigned k=0;k<old;k++){uint64_t v=scratch[in+k];clustered[pos[unsigned(v)>>26]++]=v;}
memcpy(scratch+in,clustered,(size_t)old*8);
}
in+=old;
}
unsigned* column=(unsigned*)rec+begin;unsigned* weight=column+len;
unsigned p=begin;
for(;p+32<=stop;p+=32){
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));
__m256i a2=_mm256_loadu_si256((const __m256i*)(scratch+j+16)),b2=_mm256_loadu_si256((const __m256i*)(scratch+j+20));
__m256i a3=_mm256_loadu_si256((const __m256i*)(scratch+j+24)),b3=_mm256_loadu_si256((const __m256i*)(scratch+j+28));
a0=_mm256_permutevar8x32_epi32(a0,pm);b0=_mm256_permutevar8x32_epi32(b0,pm);
a1=_mm256_permutevar8x32_epi32(a1,pm);b1=_mm256_permutevar8x32_epi32(b1,pm);
a2=_mm256_permutevar8x32_epi32(a2,pm);b2=_mm256_permutevar8x32_epi32(b2,pm);
a3=_mm256_permutevar8x32_epi32(a3,pm);b3=_mm256_permutevar8x32_epi32(b3,pm);
__m256i k0=_mm256_srli_epi32(_mm256_permute2x128_si256(a0,b0,0x20),RBITS),v0=_mm256_permute2x128_si256(a0,b0,0x31);
__m256i k1=_mm256_srli_epi32(_mm256_permute2x128_si256(a1,b1,0x20),RBITS),v1=_mm256_permute2x128_si256(a1,b1,0x31);
__m256i k2=_mm256_srli_epi32(_mm256_permute2x128_si256(a2,b2,0x20),RBITS),v2=_mm256_permute2x128_si256(a2,b2,0x31);
__m256i k3=_mm256_srli_epi32(_mm256_permute2x128_si256(a3,b3,0x20),RBITS),v3=_mm256_permute2x128_si256(a3,b3,0x31);
packed24_put8((unsigned char*)(column+begin)+(size_t)(p-begin+0)*3,k0);
packed24_put8((unsigned char*)(column+begin)+(size_t)(p-begin+8)*3,k1);
packed24_put8((unsigned char*)(column+begin)+(size_t)(p-begin+16)*3,k2);
packed24_put8((unsigned char*)(column+begin)+(size_t)(p-begin+24)*3,k3);
_mm256_stream_si256((__m256i*)(weight+p+0),v0);
_mm256_stream_si256((__m256i*)(weight+p+8),v1);
_mm256_stream_si256((__m256i*)(weight+p+16),v2);
_mm256_stream_si256((__m256i*)(weight+p+24),v3);
}
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_permutevar8x32_epi32(a,pm);b=_mm256_permutevar8x32_epi32(b,pm);
__m256i key=_mm256_srli_epi32(_mm256_permute2x128_si256(a,b,0x20),RBITS),val=_mm256_permute2x128_si256(a,b,0x31);
packed24_put8((unsigned char*)(column+begin)+(size_t)(p-begin)*3,key);
_mm256_stream_si256((__m256i*)(weight+p),val);
}
for(;p<stop;p++){uint64_t v=scratch[p-begin];unsigned k=(unsigned)v>>RBITS;memcpy((unsigned char*)(column+begin)+(size_t)(p-begin)*3,&k,3);weight[p]=(unsigned)(v>>32);}
}
}
free(clustered);
bcell[bins]=cptr;
_mm_sfence();
}
template<unsigned D,bool First> static inline void short_rows(unsigned count,unsigned& c,unsigned& p,const uint16_t*cells,const unsigned*col,const unsigned*wt,const unsigned*x,unsigned*y){
unsigned j=0;for(;j+8<=count;j+=8,c+=8,p+=8*D){
__m256i rows=_mm256_cvtepu16_epi32(_mm_loadu_si128((const __m128i*)(cells+c)));
__m256i acc=(First||D<=2)?_mm256_setzero_si256():_mm256_i32gather_epi32((const int*)y,rows,4);
__m256i odd=_mm256_setzero_si256();
for(unsigned k=0;k<D;k++){__m256i ix=packed24_get8(col,p+k*8);__m256i w=_mm256_loadu_si256((const __m256i*)(wt+p+k*8));auto product=_mm256_mullo_epi32(w,_mm256_i32gather_epi32((const int*)x,ix,4));if constexpr(D>=8){if(k&1)odd=_mm256_add_epi32(odd,product);else acc=_mm256_add_epi32(acc,product);}else acc=_mm256_add_epi32(acc,product);
_mm_prefetch(((const char*)col+(size_t)(p+k*8+32)*3),_MM_HINT_NTA);_mm_prefetch((const char*)(wt+p+k*8+32),_MM_HINT_NTA);}
if constexpr(D>=8)acc=_mm256_add_epi32(acc,odd);
_mm_prefetch((const char*)(cells+c+64),_MM_HINT_NTA);
alignas(32)unsigned v[8];_mm256_store_si256((__m256i*)v,acc);for(unsigned lane=0;lane<8;lane++){if constexpr(First||D>2)y[cells[c+lane]]=v[lane];else y[cells[c+lane]]+=v[lane];}
}
for(;j<count;j++,c++,p+=D){unsigned v=0;if constexpr(D>=8){__m256i ids=packed24_get8(col,p),weight=_mm256_loadu_si256((const __m256i*)(wt+p));__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(D),_mm256_setr_epi32(0,1,2,3,4,5,6,7));__m256i vals;if constexpr(D>=8)vals=_mm256_i32gather_epi32((const int*)x,ids,4);else vals=_mm256_mask_i32gather_epi32(_mm256_setzero_si256(),(const int*)x,ids,mask,4);auto prod=_mm256_mullo_epi32(vals,weight);auto sum=_mm_add_epi32(_mm256_castsi256_si128(prod),_mm256_extracti128_si256(prod,1));sum=_mm_hadd_epi32(sum,sum);sum=_mm_hadd_epi32(sum,sum);v=_mm_cvtsi128_si32(sum);for(unsigned k=8;k<D;k++)v+=wt[p+k]*x[packed24_get1(col,p+k)];}else for(unsigned k=0;k<D;k++)v+=wt[p+k]*x[packed24_get1(col,p+k)];if constexpr(First)y[cells[c]]=v;else y[cells[c]]+=v;}
}
static __attribute__((noinline,noclone)) void step(
unsigned b0,unsigned b1,const unsigned* bstart,const unsigned* bcell,
const uint32_t* cells,const unsigned* small,const unsigned* column,const unsigned* xw,unsigned* y,
unsigned* ybuf,unsigned zfirst){
for(unsigned b=b0;b<b1;b++){
const unsigned begin=bstart[b],len=bstart[b+1]-begin;
const unsigned* colb=column+((size_t)begin<<1);const unsigned* wtb=colb+len;
const unsigned rowbase=(b-b0)<<RBITS;
unsigned* ybase=y+rowbase;
if(zfirst){const __m256i z=_mm256_setzero_si256();for(unsigned k=0;k<RN;k+=8)_mm256_store_si256((__m256i*)(ybuf+k),z);ybase=ybuf;}
unsigned p=0,c=0;const uint16_t*shortcells=(const uint16_t*)(cells+bcell[b]);
if(zfirst){short_rows<1,true>(small[b*12+1],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<2,true>(small[b*12+2],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<3,true>(small[b*12+3],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<4,true>(small[b*12+4],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<5,true>(small[b*12+5],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<6,true>(small[b*12+6],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<7,true>(small[b*12+7],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<8,true>(small[b*12+8],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<9,true>(small[b*12+9],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<10,true>(small[b*12+10],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<11,true>(small[b*12+11],c,p,shortcells,colb,wtb,xw,ybase);
}else{short_rows<1,false>(small[b*12+1],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<2,false>(small[b*12+2],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<3,false>(small[b*12+3],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<4,false>(small[b*12+4],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<5,false>(small[b*12+5],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<6,false>(small[b*12+6],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<7,false>(small[b*12+7],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<8,false>(small[b*12+8],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<9,false>(small[b*12+9],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<10,false>(small[b*12+10],c,p,shortcells,colb,wtb,xw,ybase);
short_rows<11,false>(small[b*12+11],c,p,shortcells,colb,wtb,xw,ybase);
}
c+=bcell[b];
for(;c<bcell[b+1];c++){
_mm_prefetch((const char*)(cells+c+16),_MM_HINT_NTA);
const uint32_t cell=cells[c];
const unsigned row=cell>>CELLSH,ln=cell&CELLMAX;
unsigned sum;
{
__m256i acc0=_mm256_setzero_si256(),acc1=_mm256_setzero_si256(),acc2=_mm256_setzero_si256(),acc3=_mm256_setzero_si256();
unsigned k=0;
_mm_prefetch(((const char*)colb+(size_t)(p+32)*3),_MM_HINT_NTA);_mm_prefetch((const char*)(wtb+p+32),_MM_HINT_NTA);
for(;k+32<=ln;k+=32){
_mm_prefetch((const char*)colb+(size_t)(p+k)*3+192,_MM_HINT_NTA);_mm_prefetch((const char*)colb+(size_t)(p+k)*3+256,_MM_HINT_NTA);_mm_prefetch((const char*)colb+(size_t)(p+k)*3+320,_MM_HINT_NTA);
_mm_prefetch((const char*)(wtb+p+k+64),_MM_HINT_NTA);_mm_prefetch((const char*)(wtb+p+k+80),_MM_HINT_NTA);
__m256i i0=packed24_get8(colb,p+k+0),w0=_mm256_loadu_si256((const __m256i*)(wtb+p+k+0));
__m256i i1=packed24_get8(colb,p+k+8),w1=_mm256_loadu_si256((const __m256i*)(wtb+p+k+8));
__m256i i2=packed24_get8(colb,p+k+16),w2=_mm256_loadu_si256((const __m256i*)(wtb+p+k+16));
__m256i i3=packed24_get8(colb,p+k+24),w3=_mm256_loadu_si256((const __m256i*)(wtb+p+k+24));
__m256i s0=_mm256_i32gather_epi32((const int*)xw,i0,4);acc0=_mm256_add_epi32(acc0,_mm256_mullo_epi32(w0,s0));
__m256i s1=_mm256_i32gather_epi32((const int*)xw,i1,4);acc1=_mm256_add_epi32(acc1,_mm256_mullo_epi32(w1,s1));
__m256i s2=_mm256_i32gather_epi32((const int*)xw,i2,4);acc2=_mm256_add_epi32(acc2,_mm256_mullo_epi32(w2,s2));
__m256i s3=_mm256_i32gather_epi32((const int*)xw,i3,4);acc3=_mm256_add_epi32(acc3,_mm256_mullo_epi32(w3,s3));
}
for(;k+8<=ln;k+=8){
__m256i ix=packed24_get8(colb,p+k),w=_mm256_loadu_si256((const __m256i*)(wtb+p+k));
acc0=_mm256_add_epi32(acc0,_mm256_mullo_epi32(w,_mm256_i32gather_epi32((const int*)xw,ix,4)));
}
if(k<ln){
const unsigned rem=ln-k;
__m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(rem),_mm256_setr_epi32(7,6,5,4,3,2,1,0));
__m256i ix=packed24_get8(colb,p+ln-8),w=_mm256_loadu_si256((const __m256i*)(wtb+p+ln-8));
__m256i v=_mm256_mask_i32gather_epi32(_mm256_setzero_si256(),(const int*)xw,ix,mask,4);
acc0=_mm256_add_epi32(acc0,_mm256_mullo_epi32(w,v));
}
__m256i acc=_mm256_add_epi32(_mm256_add_epi32(acc0,acc1),_mm256_add_epi32(acc2,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);
}
ybase[row]+=sum;
p+=ln;
}
if(zfirst){unsigned* yb=y+rowbase;const unsigned* s=ybuf;
for(unsigned k=0;k<RN;k+=8)_mm256_stream_si256((__m256i*)(yb+k),_mm256_load_si256((const __m256i*)(s+k)));
}
}
if(zfirst)_mm_sfence();
}
}
static void zero_nt(unsigned* p,size_t nw){
size_t i=0;
while(i<nw&&(((uintptr_t)(p+i))&31))p[i++]=0;
for(;i+8<=nw;i+=8)_mm256_stream_si256((__m256i*)(p+i),_mm256_setzero_si256());
for(;i<nw;i++)p[i]=0;
_mm_sfence();
}
static void* allocate4096(size_t bytes){
constexpr size_t H=size_t(1)<<21;size_t span=(bytes+H-1)&~(H-1);if(!span)span=H;
void*p=nullptr;if(posix_memalign(&p,H,span))abort();
(void)madvise(p,span,MADV_HUGEPAGE);return p;}
void sparse_power20(unsigned n,unsigned m,const Edge* A,const unsigned* x,unsigned* out){
const unsigned nbb=win::nbb_of(n),nwin=win::nwin_of(n),bins=nwin*nbb,ncb=win::ncb_of(bins);
const unsigned capacity=m+(win::FLUSH-1)*bins;
uint64_t* rec=(uint64_t*)allocate4096((size_t)capacity*8);
unsigned* bstart=(unsigned*)allocate4096(((size_t)bins+1)*4);
unsigned* bcell=(unsigned*)allocate4096(((size_t)bins+1)*4);unsigned* small=(unsigned*)allocate4096((size_t)bins*48);
unsigned* coff=(unsigned*)allocate4096(((size_t)ncb+1)*4);
unsigned* cex=(unsigned*)allocate4096(((size_t)ncb+1)*4);
unsigned char* side=(unsigned char*)allocate4096((size_t)m+((size_t)ncb+1)*win::FLUSH+4096);
const size_t cellcap=std::min((size_t)m,(size_t)bins*RN)+(size_t)bins+16;
uint32_t* cells=(uint32_t*)malloc(cellcap*4);
unsigned* temp=(unsigned*)allocate4096((size_t)n*4);unsigned*root_other=(unsigned*)allocate4096((size_t)n*4);unsigned*root_seed=(unsigned*)allocate4096((size_t)n*4);memcpy(root_seed,x,(size_t)n*4);
if(!cells||!side)abort();
if(n==(1u<<23))win::build<true>(n,m,[&](unsigned e)->const Edge&{return A[e];},bstart,coff,cex,rec,side);else win::build<false>(n,m,[&](unsigned e)->const Edge&{return A[e];},bstart,coff,cex,rec,side);
unsigned SC=0,SP=0;
for(unsigned b=0;b<bins;b++){const unsigned s=bstart[b+1]-bstart[b];if(s>SC)SC=s;}
for(unsigned c=0;c<ncb;c++){const unsigned b0=c*win::CBC,b1=std::min(bins,b0+win::CBC);const unsigned s=bstart[b1]-bstart[b0];if(s>SP)SP=s;}
uint64_t* scratch=(uint64_t*)malloc(((size_t)SC+32)*8);
uint64_t* split=(uint64_t*)allocate4096(((size_t)SP+32)*8);
if(!scratch||!split)abort();
win::sort_out(n,bstart,rec,cells,bcell,small,scratch,coff,cex,side,split);
free(scratch);free(split);free(side);free(coff);free(cex);
const bool zfull=((n&(RN-1))==0);
const bool outok=zfull&&(((uintptr_t)out&31u)==0);
unsigned* ybuf=(unsigned*)allocate4096((size_t)RN*4);
for(unsigned r=0;r<20;r++){
const unsigned* cur=(r==0)?root_seed:((r&1)?temp:root_other);
unsigned* dst=(r==19&&outok)?out:((r&1)?root_other:temp);
if(!zfull){zero_nt(dst,n);for(unsigned w=0;w<nwin;w++)
win::step(w*nbb,(w+1)*nbb,bstart,bcell,cells,small,(const unsigned*)rec,cur+((size_t)w*WN),dst,ybuf,0u);}
else for(unsigned w=0;w<nwin;w++)
win::step(w*nbb,(w+1)*nbb,bstart,bcell,cells,small,(const unsigned*)rec,cur+((size_t)w*WN),dst,ybuf,w==0?1u:0u);
}
if(!outok)memcpy(out,root_other,(size_t)n*4);
free(ybuf);free(root_seed);free(root_other);free(small);free(cells);free(temp);free(bcell);free(bstart);free(rec);
}