上学期组团参加了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..假设图中有$N$个顶点, 开$N\times t$的bitset, 每一列是一个BFS的queue, 再开$N\times t$的bitset, 每一列是一个BFS的vst[]数组. 然后就可以用位运算操作同时运行$t$个BFS, 运行过程中不同的BFS在同一深度下扩展到了同一顶点的话还能够共享计算结果. 前两名的队伍都是这么BFS的, 不过他们的$t$貌似用的都是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, vector. 他们还做了很多其他事情, 包括在分支语句上手工向编译器提示是否跳转, 用手写的数据结构替代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...