代码

// EXPERIMENTAL: 4 KiB linked block pool; no measured full-sort speedup over v10.
// Duck.ac 1001, C++17 / AVX2. Exact sort for the specified n=100000000.
// Network: 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>
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,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+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_or_si256(over,_mm256_cmpgt_epi32(maximum,_mm256_set1_epi32(32)));
    V exceptional=_mm256_cmpgt_epi32(maximum,_mm256_set1_epi32(12));
    small[i>>5]=_mm256_testz_si256(exceptional,exceptional);
  }
  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;
static B*mem;
inline U get(const B*p){U x;std::memcpy(&x,p,4);return x&0xffffff;}
void split(U*a,U n,U*head,U*cnt){
 alignas(64) B cache[65536]={};U pos[256],off=0,used[256]={},previous[256];
 for(U k=0;k<256;++k){head[k]=~0u;cnt[k]=0;pos[k]=k*256;}
 auto flush=[&](U k,U t) __attribute__((always_inline)){
  if(!used[k]){previous[k]=head[k];head[k]=off;off+=4096;}
  std::memcpy(cache+t+252,previous+k,4);U target=head[k]+used[k]*256;
  repeat<8>([&](auto j) __attribute__((always_inline)){
   _mm256_stream_si256((__m256i*)(mem+target+32*j),_mm256_load_si256((const __m256i*)(cache+t+32*j)));
  });used[k]=(used[k]+1)&15;
 };
 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;flush(k,t);cnt[k]+=84;}pos[k]=t;
 };
 U i=0;for(;i+8<=n;i+=8)repeat<8>([&](auto j) __attribute__((always_inline)){push(a[i+j]);});
 for(;i<n;++i)push(a[i]);
 for(U k=0;k<256;++k){U r=(pos[k]&255)/3;if(r){flush(k,k*256);cnt[k]+=r;}}
 _mm_sfence();
}
template<class F> inline void visit(U head,U n,F&&f){
 U len=(n-1)%1344+1;
 while(head!=~0u){const B*page=mem+head;U next;std::memcpy(&next,page+((len+83)/84)*256-4,4);
  if(next!=~0u)_mm_prefetch((const char*)(mem+next),_MM_HINT_T0);
  U i=0;const B*b=page;
  for(;i+84<=len;i+=84,b+=256){
   _mm_prefetch((const char*)(b+256),_MM_HINT_T0);
   #pragma GCC unroll 1
   for(U j=0;j<84;j+=12)repeat<12>([&](auto q) __attribute__((always_inline)){f(b+3*(j+q));});
  }
  for(U j=0;i<len;++i,++j)f(b+3*j);
  head=next;len=1344;
 }
}
void middle(U head,U n,U base,U*d){
 if(n<16384||n>600000){U i=0;visit(head,n,[&](const B*r){d[i++]=base|get(r);});std::sort(d,d+n);return;}
 U cnt[256],begin[257],bytes=0;B*tmp=mem+312000000;B*p[256];
 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(;;){
  visit(head,n,[&](const B*r) __attribute__((always_inline)){U k=r[2];H lo;std::memcpy(&lo,r,2);std::memcpy(p[k],&lo,2);p[k]+=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])v2_tail::columns_merge((const H*)(tmp+begin[k]),cnt[k],d,base|(k<<16),end);d+=cnt[k];}
}
}
void sort(unsigned*a,int n){using namespace fastsort;if(n<2)return;
 if(!mem)mem=(B*)((uintptr_t(std::malloc(316000063))+63)&~uintptr_t(63));
 U head[256],cnt[256];split(a,n,head,cnt);U off=0;
 for(U k=0;k<256;++k){if(cnt[k])middle(head[k],cnt[k],k<<24,a+off);off+=cnt[k];}
}

评测结果