代码

// Duck.ac 1001. V16 candidate based on the user-tested V15 (394.793 ms).
// Interface: void sort(unsigned*, int). C++17; AVX2/BMI instructions as in V15.
// Changes: sparse middle-destination prefetch in explicit 7-record groups;
// direct low-byte widening on the common <=12 path; explicit SIMD count check;
// a 256-byte-ahead source prefetch in the first pass.
// The 84-record/256-byte format, slot layout, allocation and recovery are unchanged.
// No timing, autotuning, threads, I/O or distribution assumptions for correctness.
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <immintrin.h>
#include <array>
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <cstdlib>
static_assert(sizeof(unsigned)==4 && sizeof(uint16_t)==2, "32-bit unsigned required");
namespace v2_tail {
inline unsigned load16(const uint16_t* p) {
    uint16_t v;std::memcpy(&v,p,2);return v;
}
[[gnu::noinline]] inline void dense(const uint16_t* src,unsigned n,unsigned* dst,unsigned base) {
    alignas(64) unsigned counts[65536]={};
    for(unsigned i=0;i<n;++i)++counts[load16(src+i)];
    for(unsigned v=0;v<65536;++v)
        for(unsigned c=counts[v];c;--c)*dst++=base|v;
}
template<int J> inline __m256i merge_step(__m256i x) {
    alignas(32) static constexpr auto perm=[] {
        std::array<uint8_t,32>a{};
        for(unsigned i=0;i<32;++i)a[i]=uint8_t((i&15)^J);
        return a;
    }();
    __m256i y=_mm256_shuffle_epi8(x,_mm256_load_si256((const __m256i*)perm.data()));
    __m256i lo=_mm256_min_epu8(x,y),hi=_mm256_max_epu8(x,y);
    if constexpr(J>1)return _mm256_blend_epi16(lo,hi,J==4?0xcc:0xaa);
    else return _mm256_blendv_epi8(lo,hi,_mm256_set1_epi16(short(0xff00)));
}
inline void write8(__m128i x,unsigned* dst,unsigned c,unsigned base,unsigned* end) {
    __m256i y=_mm256_or_si256(_mm256_cvtepu8_epi32(x),_mm256_set1_epi32(base));
    if(end-dst>=8)_mm256_storeu_si256((__m256i*)dst,y);
    else _mm256_maskstore_epi32((int*)dst,_mm256_cmpgt_epi32(_mm256_set1_epi32(c),
                                      _mm256_setr_epi32(0,1,2,3,4,5,6,7)),y);
}
// 12-input, 39-comparator network from Bert Dobbelaere's sorting-network list:
// https://bertdobbelaere.github.io/sorting_networks.html#N12L39D9
// Each AVX2 byte lane represents a different bucket (32 buckets per call).
inline void batch_sort(const uint8_t* src,uint8_t* out,uint8_t* tail) {
__m256i x[12],a[8],b[8];
x[0]=_mm256_load_si256((const __m256i*)(src+0));
x[1]=_mm256_load_si256((const __m256i*)(src+256));
x[2]=_mm256_load_si256((const __m256i*)(src+512));
x[3]=_mm256_load_si256((const __m256i*)(src+768));
x[4]=_mm256_load_si256((const __m256i*)(src+1024));
x[5]=_mm256_load_si256((const __m256i*)(src+1280));
x[6]=_mm256_load_si256((const __m256i*)(src+1536));
x[7]=_mm256_load_si256((const __m256i*)(src+1792));
x[8]=_mm256_load_si256((const __m256i*)(src+2048));
x[9]=_mm256_load_si256((const __m256i*)(src+2304));
x[10]=_mm256_load_si256((const __m256i*)(src+2560));
x[11]=_mm256_load_si256((const __m256i*)(src+2816));
#define CMP(A,B) do {__m256i lo=_mm256_min_epu8(x[A],x[B]);x[B]=_mm256_max_epu8(x[A],x[B]);x[A]=lo;} while(0)
CMP(0,8);CMP(1,7);CMP(2,6);CMP(3,11);CMP(4,10);CMP(5,9);CMP(0,1);CMP(2,5);CMP(3,4);CMP(6,9);CMP(7,8);CMP(10,11);CMP(0,2);CMP(1,6);CMP(5,10);CMP(9,11);CMP(0,3);CMP(1,2);CMP(4,6);CMP(5,7);CMP(8,11);CMP(9,10);CMP(1,4);CMP(3,5);CMP(6,8);CMP(7,10);CMP(1,3);CMP(2,5);CMP(6,9);CMP(8,10);CMP(2,3);CMP(4,5);CMP(6,7);CMP(8,9);CMP(4,6);CMP(5,7);CMP(3,4);CMP(5,6);CMP(7,8);
#undef CMP
    #pragma GCC unroll 4
    for(unsigned i=0;i<4;++i) {
        a[2*i]=_mm256_unpacklo_epi8(x[2*i],x[2*i+1]);
        a[2*i+1]=_mm256_unpackhi_epi8(x[2*i],x[2*i+1]);
    }
    #pragma GCC unroll 2
    for(unsigned i=0;i<2;++i) {
        #pragma GCC unroll 2
        for(unsigned j=0;j<2;++j) {
            b[4*i+2*j]=_mm256_unpacklo_epi16(a[4*i+j],a[4*i+j+2]);
            b[4*i+2*j+1]=_mm256_unpackhi_epi16(a[4*i+j],a[4*i+j+2]);
        }
    }
    #pragma GCC unroll 4
    for(unsigned i=0;i<4;++i) {
        __m256i lo=_mm256_unpacklo_epi32(b[i],b[i+4]);
        __m256i hi=_mm256_unpackhi_epi32(b[i],b[i+4]);
        _mm256_store_si256((__m256i*)(out+32*i),_mm256_permute2x128_si256(lo,hi,0x20));
        _mm256_store_si256((__m256i*)(out+128+32*i),_mm256_permute2x128_si256(lo,hi,0x31));
    }

        a[0]=_mm256_unpacklo_epi8(x[8],x[9]);a[1]=_mm256_unpackhi_epi8(x[8],x[9]);
        a[2]=_mm256_unpacklo_epi8(x[10],x[11]);a[3]=_mm256_unpackhi_epi8(x[10],x[11]);
        b[0]=_mm256_unpacklo_epi16(a[0],a[2]);b[1]=_mm256_unpackhi_epi16(a[0],a[2]);
        b[2]=_mm256_unpacklo_epi16(a[1],a[3]);b[3]=_mm256_unpackhi_epi16(a[1],a[3]);
        #pragma GCC unroll 2
        for(unsigned i=0;i<2;++i){
            _mm256_store_si256((__m256i*)(tail+32*i),_mm256_permute2x128_si256(b[2*i],b[2*i+1],0x20));
            _mm256_store_si256((__m256i*)(tail+64+32*i),_mm256_permute2x128_si256(b[2*i],b[2*i+1],0x31));
        }
        }

alignas(16) static constexpr auto insertion_masks=[] {
    std::array<std::array<uint8_t,16>,16> a{};
    for(unsigned k=0;k<16;++k)for(unsigned j=0;j<16;++j)
        a[k][j]=j<k?j:(j==k?128:j-1);
    return a;
}();
inline __m128i insert_byte(__m128i x,unsigned byte) {
    __m128i v=_mm_set1_epi8(char(byte));
    unsigned bits=unsigned(_mm_movemask_epi8(_mm_cmpeq_epi8(x,_mm_max_epu8(x,v))));
    unsigned k=__builtin_ctz(bits);
    __m128i order=_mm_load_si128((const __m128i*)insertion_masks[k].data());
    return _mm_blendv_epi8(_mm_shuffle_epi8(x,order),v,order);
}
// Input is completely consumed before output begins. 'end' may extend past this
// leaf only for forward output into a not-yet-finalized suffix. Reverse in-place
// processing passes dst+n, so no already-finalized following leaf is overwritten.
inline void columns_merge(const uint16_t* src,unsigned n,unsigned* dst,unsigned base,unsigned* end) {
    if(n<64) {
        unsigned copy[64];for(unsigned i=0;i<n;++i)copy[i]=base|load16(src+i);
        std::sort(copy,copy+n);std::memcpy(dst,copy,n*4);return;
    }
    if(n>8192) {dense(src,n,dst,base);return;}
    alignas(64) static uint8_t columns[256*8192];
    alignas(64) unsigned count[256];
    std::memset(columns,255,3072);
    for(unsigned i=0;i<256;++i)count[i]=i;
    for(unsigned i=0;i<n;++i) {
        unsigned v=load16(src+i),h=v>>8,at=count[h];
        count[h]=at+256;columns[at]=uint8_t(v);
    }
    // n<=8192 here, so all recovered counts are nonnegative signed 32-bit values.
    __m256i bad=_mm256_setzero_si256();
    const __m256i limit=_mm256_set1_epi32(32);
    #pragma GCC unroll 1
    for(unsigned k=0;k<256;k+=8){
        __m256i counts=_mm256_srli_epi32(_mm256_load_si256((const __m256i*)(count+k)),8);
        bad=_mm256_or_si256(bad,_mm256_cmpgt_epi32(counts,limit));
        _mm256_store_si256((__m256i*)(count+k),counts);
    }
    if(!_mm256_testz_si256(bad,bad)){dense(src,n,dst,base);return;}

    for(unsigned block=0;block<256;block+=32) {
        alignas(32) uint8_t first[256],second[128];
        batch_sort(columns+block,first,second);
        for(unsigned i=0;i<32;++i) {
            unsigned h=block+i,c=count[h],p=base|(h<<8);
            if(__builtin_expect(c<=12,1)) {
                __m256i prefix=_mm256_set1_epi32(p);
                __m256i wide=_mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)(first+8*i))),prefix);
                uint32_t four;std::memcpy(&four,second+4*i,4);
                __m128i wide4=_mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)),_mm256_castsi256_si128(prefix));
                if(__builtin_expect(end-dst>=12,1)) {
                    _mm256_storeu_si256((__m256i*)dst,wide);
                    _mm_storeu_si128((__m128i*)(dst+8),wide4);
                }else {
                    alignas(32) unsigned copy[12];
                    _mm256_store_si256((__m256i*)copy,wide);
                    _mm_store_si128((__m128i*)(copy+8),wide4);
                    std::memcpy(dst,copy,c*4);
                }
            } else if(c<=16) {
                __m128i x=_mm_loadl_epi64((const __m128i*)(first+8*i));
                uint32_t four;std::memcpy(&four,second+4*i,4);
                x=_mm_unpacklo_epi64(x,_mm_cvtsi64_si128(uint64_t(four)|0xffffffff00000000ull));
                for(unsigned j=12;j<c;++j)x=insert_byte(x,columns[256*j+h]);
                write8(x,dst,8,p,end);write8(_mm_srli_si128(x,8),dst+8,c-8,p,end);
            }else {
                uint8_t copy[32];for(unsigned j=0;j<c;++j)copy[j]=columns[256*j+h];
                std::sort(copy,copy+c);for(unsigned j=0;j<c;++j)dst[j]=p|copy[j];
            }
            dst+=c;
        }
    }
}
} // namespace v2_tail
namespace fastsort {
using U=unsigned; using B=unsigned char; using H=uint16_t; using Z=uint64_t;
static B* mem;
inline U get(const B* p){U x;std::memcpy(&x,p,4);return x&0xffffff;}
inline U at(const B* p,U i){return get(p+size_t(i/84)*256+i%84*3);}
inline bool fits(B**p,B**e){
    __m256i bad=_mm256_setzero_si256();
    for(int k=0;k<256;k+=4)bad=_mm256_or_si256(bad,_mm256_cmpgt_epi64(
        _mm256_load_si256((__m256i*)(p+k)),_mm256_load_si256((__m256i*)(e+k))));
    return _mm256_testz_si256(bad,bad);
}
bool split(U*a,U n,U*cap,B**start,U*cnt){
    alignas(64) B cache[65536]={};
    alignas(64) B *p[256],*e[256];
    U pos[256];size_t off=0;
    for(U k=0;k<256;++k){
        start[k]=p[k]=mem+off;e[k]=p[k]+((size_t(cap[k])+83)/84)*256;
        off=size_t(e[k]-mem)+25344;pos[k]=k*256;
    }
    for(U i=0;i<n;){
        U stop=std::min(n,i+8192);
#define DUCK15_PUSH(J) { \
            U x=a[i+J],k=x>>24,t=pos[k];std::memcpy(cache+t,&x,4);t+=3; \
            if(__builtin_expect((t&255)==252,0)){ \
                t-=252; \
                _mm256_stream_si256((__m256i*)(p[k]+0),_mm256_load_si256((__m256i*)(cache+t+0))); \
                _mm256_stream_si256((__m256i*)(p[k]+32),_mm256_load_si256((__m256i*)(cache+t+32))); \
                _mm256_stream_si256((__m256i*)(p[k]+64),_mm256_load_si256((__m256i*)(cache+t+64))); \
                _mm256_stream_si256((__m256i*)(p[k]+96),_mm256_load_si256((__m256i*)(cache+t+96))); \
                _mm256_stream_si256((__m256i*)(p[k]+128),_mm256_load_si256((__m256i*)(cache+t+128))); \
                _mm256_stream_si256((__m256i*)(p[k]+160),_mm256_load_si256((__m256i*)(cache+t+160))); \
                _mm256_stream_si256((__m256i*)(p[k]+192),_mm256_load_si256((__m256i*)(cache+t+192))); \
                _mm256_stream_si256((__m256i*)(p[k]+224),_mm256_load_si256((__m256i*)(cache+t+224))); \
                p[k]+=256; \
            }pos[k]=t; \
}
        for(;i+8<=stop;i+=8){
            // Hint only; forming this address does not read outside the input.
            _mm_prefetch((const char*)((uintptr_t)(a+i)+256),_MM_HINT_NTA);
            DUCK15_PUSH(0) DUCK15_PUSH(1) DUCK15_PUSH(2) DUCK15_PUSH(3)
            DUCK15_PUSH(4) DUCK15_PUSH(5) DUCK15_PUSH(6) DUCK15_PUSH(7)
        }
#undef DUCK15_PUSH
        for(;i<stop;++i){
            U x=a[i],k=x>>24,t=pos[k];std::memcpy(cache+t,&x,4);t+=3;
            if(__builtin_expect((t&255)==252,0)){
                t-=252;
                _mm256_stream_si256((__m256i*)(p[k]+0),_mm256_load_si256((__m256i*)(cache+t+0)));
                _mm256_stream_si256((__m256i*)(p[k]+32),_mm256_load_si256((__m256i*)(cache+t+32)));
                _mm256_stream_si256((__m256i*)(p[k]+64),_mm256_load_si256((__m256i*)(cache+t+64)));
                _mm256_stream_si256((__m256i*)(p[k]+96),_mm256_load_si256((__m256i*)(cache+t+96)));
                _mm256_stream_si256((__m256i*)(p[k]+128),_mm256_load_si256((__m256i*)(cache+t+128)));
                _mm256_stream_si256((__m256i*)(p[k]+160),_mm256_load_si256((__m256i*)(cache+t+160)));
                _mm256_stream_si256((__m256i*)(p[k]+192),_mm256_load_si256((__m256i*)(cache+t+192)));
                _mm256_stream_si256((__m256i*)(p[k]+224),_mm256_load_si256((__m256i*)(cache+t+224)));
                p[k]+=256;
            }pos[k]=t;
        }
        if(!fits(p,e)){_mm_sfence();return false;}
    }
    for(U k=0;k<256;++k){
        U r=pos[k]&255;cnt[k]=U((p[k]-start[k])/256)*84+r/3;
        if(r){std::memcpy(p[k],cache+k*256,256);p[k]+=256;}
    }
    _mm_sfence();return fits(p,e);
}
void leaf(const B*s,U n,U base,U*d,U*end=nullptr){v2_tail::columns_merge((const H*)s,n,d,base,end?end:d+n);}
void middle(const B*s,U n,U base,U*d){
    if(n<4096){for(U i=0;i<n;++i)d[i]=base|at(s,i);std::sort(d,d+n);return;}
    U cnt[256]={},begin[257],pos[256];
    if(n>600000||n<16384){
        for(U i=0;i<n;++i)++cnt[at(s,i)>>16];
        begin[0]=0;
        for(U k=0;k<256;++k){pos[k]=begin[k];begin[k+1]=begin[k]+cnt[k];}
        for(U i=0;i<n;++i){U x=at(s,i);H lo=x;std::memcpy((B*)d+2*pos[x>>16]++,&lo,2);}
        for(int k=255;k>=0;--k)if(cnt[k])leaf((B*)d+2*begin[k],cnt[k],base|(U(k)<<16),d+begin[k]);
        return;
    }
    B*tmp=mem+380000000;B*p[256];
    U bytes=0;
    // Approx. 1.25 times the mean + 32 records, rounded up to an odd
    // number of 64-byte cache lines. This is a guess, not a capacity guarantee;
    // the exact retry below is retained. The 4 MB temporary reservation is ample
    // even if all n<=600000 records land in the last tentative slot.
    for(U k=0;k<256;++k){begin[k]=bytes;p[k]=tmp+bytes;bytes+=64*((((n+255)/256*5/4+32)*2+63)/64|1);}
    begin[256]=bytes;
    for(;;){
        U i=0;const B*b=s;
        for(;i+84<=n;i+=84,b+=256){
            _mm_prefetch((const char*)((uintptr_t)b+256),_MM_HINT_T0);
            // Exactly 12 groups per full input block. Prefetch only the first
            // destination of each group; the other six issue no extra hint.
            #pragma GCC unroll 1
            for(unsigned j=0;j<84;j+=7){
                {U x=get(b+3*j+0);U k=x>>16;H lo=x;B*where=p[k];_mm_prefetch((const char*)(where+64),_MM_HINT_T1);std::memcpy(where,&lo,2);p[k]=where+2;}
                {U x=get(b+3*j+3);U k=x>>16;H lo=x;B*where=p[k];std::memcpy(where,&lo,2);p[k]=where+2;}
                {U x=get(b+3*j+6);U k=x>>16;H lo=x;B*where=p[k];std::memcpy(where,&lo,2);p[k]=where+2;}
                {U x=get(b+3*j+9);U k=x>>16;H lo=x;B*where=p[k];std::memcpy(where,&lo,2);p[k]=where+2;}
                {U x=get(b+3*j+12);U k=x>>16;H lo=x;B*where=p[k];std::memcpy(where,&lo,2);p[k]=where+2;}
                {U x=get(b+3*j+15);U k=x>>16;H lo=x;B*where=p[k];std::memcpy(where,&lo,2);p[k]=where+2;}
                {U x=get(b+3*j+18);U k=x>>16;H lo=x;B*where=p[k];std::memcpy(where,&lo,2);p[k]=where+2;}
            }
        }
        for(;i<n;++i){U x=at(s,i);H lo=x;std::memcpy(p[x>>16],&lo,2);p[x>>16]+=2;}
        bool bad=false;
        for(U k=0;k<256;++k){cnt[k]=U(p[k]-(tmp+begin[k]))/2;bad|=p[k]>tmp+begin[k+1];}
        if(!bad)break;
        bytes=0;
        for(U k=0;k<256;++k){begin[k]=bytes;p[k]=tmp+bytes;bytes+=2*cnt[k];}
        begin[256]=bytes;
    }
    // All source data for this path is in independent tmp storage. Thus a leaf
    // may overwrite an unfinalized following leaf, but never cross this B3 range.
    U*end=d+n;
    for(U k=0;k<256;++k){if(cnt[k])leaf(tmp+begin[k],cnt[k],base|(k<<16),d,end);d+=cnt[k];}
}
}
void sort(unsigned*a,int n){
    using namespace fastsort;
    if(n<2)return;
    if(n<4096||n>100000000){std::sort(a,a+n);return;}
    // Same fixed allocation as the supplied baseline; alignment consumes <=63 B.
    void*raw=std::malloc(384000063); if(!raw){std::sort(a,a+n);return;}
    mem=(B*)((uintptr_t(raw)+63)&~uintptr_t(63));
    U cap[256],cnt[256];B*start[256];
    for(U k=0;k<256;++k)cap[k]=U((Z(n)+255)/256)*6/5+32;
    if(!split(a,n,cap,start,cnt)){
        std::memset(cap,0,sizeof cap);for(int i=0;i<n;++i)++cap[a[i]>>24];
        split(a,n,cap,start,cnt);
    }
    U off=0;for(U k=0;k<256;++k){if(cnt[k])middle(start[k],cnt[k],k<<24,a+off);off+=cnt[k];}
    std::free(raw);
}

评测结果