代码

// 8-bit 4-pass, histogram via 2x 16-bit counting (halves store-port pressure)
#include <string.h>
#include <xmmintrin.h>
typedef unsigned int u32;
static u32 tmp[100000000];
static u32 cnt16[65536];
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;
    // count (byte0,byte1) 16-bit pairs
    memset(cnt16,0,65536*4);
    for(i=0;i<(u32)n;i++) cnt16[a[i]&0xffff]++;
    memset(cnt,0,1024*4);
    for(i=0;i<65536;i++){ c0[i&255]+=cnt16[i]; c1[i>>8]+=cnt16[i]; }
    // count (byte2,byte3) 16-bit pairs
    memset(cnt16,0,65536*4);
    for(i=0;i<(u32)n;i++) cnt16[(a[i]>>16)&0xffff]++;
    for(i=0;i<65536;i++){ c2[i&255]+=cnt16[i]; c3[i>>8]+=cnt16[i]; }
    // prefix
    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);
}

评测结果