代码

/* ===== REFERENCES =====
 * duck.ac 用户 saffah_codex_6a_agg3，提交 #125828（本题 1017b 排行榜 rank-1，T = 5.210 ms）
 *     <https://duck.ac/submission/125828>
 *     用途：本件**沿用其全部骨架与语义**：1 字节随机直方图计数、AVX2 8 路 u8 独占前缀扫描
 *     （独立块进位）、输出趟 `__builtin_prefetch(&pref[x[i+64]],0,3)` 预取查表、
 *     以及"任一守卫触发即回退到 4 字节宽计数 + 前缀直写"的逐位精确保障思路（本件的回退段
 *     与之一致）。其自带的 References 链（saffah_codex_maker #125700-125702）随正文保留；
 *     本件不主张该部分著作权。
 * duck.ac 用户 saffah_codex_maker，提交 #125700 / #125701 / #125702：上件自述的
 *     "public baseline histogram/prefix/rank construction idea" 来源。
 * ======================
 * ===== 本次思路 ===== （本发为正式性能提交，非试验性）
 * 【[R2F2-P8] u8 块增量秩】rank(v)=#{点:坐标<v}。原件查表趟随机读 **4 MB u32 前缀表**；
 *   本件改为 `pref8[v] = rank(v) - base128[v>>7]`（128 值一块，块基址表 32 KB 常驻 L1）
 *   ⇒ 随机读工作集 4 MB → 1 MB。前缀扫描复用原件同一 AVX2 核，只加"减块基址 + pshufb
 *   打包 4 字节/通道成 u8"。板面读数：#127037 = 5.190380 ms（底盘 #127027 = 5.211517）。
 * 【[R2F2-PW] RMW 写预取（本发变体：去 gather 预取 + 块基址趟改 AVX2 `vpsadbw` 向量化 — 7813 块 × 128 字节标量求和 → 4 条 sad 指令/块）】计数环是**随机读-改-写**，而原件的
 *   `__builtin_prefetch(hist+..,1,3)` 被 gcc 9.3 编成 `prefetcht0`（共享态取行）⇒ 随后的
 *   自增还要再做一次 RFO 升级。本件在该环改用 `prefetchw`（独占态取行），消除升级往返。
 * 【[R2F2-THP] 大页工作区】两块工作区（<105 MB）改**堆分配 + 2 MB 对齐 + MADV_HUGEPAGE**，
 *   随机访问的 TLB 覆盖面从 4 KB 页提升到 2 MB 页（.bss 是文件后背 VMA，拿不到 THP）。
 *   分配失败则回落静态 .bss 缓冲，语义不变。
 * 【守卫（任意输入正确）】① 直方图逐值自增可能回绕 ⇒ 用**块和 == n** 事后判据统一检测
 *   （回绕必使总和小 256 的倍数）；② 块内元素数 > 255 时 u8 增量会失真 ⇒ 建块基址时逐块
 *   检查 `c > 255`。任一触发即回退到与原件的 4 字节宽路径**逐字节同语义**的实现。
 *   本机对拍：n=1e6/999983/262145/100000 随机 + n=300000 窄值域（必触发回绕）+ n=200000
 *   全等值（必触发守卫）五组输出与原件 FNV 逐位一致。
 * ====================== */
#include <immintrin.h>
#include <cstring>
#include <cstdint>
#include <cstdlib>
#include <sys/mman.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt,prfchw")
/* [R2F2-P8] u8 block-delta ranks + [R2F2-PW] prefetchw on the RMW count loop
   + [R2F2-THP] 2MB-aligned heap workspaces with MADV_HUGEPAGE. */
