~johan's blog
返回专辑
C++
·Johan·4 分钟阅读

缓存局部性：点云与图像遍历顺序

点云/图像遍历顺序、AoS vs SoA、分块与 perf 测量，减少 cache miss 的实操。

#C++#性能#Eigen
缓存局部性：点云与图像遍历顺序

1. 同样算法，差一个数量级

Velodyne 128 线滤 z 阈值，PCL PassThrough 在 120 万点上吃满 10ms 预算——不是算法 smarter，是 PCL PointXYZ 的 AoS 布局让「只读 z」每点 stride 16 字节，一条 cache line 装不满几个有效 z 值。改成 SoA 临时 buffer 两遍 pass，wall time 从 10ms 降到 6ms，结果 bit-identical。

局部性不是 premature optimization，是大数组上的默认考量。机器人感知里这类差异直接决定能不能在 33ms 帧预算内做完滤波。profile 上应看到 L1-dcache-load-misses 随 pass 数亚线性增长，而不是线性——若 miss 降了但 wall time 无感，瓶颈在 IO/锁/分配，改 layout 不是解。上次底盘上 ground filter 因为 layout 不对，profiler 里 cache miss 占 40%，改 SoA 后降到 5%，同一算法快了 1.7 倍。

2. AoS 与 SoA 的取舍

Array-of-Structures 对「取单点全部字段」友好；Structure-of-Arrays 对「只对某一 field 做 pass」友好。PCL PointXYZI 滤地面时只读 z，却把 x,y,intensity 一起拉进 cache line，命中率差一个数量级时 wall time 能差 2×。这是大数组上的默认考量，不是 premature optimization。

同一帧上连跑三个以上只读 field pass，SoA 的 upfront 转换成本才划算。只滤一次 z 就回 PCL 格式，转换开销可能抵消收益。用 reserve(n) 预分配四个 parallel vector，单次扫描 scatter；别在 inner loop 四次 push_back，branch 与 capacity check 会吃掉局部性收益。

cpp
struct CloudSoA {
  std::vector<float> x, y, z;
  size_t size() const { return x.size(); }
};

void filter_z(CloudSoA& c, float z_max) {
  size_t w = 0;
  for (size_t i = 0; i < c.size(); ++i) {
    if (c.z[i] <= z_max) {
      c.x[w] = c.x[i]; c.y[w] = c.y[i]; c.z[w] = c.z[i];
      ++w;
    }
  }
  c.x.resize(w); c.y.resize(w); c.z.resize(w);
}

3. 遍历顺序与图像

OpenCV Mat 行连续存储；外层走 rows、内层走 cols，与 mat.step 一致。列优先扫 1080p 大图 L1 miss 明显——不是 OpenCV 慢，是访问模式与内存布局不匹配。

ROI 用 cv::Mat roi = img(cv::Rect(...)) 仍共享底层，注意 isContinuous() 决定能否一行 memcpy。点云 octree 建树若 random push_back 节点，pointer chasing miss 高；按 morton/z-order 排序点索引再建树，often 比调 SIMD 更划算——但构建成本不同，要测 end-to-end，不能只看建树阶段。

4. 对齐、分块与 false sharing

多线程分块处理点云时，块边界按 cache line（64B）对齐，避免两线程写相邻计数器。OpenMP static schedule 与 manual tile 对齐。tile 大小匹配 L1：64k 点/tile 在 Skylake 上 empirical 最优。

__builtin_prefetch 只在对 profile 已证实的 hot loop 加——ARM 上有时反效果，别全局撒 prefetch。结构体热字段放前 64B，冷字段（intensity ring）后置。改 layout 后数值结果应 bit-identical（整数索引）或 within epsilon（float）。ground remove 推荐两遍 pass：第一遍只读 z 写 bitmask，第二遍 compact，比单 pass AoS 常更快。

cpp
alignas(64) std::atomic<int> block_counts[8];

5. 失败症状

  • profiler 见 memcpy 占 40%——AoS↔SoA 转换过多，或 layout 来回切换。
  • 点云 size 翻倍，耗时涨 4×——随机访问或 std::map 索引。
  • L3 miss 降 10% 但 wall time 无感——瓶颈在 IO/锁，不在 cache。
  • 改 layout 后数值漂移——float 累加顺序变了，要 within epsilon 验收。

6. 验收

bash
perf stat -e cache-references,cache-misses ./filter_benchmark --points 1000000
  • cache-miss rate 应从 ~20% 降到 ~2% 量级（视 CPU）。
  • ground remove 两遍 pass（pass1 只读 z 写 bitmask，pass2 compact）比单 pass AoS 更快。
  • 集成测试用 bag replay 验证 end-to-end，micro-bench 只证明 kernel 可行。

7. 案例：ground remove 两遍 pass

自定义 ground filter 我会临时 SoA 布局或按 field 分 pass——第一遍只扫 z 写 bitmask，第二遍 compact 有效点。Velodyne 128 线在我们 dataset 上比 PCL PassThrough 快 1.7×，结果 bit-identical。从 PCL AoS 转 SoA 有 upfront 成本，适合同一帧上连跑多个 field pass 的场景。验收时对照 PCL 原版输出，整数索引 bit-identical，浮点 within epsilon。

8. 与 pipeline 预算对齐

局部性优化要映射到一帧预算里的毫秒数，不是 perf stat 数字好看就行。若 L3 miss 降了但 wall time 无感，瓶颈在 IO/锁/分配——改 layout 不是解。集成测试用 bag replay 验证 end-to-end，micro-bench 只证明 kernel 可行。行主序扫 Mat、SoA 多点 pass，perf stat 验证 miss 降。

9. 决策：何时值得改 layout

改 layout 前先问三个问题：同一帧上该 field 会被读几次？转换成本占 wall time 多少？改完后下游模块是否仍要求 PCL AoS 格式？若答案是「只读一次」「转换占 30%」「下游硬要 PCL」，SoA 可能不值得。若答案是「连读三次以上」「转换占 5%」「下游可接受自定义格式」，SoA 几乎总是赢。别在 inner loop 里 AoS↔SoA 来回转——选定一种 layout 贯穿整条 pipeline，转换只做一次放在 ingress 或 egress。局部性优化的验收标准是 end-to-end wall time，不是 perf stat 里的 miss rate 数字。行主序扫 Mat、SoA 多点 pass，perf stat 验证 miss 降，bag replay 验证帧预算。改 layout 前先用 profiler 确认 cache 是瓶颈。

← 全部文章

johan's blog