代码

// 8-bit 4-pass LSD radix, combined histogram + NTA prefetch, ping-pong buffers
#include <xmmintrin.h>
typedef unsigned u32;
static u32 tmp[100000000];
static u32 cnt[1024];
void sort(u32 *a, int n) {
    u32 i;
    u32 *c0=cnt, *c1=cnt+256, *c2=cnt+512, *c3=cnt+768;
    for (i = 0; i < 1024; i++) cnt[i] = 0;
    for (i = 0; i < (u32)n; i++) {
        u32 x = a[i];
        c0[x & 255]++; c1[(x>>8)&255]++; c2[(x>>16)&255]++; c3[x>>24]++;
    }
    for (i = 1; i < 256; i++) { c0[i]+=c0[i-1]; c1[i]+=c1[i-1]; c2[i]+=c2[i-1]; c3[i]+=c3[i-1]; }
    for (i = (u32)n; i-- > 0;) { u32 x=a[i]; _mm_prefetch((const char*)&a[i-512], _MM_HINT_NTA); tmp[--c0[x & 255]] = x; }
    for (i = (u32)n; i-- > 0;) { u32 x=tmp[i]; _mm_prefetch((const char*)&tmp[i-512], _MM_HINT_NTA); a[--c1[(x>>8)&255]] = x; }
    for (i = (u32)n; i-- > 0;) { u32 x=a[i]; _mm_prefetch((const char*)&a[i-512], _MM_HINT_NTA); tmp[--c2[(x>>16)&255]] = x; }
    for (i = (u32)n; i-- > 0;) { u32 x=tmp[i]; _mm_prefetch((const char*)&tmp[i-512], _MM_HINT_NTA); a[--c3[x>>24]] = x; }
}

评测结果