2. 稀疏数据格式与存储布局实战

上一节我们明确了稀疏矩阵“只存非零元”的基本思想，但真正落到工程实现时，第一个必须回答的问题是：非零元到底按什么顺序、用什么索引结构存？CSR、CSC、COO、ELL、HYB 这五种格式，本质上是对同一个稀疏矩阵的五种“记账方式”。选错格式，后续 SpMV、SpGEMM 等核函数可能慢数倍，甚至因填充率过高而耗尽显存。本节我们用一个统一的稀疏矩阵集，完成格式转换、存储开销量化，并把存储结构差异与计算性能差异对应起来。

一、五种格式的存储结构对照

先约定记号：矩阵规模为 m×n，非零元个数为 nnz。COO 最直观，用三个等长数组 row、col、val 逐条记录每个非零元的坐标和值，存储量为 nnz×(4+4+8)=16·nnz 字节（索引 int32、值 float64 计）。CSR 把行索引压缩掉，用 row_ptr（长度 m+1）记录每行在 col_idx 和 val 中的起止位置，存储量为 (m+1)×4 + nnz×4 + nnz×8。CSC 是 CSR 的转置版本，压缩的是列，存储量为 (n+1)×4 + nnz×12。ELL 按“每行最多非零元数”max_nnz_per_row 补齐成稠密矩形，用 indices 和 values 两个 m×max_nnz 数组，存储量为 m×max_nnz×12，填充率是它的命门。HYB 则是 ELL 存“规则部分”加 COO 存“长行溢出部分”的混合体，兼顾向量化与负载均衡。

上图用同一个 4×5、nnz=6 的示例矩阵把五种布局并排展开。可以看到：COO 最“啰嗦”，但插入和并行构建最方便；CSR 用 row_ptr 换掉了 nnz 个行索引，是 SpMV 的经典选择；ELL 把每行补齐到 max_nnz_per_row=2，多出 2 个填充位；HYB 只把“每行至少 1 个”的规则部分放进 ELL，把第 0、3 行的第二个非零元放进 COO 溢出区，存储反而最省。这个例子说明：格式优劣不是绝对的，取决于矩阵的行非零元分布是否均匀。

二、格式转换的实现要点

工程上最常用的转换路径是 COO→CSR 和 CSR→CSC。COO→CSR 的标准做法是两遍扫描：第一遍统计每行的非零元个数得到 row_count，对 row_count 做前缀和得到 row_ptr；第二遍按 COO 中记录的行号把 col 和 val 写到对应位置，并用一个游标数组 next_pos 记录每行当前写到的位置。伪代码如下：

// COO -> CSR（行主序，索引从 0 开始）
row_ptr[0] = 0;
for (i = 0; i < m; i++) row_ptr[i+1] = row_ptr[i] + row_count[i];
copy(row_ptr, next_pos);              // next_pos 为每行写入游标
for (k = 0; k < nnz; k++) {
    int r = coo_row[k];
    int p = next_pos[r]++;
    csr_col[p] = coo_col[k];
    csr_val[p] = coo_val[k];
}

CSR→CSC 则相当于对矩阵做转置后再压缩：以 CSR 的 col_idx 作为“行号”、以原行号作为“列号”，再做一次 COO→CSR 的计数排序即可。实际实现中要注意两点：一是索引类型，nnz 超过 2³¹ 时必须用 int64，否则会静默溢出；二是转换后的列索引在行内是否有序，很多 SpMV 核函数依赖行内有序来提升缓存命中，若原始 COO 无序，应在第二遍写入后对每行做一次局部排序，或直接在构建阶段按 (row, col) 排序。

三、存储开销的量化对比

把上面的公式代入一组有代表性的示例矩阵（参数为合理假设，用于说明趋势，非实测）：

表中按 int32 索引、float64 值计算。最值得警惕的是第二行：长尾分布下 ELL 的 max_nnz_per_row 被少数长行拉到 800，存储从 640 KB 暴涨到 96 MB，填充率超过 99%，这正是 ELL 在真实图数据和幂律矩阵上“翻车”的典型场景。HYB 通过把长行溢出到 COO，把存储压回 660 KB 量级。反过来，在均匀带状矩阵上，ELL 因为无需 row_ptr 且布局规整，存储甚至略优于 CSR。

四、从存储布局到计算性能

存储开销只是第一层，真正决定性能的是访存模式与并行度。CSR 做 SpMV 时，外层按行循环、内层遍历该行的列索引，行与行之间天然可并行，但每行的非零元数不同会导致线程负载不均；同时 x[col_idx[k]] 是间接寻址，缓存不友好。ELL 的内层循环长度固定为 max_nnz_per_row，编译器容易向量化，GPU 上每个线程处理一行、按列槽位对齐访问，规整性最好，但填充位会带来无效计算。HYB 在 GPU 上通常把 ELL 部分交给规则线程块、COO 部分单独一个核函数处理，兼顾向量化与负载均衡。COO 本身很少直接用于 SpMV，因为无法快速定位某一行，但它是并行构建和格式转换的最佳中间态。

五、一个可复现的对比实验框架

要量化“格式对计算性能的影响”，建议固定矩阵集与硬件，只改变存储格式。示例流程：用 scipy.sparse 生成或读入矩阵，分别构造 csr_matrix、csc_matrix、coo_matrix，ELL 与 HYB 可用 cupy 或自写内核实现；对每种格式跑 100 次 SpMV 取中位数耗时，并记录实际分配字节数。判断依据不只看时间，还要看有效带宽：用 nnz×12 字节除以耗时得到“有效吞吐”，再与硬件峰值带宽对比，若远低于峰值，说明瓶颈在间接寻址或填充计算，而非存储本身。这样，存储开销表与性能数据就能互相印证，而不是两张互不相干的表。