代码

// Q32-D8: experimental challenger derived from the user's accepted v10.
// Capacity checks every 32768 inputs; 100352-byte guard per top bucket.
// At n<=100000000, speculative top layout ends at 368574464 < 380000000.
// Preserves exact overflow retries, dense fallback and bounded final output.
// No Duck.ac result is claimed for this file.
// Network: Bert Dobbelaere N12L40D8 (40 comparators, 8 layers).
// Duck.ac 1001 v10: v8 with independent byte-key / word-payload loads.
// Middle-load idea: https://duck.ac/submission/48085
// Network: https://bertdobbelaere.github.io/sorting_networks.html#N12L40D8
#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>
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;
alignas(64) static B columns[256*8192];
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 base){
  V y=_mm256_or_si256(_mm256_cvtepu8_epi32(x),_mm256_set1_epi32(base));
  __asm__ volatile("vmovdqu {%1, %0|%0, %1}" : "=m"(*reinterpret_cast<__m256i_u*>(dst)) : "x"(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,2);CMP(1,4);CMP(3,5);CMP(6,8);CMP(7,10);CMP(9,11);
CMP(0,1);CMP(2,9);CMP(4,7);CMP(5,6);CMP(10,11);
CMP(1,3);CMP(2,7);CMP(4,9);CMP(8,10);
CMP(0,1);CMP(2,3);CMP(4,5);CMP(6,7);CMP(8,9);CMP(10,11);
CMP(1,2);CMP(3,5);CMP(6,8);CMP(9,10);
CMP(2,4);CMP(3,6);CMP(5,8);CMP(7,9);
CMP(1,2);CMP(3,4);CMP(5,6);CMP(7,8);CMP(9,10);
#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+64*i),lo);
    _mm256_store_si256((V*)(out+64*i+32),hi);
  }
    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+64*i),b[2*i]);
      _mm256_store_si256((V*)(tail+64*i+32),b[2*i+1]);
    }
    }
// 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))));
}
[[gnu::noinline]] inline void slow_output(const B* first8,const B* last4,U h,U c,U* dst,U p){
  if(c<=16){
      W x=_mm_loadl_epi64((const W*)(first8));
      uint32_t four;std::memcpy(&four,last4,4);
        x=_mm_unpacklo_epi64(x,_mm_cvtsi64_si128(uint64_t(four)|0xffffffff00000000ull));
        U j=12;do{x=insert_byte(x,columns[256*j+h]);}while(++j<c);
        write8(x,dst,p);write8(_mm_srli_si128(x,8),dst+8,p);
      }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];
      }
}
template<bool AllSmall>
[[gnu::always_inline]] inline U* emit_block(const B* first,const B* second,
    const U* count,U block,U* dst,U base){
  V prefix=_mm256_set1_epi32(base|(block<<8));
  auto emit=[&](U i,const B* first8,const B* last4) __attribute__((always_inline)){
    U h=block+i,c=count[h];
    if(AllSmall || __builtin_expect(c<=12,1)){
      V wide=_mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const W*)first8)),prefix);
      __asm__ volatile("vmovdqu {%1, %0|%0, %1}" : "=m"(*reinterpret_cast<__m256i_u*>(dst)) : "x"(wide));
      U four;std::memcpy(&four,last4,4);
      W y=_mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)),_mm256_castsi256_si128(prefix));
      _mm_storeu_si128((W*)(dst+8),y);
    }else slow_output(first8,last4,h,c,dst,base|(h<<8));
    dst+=c;prefix=_mm256_add_epi32(prefix,_mm256_set1_epi32(256));
    __asm__("" : "+x"(prefix));
  };
  #pragma GCC unroll 1
  for(U half=0;half<2;++half){
    #pragma GCC unroll 1
    for(U group=0;group<4;++group){
      fastsort::repeat<4>([&](auto r) __attribute__((always_inline)){
        emit(16*half+4*group+r,
             first+16*half+64*group+8*r+16*(r/2),
             second+16*half+32*group+4*r);
      });
    }
  }
  return dst;
}
// Needs sixteen writable padding elements unless a precise fallback is taken.
[[gnu::noinline]] inline void columns_fast(const H* src,U n,U* dst,U base){
  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) 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);
  }
  U small[8];
  V over=_mm256_setzero_si256();
  #pragma GCC unroll 1
  for(U i=0;i<256;i+=32){
    V a=_mm256_srli_epi32(_mm256_load_si256((const V*)(count+i)),8);
    V b=_mm256_srli_epi32(_mm256_load_si256((const V*)(count+i+8)),8);
    V c=_mm256_srli_epi32(_mm256_load_si256((const V*)(count+i+16)),8);
    V d=_mm256_srli_epi32(_mm256_load_si256((const V*)(count+i+24)),8);
    _mm256_store_si256((V*)(count+i),a);_mm256_store_si256((V*)(count+i+8),b);
    _mm256_store_si256((V*)(count+i+16),c);_mm256_store_si256((V*)(count+i+24),d);
    V maximum=_mm256_max_epu32(_mm256_max_epu32(a,b),_mm256_max_epu32(c,d));
    over=_mm256_max_epu32(over,maximum);
    V exceptional=_mm256_cmpgt_epi32(maximum,_mm256_set1_epi32(12));
    small[i>>5]=_mm256_testz_si256(exceptional,exceptional);
  }
  over=_mm256_cmpgt_epi32(over,_mm256_set1_epi32(32));
  if(!_mm256_testz_si256(over,over)){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);
    if(__builtin_expect(small[block>>5],1))dst=emit_block<true>(first,second,count,block,dst,base);
    else dst=emit_block<false>(first,second,count,block,dst,base);
  }
}
[[gnu::noinline]] inline void last_leaf(const H* src,U n,U* dst,U base){
  alignas(32) U copy[8192+16];
  columns_fast(src,n,copy,base);std::memcpy(dst,copy,n*4);
}
template<bool Full=false> inline void columns_merge(const H* src,U n,U* dst,U base,U* end){
  if(!Full && n>=64 && n<=8192 && end-dst<n+16)last_leaf(src,n,dst,base);
  else columns_fast(src,n,dst,base);
}
}
namespace fastsort {
using U=unsigned;using B=unsigned char;using H=uint16_t;using Z=uint64_t;
// Retained for the process lifetime and reused on subsequent calls.
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=100352; // ((32768+83)/84+1)*256; includes partial-block slack.
  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+32768);
    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 k=r[2];H lo;std::memcpy(&lo,r,2);std::memcpy(p[k],&lo,2);p[k]+=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(!mem)mem=(B*)((uintptr_t(std::malloc(384000063))+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)*9/8+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];}
}

评测结果