使用 GPU 完成大规模计算

大数据点图在渲染前要先采样。这个场景一次要处理 100 万个圆，目标很明确：找出已经被其它圆完全盖住的点，在渲染前摘掉。少画一个不可见的点不会改变画面，却能直接减轻后续布局和绘制的压力。

这篇的第一版写得太干，只有结论没有过程，也没有一张图。这次我把当时的路重新走一遍：从一个写对的判断出发，撞上 O(n²) 的墙，用空间索引把墙拆矮，再把剩下的活交给 GPU。每一步都配了能动手的演示——包括最后那个跑分台，是一个真的 WebGL kernel，数字在你自己的机器上现跑。

整条管线长这样，两层，前后接力，不是二选一：

整体管线：空间索引和 GPU 是前后两层，不是两个备选方案。索引负责让比较次数从天文数字降回人间，GPU 负责把降下来之后依然庞大的同构计算一次铺开。

第一步：把「被盖住」说清楚

问题定义不许含糊。本文把“覆盖”定义为：圆 i 被某一个圆 j 完整包含，即圆心距离加 rᵢ 不大于 rⱼ。多个圆共同遮住一个圆属于另一个几何问题，这里不算。

写成代码就一行判断：

// 圆 j 是否把圆 i 整个盖住
function covered(i, j) {
  const dx = x[j] - x[i], dy = y[j] - y[i];
  return Math.hypot(dx, dy) + r[i] <= r[j];
}

输入收成一个圆数组，每项是 (x, y, r)；输出仍然是等长数组，1 表示命中上述条件，0 表示保留。

光看不等式没有手感。下面这个圆可以拖，注意虚线圈：它的半径正好是 r₂ − r₁，小圆的圆心一旦进入虚线圈，d + r₁ ≤ r₂ 就成立，整个圆被盖住——判断从一个几何关系变成了“点在不在圈里”。

演示 1 · 什么叫「被盖住」拖动橙色小圆试试

r₁ 保留

判断只看三个数：圆心距 d、小圆半径 r₁、大圆半径 r₂。把 r₁ 拉大，虚线圈会缩小——大圆能“吞下”的范围变小了；r₁ 逼近 r₂ 时虚线圈几乎缩成一个点，怎么拖都很难盖住。

问题本身不复杂。数据量把它变难了。

第二步：承认 O(n²) 撑不住

暴力解是每个圆和其它圆全比一遍，两层循环，复杂度 O(n²)。它不是写错了，它只是活不到 100 万：

n	比较次数 ≈ n²	直观感受
1 万	10⁸	主线程卡一下
10 万	10¹⁰	标签页假死
100 万	10¹²	按天计的等待

10¹² 次候选比较，这不是 JavaScript 循环再快一点能解决的问题——就算把每次比较优化到 1 纳秒，也要跑十几分钟。平方增长面前，常数优化是给自己找的安慰。要动的是那个平方本身。

第三步：网格把候选压下来

出路藏在数据的形状里：圆的分布有空间局部性。能盖住我的圆一定在我附近，跟画布另一头的圆比是白比。空间索引（四叉树或网格分块）负责把“全部圆”换成“附近的圆”。我用最朴素的均匀网格来演示，因为它好写、好查、好画出来。

网格有一个很舒服的性质，让查询可以只查一格：

若圆 j 完整盖住圆 i，那么 j 的圆盘必然盖住 i 的圆心。

所以建索引时把每个圆登记进它覆盖到的所有格子，查询时只取自己圆心所在的那一格，候选就一个不漏——大圆占格多是它自己付出的代价，小圆查询时反而干净。

// 建格：每个圆登记进它碰到的所有格子
for (const c of circles)
  for (const cell of cellsOverlapping(c))   // 以包围盒粗算即可
    grid[cell].push(c);

// 查询：只看圆心落在的那一格
candidates = grid[cellOf(c.x, c.y)];

下面这块画布放了 260 个圆。移动指针（或手指点按）选中任何一个，看它真正需要比较的候选有几个：

演示 2 · 网格怎么省掉九成以上的比较指到哪个圆，就看它的候选

移动指针选一个圆

橙色实心是选中的圆，橙色描边是它所在格子里登记过的候选（可能包括从别的格子伸过来的大圆），其余的圆全部不用碰。账每次都算给你看：暴力是 n−1 次，网格通常只剩个位数到十几个。

