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