Program Efficiency: Algorithm Doesn't Matter So Much - SIGMOD 2014

上学期组团参加了 SIGMOD Programming Contest 2014, 进入了 Finalist. 因此 6 月 23 日至 26 日, 我在 Utah 州 Snowbird 度假村参加 ACM SIGMOD/PODS 2014 会议.

每年的比赛题目跟 ACM-ICPC 比较像, 就是给输入, 产生确定的输出. 比赛形式的不同在于, ICPC 中选手要尽量快的写出一个运行速度可以接受的程序, 而在 SIGMOD 比赛里, 我们需要在一个多月时间里写出一个在给定机器上运行速度尽量快的程序, 而且可以用任何手段 (并行, 汇编, SIMD, 文件读写).

最终结果与之前的 online 测试结果基本一致, 获得了第四名. 听了其他选手的报告, 深深的感觉到, 压榨程序效率时, 算法并不怎么重要.

SIGMODContest 每年的题目都是实际的数据库系统中需要解决的问题, 这些问题不像 ICPC 或 OI 中那样特意设计出来供某些 fancy 的算法来用. 这些实际的问题常常没有特别 fancy 的算法, 可以让人在复杂度上压制别人. 相反, 大家都是在相同复杂度下, 用各种手段优化效率, 这其中对编译原理以及更底层体系结构的理解远比算法要重要.

我们队伍里都是各种 OI 选手, 算法着实比别人 fancy 很多. 例如第二题, 在不断增加点的图上维护一些连通分量, 只有我们队和排名第五的北大队用了并查集 (中国人的算法比较好吧..), 第一名直接在图上 BFS 搜连通分量在加一些剪枝. 第三题是在图上找距离不超过 h 的共同标签 (整数集合求交) 尽量多的 k 个点对, 我们先建立了 "标签 - 点" 的倒排表, 再用倒排表合并计数的那些算法来找出共同标签多的点对, 再双向广搜验证距离是否超过 h. 而前两名队伍都是很 naive 的对每个点直接 BFS 出距离不超过 h 的点, 再计算共同标签数, 同时维护 top-k.

感觉至少在第三题上我们的算法应该是比其他队伍好的, 但是第一名的优化实在做的太好:

• 图上的 BFS, 用 bitset 实现了单 CPU 多 BFS.. 假设图中有 个顶点, 开 的 bitset, 每一列是一个 BFS 的 queue, 再开 的 bitset, 每一列是一个 BFS 的 vst [] 数组. 然后就可以用位运算操作同时运行 个 BFS, 运行过程中不同的 BFS 在同一深度下扩展到了同一顶点的话还能够共享计算结果. 前两名的队伍都是这么 BFS 的, 不过他们的 貌似用的都是 64 位整数, 而不是 SSE 的 128, 还不清楚为什么.

• 整数集合求交, 也是用 SIMD 实现的. 有论文: Fast Sorted-Set Intersection using SIMD Instructions 和 SIMD Compression and the Intersection of Sorted Integers

第四题是这次比赛的核心, 因为最耗时间. 题意可以简化的理解为: 求一个连通图图中到各点距离和最小的 k 个点. 我至今仍觉得我们队伍这题的算法是相当好的: 快速估计每一点到各点距离和的下界而不计算真实值, 然后挑下界小的点来计算真实值, 从而快速获得 top-k 的较好的 bound 用于剪枝. 在估计距离和的下界上, 我们也做了很多工作, 包括利用概率性算法估计距离和的近似值, 以衡量当前下界是否紧; 以及把一个点 k 步走到的点放到 bitset 里, 用位运算进行 BFS, 再用 popcount 计算 k 步能走到多少点.

然而第一名的算法十分简单: 对每个点依次 BFS 计算它到各点的距离和, BFS 中顺便估一个距离和的下界, 下界超过当前已知的 top-k 的 bound 就剪枝.

由于实现技巧太好, 他们的程序快我们好几倍. 其中主要是由于他们的 BFS 是用 bitset 及位运算并行做的, 另外还要归功于内存分配的策略. 他们在读完数据后, 很少再有堆上的内存分配操作. BFS 所需空间都是建了大块内存之后重用的, 小内存分配全都是用自己的 Allocator 维护的. 相反我们每次 BFS 都会开一个queue<int>, vector<bool>. 他们还做了很多其他事情, 包括在分支语句上手工向编译器提示是否跳转, 用手写的数据结构替代 STL. 他们的 poster 上还列了好多:

这次比赛除了第四题是个瓶颈之外, 数据读入也耗时很久. 为了快速读入几十个 G 的数据, 我们最初使用开哥当年 OI 用的手段: fread () 一次读入定长的数据放到大 buffer 里使用. 后来仍然觉得不够快, 就先把文件 mmap () 到内存里再手动逐字节解析. 然而第一名在读入上依然用了 SIMD, 例如可以用 SIMD 指令快速数给定字符 (如换行符) 的个数; 在解析数值时要逐字符减去 "0", 也可以用 SIMD 快速完成.

第一名队伍名叫 AWFY (Are We Fast Yet), 来自慕尼黑, 他们拿走了 5000 刀的奖金. 坐等过几天代码公布之后去学习各种丧心病狂的技巧. 颁奖结束后了解到这个队伍的成员都是 HyperDB 的开发者. HyperDB 貌似是世界上最快的 OLTP/OLAP 数据库, 听说他们即将拿这个去创业了. 另外, 去年的 SIGMOD Programming Contest 的第二名队伍也是 HyperDB 团队的子集.

贴一张我们队伍的 poster:

另外这次会议还是很不错的, 住的地方是海拔 3000 米的山上, 酒店设备很充足, 房间里有壁炉, 冰箱, 电磁炉等神奇的东西. 走在山路上都能连 wifi, 每天有免费的美味三餐, 两个 break 还会分发食品和冷饮什么的. 主办方特意要求会场的电视播放世界杯直播. 另外每个参会者都得到了一张 hiking 的缆车票, 想去爬山还可以找主办方要打包的午餐. 由于这里是度假村, 娱乐设施很多, 满山都是小盆友在滑滑梯坐缆车..

一件有趣的事情是, 周二早上我在会场的沙发上玩电脑, 听到旁边一个老人在跟一个学生说什么 co-author, conference 什么的貌似学术挖掘的东西, 听了几分钟突然发现, 这人是 Jiawei Han...