代码

/* References:
 * saffah_codex_maker, https://duck.ac/submission/125700,
 * https://duck.ac/submission/125701 and https://duck.ac/submission/125702:
 * problem-specific public baseline histogram/prefix/rank construction idea.
 * Idea: Count into a byte histogram to reduce the random update working set,
 * widen eight counts at a time into an AVX2 prefix scan with an independent
 * block total, then prefetch the rank lookups. If any byte would wrap, restart
 * using full-width counts so every repeated-coordinate distribution remains exact.
 * Purpose: Official experiment reducing random histogram cache misses and prefix work.
 */
#include <immintrin.h>
#include <cstring>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")
static unsigned char hist[100000000];
alignas(64) static unsigned pref[100000016];
void count_1d(int n,const unsigned*x,unsigned*out){
 std::memset(hist,0,(size_t)n);
 bool wide=false;
 for(int i=0;i<n;i++){
  if(i+64<n)__builtin_prefetch(hist+x[i+64],1,3);
  if(++hist[x[i]]==0){wide=true;break;}
 }
 if(wide){
  std::memset(pref,0,(size_t)n*sizeof(unsigned));
  for(int i=0;i<n;i++)++pref[x[i]];
  unsigned s=0;for(int i=0;i<n;i++){unsigned c=pref[i];pref[i]=s;s+=c;}
 }else{
  __m256i carry=_mm256_setzero_si256();int i=0;
  for(;i+8<=n;i+=8){
   __m256i raw=_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)(hist+i)));
   __m256i v=raw;
   v=_mm256_add_epi32(v,_mm256_slli_si256(v,4));
   v=_mm256_add_epi32(v,_mm256_slli_si256(v,8));
   __m256i low=_mm256_permute2x128_si256(v,v,0x08);
   low=_mm256_shuffle_epi32(low,0xff);
   v=_mm256_add_epi32(v,low);
   __m256i total=_mm256_permutevar8x32_epi32(v,_mm256_set1_epi32(7));
   __m256i result=_mm256_sub_epi32(_mm256_add_epi32(v,carry),raw);
   _mm256_store_si256((__m256i*)(pref+i),result);
   carry=_mm256_add_epi32(carry,total);
  }
  unsigned s=(unsigned)_mm256_extract_epi32(carry,0);
  for(;i<n;i++){pref[i]=s;s+=hist[i];}
 }
 for(int i=0;i<n;i++){
  if(i+64<n)__builtin_prefetch(pref+x[i+64],0,3);
  out[i]=pref[x[i]];
 }
}

评测结果