static unsigned char* hist=nullptr;
alignas(64) static unsigned char* pref8=nullptr;
alignas(64) static unsigned* base128=nullptr;
alignas(64) static unsigned* pref32=nullptr;
static unsigned char hist_static[100000000];
alignas(64) static unsigned char pref8_static[100000000+64];
alignas(64) static unsigned base128_static[1048576+64];
alignas(64) static unsigned pref32_static[100000016];
static void* r2f2_halloc(size_t bytes){
    void* p=nullptr;
    if(posix_memalign(&p,(size_t)2<<20,bytes)) return nullptr;
    madvise(p,bytes,MADV_HUGEPAGE);
    return p;
}
#define BS 128
void count_1d(int n,const unsigned*xx,unsigned*outp){
 if(!hist){
  hist=(unsigned char*)r2f2_halloc(100000000+64);
  pref8=(unsigned char*)r2f2_halloc(100000000+128);
  base128=(unsigned*)r2f2_halloc((1048576+64)*sizeof(unsigned));
  pref32=(unsigned*)r2f2_halloc((100000016)*sizeof(unsigned));
  if(!hist||!pref8||!base128||!pref32){hist=hist_static;pref8=pref8_static;base128=base128_static;pref32=pref32_static;}
 }
 std::memset(hist,0,(size_t)n);
 for(int i=0;i<n;i++){
  if(i+64<n)__asm__ volatile("prefetchw %0" :: "m"(*(const unsigned char*)(hist+xx[i+64])));
  ++hist[xx[i]];
 }
 const int NB=(n+127)>>7;
 unsigned s=0; unsigned long long sum=0; bool bad=false;
 const __m256i vz=_mm256_setzero_si256();
 for(int b=0;b<NB;b++){
  int beg=b<<7, e=beg+128; if(e>n)e=n;
  unsigned c;
  if(e-beg==128){
   __m256i q0=_mm256_sad_epu8(_mm256_loadu_si256((const __m256i*)(hist+beg)),vz);
   __m256i q1=_mm256_sad_epu8(_mm256_loadu_si256((const __m256i*)(hist+beg+32)),vz);
   __m256i q2=_mm256_sad_epu8(_mm256_loadu_si256((const __m256i*)(hist+beg+64)),vz);
   __m256i q3=_mm256_sad_epu8(_mm256_loadu_si256((const __m256i*)(hist+beg+96)),vz);
   __m256i t=_mm256_add_epi64(_mm256_add_epi64(q0,q1),_mm256_add_epi64(q2,q3));
   __m128i lo=_mm256_castsi256_si128(t), hi=_mm256_extracti128_si256(t,1);
   __m128i uu=_mm_add_epi64(lo,hi);
   c=(unsigned)((unsigned long long)_mm_cvtsi128_si64(uu)+(unsigned long long)_mm_extract_epi64(uu,1));
  } else {
   unsigned cc=0; for(int j=beg;j<e;j++)cc+=hist[j]; c=cc;
  }
  sum+=c;
  base128[b]=s;
  if(c>255){bad=true;break;}
  s+=c;
 }
 if(!bad && sum==(unsigned long long)n){
  __m256i carry=_mm256_setzero_si256();int i=0;
  for(;i+8<=n;i+=8){
   const unsigned bs=base128[i>>7];
   __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 res=_mm256_sub_epi32(_mm256_add_epi32(v,carry),raw);
   __m256i d=_mm256_sub_epi32(res,_mm256_set1_epi32((int)bs));
   __m256i sh=_mm256_shuffle_epi8(d,_mm256_setr_epi8(0,4,8,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
                                                      0,4,8,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1));
   uint32_t w0=(uint32_t)_mm_cvtsi128_si32(_mm256_castsi256_si128(sh));
   uint32_t w1=(uint32_t)_mm_cvtsi128_si32(_mm256_extracti128_si256(sh,1));
   std::memcpy(pref8+i,&w0,4);
   std::memcpy(pref8+i+4,&w1,4);
   carry=_mm256_add_epi32(carry,total);
  }
  unsigned s2=(unsigned)_mm256_extract_epi32(carry,0);
  for(;i<n;i++){pref8[i]=(unsigned char)(s2-base128[i>>7]);s2+=hist[i];}
  for(int k=0;k<n;k++){
   outp[k]=base128[xx[k]>>7]+pref8[xx[k]];
  }
  return;
 }
 std::memset(pref32,0,(size_t)n*sizeof(unsigned));
 for(int i=0;i<n;i++)++pref32[xx[i]];
 {unsigned t=0;for(int i=0;i<n;i++){unsigned c=pref32[i];pref32[i]=t;t+=c;}}
 for(int i=0;i<n;i++){
  if(i+64<n)__builtin_prefetch(pref32+xx[i+64],0,3);
  outp[i]=pref32[xx[i]];
 }
}

评测结果