北京构力科技有限公司
项目概况
业务背景
墨斗云是 BimBase 旗下的插件之一，目标是面向 AI 时代做优质数据的批量生产——用智能识别算法成规模地替代传统人工数据标注。
识别算法的输入是建筑 3D 扫描产出的 OBJ。OBJ 是渲染格式：里面只有顶点，以及「哪三个点构成一个三角面」， 没有任何「这是一面墙」「这是一扇窗」的语义。下游要用的却是结构化信息——构件类型、位置坐标、尺寸。 算法需要从几何信息中识别构件，再输出结构化 JSON。
识别算法由算法团队开发，我的工作是把它接进软件、跑通端到端流程，并和产品经理一起按真实用户的使用路径做测试。 集成部分比计划提前两周完成。
问题是怎么发现的
- 端到端测试：用户侧延迟明显偏高 和产品经理按用户路径走流程时，大模型上的识别等待时间明显偏长，体验上不可接受。 算法团队此前只验证过识别效果，没有做过细粒度的性能测试。
- 把算法拆出来做离线测试 第一个要回答的问题是：慢在算法本身，还是慢在宿主软件。我把识别算法从软件里拆出来单独跑， 结果离线耗时和集成后的耗时差距不大——瓶颈在算法内部，不在软件集成层。
- 离线埋点，定位到具体阶段 在离线版本里分阶段埋点计时，同时找算法团队把原算法的思路和流程过了一遍，最终定位到墙体聚类（Wall Clustering）这一步。
-
看清原算法在做什么
原算法按几何特征分类：对空间中的三角面两两比较——空间位置、法向量、是否邻接，以及其他建筑空间特征——
判断两个面是否属于同一面墙。两两比较意味着
O(N²)，大型模型上约 1.5 亿次比较。
优化：先剪枝，再并行
大多数三角面在空间上相距很远，不可能属于同一面墙，原算法却仍会逐一比较。 优化的核心是让每个三角面只和附近的三角面比较。
- 第一层：按朝向和平面粗分桶 先按三角面法向量的水平方向、以及三角面所在平面到原点的距离做一次粗分类， 把明显不可能属于同一面墙的面分到不同的 wall bin 里。
-
第二层：bin 内建局部网格，只比邻近格
在每个 wall bin 内，根据墙面法向量建立局部二维坐标系，把三角面投影成平面坐标，再划成网格，
用
std::unordered_map<CellKey, std::vector<TriangleId>>记录每个格子里有哪些面。 之后每个面只和同格及相邻格里的面做几何判断，判定为同一面墙的用并查集（DSU）合并。- 比较次数：约 1.5 亿 → 2720 万。
- 耗时：约 206.6ms → 69.2ms，约 3.0×。
-
第三层：bin 之间互不干扰，OpenMP 并行
分桶之后，不同 wall bin 之间没有任何共享状态：每个 bin 有自己的 cell map、自己的 DSU、自己的中间结果。
于是用
#pragma omp parallel for schedule(dynamic, 1)按 bin 并行，最后串行合并结果。 没有共享哈希表、没有共享 DSU，也就不需要锁。- 4 线程下耗时：69.2ms → 28ms，约 2.4×。
- 用
dynamic调度是因为各个 bin 大小差别很大，静态均分容易让某个线程拖尾。
| 版本（Large，30.9 万三角面） | 比较次数 | Wall Clustering 耗时 | 相对原算法 |
|---|---|---|---|
| 原算法：两两比较 | ≈ 1.5 亿 | ≈ 206.6 ms | 1.0× |
| + 空间哈希分桶剪枝 | 2720 万 | ≈ 69.2 ms | ≈ 3.0× |
| + OpenMP 4 线程 | 2720 万 | ≈ 28 ms | ≈ 7.4× |
取 10 次正式测量的中位数（另有 3 次 warm-up），环境为 WSL2 / i7-14650HX（分配 4 逻辑核）/ GCC 13.3 -O3。WSL 下不同轮次有几个百分点的波动。
我先减少比较次数，再做并行。直接并行原来的两两比较，收益仍会受线程数限制。
为什么用 OpenMP
- std::thread：C++17 没有标准线程池，任务队列、负载均衡、线程生命周期都得自己写，基础设施代码很多，但不改变核心算法。
- oneTBB：work-stealing 对不规则任务很合适，但要引入额外依赖。
- Parallel STL：在 GCC/libstdc++ 下的后端支持不理想，也不好表达「每个 bin 各自维护 cell map 和 DSU」这种结构。
选择OpenMP。并行边界本来就是「一个 bin 一个任务」，一行 pragma 就能表达；线程数和调度策略可以直接调， 不需要额外依赖，输出也能确定性地合并。
边界如果以后出现大量超大且分布不均的 bin，需要在 bin 内再拆任务，oneTBB 的任务模型会更合适。
reserve 减少了 rehash，但没有明显提速
分桶过程中 std::unordered_map 会边插边扩容。我按插入规模预估容量、提前 reserve，
rehash 次数确实大幅下降（统计方式：插入过程中观察到 bucket_count() 变化的次数）：
| 数据集 | 三角面数 | rehash（不预分配） | rehash（reserve） | 耗时变化 |
|---|---|---|---|---|
| Large | 309,630 | 1340 | 15 | 约 −0.8% |
| Medium | 14,238 | 167 | 10 | 约 −0.4% ~ −2% |
| Small | 1,764 | 157 | 42 | 持平或略慢 |
Large 模型的 rehash 次数减少了约 98.9%，耗时却只改善了约 0.8%；Small 模型持平或略慢。
提前 reserve 也需要初始化 bucket，容量留得过多还会增加内存占用和缓存压力。
我又试了不同的 reserve 容量和 load factor。最终没有把这项改动计入性能收益，因为测得的耗时变化很小。
为什么最终保留了两套流程
最初讨论优化方案时，算法团队认为延迟主要来自宿主软件的历史代码。 我拿出了离线测试数据和实现思路，但双方仍没能就改动达成一致。
当时我只拿速度作比较，没有把识别精度放进讨论。仅凭耗时，还不能判断新流程能否替代原流程。
产品经理希望缩短用户的等待时间。我补做了速度和识别精度的对比，再和产品、算法团队讨论两套流程各适合什么场景：
- 补充对比测试 把识别精度也纳入测试。结果是原算法速度较慢、精度较高；新算法速度更快，但精度有所下降。
- 把结论写成报告，交给各方讨论 报告列出两套流程的速度和精度差异，供产品、算法和开发团队讨论使用场景。
- 最终落地：双模式 经过产品、算法和开发几方讨论，软件同时提供两种服务——快速识别走新流程，精确识别保留原算法流程，由用户按需选择。
项目复盘
- 离线测试显示，主要耗时在算法内部，而不是软件集成层；分阶段计时又把问题定位到墙体聚类。
- 先用空间分桶减少比较次数，再按 bin 并行；两步分别把耗时从 206.6ms 降到 69.2ms、再降到 28ms。
reserve大幅减少了 rehash，但对总耗时帮助很小，这项尝试最终没有算进优化收益。- 速度不是产品决策的唯一指标。把精度一起纳入比较后，团队最终保留了快速识别和精确识别两种模式。