代码

// 1001 v16: [8][8][16] MSD + PACKED 3-byte compress (4 elem -> 3 u32 stores) + u16 SIDECAR lower passes.
// Pass 2: packed compress (staging 16/bucket, pack4). Pass 3: hist byte2 (read s[3i+2]) + scatter
// low-16 (u16) by byte2. Pass 4: sort16 (2x8-bit on u16) + reconstruct NT. This fixes BOTH the
// compress store-count (v15) AND the direct-scatter-into-a[] regression (v10) vs v8.
#include <immintrin.h>
#include <string.h>
#include <emmintrin.h>
typedef unsigned int u32;
typedef unsigned short u16;
typedef unsigned char u8;

#ifndef N
#define N 100000000
#endif

#define NB 256
#define W 16

static u8 s[3*N + 256*4] __attribute__((aligned(64)));
static u32 stg[NB * W] __attribute__((aligned(64)));
static u8  pos[NB];
static u32 cur[NB];
static u32 cnt[NB];
static u32 B[257];
static u16 scratch[1048576] __attribute__((aligned(64)));
static u16 scratch2[65536] __attribute__((aligned(64)));
static u16 scratch3[65536] __attribute__((aligned(64)));
static u32 bc[256];
static u32 bc2[256];
static u32 sstart[256];
static u32 spos[256];
static u32 scount[256];

static inline void pack4(u8 *dst, const u32 *e) {
    u32 w0 = (e[0] & 0xFFFFFF) | (e[1] << 24);
    u32 w1 = ((e[1] & 0xFFFFFF) >> 8) | ((e[2] & 0xFFFFFF) << 16);
    u32 w2 = ((e[2] & 0xFFFFFF) >> 16) | ((e[3] & 0xFFFFFF) << 8);
    __builtin_memcpy(dst, &w0, 4);
    __builtin_memcpy(dst+4, &w1, 4);
    __builtin_memcpy(dst+8, &w2, 4);
}

static inline void flush_full(int k) {
    u32 b = cur[k];
    const u32 *e = stg + k*W;
    pack4(s+b+0, e+0); pack4(s+b+12, e+4); pack4(s+b+24, e+8); pack4(s+b+36, e+12);
    cur[k] = b + 48;
}
static inline void flush_partial(int k, int m) {
    u32 b = cur[k];
    for (int j = 0; j < m; j++) { u32 x = stg[k*W+j]; s[b]=(u8)x; s[b+1]=(u8)(x>>8); s[b+2]=(u8)(x>>16); b+=3; }
    cur[k] = b;
}

__attribute__((target("avx2")))
static inline void flush16_nt(u32 *dst, const u16 *src, int m, u32 top16) {
    int mi = 0;
    while ((((unsigned long)(dst + mi)) & 31) && mi < m) { dst[mi] = ((u32)src[mi]) | top16; mi++; }
    __m256i t = _mm256_set1_epi32((int)top16);
    for (; mi + 16 <= m; mi += 16) {
        __m128i lo = _mm_loadu_si128((const __m128i*)(src + mi));
        __m128i hi = _mm_loadu_si128((const __m128i*)(src + mi + 8));
        __m256i a0 = _mm256_cvtepu16_epi32(lo);
        __m256i a1 = _mm256_cvtepu16_epi32(hi);
        _mm256_stream_si256((__m256i*)(dst + mi + 0), _mm256_or_si256(a0, t));
        _mm256_stream_si256((__m256i*)(dst + mi + 8), _mm256_or_si256(a1, t));
    }
    for (; mi < m; mi++) dst[mi] = ((u32)src[mi]) | top16;
}

