/* 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.
*/
#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>
static constexpr unsigned SPARSE_BUCKET_BITS=11;
namespace sparse_stream {
enum{FLUSH=64};
struct alignas(64) Fifo{uint64_t data[FLUSH];};
template<class GetSource,class GetRecord>
static unsigned build(unsigned n,unsigned m,GetSource get_source,GetRecord get_record,
unsigned*offset,uint64_t*record){
constexpr unsigned bits=SPARSE_BUCKET_BITS,rows=1u<<bits,mask=rows-1;
const unsigned bins=(n+mask)>>bits;
unsigned*count=(unsigned*)calloc(bins,4),*start=(unsigned*)malloc(((size_t)bins+1)*4),*cursor=(unsigned*)malloc(((size_t)bins+1)*4);
unsigned char*fill=(unsigned char*)calloc(bins,1);Fifo*fifo=nullptr;
if(posix_memalign((void**)&fifo,64,(size_t)bins*sizeof(Fifo))||!count||!start||!cursor||!fill)abort();
for(unsigned e=0;e<m;e++)++count[get_source(e)>>bits];
unsigned padded=0;for(unsigned b=0;b<bins;b++){start[b]=padded;padded+=(count[b]+FLUSH-1)&~(FLUSH-1);}start[bins]=padded;memcpy(cursor,start,((size_t)bins+1)*4);
for(unsigned e=0;e<m;e++){auto r=get_record(e);unsigned b=r.src>>bits,j=fill[b];fifo[b].data[j]=(uint64_t(r.weight)<<32)|((r.dst<<bits)|(r.src&mask));
if(j+1==FLUSH){for(unsigned k=0;k<FLUSH;k+=4)_mm256_stream_si256((__m256i*)(record+cursor[b]+k),_mm256_load_si256((const __m256i*)(fifo[b].data+k)));cursor[b]+=FLUSH;fill[b]=0;}else fill[b]=j+1;
}
_mm_sfence();
for(unsigned b=0;b<bins;b++){unsigned rowcount=std::min(rows,n-(b<<bits)),j=fill[b],at=cursor[b];memcpy(record+at,fifo[b].data,j*8);for(unsigned p=at+j;p<start[b+1];p++)record[p]=rowcount-1;}
for(unsigned b=0;b<bins;b++){unsigned histogram[rows]={},begin=start[b],stop=start[b+1],rowbase=b<<bits;for(unsigned p=begin;p<stop;p++)++histogram[unsigned(record[p])&mask];unsigned first=begin,rowcount=std::min(rows,n-rowbase);for(unsigned r=0;r<rowcount;r++){offset[rowbase+r]=first;first+=histogram[r];}}
offset[n]=padded;free(fifo);free(fill);free(cursor);free(start);free(count);return padded;
}
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,target,original;};
static unsigned degree_bin(unsigned d){return d<8?d:36u-(unsigned)__builtin_clz(d);}
static void make_permutation(unsigned n,const unsigned*offset,unsigned*perm,unsigned*hist,
RootRow*rows,unsigned*smallrows,unsigned*nbig,unsigned*nsmall){
unsigned count[37]={},next[37];
for(unsigned i=0;i<n;++i)++count[degree_bin(offset[i+1]-offset[i])];
memcpy(hist,count,sizeof(count));
unsigned first=0;
for(unsigned b=37;b-->0;){next[b]=first;first+=count[b];}
unsigned k=0,s=0;
for(unsigned i=0;i<n;++i){unsigned d=offset[i+1]-offset[i];unsigned b=degree_bin(d);unsigned p=next[b]++;perm[i]=p;
if(b>=8)rows[k++]={offset[i],offset[i+1],p,i};
else if(b)smallrows[s++]=i;}
*nbig=k;*nsmall=s;
}
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 __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[last?rows[ri].original:rows[ri].target]=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=_mm256_add_epi32(acc0,_mm256_mullo_epi32(weights0,selected0));
__m256i selected1=_mm256_i32gather_epi32((const int*)x,index1,4);acc1=_mm256_add_epi32(acc1,_mm256_mullo_epi32(weights1,selected1));
__m256i selected2=_mm256_i32gather_epi32((const int*)x,index2,4);acc2=_mm256_add_epi32(acc2,_mm256_mullo_epi32(weights2,selected2));
__m256i selected3=_mm256_i32gather_epi32((const int*)x,index3,4);acc3=_mm256_add_epi32(acc3,_mm256_mullo_epi32(weights3,selected3));
}
for(;p+8<=end;p+=8){_mm_prefetch((const char*)(column+p+16),_MM_HINT_NTA);_mm_prefetch((const char*)(weight+p+16),_MM_HINT_NTA);__m256i index=_mm256_loadu_si256((const __m256i*)(column+p)),w=_mm256_loadu_si256((const __m256i*)(weight+p));acc0=_mm256_add_epi32(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=_mm256_add_epi32(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[last?rows[ri].original:rows[ri].target]=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*)(q.weight+at));__m256i vals=_mm256_setr_epi32((int)x[q.column[at+0]],(int)x[q.column[at+1]],(int)x[q.column[at+2]],(int)x[q.column[at+3]],(int)x[q.column[at+4]],(int)x[q.column[at+5]],(int)x[q.column[at+6]],(int)x[q.column[at+7]]);acc=_mm256_add_epi32(acc,_mm256_mullo_epi32(w,vals));_mm_prefetch((const char*)(q.column+at+16),_MM_HINT_NTA);_mm_prefetch((const char*)(q.weight+at+16),_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*)(q.weight+at));__m256i vals=_mm256_setr_epi32((int)x[q.column[at+0]],(int)x[q.column[at+1]],(int)x[q.column[at+2]],(int)x[q.column[at+3]],(int)x[q.column[at+4]],(int)x[q.column[at+5]],(int)x[q.column[at+6]],(int)x[q.column[at+7]]);root_acc0=_mm256_add_epi32(root_acc0,_mm256_mullo_epi32(w,vals));_mm_prefetch((const char*)(q.column+at+16),_MM_HINT_NTA);_mm_prefetch((const char*)(q.weight+at+16),_MM_HINT_NTA);}
{size_t at=(size_t)((group+1)*D+k)*8;__m256i w=_mm256_loadu_si256((const __m256i*)(q.weight+at));__m256i vals=_mm256_setr_epi32((int)x[q.column[at+0]],(int)x[q.column[at+1]],(int)x[q.column[at+2]],(int)x[q.column[at+3]],(int)x[q.column[at+4]],(int)x[q.column[at+5]],(int)x[q.column[at+6]],(int)x[q.column[at+7]]);root_acc1=_mm256_add_epi32(root_acc1,_mm256_mullo_epi32(w,vals));_mm_prefetch((const char*)(q.column+at+16),_MM_HINT_NTA);_mm_prefetch((const char*)(q.weight+at+16),_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<=2){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 twenty(unsigned n,unsigned m,const unsigned*offset,unsigned*column,
unsigned*weight,uint64_t*record,const unsigned*x,unsigned*out,
unsigned*temp,unsigned*perm){
unsigned hist[37];unsigned big_count=0,nsmall=0;
RootRow*rows=(RootRow*)malloc((size_t)(n?n:1)*sizeof(RootRow));if(!rows)abort();
unsigned*smallrows=(unsigned*)malloc((size_t)(n?n:1)*4);if(!smallrows)abort();
make_permutation(n,offset,perm,hist,rows,smallrows,&big_count,&nsmall);
sparse_stream::resort(n,m,offset,record,column,weight,perm);free(record);
SmallBatch small[8]{};unsigned live=n-hist[0];
{unsigned f=0;for(int b=36;b>=0;--b){if(b>=1&&b<=7)small[b].begin=f;f+=hist[b];}}
for(unsigned d=1;d<8;d++)small[d].count=hist[d];
for(unsigned d=1;d<8;d++){size_t count=(size_t)((small[d].count+7)/8)*8*d;small[d].column=(unsigned*)calloc(count?count:1,4);small[d].weight=(unsigned*)calloc(count?count:1,4);if(!small[d].column||!small[d].weight)abort();small[d].original=(unsigned*)malloc((size_t)(small[d].count?small[d].count:1)*4);if(!small[d].original)abort();}
for(unsigned q2=0;q2<nsmall;++q2){unsigned i=smallrows[q2];unsigned d=offset[i+1]-offset[i];SmallBatch&q=small[d];unsigned r=perm[i]-q.begin,g=r>>3,lane=r&7;q.original[r]=i;
for(unsigned k=0;k<d;++k){size_t dst=(size_t)(g*d+k)*8+lane;unsigned src=offset[i]+k;q.column[dst]=column[src];q.weight[dst]=weight[src];}}
for(unsigned i=0;i<n;i++)out[perm[i]]=x[i];memset(temp+live,0,(size_t)(n-live)*4);const unsigned*cur=out;
for(unsigned r=0;r<20;r++){bool last=r==19;unsigned*dst=(r&1)?out:temp;if(last)memset(out,0,(size_t)n*4);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);}else{small_step<1>(small[1],cur,dst);small_step<2>(small[2],cur,dst);small_step<3>(small[3],cur,dst);small_step<4>(small[4],cur,dst);small_step<5>(small[5],cur,dst);small_step<6>(small[6],cur,dst);small_step<7>(small[7],cur,dst);}cur=dst;if(r==0){memset(out+live,0,(size_t)(n-live)*4);prune_big(big_count,rows,column,weight,live);}}
free(smallrows);free(rows);for(unsigned d=1;d<8;d++){free(small[d].weight);free(small[d].column);free(small[d].original);}
}
}
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){
const unsigned bins=(n+((1u<<SPARSE_BUCKET_BITS)-1))>>SPARSE_BUCKET_BITS,capacity=m+(sparse_stream::FLUSH-1)*bins;
uint64_t*record=(uint64_t*)allocate4096((size_t)capacity*8);
unsigned*off=(unsigned*)allocate4096(((size_t)n+1)*4);
unsigned*col=(unsigned*)allocate4096((size_t)capacity*4);
unsigned*val=(unsigned*)allocate4096((size_t)capacity*4);
unsigned*temp=(unsigned*)allocate4096((size_t)n*4);
unsigned*perm=(unsigned*)allocate4096((size_t)n*4);
unsigned used=sparse_stream::build(n,m,[&](unsigned e){return A[e].src;},[&](unsigned e){return A[e];},off,record);
sparse_degree::twenty(n,used,off,col,val,record,x,out,temp,perm);
free(perm);free(temp);free(val);free(col);free(off);
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 526.819 ms | 277 MB + 448 KB | Accepted | Score: 100 | 显示更多 |