月度归档:2018年03月

如何编写缓存友好的代码——从一道卡常数的题目说起

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利用率之间的平衡。