代码

// 1001 v8: [8][8][16] MSD + u16 sidecar in the lower passes (port of wc2017b1 solution_v12).
// sort_bucket scatters low-16 bits (u16) into scratch; sort16 sorts u16 keys; final reconstruct
// ORs the sub-bucket top16 and NT-flushes to a[]. Halves L3/L2 data width in the lower passes.
#include <immintrin.h>
#include <string.h>
#include <emmintrin.h>
typedef unsigned int u32;
typedef unsigned short u16;
typedef unsigned char u8;

__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);
}

#define NB 256
#define LINE 128

static u32 tmp[100000000 + 2048 * LINE] __attribute__((aligned(64)));
static u32 tmp2[100000000 + 2048 * LINE] __attribute__((aligned(64)));
static u32 staging[NB * LINE] __attribute__((aligned(64)));
static u32 cnt[NB];
static u32 rbase[NB];
static u32 pbase[NB];
static u32 off[NB];
static u8  pos[NB];
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 u32 cntx[2048], rbasex[2048], pbasex[2048], offx[2048];
static u8 posx[2048];
static u32 stagingx[2048 * LINE] __attribute__((aligned(64)));

static void scatter_bits(u32 *src, u32 *dst, int n, int sh, int nbits) {
    int i, j;
    int NBX = 1 << nbits;
    int MASKX = NBX - 1;
    for (j = 0; j < NBX; j++) cntx[j] = 0;
    int n8 = n & ~7;
    for (i = 0; i < n8; i += 8) {
        cntx[(src[i]>>sh)&MASKX]++; cntx[(src[i+1]>>sh)&MASKX]++; cntx[(src[i+2]>>sh)&MASKX]++; cntx[(src[i+3]>>sh)&MASKX]++;
        cntx[(src[i+4]>>sh)&MASKX]++; cntx[(src[i+5]>>sh)&MASKX]++; cntx[(src[i+6]>>sh)&MASKX]++; cntx[(src[i+7]>>sh)&MASKX]++;
    }
    for (; i < n; i++) cntx[(src[i] >> sh) & MASKX]++;
    { u32 t = 0, p = 0; for (j = 0; j < NBX; j++) { u32 c = cntx[j]; rbasex[j] = t; pbasex[j] = p; t += c; p = (p + c + 127) & ~127u; } }
    for (j = 0; j < NBX; j++) { offx[j] = pbasex[j]; posx[j] = 0; }
#define S1(X) do { u32 x_ = (X); u32 b_ = (x_ >> sh) & MASKX; u32 p_ = posx[b_]; \
    stagingx[b_ * LINE + p_] = x_; p_++; \
    if (p_ == LINE) { u32 go_ = offx[b_]; flush_nt(dst + go_, stagingx + b_ * LINE); offx[b_] = go_ + LINE; p_ = 0; } \
    posx[b_] = (u8)p_; } while (0)
    int n8s = n & ~7;
    for (i = 0; i < n8s; i += 8) {
        S1(src[i]); S1(src[i+1]); S1(src[i+2]); S1(src[i+3]);
        S1(src[i+4]); S1(src[i+5]); S1(src[i+6]); S1(src[i+7]);
    }
    for (; i < n; i++) S1(src[i]);
#undef S1
    for (j = 0; j < NBX; j++) { u32 p = posx[j]; if (p > 0) __builtin_memcpy(dst + offx[j], stagingx + j * LINE, p * 4); }
}

static void scatter_bits_exact(u32 *src, u32 *dst, int n, int sh, int nbits) {
    int i, j;
    int NBX = 1 << nbits;
    int MASKX = NBX - 1;
    for (j = 0; j < NBX; j++) cntx[j] = 0;
    int n8 = n & ~7;
    for (i = 0; i < n8; i += 8) {
        cntx[(src[i]>>sh)&MASKX]++; cntx[(src[i+1]>>sh)&MASKX]++; cntx[(src[i+2]>>sh)&MASKX]++; cntx[(src[i+3]>>sh)&MASKX]++;
        cntx[(src[i+4]>>sh)&MASKX]++; cntx[(src[i+5]>>sh)&MASKX]++; cntx[(src[i+6]>>sh)&MASKX]++; cntx[(src[i+7]>>sh)&MASKX]++;
    }
    for (; i < n; i++) cntx[(src[i] >> sh) & MASKX]++;
    { u32 t = 0; for (j = 0; j < NBX; j++) { u32 c = cntx[j]; rbasex[j] = t; t += c; } }
    for (j = 0; j < NBX; j++) { offx[j] = rbasex[j]; posx[j] = 0; }
#define S2(X) do { u32 x_ = (X); u32 b_ = (x_ >> sh) & MASKX; u32 p_ = posx[b_]; \
    stagingx[b_ * LINE + p_] = x_; p_++; \
    if (p_ == LINE) { u32 go_ = offx[b_]; __builtin_memcpy(dst + go_, stagingx + b_ * LINE, LINE * 4); offx[b_] = go_ + LINE; p_ = 0; } \
    posx[b_] = (u8)p_; } while (0)
    int n8s = n & ~7;
    for (i = 0; i < n8s; i += 8) {
        S2(src[i]); S2(src[i+1]); S2(src[i+2]); S2(src[i+3]);
        S2(src[i+4]); S2(src[i+5]); S2(src[i+6]); S2(src[i+7]);
    }
    for (; i < n; i++) S2(src[i]);
#undef S2
    for (j = 0; j < NBX; j++) { u32 p = posx[j]; if (p > 0) __builtin_memcpy(dst + offx[j], stagingx + j * LINE, p * 4); }
}

static void copy_seq(u32 *dst, const u32 *src, int n) {
    int i = 0;
    while ((((unsigned long)(dst + i)) & 31) && i < n) { dst[i] = src[i]; i++; }
    for (; i + 4096 <= n; i += 4096) flush_nt(dst + i, src + i);
    for (; i < n; i++) dst[i] = src[i];
}

void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    scatter_bits_exact(a, tmp, n, 0, 10);          /* low 10 -> tmp */
    scatter_bits_exact(tmp, tmp2, n, 10, 11);     /* middle 11 -> tmp2 */
    scatter_bits_exact(tmp2, a, n, 21, 11);       /* top 11 -> a[] */
}

评测结果