代码

// 8-bit 4-pass LSD radix, combined histogram, unroll-4 + NTA prefetch scatter
#include <xmmintrin.h>
typedef unsigned u32;
static u32 tmp[100000000];
static u32 cnt[1024];

static inline void sc4(u32*dst,u32*c,const u32*src,u32 n,u32 sh){
    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)&255]]=x0;
        dst[--c[(x1>>sh)&255]]=x1;
        dst[--c[(x2>>sh)&255]]=x2;
        dst[--c[(x3>>sh)&255]]=x3;
    }
    for(;i-->0;){u32 x=src[i];dst[--c[(x>>sh)&255]]=x;}
}

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];}
    sc4(tmp,c0,a,(u32)n,0);
    sc4(a,c1,tmp,(u32)n,8);
    sc4(tmp,c2,a,(u32)n,16);
    sc4(a,c3,tmp,(u32)n,24);
}

评测结果