候选集降下来以后，剩余每组判断都在做同一件事：同一个不等式，套不同的数。一个圆的结果也不依赖另一个圆的结果。同构、无依赖——这两个词凑齐，就轮到 GPU 出场了。

第四步：剩下的活是 GPU 的形状

CPU 擅长复杂的、彼此纠缠的逻辑；GPU 擅长把同一段简单计算同时铺开到成千上万个数据上。覆盖判断正好长成后面这个形状：

同一个 kernel（那行不等式）被应用到一批候选圆上，每个判断互不依赖——串行是一格一格点亮，并行是一整排同时点亮。

为了快速验证并行计算这一层，当时我用了 GPU.js，让它处理 WebGL 的 kernel 生成和执行。kernel 写起来还是 JavaScript 的样子：

const kernel = gpu.createKernel(function (xs, ys, rs, n) {
  const i = this.thread.x;             // 我是第 i 个圆
  for (let j = 0; j < n; j++) {
    if (j === i) continue;
    const dx = xs[j] - xs[i], dy = ys[j] - ys[i];
    if (Math.sqrt(dx * dx + dy * dy) + rs[i] <= rs[j]) return 1;
  }
  return 0;
}).setOutput([count]);

但有几件事必须说在前面，都是踩过才知道的：

GPU.js 会把它支持的简单 JavaScript kernel 转成 shader，在浏览器里通常由 WebGL/WebGL2 执行。它不是任意 JavaScript 的透明加速器，对输入类型、循环和返回值都有约束——写复杂了直接编译失败。
GPU 不可用时它还可能静默回退到 CPU。你以为在跑 GPU，实际在跑一个更慢的 CPU 模拟。验证时必须确认实际执行模式（下一节的演示会把执行设备直接打出来）。
切换执行器不是零成本：适配层要把 x / y / r 整理成 GPU.js 支持的数值布局，设置输出规模与精度，还要把 TypedArray 或纹理结果转回上层需要的形式。好在图表引擎里采样和布局早已拆成独立函数，上层依然维持“圆数组进去、标记数组出来”的接口，改动被锁在适配层里。

第五步：亲手跑一遍

第一版文章到这里就结束了，因为完整的硬件、数据分布和计时记录当时没保存下来，我不愿意写一个无法复核的加速倍数。这次干脆换个做法：把实验台嵌进文章里。下面是同一个覆盖问题的三种解法——CPU 暴力、CPU 网格、GPU 暴力（手写的 WebGL2 kernel，零依赖，思路和 GPU.js 生成的 shader 一致）——数字在你机器上现跑，加速比是你自己的加速比。

演示 3 · 三种解法真实跑分检测 WebGL2…

规模 2 千 5 千 1 万 2 万

CPU 暴力

— CPU 网格

— GPU 暴力

—

2 万个圆时暴力是 4 亿次比较——慢是故意留给你看的。暴力部分做了分片，跑分不会卡死页面。

三条都算同一份数据、同一个不等式。值得看的不只是倍数：小规模时 GPU 未必赢（数据上传、结果回读、kernel 编译都要还账）；规模翻倍时，注意谁是四倍地变慢、谁几乎原地不动。GPU 行首跑含 shader 编译，第二次再跑更接近真实吞吐。

几个读数的门道：

网格常常比 GPU 还快。 这不丢人——它靠的是少干活（比较次数从 n² 掉到近似线性），GPU 靠的是快干活（还是 n² 次，只是同时干）。少干活永远优先于快干活，这正是两层管线里索引排在前面的原因。
GPU 的账单里一大半不是计算。 数据上传、结果回读、kernel 编译预热都在计时里。规模小时这些固定开销摊不薄，GPU 输给 CPU 是正常结果。
右上角那行执行设备要看一眼。 如果写着 SwiftShader 或 llvmpipe 之类，说明你在跑软件模拟的“GPU”——这就是 GPU.js 静默回退的同款陷阱，数字会难看得理直气壮。

什么时候不该上 GPU

这次实现留下的结论很清楚：先用四叉树或网格缩小候选集，再把剩余的同构比较交给 GPU。反过来，两种情况别硬上：任务无法拆成互不依赖的同构小块；或者数据搬运（上传 + 回读）已经比计算本身更贵——上面的跑分台在小规模档位就能让你亲眼看到第二种。

GPU 不是更快的 CPU，它是另一种形状的算力。先把问题修剪成它的形状，它才会快。