代码

// Duck.ac 1001, V18 candidate based on the user-supplied 376.352 ms implementation.
// Entry: void sort(unsigned*, int). C++17 / AVX2; single thread, no runtime timing.
// Changes: direct byte-key + 16-bit-payload reads in middle full blocks;
// exact 32-bin classification, common output without per-bin branches.
// Preserves the 84-record/256-byte format, top splitter and guards, 12-input
// network, three-operation insertion, all overflow recovery and allocation sizes.
// 12-input/39-comparator network credit: Bert Dobbelaere.
// https://bertdobbelaere.github.io/sorting_networks.html#N12L39D9
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <immintrin.h>
#include <utility>
#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 fastsort {
template<class F,size_t... I>
[[gnu::always_inline]] inline void each(F&& f,std::index_sequence<I...>){
  (f(std::integral_constant<size_t,I>{}),...);
}
template<size_t N,class F> [[gnu::always_inline]] inline void repeat(F&&f){
  each(std::forward<F>(f),std::make_index_sequence<N>{});
}
}
namespace v2_tail {
using U=unsigned;using B=uint8_t;using H=uint16_t;using V=__m256i;using W=__m128i;
inline U load16(const H* p){H v;std::memcpy(&v,p,2);return v;}
[[gnu::noinline]] inline void dense(const H* src,U n,U* dst,U base){
  alignas(64) U counts[65536]={};
  for(U i=0;i<n;++i)++counts[load16(src+i)];
  for(U v=0;v<65536;++v)for(U c=counts[v];c;--c)*dst++=base|v;
}
inline void write8(W x,U* dst,U c,U base,U* end){
  V y=_mm256_or_si256(_mm256_cvtepu8_epi32(x),_mm256_set1_epi32(base));
  if(end-dst>=8)_mm256_storeu_si256((V*)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);
}
[[gnu::always_inline]] inline void batch_sort(const B* src,B* out,B* tail){
V x[12],a[8],b[8];
fastsort::repeat<12>([&](auto j) __attribute__((always_inline)){
    x[j]=_mm256_load_si256((const V*)(src+256*j));
});
#define CMP(A,B) do {V 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(U 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(U i=0;i<2;++i){
    #pragma GCC unroll 2
    for(U 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(U i=0;i<4;++i){
    V lo=_mm256_unpacklo_epi32(b[i],b[i+4]);
    V hi=_mm256_unpackhi_epi32(b[i],b[i+4]);
    _mm256_store_si256((V*)(out+32*i),_mm256_permute2x128_si256(lo,hi,0x20));
    _mm256_store_si256((V*)(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(U i=0;i<2;++i){
      _mm256_store_si256((V*)(tail+32*i),_mm256_permute2x128_si256(b[2*i],b[2*i+1],0x20));
      _mm256_store_si256((V*)(tail+64+32*i),_mm256_permute2x128_si256(b[2*i],b[2*i+1],0x31));
    }
}
// x is sorted and has at least one trailing 255 sentinel.
inline W insert_byte(W x,U byte){
  return _mm_min_epu8(x,_mm_max_epu8(_mm_slli_si128(x,1),_mm_set1_epi8(char(byte))));
}
// Extended end is allowed only for independent-source forward output.
inline void columns_merge(const H* src,U n,U* dst,U base,U* end){
  if(n<64){
    U copy[64];for(U 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 B columns[256*8192];
  alignas(64) U count[256];
  std::memset(columns,255,3072);
  for(U i=0;i<256;++i)count[i]=i;
  for(U i=0;i<n;++i){
    U v=load16(src+i),h=v>>8,at=count[h];
    count[h]=at+256;columns[at]=B(v);
  }
    // Restore the exact counts, reduce maxima per 32-bin group, and record
    // which groups are entirely handled by the already-sorted twelve rows.
    alignas(32) U exceptional[8];
    __m256i bad=_mm256_setzero_si256();
    const __m256i limit32=_mm256_set1_epi32(32);
    const __m256i limit12=_mm256_set1_epi32(12);
    #pragma GCC unroll 1
    for(U k=0;k<256;k+=32){
        __m256i a=_mm256_srli_epi32(_mm256_load_si256((const __m256i*)(count+k)),8);
        __m256i b=_mm256_srli_epi32(_mm256_load_si256((const __m256i*)(count+k+8)),8);
        __m256i c=_mm256_srli_epi32(_mm256_load_si256((const __m256i*)(count+k+16)),8);
        __m256i d=_mm256_srli_epi32(_mm256_load_si256((const __m256i*)(count+k+24)),8);
        _mm256_store_si256((__m256i*)(count+k),a);
        _mm256_store_si256((__m256i*)(count+k+8),b);
        _mm256_store_si256((__m256i*)(count+k+16),c);
        _mm256_store_si256((__m256i*)(count+k+24),d);
        __m256i maxes=_mm256_max_epu32(_mm256_max_epu32(a,b),_mm256_max_epu32(c,d));
        bad=_mm256_or_si256(bad,_mm256_cmpgt_epi32(maxes,limit32));
        exceptional[k>>5]=U(_mm256_movemask_epi8(_mm256_cmpgt_epi32(maxes,limit12)));
    }
    if(!_mm256_testz_si256(bad,bad)){dense(src,n,dst,base);return;}

  for(U block=0;block<256;block+=32){
    alignas(32) B first[256],second[128];
    batch_sort(columns+block,first,second);
        // Every exact count in this group is <= 12. 31*12+12 = 384
        // bounds all full stores. Extra sentinel stores touch only an
        // unfinished suffix and are overwritten by subsequent real output.
        if(__builtin_expect(exceptional[block>>5]==0 && end-dst>=384,1)){
            __m256i prefix=_mm256_set1_epi32(base|(block<<8));
            const __m256i step=_mm256_set1_epi32(256);
            #pragma GCC unroll 1
            for(U i=0;i<32;++i){
                __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));
                __asm__ volatile("vmovdqu {%1, %0|%0, %1}" : "=m"(*reinterpret_cast<__m256i_u*>(dst)) : "x"(wide));
                _mm_storeu_si128((__m128i*)(dst+8),wide4);
                dst+=count[block+i];
                prefix=_mm256_add_epi32(prefix,step);
            }
            continue;
        }
    V prefix=_mm256_set1_epi32(base|(block<<8));
    for(U i=0;i<32;++i){
      U h=block+i,c=count[h],p=base|(h<<8);
      if(__builtin_expect(c<=12,1)){
        W x=_mm_loadl_epi64((const W*)(first+8*i));
        uint32_t four;std::memcpy(&four,second+4*i,4);
        V wide=_mm256_or_si256(_mm256_cvtepu8_epi32(x),prefix);
        if(__builtin_expect(end-dst>=12,1)){
          __asm__ volatile("vmovdqu {%1, %0|%0, %1}"
                        : "=m"(*reinterpret_cast<__m256i_u*>(dst)) : "x"(wide));
          W y=_mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)),_mm256_castsi256_si128(prefix));
          _mm_storeu_si128((W*)(dst+8),y);
        }else{
          alignas(32) U copy[16];
          _mm256_store_si256((V*)copy,wide);
          W y=_mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)),_mm256_castsi256_si128(prefix));
          _mm_store_si128((W*)(copy+8),y);
          std::memcpy(dst,copy,c*4);
        }
      } else if(c<=16){
        W x=_mm_loadl_epi64((const W*)(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(U 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{
        B copy[32];for(U j=0;j<c;++j)copy[j]=columns[256*j+h];
        std::sort(copy,copy+c);for(U j=0;j<c;++j)dst[j]=p|copy[j];
      }
      dst+=c;
      prefix=_mm256_add_epi32(prefix,_mm256_set1_epi32(256));
    }
  }
}
}
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(U 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){
  constexpr U guard=25344;
  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)+guard;pos[k]=k*256;
  }
  auto push=[&](U x) __attribute__((always_inline)){
    U k=x>>24,t=pos[k];std::memcpy(cache+t,&x,4);t+=3;
    if(__builtin_expect((t&255)==252,0)){
      t-=252;
      repeat<8>([&](auto j) __attribute__((always_inline)){
        _mm256_stream_si256((__m256i*)(p[k]+32*j),_mm256_load_si256((const __m256i*)(cache+t+32*j)));
      });
      p[k]+=256;
    }
    pos[k]=t;
  };
  for(U i=0;i<n;){
    U stop=std::min(n,i+8192);
    for(;i+8<=stop;i+=8)repeat<8>([&](auto j) __attribute__((always_inline)){push(a[i+j]);});
    for(;i<stop;++i)push(a[i]);
    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;
  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);
      #pragma GCC unroll 1
      for(U j=0;j<84;j+=12)repeat<12>([&](auto q) __attribute__((always_inline)){
        const B* r=b+3*(j+q);
        U key=r[2]; // Independent bucket-key load, no 24-bit mask/shift chain.
        H lo;std::memcpy(&lo,r,2);
        std::memcpy(p[key],&lo,2);p[key]+=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;
  }
  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;}
  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);
}

评测结果