WC2017的第二题是一道卡常三合一题。其中,第一个子任务要求对最多2e8个32位无符号整数排序,时限3s,内存2G。输入采用伪随机数,输出采用hash,从而避免输入输出的影响。
看到题目第一反应是暴力。采用标准库中的sort函数,可以很容易地写出下面的代码
#include <cstdio> #include <algorithm> using namespace std; typedef unsigned uint32_t; inline uint32_t next_integer(uint32_t &x) { x = x ^ (x << 13); x = x ^ (x >> 17); x = x ^ (x << 5); return x; } const int n = 200000000; uint32_t arr[n]; void genarray() { uint32_t x = 0x98765432; for (int i=0; i<n; i++) arr[i] = next_integer(x); } uint32_t output(uint32_t* ptr) { uint32_t ret = n * 4; uint32_t x = 23333333; for (int i=0; i<n; i++) { ret ^= ptr[i] + x; next_integer(x); } return ret; } int main() { genarray(); sort(arr, arr+n); printf("%x\n", output(arr)); return 0; }
显然,这段代码是会TLE的。在我的电脑配置下(Intel Core i5-7200U, 8G, Ubuntu 16.04 LTS, 编译参数 g++ -O2 -m32 <source>,下同)一共跑了22.4s。
众所周知,标准库中的sort的复杂度是$O(n \log n)$。看来,必须使用线性时间排序才行。计数排序在这边用不了,因为32位无符号整数的取值范围太大了。那么,使用基数排序如何?将每个整数拆分为前16位和后16位,然后先以后16位为key使用计数排序,再以前16位为key使用计数排序,就可以在2倍线性时间内完成整个排序。
// ... typedef unsigned uint32_t; typedef unsigned short uint16_t; typedef unsigned char uint8_t; union { uint32_t u32; uint16_t word[2]; } arr[n], arr2[n]; uint32_t cnt[2][65536]; void counting() { for (int i=0; i<n; i++) { cnt[0][arr[i].word[0]]++; cnt[1][arr[i].word[1]]++; } for (int j=0; j<2; j++) partial_sum(cnt[j], cnt[j]+65536, cnt[j]); } void sort0() { for (int i=n-1; i>=0; i--) arr2[--cnt[0][arr[i].word[0]]].u32 = arr[i].u32; } void sort1() { for (int i=n-1; i>=0; i--) arr[--cnt[1][arr2[i].word[1]]].u32 = arr2[i].u32; } int main() { genarray(); counting(); sort0(); sort1(); printf("%x\n", output((uint32_t*)arr)); return 0; }
这回运行时间为5.2s,比之前快了许多,但仍然不能在时间限制内通过。使用perf工具监测cpu用时,发现sort1和sort0函数是瓶颈,时间占比分别达到了34.37%和33.91%。再监测cache miss数量,发现程序总共发生约6.38亿次cache miss,而sort1和sort0中的占比分别为44.88%和43.74%。考虑基数排序的原理:每一趟基数排序是一次计数排序,对于相同key的元素,它们是在内存中连续放置的,而key不同的元素,则需要随机访问。通常,一趟基数排序的cache hit率可以如下估算:
\[ hit\% = \min\{1, \frac{\#\text{cache line}}{k}\} * \left( 1 – \frac{\text{size of element}}{\text{size of cache line}}\right) \]
其中,k表示基数排序中基的大小,这里为65536。Intel i5-7200U的cache信息如下:
L1 data cache: 2 x 32 KBytes, 8-way set associative, 64-byte line size
L2 cache: 2 x 256 KBytes, 4-way set associative, 64-byte line size
L3 cache: 3 MBytes, 12-way set associative, 64-byte line size
经过简单的计算发现L3 cache一共只有约5万行,也就是说,这样写连3级缓存都不能充分利用,CPU必须经常花费数倍的时间访问主存,因此效率十分低下。
L1 cache一共只有512行,那么我们将32位整数分为4段,每段8位,然后进行基数排序行不行呢?让我们重新改写一下程序。
// ... uint32_t cnt[4][256]; void counting() { for (int i=0; i<n; i++) { cnt[0][arr[i].byte[0]]++; cnt[1][arr[i].byte[1]]++; cnt[2][arr[i].byte[2]]++; cnt[3][arr[i].byte[3]]++; } for (int j=0; j<4; j++) partial_sum(cnt[j], cnt[j]+256, cnt[j]); } void sort0() { for (int i=n-1; i>=0; i--) arr2[--cnt[0][arr[i].byte[0]]].u32 = arr[i].u32; } void sort1() { for (int i=n-1; i>=0; i--) arr[--cnt[1][arr2[i].byte[1]]].u32 = arr2[i].u32; } void sort2() { for (int i=n-1; i>=0; i--) arr2[--cnt[2][arr[i].byte[2]]].u32 = arr[i].u32; } void sort3() { for (int i=n-1; i>=0; i--) arr[--cnt[3][arr2[i].byte[3]]].u32 = arr2[i].u32; } int main() { genarray(); counting(); sort0(); sort1(); sort2(); sort3(); printf("%x\n", output((uint32_t*)arr)); return 0; }
跑下来运行时间为2.7s,能够在时限内通过。使用性能分析工具perf,发现总共只发生了2.5亿次cache miss。虽然经过修改后,理论运行时间变为2倍,但实际运行时间反而减少了将近一半。
CPU在访问主存时,往往需要等待数百个时钟周期。由于burst机制的存在,CPU可以一次性与主存交换大量连续数据,使得cache能够被十分有效的实现。要增加cache的利用率,主要是要提高程序访问数据的空间局部性和时间局部性。将 $O(n \log n)$ 的排序改为线性时间排序,是一种典型的space-time tradeoff, 如果排序的基数太大,那么count数组会变得很大,排序后的数据在内存中的分布会很散,降低了缓存利用率,这时就可以通过适当降低基数的方式,提高cache利用率,从而达到理论运行时间和cache利用率之间的平衡。