代码

#define FLUSH_NT 1
#include <string.h>
typedef unsigned int u32;
typedef unsigned char u8;

static u32 b[200000000];
static u32 cnt[1024];

// FLUSH_NT: 1 = non-temporal (movnti) full-line flush, 0 = plain stores
#ifndef FLUSH_NT
#define FLUSH_NT 0
#endif

static u32 staging[256][16];
static u8 pos[256];

static inline void flush_line(u32 *dst, const u32 *src) {
#if FLUSH_NT
  asm volatile("movnti %0, %1" : : "r"(src[0]), "m"(dst[0]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[1]), "m"(dst[1]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[2]), "m"(dst[2]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[3]), "m"(dst[3]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[4]), "m"(dst[4]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[5]), "m"(dst[5]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[6]), "m"(dst[6]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[7]), "m"(dst[7]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[8]), "m"(dst[8]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[9]), "m"(dst[9]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[10]), "m"(dst[10]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[11]), "m"(dst[11]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[12]), "m"(dst[12]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[13]), "m"(dst[13]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[14]), "m"(dst[14]) : "memory");
  asm volatile("movnti %0, %1" : : "r"(src[15]), "m"(dst[15]) : "memory");
#else
  dst[0] = src[0]; dst[1] = src[1]; dst[2] = src[2]; dst[3] = src[3];
  dst[4] = src[4]; dst[5] = src[5]; dst[6] = src[6]; dst[7] = src[7];
  dst[8] = src[8]; dst[9] = src[9]; dst[10] = src[10]; dst[11] = src[11];
  dst[12] = src[12]; dst[13] = src[13]; dst[14] = src[14]; dst[15] = src[15];
#endif
}

static void scatter_pass(u32 *S, u32 *D, int n, u32 *cnttab, int shift) {
  for (int k = 0; k < 256; k++) pos[k] = 0;
  for (int i = 0; i < n; i++) {
    u32 x = S[i];
    u32 k = (x >> shift) & 255;
    u32 p = pos[k];
    staging[k][p] = x;
    p++;
    if (p == 16) {
      flush_line(&D[cnttab[k]], &staging[k][0]);
      cnttab[k] += 16;
      p = 0;
    }
    pos[k] = p;
  }
  for (int k = 0; k < 256; k++) {
    u32 p = pos[k];
    if (p > 0) {
      u32 go = cnttab[k];
      for (u32 j = 0; j < p; j++) D[go + j] = staging[k][j];
      cnttab[k] = go + p;
    }
  }
#if FLUSH_NT
  asm volatile("sfence" ::: "memory");
#endif
}

void sort(unsigned *a, int n) {
  u32 *c1 = cnt, *c2 = cnt + 256, *c3 = cnt + 512, *c4 = cnt + 768;
  u32 *t = b;
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < n; i++) {
    u32 x = a[i];
    c1[x & 255]++;
    c2[(x >> 8) & 255]++;
    c3[(x >> 16) & 255]++;
    c4[x >> 24]++;
  }
  // convert to start positions (scatter_pass increments them)
  u32 s1 = 0, s2 = 0, s3 = 0, s4 = 0;
  for (int i = 0; i < 256; i++) {
    u32 v1 = c1[i], v2 = c2[i], v3 = c3[i], v4 = c4[i];
    c1[i] = s1; s1 += v1;
    c2[i] = s2; s2 += v2;
    c3[i] = s3; s3 += v3;
    c4[i] = s4; s4 += v4;
  }
  scatter_pass(a, t, n, c1, 0);
  scatter_pass(t, a, n, c2, 8);
  scatter_pass(a, t, n, c3, 16);
  scatter_pass(t, a, n, c4, 24);
}

评测结果