代码

#if defined(__GNUC__) && !defined(__clang__)
#define O2 __attribute__((optimize("-O2")))
#else
#define O2
#endif

#include <stdio.h>
#include <stdlib.h>
#define BUCKET_MOD (0xFFU)
#define BUCKET_SIZE (BUCKET_MOD + 1U)
#ifndef MAX_SIZE
#define MAX_SIZE (1000000U)
#endif

#define SPLIT_LOOP_1(p, key, mod, value, index)     \
p[--(key[value[index] mod].offset)] = value[index]
#define SPLIT_LOOP_2(p, key, mod, value, index)     \
SPLIT_LOOP_1(p, key, mod, value, index + 1);        \
SPLIT_LOOP_1(p, key, mod, value, index)
#define SPLIT_LOOP_4(p, key, mod, value, index)     \
SPLIT_LOOP_2(p, key, mod, value, index + 2);        \
SPLIT_LOOP_2(p, key, mod, value, index)
#define _SPLIT_LOOP_8_(p, key, mod, value)          \
SPLIT_LOOP_4(p, key, mod, value, 4);                \
SPLIT_LOOP_4(p, key, mod, value, 0)

#define ADD_LOOP_1(key, mod, v1)                    \
++key[v1 mod].offset
#define ADD_LOOP_2(key, mod, v1, v2)                \
ADD_LOOP_1(key, mod, v1);                           \
ADD_LOOP_1(key, mod, v2)
#define ADD_LOOP_4(key, mod, v1, v2, v3, v4)        \
ADD_LOOP_2(key, mod, v1, v2);                       \
ADD_LOOP_2(key, mod, v3, v4)
#define ADD_LOOP_8(key, mod, v1, v2, v3, v4, v5, v6, v7, v8)    \
ADD_LOOP_4(key, mod, v1, v2, v3, v4)                \
ADD_LOOP_4(key, mod, v5, v6, v7, v8)

#ifdef LOOP
#define SPLIT(dst, src, size, key, mod, p)          \
for (p = src + size; p > src; ) {                   \
    p -= 8;                                         \
    _SPLIT_LOOP_8_(dst, key, mod, p);               \
}               
#else
#define SPLIT(dst, src, size, key, mod, p)          \
for (p = src + size; p > src; ) {                   \
    register sort_t tmp = *(--p);                   \
    dst[--key[tmp mod].offset] = tmp;                      \
}
#endif

typedef unsigned sort_t;
typedef union int_p_t {
    unsigned int offset;
    sort_t* addr;
} int_p_t;
// sort_t arr[MAX_SIZE];
O2 void sort(sort_t *data, int n) {
    unsigned int i;
    int_p_t k1[BUCKET_SIZE] = {0}, k2[BUCKET_SIZE] = {0}, k3[BUCKET_SIZE] = {0}, k4[BUCKET_SIZE] = {0};
    sort_t *arr = (sort_t*)malloc(sizeof(data[0]) * n);
    sort_t *p;
    for (p = data + n; p > data; ) {
        // register sort_t tmp = *(--p);
        // ++k4[tmp & BUCKET_MOD];
        // ++k3[(tmp >> 8) & BUCKET_MOD];
        // ++k2[(tmp >> 16) & BUCKET_MOD];
        // ++k1[tmp >> 24];
        p -= 4;
        register sort_t tmp = p[0], tmp_ = p[1], tmp__ = p[2], tmp___ = p[3];
        ADD_LOOP_4(k4, & BUCKET_MOD, tmp, tmp_, tmp__, tmp___);
        ADD_LOOP_4(k3, >> 8 & BUCKET_MOD, tmp, tmp_, tmp__, tmp___);
        ADD_LOOP_4(k2, >> 16 & BUCKET_MOD, tmp, tmp_, tmp__, tmp___);
        ADD_LOOP_4(k1, >> 24, tmp, tmp_, tmp__, tmp___);
        // p -= 8;
        // register sort_t tmp = p[0], tmp_ = p[1], tmp__ = p[2], tmp___ = p[3];
        // ADD_LOOP_4(k4, & BUCKET_MOD, tmp, tmp_, tmp__, tmp___);
        // ADD_LOOP_4(k3, >> 8 & BUCKET_MOD, tmp, tmp_, tmp__, tmp___);
        // ADD_LOOP_4(k2, >> 16 & BUCKET_MOD, tmp, tmp_, tmp__, tmp___);
        // ADD_LOOP_4(k1, >> 24, tmp, tmp_, tmp__, tmp___);
        // tmp = p[4], tmp_ = p[5], tmp__ = p[6], tmp___ = p[7];
        // ADD_LOOP_4(k4, & BUCKET_MOD, tmp, tmp_, tmp__, tmp___);
        // ADD_LOOP_4(k3, >> 8 & BUCKET_MOD, tmp, tmp_, tmp__, tmp___);
        // ADD_LOOP_4(k2, >> 16 & BUCKET_MOD, tmp, tmp_, tmp__, tmp___);
        // ADD_LOOP_4(k1, >> 24, tmp, tmp_, tmp__, tmp___);
        // tmp = p[4], tmp_ = p[5], tmp__ = p[6], tmp___ = p[7];
    }
    for (i = 1; i < BUCKET_SIZE; ++i) {
        k4[i].offset += k4[i - 1].offset;
        k3[i].offset += k3[i - 1].offset;
        k2[i].offset += k2[i - 1].offset;
        k1[i].offset += k1[i - 1].offset;
    }
    SPLIT(arr, data, n, k4, & BUCKET_MOD, p);
    SPLIT(data, arr, n, k3, >> 8 & BUCKET_MOD, p);
    SPLIT(arr, data, n, k2, >> 16 & BUCKET_MOD, p);
    SPLIT(data, arr, n, k1, >> 24, p);
    free(arr);
}

评测结果