static void sort16(u16 *src, u32 *dst, int m, u32 top16) {
    int i, j;
    for (j = 0; j < 256; j++) bc[j] = 0;
    int m8 = m & ~7;
    for (i = 0; i < m8; i += 8) {
        bc[src[i]&255]++; bc[src[i+1]&255]++; bc[src[i+2]&255]++; bc[src[i+3]&255]++;
        bc[src[i+4]&255]++; bc[src[i+5]&255]++; bc[src[i+6]&255]++; bc[src[i+7]&255]++;
    }
    for (; i < m; i++) bc[src[i] & 255]++;
    for (j = 1; j < 256; j++) bc[j] += bc[j-1];
    for (j = 0; j < 256; j++) bc2[j] = 0;
    int rm = m & ~7;
    for (i = m - 1; i >= rm; i--) { u16 x = src[i]; scratch2[--bc[x & 255]] = x; bc2[(x >> 8) & 255]++; }
    for (i = rm - 1; i >= 0; i -= 8) {
        u16 x0=src[i],x1=src[i-1],x2=src[i-2],x3=src[i-3],x4=src[i-4],x5=src[i-5],x6=src[i-6],x7=src[i-7];
        scratch2[--bc[x0&255]]=x0; bc2[(x0>>8)&255]++;
        scratch2[--bc[x1&255]]=x1; bc2[(x1>>8)&255]++;
        scratch2[--bc[x2&255]]=x2; bc2[(x2>>8)&255]++;
        scratch2[--bc[x3&255]]=x3; bc2[(x3>>8)&255]++;
        scratch2[--bc[x4&255]]=x4; bc2[(x4>>8)&255]++;
        scratch2[--bc[x5&255]]=x5; bc2[(x5>>8)&255]++;
        scratch2[--bc[x6&255]]=x6; bc2[(x6>>8)&255]++;
        scratch2[--bc[x7&255]]=x7; bc2[(x7>>8)&255]++;
    }
    for (j = 1; j < 256; j++) bc2[j] += bc2[j-1];
    for (i = m - 1; i >= rm; i--) { u16 x = scratch2[i]; scratch3[--bc2[(x >> 8) & 255]] = x; }
    for (i = rm - 1; i >= 0; i -= 8) {
        u16 x0=scratch2[i],x1=scratch2[i-1],x2=scratch2[i-2],x3=scratch2[i-3],x4=scratch2[i-4],x5=scratch2[i-5],x6=scratch2[i-6],x7=scratch2[i-7];
        scratch3[--bc2[(x0>>8)&255]]=x0;
        scratch3[--bc2[(x1>>8)&255]]=x1;
        scratch3[--bc2[(x2>>8)&255]]=x2;
        scratch3[--bc2[(x3>>8)&255]]=x3;
        scratch3[--bc2[(x4>>8)&255]]=x4;
        scratch3[--bc2[(x5>>8)&255]]=x5;
        scratch3[--bc2[(x6>>8)&255]]=x6;
        scratch3[--bc2[(x7>>8)&255]]=x7;
    }
    flush16_nt(dst, scratch3, m, top16);
}

