代码

// 11+11+10 3-pass LSD radix, combined histogram, reverse scatter + NTA prefetch
#include <xmmintrin.h>
typedef unsigned int u32;
static u32 tmp[100000000];
static u32 cnt[2048*3];

static inline void sc(u32*dst,u32*c,const u32*src,u32 n,u32 sh,u32 mask){
    u32 i=n;
    for(;i>=4;i-=4){
        _mm_prefetch((const char*)&src[i-512],_MM_HINT_NTA);
        u32 x0=src[i-1],x1=src[i-2],x2=src[i-3],x3=src[i-4];
        dst[--c[(x0>>sh)&mask]]=x0;
        dst[--c[(x1>>sh)&mask]]=x1;
        dst[--c[(x2>>sh)&mask]]=x2;
        dst[--c[(x3>>sh)&mask]]=x3;
    }
    for(;i-->0;){u32 x=src[i];dst[--c[(x>>sh)&mask]]=x;}
}

void sort(u32 *a, int n) {
    u32 i;
    u32 *c0=cnt,*c1=cnt+2048,*c2=cnt+4096;
    for(i=0;i<6144;i++)cnt[i]=0;
    for(i=0;i<(u32)n;i++){u32 x=a[i];c0[x&2047]++;c1[(x>>11)&2047]++;c2[x>>22]++;}
    for(i=1;i<2048;i++){c0[i]+=c0[i-1];c1[i]+=c1[i-1];c2[i]+=c2[i-1];}
    sc(tmp,c0,a,(u32)n,0,2047);
    sc(a,c1,tmp,(u32)n,11,2047);
    sc(tmp,c2,a,(u32)n,22,1023);
}

评测结果