代码

// WA-probe: v5 pass-1 only (top-8 hist + NT line-buffer scatter into tmp), NO write-back to a[].
#include <immintrin.h>
#include <string.h>
#include <emmintrin.h>
typedef unsigned int u32;
typedef unsigned char u8;
#define NB 256
#define LINE 128
static u32 tmp[100000000 + NB*LINE] __attribute__((aligned(64)));
static u32 staging[NB*LINE] __attribute__((aligned(64)));
static u32 cnt[NB], rbase[NB], pbase[NB], off[NB];
static u8 pos[NB];
__attribute__((target("avx2")))
static inline void flush_nt(u32 *dst, const u32 *src) {
    __m256i v0=_mm256_loadu_si256((const __m256i*)(src+0));
    __m256i v1=_mm256_loadu_si256((const __m256i*)(src+8));
    __m256i v2=_mm256_loadu_si256((const __m256i*)(src+16));
    __m256i v3=_mm256_loadu_si256((const __m256i*)(src+24));
    __m256i v4=_mm256_loadu_si256((const __m256i*)(src+32));
    __m256i v5=_mm256_loadu_si256((const __m256i*)(src+40));
    __m256i v6=_mm256_loadu_si256((const __m256i*)(src+48));
    __m256i v7=_mm256_loadu_si256((const __m256i*)(src+56));
    __m256i v8=_mm256_loadu_si256((const __m256i*)(src+64));
    __m256i v9=_mm256_loadu_si256((const __m256i*)(src+72));
    __m256i v10=_mm256_loadu_si256((const __m256i*)(src+80));
    __m256i v11=_mm256_loadu_si256((const __m256i*)(src+88));
    __m256i v12=_mm256_loadu_si256((const __m256i*)(src+96));
    __m256i v13=_mm256_loadu_si256((const __m256i*)(src+104));
    __m256i v14=_mm256_loadu_si256((const __m256i*)(src+112));
    __m256i v15=_mm256_loadu_si256((const __m256i*)(src+120));
    _mm256_stream_si256((__m256i*)(dst+0),v0); _mm256_stream_si256((__m256i*)(dst+8),v1);
    _mm256_stream_si256((__m256i*)(dst+16),v2); _mm256_stream_si256((__m256i*)(dst+24),v3);
    _mm256_stream_si256((__m256i*)(dst+32),v4); _mm256_stream_si256((__m256i*)(dst+40),v5);
    _mm256_stream_si256((__m256i*)(dst+48),v6); _mm256_stream_si256((__m256i*)(dst+56),v7);
    _mm256_stream_si256((__m256i*)(dst+64),v8); _mm256_stream_si256((__m256i*)(dst+72),v9);
    _mm256_stream_si256((__m256i*)(dst+80),v10); _mm256_stream_si256((__m256i*)(dst+88),v11);
    _mm256_stream_si256((__m256i*)(dst+96),v12); _mm256_stream_si256((__m256i*)(dst+104),v13);
    _mm256_stream_si256((__m256i*)(dst+112),v14); _mm256_stream_si256((__m256i*)(dst+120),v15);
}
void sort(unsigned *a, int n) {
    int i, j;
    for (j = 0; j < NB; j++) cnt[j] = 0;
    int n8 = n & ~7;
    for (i = 0; i < n8; i += 8) {
        cnt[a[i]>>24]++; cnt[a[i+1]>>24]++; cnt[a[i+2]>>24]++; cnt[a[i+3]>>24]++;
        cnt[a[i+4]>>24]++; cnt[a[i+5]>>24]++; cnt[a[i+6]>>24]++; cnt[a[i+7]>>24]++;
    }
    for (; i < n; i++) cnt[a[i] >> 24]++;
    { u32 t=0,p=0; for(j=0;j<NB;j++){ u32 c=cnt[j]; rbase[j]=t; pbase[j]=p; t+=c; p=(p+c+127)&~127u; } }
    for(j=0;j<NB;j++){ off[j]=pbase[j]; pos[j]=0; }
    #define S1(X) do{ u32 x_=(X); u32 b_=x_>>24; u32 p_=pos[b_]; staging[b_*LINE+p_]=x_; p_++; \
        if(p_==LINE){ u32 go_=off[b_]; flush_nt(tmp+go_, staging+b_*LINE); off[b_]=go_+LINE; p_=0; } pos[b_]=(u8)p_; }while(0)
    for (i = 0; i < n8; i += 8) { S1(a[i]);S1(a[i+1]);S1(a[i+2]);S1(a[i+3]);S1(a[i+4]);S1(a[i+5]);S1(a[i+6]);S1(a[i+7]); }
    for (; i < n; i++) S1(a[i]);
    #undef S1
    for(j=0;j<NB;j++){ u32 p=pos[j]; if(p>0) __builtin_memcpy(tmp+off[j], staging+j*LINE, p*4); }
    // no write-back to a[] => WA
    a[0] = tmp[0]; // keep tmp live
}

评测结果