void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    int i, j;
    (void)n;

    // Pass 1: hist top-8
    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 acc = 0; B[0] = 0; for (j = 0; j < NB; j++) { acc += cnt[j]; B[j+1] = acc; } }

    // Pass 2: packed compress
    for (j = 0; j < NB; j++) { pos[j] = 0; cur[j] = B[j] * 3; }
    for (i = 0; i < n8; i += 8) {
        u32 x0=a[i+0],k0=x0>>24,p0=pos[k0]; stg[k0*W+p0]=x0; p0++; if(p0==W){flush_full(k0); p0=0;} pos[k0]=(u8)p0;
        u32 x1=a[i+1],k1=x1>>24,p1=pos[k1]; stg[k1*W+p1]=x1; p1++; if(p1==W){flush_full(k1); p1=0;} pos[k1]=(u8)p1;
        u32 x2=a[i+2],k2=x2>>24,p2=pos[k2]; stg[k2*W+p2]=x2; p2++; if(p2==W){flush_full(k2); p2=0;} pos[k2]=(u8)p2;
        u32 x3=a[i+3],k3=x3>>24,p3=pos[k3]; stg[k3*W+p3]=x3; p3++; if(p3==W){flush_full(k3); p3=0;} pos[k3]=(u8)p3;
        u32 x4=a[i+4],k4=x4>>24,p4=pos[k4]; stg[k4*W+p4]=x4; p4++; if(p4==W){flush_full(k4); p4=0;} pos[k4]=(u8)p4;
        u32 x5=a[i+5],k5=x5>>24,p5=pos[k5]; stg[k5*W+p5]=x5; p5++; if(p5==W){flush_full(k5); p5=0;} pos[k5]=(u8)p5;
        u32 x6=a[i+6],k6=x6>>24,p6=pos[k6]; stg[k6*W+p6]=x6; p6++; if(p6==W){flush_full(k6); p6=0;} pos[k6]=(u8)p6;
        u32 x7=a[i+7],k7=x7>>24,p7=pos[k7]; stg[k7*W+p7]=x7; p7++; if(p7==W){flush_full(k7); p7=0;} pos[k7]=(u8)p7;
    }
    for (; i < N; i++) {
        u32 x = a[i]; u32 k = x >> 24; u32 p = pos[k];
        stg[k*W + p] = x; p++;
        if (p == W) { flush_full(k); p = 0; }
        pos[k] = (u8)p;
    }
    for (j = 0; j < NB; j++) if (pos[j]) flush_partial(j, pos[j]);

    // Pass 3+4: per bucket, u16 sidecar lower passes reading packed 3-byte scratch
    for (j = 0; j < NB; j++) {
        u32 m = cnt[j];
        if (m == 0) continue;
        u32 base3 = B[j] * 3;
        u32 baseA = B[j];
        int mb8 = (int)m & ~7;

        for (int q = 0; q < 256; q++) bc[q] = 0;
        for (i = 0; i < mb8; i += 8) {
            bc[s[base3+3*i+2]]++; bc[s[base3+3*(i+1)+2]]++; bc[s[base3+3*(i+2)+2]]++; bc[s[base3+3*(i+3)+2]]++;
            bc[s[base3+3*(i+4)+2]]++; bc[s[base3+3*(i+5)+2]]++; bc[s[base3+3*(i+6)+2]]++; bc[s[base3+3*(i+7)+2]]++;
        }
        for (; i < (int)m; i++) bc[s[base3 + 3*i + 2]]++;
        { u32 t = 0; for (int q = 0; q < 256; q++) { u32 c = bc[q]; scount[q] = c; sstart[q] = t; spos[q] = t; t += c; } }

        for (i = 0; i < mb8; i += 8) {
            u32 b0 = base3 + 3*i;
            u32 g0=s[b0+2]; scratch[spos[g0]++] = (u16)((u32)s[b0] | ((u32)s[b0+1]<<8));
            u32 b1 = b0+3;
            u32 g1=s[b1+2]; scratch[spos[g1]++] = (u16)((u32)s[b1] | ((u32)s[b1+1]<<8));
            u32 b2 = b1+3;
            u32 g2=s[b2+2]; scratch[spos[g2]++] = (u16)((u32)s[b2] | ((u32)s[b2+1]<<8));
            u32 b3 = b2+3;
            u32 g3=s[b3+2]; scratch[spos[g3]++] = (u16)((u32)s[b3] | ((u32)s[b3+1]<<8));
            u32 b4 = b3+3;
            u32 g4=s[b4+2]; scratch[spos[g4]++] = (u16)((u32)s[b4] | ((u32)s[b4+1]<<8));
            u32 b5 = b4+3;
            u32 g5=s[b5+2]; scratch[spos[g5]++] = (u16)((u32)s[b5] | ((u32)s[b5+1]<<8));
            u32 b6 = b5+3;
            u32 g6=s[b6+2]; scratch[spos[g6]++] = (u16)((u32)s[b6] | ((u32)s[b6+1]<<8));
            u32 b7 = b6+3;
            u32 g7=s[b7+2]; scratch[spos[g7]++] = (u16)((u32)s[b7] | ((u32)s[b7+1]<<8));
        }
        for (; i < (int)m; i++) {
            u32 b = base3 + 3*i;
            u32 g = s[b+2];
            scratch[spos[g]++] = (u16)((u32)s[b] | ((u32)s[b+1]<<8));
        }
        for (int q = 0; q < 256; q++) { int c = scount[q]; if (c > 0) sort16(scratch + sstart[q], a + baseA + sstart[q], c, ((u32)((j<<8)|q))<<16); }
    }
}

评测结果