代码

// 1001: fused histogram + reverse scatter + NTA prefetch (4-pass LSD).
#include <xmmintrin.h>
typedef unsigned int u32;
static u32 tmp[100000000];
static u32 cnt[1024];

// reverse scatter by `sh`, fusing histogram of next byte (sh+8) into cnext.
static inline void sc4_fused(u32*dst,u32*c,const u32*src,u32 n,u32 sh,u32*cnext,u32 nsh){
    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; cnext[(x0>>nsh)&255]++;
        dst[--c[(x1>>sh)&255]]=x1; cnext[(x1>>nsh)&255]++;
        dst[--c[(x2>>sh)&255]]=x2; cnext[(x2>>nsh)&255]++;
        dst[--c[(x3>>sh)&255]]=x3; cnext[(x3>>nsh)&255]++;
    }
    for(;i-->0;){u32 x=src[i];dst[--c[(x>>sh)&255]]=x; cnext[(x>>nsh)&255]++;}
}

// plain reverse scatter (last pass, no fusion)
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;

    // pass 0: count byte0 only (1 RMW/elem)
    for(i=0;i<256;i++)c0[i]=0;
    for(i=0;i<(u32)n;i++){u32 x=a[i];c0[x&255]++;}
    for(i=1;i<256;i++)c0[i]+=c0[i-1];

    // pass 1: reverse scatter byte0 (a->tmp), fuse byte1 count
    for(i=0;i<256;i++)c1[i]=0;
    sc4_fused(tmp,c0,a,(u32)n,0,c1,8);
    for(i=1;i<256;i++)c1[i]+=c1[i-1];

    // pass 2: reverse scatter byte1 (tmp->a), fuse byte2 count
    for(i=0;i<256;i++)c2[i]=0;
    sc4_fused(a,c1,tmp,(u32)n,8,c2,16);
    for(i=1;i<256;i++)c2[i]+=c2[i-1];

    // pass 3: reverse scatter byte2 (a->tmp), fuse byte3 count
    for(i=0;i<256;i++)c3[i]=0;
    sc4_fused(tmp,c2,a,(u32)n,16,c3,24);
    for(i=1;i<256;i++)c3[i]+=c3[i-1];

    // pass 4: reverse scatter byte3 (tmp->a)
    sc4(a,c3,tmp,(u32)n,24);
}

评测结果