// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #104746 <https://duck.ac/submission/104746>
// 用途：**直接复制了该提交的全部正文**（本文件 = 其正文 + 一处 [ASM8] 改动，见"思路"）。
// #104746 自述的上游引用（#102751 / #104721 / #103322 等）一并在其头部注释里保留。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #104721 <https://duck.ac/submission/104721>
// 用途：参考了它给出的**判题机单价标定**。它把 `screen` 双直方图趟 7→5 条指令/元素
// （唯一访存变化 = +1 条 load），判题机实测 **+16.756 ms = +0.1248 ns/元素**。
// ★ 据此换算：+0.1248 ns/元素 ÷ (0.25 cycle/µop) ⇒ 判题机有效主频 ≈ **2.2 GHz**，
// 即实测 cycle/元素 = 指令条数 × 0.25（前段 4 宽），**而不是** 3.6 GHz 下的 4.05。
// 用 2.2 GHz 复核已定价相位：L0 10 条→2.48（实测 2.476 ✓）、screen 7 条→1.79（实测 1.787 ✓）
// ⇒ 这些环恰好落在 `max(loads/2, stores/1, uops/4)` 地板上；此前算出的"+0.9~+1.6 停顿"
// 是**主频标定误差**，不是停顿。⇒ L0 的绑定项 = 前段 **10/4 = 2.50**，唯一杠杆是**减条数**。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #105144 <https://duck.ac/submission/105144>
// 用途：本次改动的前一版（**Wrong Answer**）。那一版把宏参数 `B` 当字节偏移用在了 C 表达式
// `aa[i+B]` 里（应为元素下标）⇒ 除第 0 个展开体外 v/d 取自不同元素。本发修正为
// `L2BODY(K,4K+3)`（K = 元素下标、4K+3 = 汇编的字节位移），其余逐字节相同。
// ======================
// ===== 思路 =====
// 【ASM8：把 L0 热循环的每元素指令数从 10 条降到 8 条】
// 判题机 gcc 9.3 逐条核对（godbolt g93，`-O2`；本代理生成，见 work/b1b/b1b_asmb4_93.s）：
// 改前 10 条/元素：movzx d / mov v / movzx off / lea _n / **mov rdx,r11** / **lea r10d,[r11+3]** /
// movw store / test / je / mov g_stg[r11]
// 改后 8 条/元素：mov v / movzbl d / movzwl off / leal _n / movw store / test / je /
// **mov DWORD PTR g_stg[rcx-3]**
// 被去掉的正是那两条"只为跨 flush 分支保住 o 与 _n"的复制。做法：游标 RMW 的 4 条指令用内联汇编
// 固定下来（movzbl d / movzwl off[d] / leal +3 / movw 回写），游标声明成 `unsigned long long`
// 而汇编用 32 位形式写它 ⇒ 零扩展，gcc 由此不必再补 `mov edx,edx`；payload 的 4 字节存留在
// **非 flush 分支**里、地址仍是 `SG+o` 一步折叠（`mov [rcx-3], r8d`）。
// 语义：搬运的是同一批值，写出的每个字节/每个地址/每个次序都与 [1] 逐位相同。
// 本地闸门（gcc 15，`-O2`，full-sort 输出 FNV 哈希逐位对比）：n=2^24 的 9 种形状
// （judge/a1y/k16/k64/k128/k256/b2skew/b0skew/skewtail）**全部 SAME** ✓，
// 并且 n=2^27 的 judge 与 a1y 形状也 **SAME** ✓。
// 本次为**单变量**提交：目的是在判题机上定价"L0 每个元素减 2 条 uop"。预测（若判题机确实前段受限）
// −0.5 cycle/元素 ≈ **−30 ms**（缺口只有 3.436 ms）；若不是前段受限则 ≈ 0。两种结果都有信息量。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #102751 <https://duck.ac/submission/102751>
// 用途：**直接复制了该提交的全部正文**（本文件 = 其正文逐字节 + 一处 [HIREG] 改动）。
// #102751 自述的上游引用（本账号 #100862 / #100684 / #100856 / #100737 / #100775 / #100797 /
// #102554 / #102608 / #102695 / #102726 等）一并在其头部注释里保留。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #104721
// <https://duck.ac/submission/104721>
// 用途：**用它标定"端口模型"**（见下）。#104721 是本代理把 `screen` 双直方图趟从 7 条指令/元素
// 改成 5 条指令/元素的那一发，**判题机实测 648.754746 ms = +16.756 ms（+2.651%）**。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #103322
// <https://duck.ac/submission/103322>
// 用途：参考了它"删掉一条同址重复 load"的结论（判题机 **+0.19% ≈ 0**）——见下方"为什么这一发不同"。
// ======================
// ===== 思路 =====
// ★ 方法（BRIEF §2.18.819 的"确定性代理"）—— 但**换了被数的东西：不数指令，数端口**。
// 本代理先做了那次标定（`#104721`：`screen` 趟 7 → 5 条指令/元素，**唯一的访存变化是 +1 条 load**）：
// 实测 **+16.756 ms / 1.342e8 元素 = +0.4494 cycle/元素**；
// 而端口模型预测 `Δload/2 + Δstore/1 + ΔALU/4(前段有空档时≈0)` = **+0.500** ✓（误差 10%）。
// ⇒ ★★★ **本引擎（实测 IPC≈2.4 < 4）的经验标定：ALU uop 基本免费；每条 load 值 0.5 cycle/元素、
// 每条 store 值 1.0 cycle/元素**（1.342e8 元素上 0.5 cycle/元素 = **18.6 ms**）。
// ⇒ **要赢只能删 load 或删 store，不能删 ALU。**
//
// ★ 本发：删掉 `ROBUST` 第二趟散射（byte1 散射）里的**一条循环不变的 load**。
// 原：`for(i<m2){ u32 v=sc[i]; sc2[off1[v>>8]++] = hi24|v; }`
// —— gcc 9.3 把 `hi24`（一个 `const u32` 局部量）**每轮从栈槽重读一次**：
// `or edx, DWORD PTR [rsp+636]`（栈槽与 `off1[]` 同栈，GCC 无法证明不别名 ⇒ 不能提升）
// 新：`u32 HI=hi24; __asm__("" : "+r"(HI));` 把 `HI` 钉在寄存器里 ⇒ `or edx, r11d`
// ★ **已用判题机同版本 gcc 9.3 汇编逐条核对**（本机 g++ 是 15.x，看不到这个差别）：
// 环内指令数**不变**，但每元素**少一条 load** ⇒ 模型预测 **−0.5 cycle/元素 ≈ −18.6 ms**（缺口 3.566 ms）。
// 寄存器压力核算：该环只用 rsi/ecx/edx/r13/rax/rdi + 新增 r11 = 7 个 GPR ✓ 有余量。
//
// ★ **为什么这一发不该重复 `#103322` 的"零"**（`#103322` 删掉 L0 里一条重复 load，判题机 +0.19% ≈ 0）：
// 那一发把"被删的 load"换成了 `v>>24`，而 `v>>24` **正好落在依赖链上**
// （`load aa[i] → shr → load off[d] → store`）⇒ 省下的 0.5 cycle 被链上多出的 1 拍抵掉 ⇒ 净 0 ✓（与其实测吻合）。
// 本发**不引入任何新运算**：`or` 还在原位、还在同一条数据通路上，只是**它的操作数从内存变成寄存器**
// ⇒ 纯粹的"少一条 load"，不付链代价。
//
// ★ 本机闸门（n=2^24）：`judge / k256 / skewtail / b0skew` 四形状 **hash 与基线逐位相同、sorted=1** ✓
// （本机时间分别 158.1/162.9/154.5/157.4 vs 基线 163.8/165.8/150.8/162.7 —— 3 好 1 坏，**在本机噪声内**，
// 按 §2.18.814 本机也不是同一台机器，**故只做正确性闸门、不下判词**。）
// ★ 本次为**试验性提交**：目的是用一次判题机读数检验上面那套"端口模型"的第二点。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 #102619 <https://duck.ac/submission/102619>
// （634.780 ms，本题当前榜首）。用途：**本文件正文直接复制了该提交的全部实现**，
// 唯一改动 = 思路段那一行（`BLKST` 320 → 192）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #102547 <https://duck.ac/submission/102547>
// / #102554 <https://duck.ac/submission/102554> / #102608 <https://duck.ac/submission/102608>。
// 用途：**本账号先把「L3 robust 输出落地改 L1 scratch + 整行 NT 写」这条刀交了出去**
// （#102547，去 RFO；#102608 再叠 BLKST 位移格），[1] 的 #102521/#102524/#102530 正是在它之上
// 做的细化（partial-line carry、scratch 相位对齐）。本发从 [1] 取回了这些细化。
// [3] duck.ac 用户 saffah_cc_v41_260924，提交 #100292 <https://duck.ac/submission/100292>
// —— 整条定长区域散列 + 位排序网络引擎的原始来源（经 [2] 转来）。
// ======================
// ===== 思路 =====
// 【单变量】level-2 的散列环里每 16 个元素发一条 **`prefetchnta`**（`__builtin_prefetch(p,0,0)`，
// 前瞻 `sp+512` ≈ 170 个元素 ≈ 620 cycle）打在这条 **402 MB 的源读**上。
// 动机：T 的每个桶区只有 ~4.6 KB、整块 T=1.16 MB，且**每个 byte3 区都要重写一遍**；
// 如果 402 MB 的源流把 T 的脏行从 L3 挤出去，就会多出 ~300 MB 写回 + ~300 MB 重取。
// NTA 提示让源流不驻留 L2/L3 ⇒ 把 T 钉在 cache 里。地址/字节/输出完全不变。
// 【单变量改动】`BLKST` 320 → 192。`BLKST` 只用于 `g_stg[256*BLKST]` 的**数组长度**
// （真正的分组步长是 `g_blkst`=192，寻址表达式逐字节不变）⇒ 本发把 BSS 里 g_stg 之后的
// g_T / g_sc / g_sc2 / g_U 整体前移 32 KB（= 8×4096，故 mod 4096 不变、mod 65536 变），
// 即 §2.18.562 的「地址几何」轴。本账号 #102608 在**上一个 codegen** 上实测该位移 = −0.047 ms。
// 依据（本账号本轮真机实测）：#102547（同结构 + 4 字节散存写 512 MB 输出）= 635.912；
// #102554（+ padding 格）= 635.396；#102608（+ BLKST 192）= 635.344。
// 语义：读写地址集合与写出的每一个字节都不变。
// ================
#pragma GCC optimize("O3","unroll-loops","schedule-insns","sched-stalled-insns=2","live-range-shrinkage")
#pragma GCC optimize("-fno-crossjumping")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,sse4.1,ssse3")
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <immintrin.h>
#include <stdint.h>
// lane p1001_dead: THE STORE BARRIER WAS TOO WIDE. The shipped st256 is an
// `asm volatile` with a **"memory" clobber**, i.e. it tells GCC-9 that the store
// may have modified ALL of memory. The emit executes ~21 M of these (4 per
// group always + 8 in the merge arm), so the clobber invalidates every load in
// the loop body on every iteration: the four `cnt3[b1..b1+3]` scalars, the
// `BM(g_pb1+8*b1)` prefix vectors, and -- crucially -- it is the reason the
// seven loop-invariant constant tables were re-loaded per iteration at all
// (work/e1001o (D) recorded that "constexpr changes NOTHING"; this clobber is
// why). Declaring the EXACT bytes written as a memory output operand keeps the
// asm `volatile` (so the store still executes, is never deleted, and the nine
// sites keep their RELATIVE ORDER, which the overlapping-store chain relies on)
// while letting GCC keep unrelated loads in registers across it. Same
// instruction, same address, same value, same order.
static inline void st256(void *p,__m256i v){ // GCC-9 splits storeu into 2x128B + vextracti128
asm("vmovdqu %1, %0" : "=m"(*(__m256i*)p) : "x"(v));
}
typedef unsigned u32; typedef unsigned short u16; typedef unsigned char u8;
#define SLK1 4352u
#define DIT 256u
#define NMAX 134217728u
#define CAP1M (NMAX/256u + SLK1)
// region base must be 64-byte aligned: base = 3*(b*STR1M + 64*k), and 3*x is
// 64-aligned iff x is. Otherwise the 192-byte NT flush straddles line boundaries
// and each destination is a PARTIAL line -- the exact case where NT pays nothing.
#define STR1M (((CAP1M + DIT + 64u) + 63u) & ~63u)
#define REC3 3u
// Guard region: an adversarially skewed input (one byte3 bucket holding far more
// than CAP1M elements) can push a region cursor past its own region; this slack
// absorbs that so the scatter can never write outside g_S8. In normal operation
// these pages are never written, and the judge charges only WRITTEN pages.
#define GUARD8 (64u<<20)
static u8 g_S8[REC3*(256u*STR1M + CAP1M + 8192u) + 64u + GUARD8];
// L1 staging: one BLK-byte block per bucket, L2-resident. A block holds
// BLK/3 = 85 records + the trailing 4-byte store; it is flushed to the real
// destination as whole cache lines with non-temporal stores (full-line NT is
// what the judge rewards: 2.6-4.5x over a strided regular scatter).
#define BLK 192u
#define BLKREC 64u
#define BLKST 384u // staging stride: 192B payload + pad, multiple of 32
// lane p1001_gstg: THE PRICING INSTRUMENT. `volatile` so gcc-9 cannot fold it:
// `off[b]=b*g_blkst` is the ONLY use in the L2 loop's data flow, and the flush
// test forces `o+3 == 0 (mod 64)` while BLK is 192, so the flush source `SG+(o+3-BLK)`
// is 64-byte aligned for EVERY value below => the loop's .text is IDENTICAL.
static volatile u32 g_blkst = 192u;
static u8 g_stg[256u*BLKST] __attribute__((aligned(256)));
#define SLK2 256u
#define RS2MAX ((((CAP1M>>8) + SLK2 + 63u) >> 5) + 2u) * 32u
static u16 g_T[256u*RS2MAX + CAP1M + 8192u];
#define TSZ (256u*RS2MAX + CAP1M + 8192u)
#define SCZ (CAP1M + 8192u)
static u16 * const g_sc = g_T + (256u*RS2MAX);
alignas(64) static u32 g_sc2[SCZ+16u];
#define SLK3 18u
#define RS3MAX 32u
// e1001o: with RS3 == 32 every bucket starts at U + 32*b, so a 32-byte-aligned
// g_U makes EVERY bucket load 32-byte aligned (no split 16-byte loads). The
// fleet's earlier alignas(64) test on g_U was NULL, but that was with the old
// non-power-of-two RS3 = 23, where the bucket addresses were arbitrary anyway.
alignas(32) static u8 g_U[256u*RS3MAX + RS2MAX + 256u];
static u32 g_off[257];
static inline void sink64(unsigned long long v){ __asm__ volatile("" :: "r"(v) : "memory"); }
int g_noavx_dbg=-1; static int g_noavx=0;
static inline void pretouch_a(unsigned *p,int n){
if(n<=0) return;
for(int i=0;i<n;i+=1024)
__asm__ volatile("orl $0, %0" : "+m"(p[i]) : : "memory");
__asm__ volatile("orl $0, %0" : "+m"(p[n-1]) : : "memory");
}
static inline __m256i net8_simd(__m256i v){
#define BD(P,IMM) { __m256i t=P; __m256i lo=_mm256_min_epu32(v,t),hi=_mm256_max_epu32(v,t); v=_mm256_blend_epi32(hi,lo,IMM); }
BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(2,3,0,1)),0x99)
BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(1,0,3,2)),0xC3)
BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(2,3,0,1)),0xA5)
BD(_mm256_permute2x128_si256(v,v,1),0x0F)
BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(1,0,3,2)),0x33)
BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(2,3,0,1)),0x55)
return v;
#undef BD
}
static inline __m256i ld8s(const u8 *g,u32 prefix){
return _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)g)),
_mm256_set1_epi32((int)prefix));
}
static inline __m256i ld8p(const u8 *g,u32 cc,u32 prefix){
const __m256i idx=_mm256_setr_epi32(0,1,2,3,4,5,6,7);
__m256i msk=_mm256_cmpgt_epi32(_mm256_set1_epi32((int)cc),idx);
__m256i x=_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)g));
x=_mm256_or_si256(x,_mm256_set1_epi32((int)prefix));
return _mm256_blendv_epi8(_mm256_set1_epi32(-1),x,msk);
}
static void emit_avx2(const u8 *g,u32 c,u32 prefix,u32 *o){
if(c<=8){
st256(o,net8_simd(ld8p(g,c,prefix)));
} else {
__m256i A=net8_simd(ld8p(g,8u,prefix));
__m256i B=net8_simd(ld8p(g+8,c-8u,prefix));
__m256i BR=_mm256_permutevar8x32_epi32(B,_mm256_setr_epi32(7,6,5,4,3,2,1,0));
st256(o,net8_simd(_mm256_min_epu32(A,BR)));
st256(o+8,net8_simd(_mm256_max_epu32(A,BR)));
}
}
static inline __m256i bmerge8(__m256i v){
#define BS(P,IMM) { __m256i t=P; __m256i lo=_mm256_min_epu32(v,t),hi=_mm256_max_epu32(v,t); v=_mm256_blend_epi32(hi,lo,IMM); }
BS(_mm256_permute2x128_si256(v,v,1),0x0F)
BS(_mm256_shuffle_epi32(v,_MM_SHUFFLE(1,0,3,2)),0x33)
BS(_mm256_shuffle_epi32(v,_MM_SHUFFLE(2,3,0,1)),0x55)
return v;
#undef BS
}
static inline void emitv(const u8 *g,u32 c,u32 prefix,__m256i *A,__m256i *B){
if(c<=8){ *A=net8_simd(ld8s(g,prefix)); }
else {
const __m256i REV=_mm256_setr_epi32(7,6,5,4,3,2,1,0);
__m256i X=net8_simd(ld8s(g,prefix));
__m256i Y=net8_simd(ld8s(g+8,prefix));
__m256i YR=_mm256_permutevar8x32_epi32(Y,REV);
__m256i MN=_mm256_min_epu32(X,YR), MX=_mm256_max_epu32(X,YR);
*A=bmerge8(MN); *B=bmerge8(MX);
}
}
static void emit_scalar(const u8 *g,u32 c,u32 prefix,u32 *o){
for(u32 i=0;i<c;i++){
u32 v=prefix|g[i]; u32 j=i;
while(j&&o[j-1]>v){ o[j]=o[j-1]; j--; }
o[j]=v;
}
}
static inline void emit(const u8 *g,u32 c,u32 prefix,u32 *o){
if(!g_noavx && c<=16) emit_avx2(g,c,prefix,o);
else emit_scalar(g,c,prefix,o);
}
// ---- packed emit: 4 buckets x 8 bytes in one ymm (byte-lane network) ----
static u32 g_pb1[256*8] __attribute__((aligned(32))); // PB1[b] = 8 x (b<<8)
static void init_pb1(void){
for(u32 b=0;b<256;b++){ u32 v=b<<8; for(int k=0;k<8;k++) g_pb1[8*b+k]=v; }
}
alignas(32) static u8 g_sh1[32],g_sh2[32],g_sh4[32],g_selb[6][32],g_shrev[32];
static u8 g_mp0[32],g_mp2[32],g_mp2r[32],g_mp0s[32],g_mp2s[32];
static u8 g_k0s2[32],g_k2s4[32];
static void init_bmasks(void){
for(int g=0;g<4;g++){ u8*p=g_shrev+8*g; int b=(g&1)*8; for(int k=0;k<8;k++) p[k]=b+7-k; }
static const u8 P1[8]={1,0,3,2,5,4,7,6};
static const u8 P2[8]={2,3,0,1,6,7,4,5};
static const u8 P4[8]={4,5,6,7,0,1,2,3};
for(int g=0;g<4;g++){
int b=(g&1)*8; // vpshufb byte indices are absolute within the 128-bit lane
u8*p=g_sh1+8*g; u8*q=g_sh2+8*g; u8*r=g_sh4+8*g;
for(int k=0;k<8;k++){ p[k]=P1[k]+b; q[k]=P2[k]+b; r[k]=P4[k]+b; }
}
const u32 S[6]={0x99,0xC3,0xA5,0x0F,0x33,0x55};
for(int s=0;s<6;s++) for(int g=0;g<4;g++) for(int e=0;e<8;e++)
g_selb[s][8*g+e]=((S[s]>>e)&1)?0xFF:0x00;
// ---- lane p1001_bi: PATTERN-SWAP masks for the E-form of the d=1 K0/K2 stages.
// blend_epi16's imm bit i selects lane-local WORD i (lane-local bytes 2i,2i+1); the
// 8-byte group g&1 inside a 128-bit lane owns imm bits 4*(g&1)+{0..3}. Mapping derived
// EMPIRICALLY (work/p1001_bi/immmap.cpp), never from the intrinsic's name.
for(int g=0;g<4;g++){
int gb=g&1, base=8*gb;
for(int w=0;w<4;w++){
int i0=base+2*w, i1=base+2*w+1;
int b0=(0x55u>>(4*gb+w))&1, b2=(0x33u>>(4*gb+w))&1;
g_mp0[8*g+2*w]=b0?i1:i0; g_mp0[8*g+2*w+1]=b0?i0:i1;
g_mp2[8*g+2*w]=b2?i1:i0; g_mp2[8*g+2*w+1]=b2?i0:i1;
}
}
for(int i=0;i<32;i++){ int off=(i>=16)?16:0;
g_mp2r[i]=g_mp2[g_shrev[i]+off];
g_mp0s[i]=g_mp0[g_sh1[i]+off]; g_mp2s[i]=g_mp2[g_sh1[i]+off];
g_k0s2[i]=g_mp0[g_sh2[i]+off]; g_k2s4[i]=g_mp2[g_sh4[i]+off]; }
}
#define BM(a) _mm256_load_si256((const __m256i*)(a))
// v95: identical networks, but VPBLENDD (1 uop, lat 1) replaces VPBLENDVB
// (2 uops, lat 2) in the three stages whose constant selection mask is
// dword- or WORD-granular, and VPBLENDW likewise in three more. The mask has
// PERIOD 8 over the 32-byte register, so e.g. S=0x0F selects lane dwords 0 AND
// 2 -- the lane mapping was derived by direct measurement (work/e1001g/u3.cpp),
// not from the intrinsic's name.
#define BSTW(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blend_epi16(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),IMM); }
#define BSTD(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blend_epi32(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),IMM); }
static inline __m256i bsort8(__m256i v){
#define BST(M,S) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blendv_epi8(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),BM(S)); }
BST(g_sh1,g_selb[0]) BSTW(g_sh2,0x99) BST(g_sh1,g_selb[2])
BSTD(g_sh4,0x55) BSTW(g_sh2,0x55) BST(g_sh1,g_selb[5])
#undef BST
return v;
}
// ---- lane p1001_dead: TABLE-HOISTED networks ---------------------------------
// The five shuffle/select tables are LOOP-INVARIANT: bsort8/bsort8x3/bmerge8b use
// the fixed indices g_sh1, g_sh2, g_sh4, g_selb[0], g_selb[2], g_selb[5] and
// g_shrev. The shipped forms re-load each of them from memory on EVERY call
// (GCC cannot hoist a load from a non-const static that stores in the loop might
// alias). These forms take the values as ARGUMENTS, so the caller can load them
// ONCE per b2 and keep them in registers across the whole b1 loop.
#define BH_SEL(S) __m256i S
static inline __m256i bsort8h(__m256i v,__m256i S1,__m256i S2,__m256i S4,
__m256i K0,__m256i K2,__m256i K5,__m256i K0S2,__m256i K2S4){
#define BSW(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
#define BSD(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi32(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
{ __m256i t0=_mm256_shuffle_epi8(v,S1); __m256i m0=_mm256_min_epu16(v,t0);
__m256i t2=_mm256_shuffle_epi8(m0,K0S2); v=_mm256_shuffle_epi8(m0,K0);
v=_mm256_blend_epi16(_mm256_min_epu8(v,t2),_mm256_max_epu8(v,t2),0x66); }
{ __m256i t3=_mm256_shuffle_epi8(v,S1); __m256i m3=_mm256_min_epu16(v,t3);
__m256i t4=_mm256_shuffle_epi8(m3,K2S4); v=_mm256_shuffle_epi8(m3,K2);
v=_mm256_blend_epi32(_mm256_min_epu8(v,t4),_mm256_max_epu8(v,t4),0xAA); }
BSW(S2,0xAA)
{ __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_max_epu16(v,t); }
#undef BSH
#undef BSW
#undef BSD
return v;
}
static inline __m256i bsort8x3hR(__m256i v,__m256i S1,__m256i S2,__m256i K0,__m256i K5r){
#define BSY(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
{ __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_shuffle_epi8(_mm256_min_epu16(v,t),K0); }
BSY(S2,0x66)
{ __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_shuffle_epi8(_mm256_min_epu16(v,t),K5r); }
#undef BSY
return v;
}
static inline __m256i bsort8x3h(__m256i v,__m256i S1,__m256i S2,__m256i K0,__m256i K2){
#define BSY(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
{ __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_shuffle_epi8(_mm256_min_epu16(v,t),K0); }
BSY(S2,0x66)
{ __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_shuffle_epi8(_mm256_min_epu16(v,t),K2); }
#undef BSY
#undef BSZ
return v;
}
static inline __m256i bmerge8bhMX(__m256i v,__m256i S1,__m256i S2,__m256i S4,__m256i K5){
/* MX12 form: positions 0..3 of every 8-byte group are 0xFF, so the merge's d=4 stage
reduces to a dword swap (min(FF,x)=x to the low dword, max(FF,x)=FF to the high one). */
#define BMX(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi32(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
#define BMY(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
v=_mm256_shuffle_epi8(v,S4);
BMY(S2,0xAA)
{ __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_max_epu16(v,t); }
#undef BMX
#undef BMY
return v;
}
static inline __m256i bmerge8bh(__m256i v,__m256i S1,__m256i S2,__m256i S4,__m256i K5){
#define BMD(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi32(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
#define BMW(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
BMD(S4,0xAA)
BMW(S2,0xAA)
{ __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_max_epu16(v,t); }
#undef BMH
#undef BMD
#undef BMW
return v;
}
// v99: bsort8 truncated to its first 3 stages -- fully sorts bytes 0..3 of each
// 8-byte group and leaves bytes 4..7 untouched. Bit-identical to the full
// bsort8 in those positions whenever bytes 4..7 are 0xFF (verified over 4.8e6
// random cases, work/e1001g/u5.cpp). The merge's B-half holds bytes 8..16 of a
// bucket, so this is valid exactly when c <= 12.
static inline __m256i bsort8x3(__m256i v){
#define BSTY(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blend_epi16(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),IMM); }
#define BSTZ(M,S) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blendv_epi8(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),BM(S)); }
BSTZ(g_sh1,g_selb[0]) BSTY(g_sh2,0x99) BSTZ(g_sh1,g_selb[2])
#undef BSTY
#undef BSTZ
return v;
}
// sorts each of 4 buckets' first 8 bytes; bytes[c..8) must be 0xFF (U is pre-filled)
static inline void emit4b(const u8*g0,const u8*g1,const u8*g2,const u8*g3,__m256i O[4]){
__m128i a=_mm_loadl_epi64((const __m128i*)g0);
__m128i b=_mm_loadl_epi64((const __m128i*)g1);
__m128i c=_mm_loadl_epi64((const __m128i*)g2);
__m128i d=_mm_loadl_epi64((const __m128i*)g3);
__m256i v=_mm256_set_m128i(_mm_unpacklo_epi64(c,d),_mm_unpacklo_epi64(a,b));
v=bsort8(v);
__m128i lo=_mm256_castsi256_si128(v), hi=_mm256_extracti128_si256(v,1);
O[0]=_mm256_cvtepu8_epi32(lo);
O[1]=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
O[2]=_mm256_cvtepu8_epi32(hi);
O[3]=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
}
static inline __m256i bmerge8b(__m256i v){
#define BMG(M,S) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blendv_epi8(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),BM(S)); }
BSTD(g_sh4,0x55) BSTW(g_sh2,0x55) BMG(g_sh1,g_selb[5])
#undef BMG
return v;
}
// packed8 that also returns the packed sorted first-8 (A) and the raw bytes 8..16 (B)
static inline void emit4b2(const u8*g0,const u8*g1,const u8*g2,const u8*g3,__m256i*A,__m256i*B,__m256i O[4]){
__m128i x0=_mm_loadu_si128((const __m128i*)g0);
__m128i x1=_mm_loadu_si128((const __m128i*)g1);
__m128i x2=_mm_loadu_si128((const __m128i*)g2);
__m128i x3=_mm_loadu_si128((const __m128i*)g3);
__m256i a=_mm256_set_m128i(_mm_unpacklo_epi64(x2,x3),_mm_unpacklo_epi64(x0,x1));
*B=_mm256_set_m128i(_mm_unpackhi_epi64(x2,x3),_mm_unpackhi_epi64(x0,x1));
a=bsort8(a); *A=a;
__m128i lo=_mm256_castsi256_si128(a), hi=_mm256_extracti128_si256(a,1);
O[0]=_mm256_cvtepu8_epi32(lo);
O[1]=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
O[2]=_mm256_cvtepu8_epi32(hi);
O[3]=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
}
// ---- xc3 v20 (L3): the byte0 scatter cursor and the byte1 emit cursor hold values
// in [0,m2]; xc3_h0u is used only when m2 < 65536 (else the original u32 code runs), so
// both tables can be u16. Bit-identical: same values, same order. Halves the L1
// footprint of the two hottest RMW cursors and narrows their stores to 2 bytes.
static inline void xc3_z256u16(u16 *p){ const __m256i z=_mm256_setzero_si256();
for(u32 k=0;k<256u;k+=16) _mm256_storeu_si256((__m256i*)(p+k),z); }
static inline void xc3_pfx256u16(u16 *p){ __m256i c=_mm256_setzero_si256();
for(u32 k=0;k<256u;k+=16){
__m256i v=_mm256_loadu_si256((const __m256i*)(p+k));
__m256i in=_mm256_add_epi16(v,_mm256_slli_si256(v,2));
in=_mm256_add_epi16(in,_mm256_slli_si256(in,4));
in=_mm256_add_epi16(in,_mm256_slli_si256(in,8));
in=_mm256_add_epi16(in,_mm256_blend_epi32(_mm256_setzero_si256(),
_mm256_set1_epi16((short)(u16)_mm_extract_epi16(_mm256_castsi256_si128(in),7)),0xF0));
_mm256_storeu_si256((__m256i*)(p+k),_mm256_add_epi16(_mm256_sub_epi16(in,v),c));
c=_mm256_add_epi16(c,_mm256_set1_epi16((short)(u16)_mm256_extract_epi16(in,15))); } }
static u16 xc3_h0u[256];
// ---- xc3 v21 (L3): the byte1 histogram (cnt3) is the last u32 table on the robust
// path although its values are <= m2; xc3_cnt3u is used only when m2 < 65536, and if the
// SIMD path is selected instead, cnt3 is materialised in u32 from it before that path
// runs. The u32 code stays as the else branch. Bit-identical.
static inline void xc3_pfx256u16_to(const u16 * __restrict src,u16 * __restrict dst){
__m256i c=_mm256_setzero_si256();
for(u32 k=0;k<256u;k+=16){
__m256i v=_mm256_loadu_si256((const __m256i*)(src+k));
__m256i in=_mm256_add_epi16(v,_mm256_slli_si256(v,2));
in=_mm256_add_epi16(in,_mm256_slli_si256(in,4));
in=_mm256_add_epi16(in,_mm256_slli_si256(in,8));
in=_mm256_add_epi16(in,_mm256_blend_epi32(_mm256_setzero_si256(),
_mm256_set1_epi16((short)(u16)_mm_extract_epi16(_mm256_castsi256_si128(in),7)),0xF0));
_mm256_storeu_si256((__m256i*)(dst+k),_mm256_add_epi16(_mm256_sub_epi16(in,v),c));
c=_mm256_add_epi16(c,_mm256_set1_epi16((short)(u16)_mm256_extract_epi16(in,15))); } }
static u16 xc3_cnt3u[256];
static inline u32 xc3_max256u16(const u16 *p){ __m256i m=_mm256_setzero_si256();
for(u32 k=0;k<256u;k+=16) m=_mm256_max_epu16(m,_mm256_loadu_si256((const __m256i*)(p+k)));
m=_mm256_max_epu16(_mm256_permute2x128_si256(m,m,1),m);
m=_mm256_max_epu16(_mm256_shuffle_epi32(m,_MM_SHUFFLE(1,0,3,2)),m);
m=_mm256_max_epu16(_mm256_shuffle_epi32(m,_MM_SHUFFLE(2,3,0,1)),m);
return (u32)(u16)_mm_extract_epi16(_mm256_castsi256_si128(m),0); }
static __attribute__((noinline)) u32 *emit_b1range(u32 b1,const u16 *p,const u32 *cnt3,u32 hi24,u32 *o){
for(u32 b=b1;b<b1+4;b++){ u32 c=cnt3[b]; if(!c) continue;
emit(g_U+(b*RS3MAX),c,hi24|(b<<8),o); o+=c; }
return o;
}
static inline void flush_partial(u32 *out,u32 pos,u32 partial[16],u32 &used){
if(!used) return;
u32 *dest=out+pos-used;
for(u32 j=0;j<used;j++) dest[j]=partial[j];
used=0;
}
static inline void emit_coalesced(u32 *out,u32 pos,const u32 *src,u32 n,
u32 partial[16],u32 &used){
u32 *dest=out+pos;
u32 i=0;
if(used){
u32 take=16u-used;
if(take>n) take=n;
for(u32 j=0;j<take;j++) partial[used+j]=src[j];
used+=take;i=take;
if(used==16u){
u32 *line=dest+i-16u;
__m256i lo=_mm256_load_si256((const __m256i*)partial);
__m256i hi=_mm256_load_si256((const __m256i*)(partial+8));
_mm256_stream_si256((__m256i*)line,lo);
_mm256_stream_si256((__m256i*)(line+8),hi);
used=0;
}
if(i==n) return;
}
while(i<n && ((uintptr_t)(dest+i)&63u)) {dest[i]=src[i];i++;}
for(;i+16u<=n;i+=16u){
__m256i lo=_mm256_load_si256((const __m256i*)(src+i));
__m256i hi=_mm256_load_si256((const __m256i*)(src+i+8));
_mm256_stream_si256((__m256i*)(dest+i),lo);
_mm256_stream_si256((__m256i*)(dest+i+8),hi);
}
used=n-i;
for(u32 j=0;j<used;j++) partial[j]=src[i+j];
}
// src: 24-bit records packed 3 bytes; m elements
static void sort_region(const u8 *src,u32 m,u32 *out,u32 d3){
if(m<=64){
const u32 hi=(u32)d3<<24;
for(u32 i=0;i<m;i++){
u32 v=hi|((*(const u32*)(src+REC3*i))&0xFFFFFFu); u32 j=i;
while(j&&out[j-1]>v){ out[j]=out[j-1]; j--; }
out[j]=v;
}
return;
}
u32 RS2=(m>>8)+SLK2;
{ u32 k=(RS2+31u)>>5; if(!(k&1u)) k++; RS2=k<<5; } // odd # of 64B lines -> no L1 set aliasing
if(256u*RS2+m>TSZ || m>SCZ){ // pathological size: no scratch fits
const u32 hi=(u32)d3<<24;
for(u32 i=0;i<m;i++) out[i]=hi|((*(const u32*)(src+REC3*i))&0xFFFFFFu);
std::sort(out,out+m); return;
}
u16 * __restrict T=g_T;
u32 st2[256];
for(u32 b=0;b<256;b++) st2[b]=b*RS2;
{
const u8 * __restrict sp=src;
#pragma GCC unroll 8
for(u32 i=0;i<m;i++){
u32 lo=*(const u16*)sp; u32 b2=sp[2]; sp+=REC3;
if(__builtin_expect((i&15u)==0u,0)) __builtin_prefetch((const void*)(sp+512),0,0);
T[st2[b2]++]=lo;
}
}
// ---- ROBUST L2: if any byte2 sub-bucket overflows its fixed region, redo the
// scatter as a compact counting sort instead of falling back to std::sort.
// This fires on the judge's 1001c data (one region), where the old path cost ~35 ms.
u32 cb2[256]; u32 bs2[256];
{ int ovf=0;
for(u32 b=0;b<256;b++){ u32 c=st2[b]-b*RS2; cb2[b]=c; if(c>RS2) ovf=1; }
if(!ovf){ for(u32 b=0;b<256;b++) bs2[b]=b*RS2; }
else{
u32 cs[256];
for(u32 b=0;b<256;b++) cs[b]=0;
{ const u8 * __restrict sp=src;
for(u32 i=0;i<m;i++){ cs[sp[2]]++; sp+=REC3; } }
u32 s=0;
for(u32 b=0;b<256;b++){ u32 c=cs[b]; cb2[b]=c; bs2[b]=s; cs[b]=s; s+=c; }
{ const u8 * __restrict sp=src;
for(u32 i=0;i<m;i++){ u32 lo=*(const u16*)sp; u32 b2=sp[2]; sp+=REC3; T[cs[b2]++]=lo; } }
}
}
u32 pos=0;
alignas(64) u32 partial[16]; u32 partial_used=0;
alignas(32) u32 st3[256];
{ for(u32 b=0;b<256;b++) st3[b]=b<<5; }
for(u32 b2=0;b2<256;b2++){
u32 m2=cb2[b2];
if(!m2) continue;
const u16 *p=T+bs2[b2];
u32 hi24=(b2<<16)|(d3<<24);
if(m2<=8){
flush_partial(out,pos,partial,partial_used);
u32 buf[8];
for(u32 i=0;i<m2;i++){ u32 v=(u32)p[i]|hi24; u32 j=i;
while(j&&buf[j-1]>v){ buf[j]=buf[j-1]; j--; } buf[j]=v; }
for(u32 i=0;i<m2;i++) out[pos+i]=buf[i];
pos+=m2; continue;
}
// ---- e1001o: RS3 pinned to RS3MAX = 32 = 2^5 (see sol_v103_rs3.cpp header) --
const u32 RS3=RS3MAX;
const u32 RSH=5u; // log2(RS3); b*RS3 is a shift everywhere
u8 * __restrict U=g_U;
alignas(32) u32 cnt3[256];
u32 bad=0;
static u32 h0[256];
u16 *h0u=xc3_h0u; u32 use16=(m2<65536u);
// ---- change (this submission): build the byte1 histogram (cnt3) AND the byte0
// histogram (h0) in ONE cheap scalar pass BEFORE the U scatter. When `bad` fires the
// U scatter's only remaining job is to produce cnt3, so it is skipped outright
// (7 uop/element + an 8 KB table write); cnt3's values are identical, so the decision
// is unchanged. The robust branch then reuses h0 and loses a whole read pass over p[].
{ if(use16){
xc3_z256u16(xc3_cnt3u); xc3_z256u16(h0u);
#pragma GCC unroll 8
for(u32 i=0;i<m2;i++){ u32 r=p[i]; xc3_cnt3u[r>>8]++; h0u[r&255u]++;
} }
else{
for(u32 k=0;k<256u;k++) cnt3[k]=0;
for(u32 k=0;k<256u;k++) h0[k]=0;
#pragma GCC unroll 8
for(u32 i=0;i<m2;i++){ u32 r=p[i]; cnt3[r>>8]++; h0[r&255u]++; } }
u32 mx=0;
if(use16) mx=xc3_max256u16(xc3_cnt3u);
else for(u32 k=0;k<256u;k++) if(cnt3[k]>mx) mx=cnt3[k];
if(mx>RS3) bad=1;
if(use16 && !bad){ /* materialise cnt3 (u32) for the SIMD path below */
for(u32 k=0;k<256u;k+=16){ __m256i v=_mm256_loadu_si256((const __m256i*)(xc3_cnt3u+k));
_mm256_store_si256((__m256i*)(cnt3+k), _mm256_cvtepu16_epi32(_mm256_castsi256_si128(v)));
_mm256_store_si256((__m256i*)(cnt3+k+8), _mm256_cvtepu16_epi32(_mm256_extracti128_si256(v,1))); } } }
if(!bad){
{ __m256i mx=_mm256_set1_epi8(-1);
for(u32 bb=0;bb<256u;bb++) _mm_store_si128((__m128i*)(U+(bb<<RSH)),_mm256_castsi256_si128(mx)); }
#pragma GCC unroll 8
for(u32 i=0;i<m2;i++){ u32 r=p[i]; u32 b1=r>>8; u32 c=st3[b1]; U[c&(RS3MAX*256u-1u)]=(u8)r; st3[b1]=c+1u; }
{ __m256i r=_mm256_setr_epi32(0,1,2,3,4,5,6,7),stp=_mm256_set1_epi32(8),sh=_mm256_set1_epi32((int)RSH);
__m256i mx=_mm256_setzero_si256();
for(u32 b=0;b<256;b+=8){ __m256i bv=_mm256_sllv_epi32(r,sh); __m256i v=_mm256_load_si256((const __m256i*)(st3+b));
v=_mm256_sub_epi32(v,bv);
_mm256_store_si256((__m256i*)(cnt3+b),v);
_mm256_store_si256((__m256i*)(st3+b),bv); /* RESET: the next b2 starts at b<<5 */
mx=_mm256_max_epu32(mx,v); r=_mm256_add_epi32(r,stp); }
__m256i mr=_mm256_max_epu32(_mm256_permute2x128_si256(mx,mx,1),mx);
mr=_mm256_max_epu32(_mm256_shuffle_epi32(mr,_MM_SHUFFLE(1,0,3,2)),mr);
mr=_mm256_max_epu32(_mm256_shuffle_epi32(mr,_MM_SHUFFLE(2,3,0,1)),mr);
if((u32)_mm256_extract_epi32(mr,0)>RS3) bad=1; }
}
if(bad){
// ---- ROBUST L3: byte0 counting pass + scatter into a scratch, then a
// single emit pass bucketed by BYTE1 -- and cnt3 IS ALREADY the byte1
// histogram of p[], so that pass is not repeated. All tables are 256
// entries (L1) and the byte1 bucket sizes come from a 4-bank histogram, so
// no step has a serial RMW chain. (Two earlier forms were board-priced:
// an O(m2^2) insertion sort -> 27.4 s, and a 65536-entry single counting
// sort -> 2.203 s. This is the third.)
u32 *o=out+pos;
u16 *sc=g_sc;
if(use16){ /* xc3 v20: same tables, u16 (values <= m2 < 65536) */
u16 off1[256], *h16=h0u;
xc3_pfx256u16_to(xc3_cnt3u,off1);
xc3_pfx256u16(h16);
for(u32 i=0;i<m2;i++){ u32 v=p[i]; sc[h16[v&255u]++] = (u16)v; }
u32 pad=((u32)((uintptr_t)o>>2))&15u;
u32 *sc2=g_sc2+pad;
{ u32 HI=hi24; __asm__("" : "+r"(HI)); /* [HIREG] 把循环不变的 hi24 钉在寄存器里 */
for(u32 i=0;i<m2;i++){ u32 v=sc[i]; sc2[off1[v>>8]++] = HI|v; } }
emit_coalesced(out,pos,sc2,m2,partial,partial_used);
pos+=m2; continue; }
flush_partial(out,pos,partial,partial_used);
u32 *h = h0; /* byte0 histogram already built by the pass above */
u32 off1[256];
{ u32 s=0;
for(u32 k=0;k<256u;k++){ off1[k]=s; s+=cnt3[k]; } }
{ u32 s=0; for(u32 k=0;k<256u;k++){ u32 c=h[k]; h[k]=s; s+=c; } }
for(u32 i=0;i<m2;i++){ u32 v=p[i]; sc[h[v&255u]++] = (u16)v; }
{ u32 HI=hi24; __asm__("" : "+r"(HI));
for(u32 i=0;i<m2;i++){ u32 v=sc[i]; o[off1[v>>8]++] = HI | v; } }
pos+=m2; continue;
}
flush_partial(out,pos,partial,partial_used);
if(d3!=255u){
u32 *o=out+pos;
const __m256i HIV=_mm256_set1_epi32((int)hi24);
// ---- lane p1001_dead: HOIST THE SEVEN LOOP-INVARIANT TABLES OUT OF THE
// b1 LOOP. bsort8/bsort8x3/bmerge8b reference g_sh1, g_sh2, g_sh4,
// g_selb[0], g_selb[2], g_selb[5] and g_shrev at FIXED indices, so every
// one of those loads is loop-invariant -- but they are non-const statics,
// so GCC must re-issue them on every iteration. Loading them once here
// is bit-identical (same values, same instruction sequence otherwise).
const __m256i SH1=BM(g_sh1),SH2=BM(g_sh2),SH4=BM(g_sh4);
const __m256i K0S2=BM(g_k0s2),K2S4=BM(g_k2s4);
const __m256i K0=BM(g_mp0),K2=BM(g_mp2),K5=BM(g_mp2r);
__m256i Pn=_mm256_set_m128i(_mm_loadu_si128((const __m128i*)(U+(2*RS3))),_mm_loadu_si128((const __m128i*)(U)));
__m256i Qn=_mm256_set_m128i(_mm_loadu_si128((const __m128i*)(U+(3*RS3))),_mm_loadu_si128((const __m128i*)(U+RS3)));
for(u32 b1=0;b1<256;b1+=4){
u32 c0=cnt3[b1],c1=cnt3[b1+1],c2=cnt3[b1+2],c3=cnt3[b1+3];
u32 mx=c0; if(c1>mx)mx=c1; if(c2>mx)mx=c2; if(c3>mx)mx=c3;
// ---- lane p1001_ports: THE A HALF IS COMMON TO BOTH PATHS, SO SORT IT
// BEFORE THE BRANCH. The 8 low bytes of each of the 4 buckets form `AP`,
// and `bsort8(AP)` is EXACTLY what the old emit4b (packed path) and the old
// emit4b2 (merge arm) each computed SEPARATELY, once per taken branch. The
// packed path therefore pays NOTHING (same loads, same unpack, same network)
// while the arm stops paying a second A assembly + a second 6-stage network
// inside an unpredictable (15.3 % taken) branch, where its ~18 cycles of
// latency are largely EXPOSED rather than overlapped.
__m256i P=Pn,Q=Qn;
{ const u8 *nb=U+((b1+4)*RS3);
Pn=_mm256_set_m128i(_mm_loadu_si128((const __m128i*)(nb+(2*RS3))),_mm_loadu_si128((const __m128i*)(nb)));
Qn=_mm256_set_m128i(_mm_loadu_si128((const __m128i*)(nb+(3*RS3))),_mm_loadu_si128((const __m128i*)(nb+RS3))); }
__m256i AP=_mm256_unpacklo_epi64(P,Q);
__m256i A=bsort8h(AP,SH1,SH2,SH4,K0,K2,K5,K0S2,K2S4);
if(__builtin_expect(mx<=8u,1)){
__m128i lo=_mm256_castsi256_si128(A), hi=_mm256_extracti128_si256(A,1);
__m256i O0=_mm256_cvtepu8_epi32(lo), O1=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
__m256i O2=_mm256_cvtepu8_epi32(hi), O3=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
st256(o,_mm256_or_si256(_mm256_or_si256(O0,BM(g_pb1+8*b1)), HIV)); o+=c0;
st256(o,_mm256_or_si256(_mm256_or_si256(O1,BM(g_pb1+8*(b1+1))), HIV)); o+=c1;
st256(o,_mm256_or_si256(_mm256_or_si256(O2,BM(g_pb1+8*(b1+2))), HIV)); o+=c2;
st256(o,_mm256_or_si256(_mm256_or_si256(O3,BM(g_pb1+8*(b1+3))), HIV)); o+=c3;
continue;
}
// lane p1001_dead: TWO REMOVALS FROM THE ARM'S CRITICAL CHAIN.
// (1) The B half is NOT used by the >16 fallback (that path re-reads U), so
// its 3-instruction assembly (2 vpunpckhqdq + vinserti128) is moved
// BELOW the test instead of being computed on 100 % of arm entries.
// (2) `(c0|c1|c2|c3)>16u` is a CONSERVATIVE over-approximation of "some
// bucket exceeds 16" -- it fires for (16,1,1,1) too. `mx` (already
// computed 7 instructions earlier, for the mx<=8 test) is the EXACT
// test and costs nothing: it deletes `movl+3x orl` from every arm
// entry. The scalar path stays correct for every c, and a bucket with
// c>16 always sets mx>16, so the routing can only get tighter.
if(__builtin_expect(mx>16u,0)){
o=emit_b1range(b1,p,cnt3,hi24,o);
continue;
}
__m256i B=_mm256_unpackhi_epi64(P,Q);
// 9..16 elements in at least one bucket: one packed bitonic merge of (sorted first 8)
// with (sorted bytes 8..16); stores stay in bucket order so each 32B tail is
// overwritten by the next bucket's store (c>=9 for the buckets that get a tail).
// mx<=12 <=> all four buckets have c<=12 <=> every B half holds <=4 real
// values in its low 4 positions plus 0xFF padding, so 3 of bsort8's 6
// stages are provably dead. P(mx<=12 | mx>8) = 0.909.
__m256i MN,MX;
if(__builtin_expect(mx<=12u,1)){
__m256i BR=bsort8x3hR(B,SH1,SH2,K0,K5);
MN=bmerge8bh(_mm256_min_epu8(A,BR),SH1,SH2,SH4,K5);
MX=bmerge8bhMX(_mm256_max_epu8(A,BR),SH1,SH2,SH4,K5);
} else {
__m256i BR=_mm256_shuffle_epi8(bsort8h(B,SH1,SH2,SH4,K0,K2,K5,K0S2,K2S4),BM(g_shrev));
MN=bmerge8bh(_mm256_min_epu8(A,BR),SH1,SH2,SH4,K5);
MX=bmerge8bh(_mm256_max_epu8(A,BR),SH1,SH2,SH4,K5);
}
__m128i lo,hi;
lo=_mm256_castsi256_si128(MN); hi=_mm256_extracti128_si256(MN,1);
__m256i M0=_mm256_cvtepu8_epi32(lo), M1=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
__m256i M2=_mm256_cvtepu8_epi32(hi), M3=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
lo=_mm256_castsi256_si128(MX); hi=_mm256_extracti128_si256(MX,1);
__m256i X0=_mm256_cvtepu8_epi32(lo), X1=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
__m256i X2=_mm256_cvtepu8_epi32(hi), X3=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
u32 *p=o;
// branchless: MV==OO and XV==0xFF|HIV when CC<=8 (B is all-0xFF there, so
// min(A,BR)=A, bmerge8b(A)=A; max(A,BR)=bmerge8b(0xFF)=0xFF). The extra p+8
// store is garbage for CC<=8 but the NEXT bucket's store starts at p+CC and
// covers [p+CC, p+CC+64) â [p+CC, p+64) for CC<8, so it is always
// overwritten -- the same store-overlap chain the CC<=8 path already relies on.
// lane p1001_dead: `BM(PB)` was evaluated TWICE per invocation (once per store),
// so each of the four prefix vectors g_pb1[b1..b1+3] was loaded from memory twice
// per arm group -- 8 loads where 4 suffice -- and the whole `or(PB,HIV)` product
// was rebuilt for the second store. Named operands (an unused macro parameter is
// EXACTLY how a duplicate like this hides: OO looked like the dead one) turn it
// into one load + three ORs per bucket instead of two loads + four.
#define STK(CC,MV,XV,OO,PB) { __m256i PV=_mm256_or_si256(BM(PB),HIV); \
st256(p,_mm256_or_si256(MV,PV)); \
st256(p+8,_mm256_or_si256(XV,PV)); p+=CC; }
STK(c0,M0,X0,O[0],g_pb1+8*b1)
STK(c1,M1,X1,O[1],g_pb1+8*(b1+1))
STK(c2,M2,X2,O[2],g_pb1+8*(b1+2))
STK(c3,M3,X3,O[3],g_pb1+8*(b1+3))
#undef STK
o=p;
}
pos=(u32)(o-out);
} else {
for(u32 b1=0;b1<256;b1++){
u32 c=cnt3[b1];
if(!c) continue;
const u8 *g=U+(b1*RS3);
u32 prefix=hi24|(b1<<8);
u32 *o=out+pos;
u32 w=(c<=8)?8u:16u;
if(pos+w<=m) emit(g,c,prefix,o);
else emit_scalar(g,c,prefix,o);
pos+=c;
}
}
}
flush_partial(out,pos,partial,partial_used);
}
__attribute__((noinline)) void pospad(void) {
__asm__ __volatile__(".fill 155,1,0x90 ; ret");
}
__attribute__((noinline)) void pospadB(void) {
__asm__ __volatile__(".fill 139,1,0x90 ; ret");
}
void sort(unsigned *a,int n){
static int initt=0;
if(!initt){ initt=1; init_pb1(); init_bmasks(); }
static int init=0;
if(g_noavx_dbg>=0) g_noavx=g_noavx_dbg; else if(!init){ init=1; g_noavx = __builtin_cpu_supports("avx2")?0:1; }
{
// ---- v102 (e1001n cursor x e1001m unroll) ---------------------------------
// (a) e1001n: the L1 cursor is a 4-BYTE BYTE-OFFSET (u32 off[256], 1 KB)
// instead of 8-byte pointers (cur[256] + ecur[256], 4 KB); the block base
// is COMPUTED from d and the bound test is against the CONSTANT BLK-3, so
// the ecur[] array and its load do not exist. Harness ct_cur2.cpp #26:
// 3.9820 vs controls 4.1660/4.1621 = -0.184 cyc/el, 3x reproduced.
// BOARD-ALONE: 390.873 (sid 91469) vs controls 395.123 / 395.121.
// (b) e1001m: the same loop hand-unrolled 8x (their -0.25 ms on this base).
// --------------------------------------------------------------------------
u16 off[256]; u32 base[256], ob[256]; // xc4_e7: 游标改 u16（值域 49152 < 65536 ⇒ 逐位不变），数组 1KB->512B
for(u32 b=0;b<256;b++){ u32 bs=REC3*(b*STR1M+64u*((b*1237u)&7u)); base[b]=bs; ob[b]=bs; off[b]=b*(u32)g_blkst; }
const u32 * __restrict aa=a; u8 * __restrict S=g_S8; u8 * __restrict SG=g_stg; u8 * __restrict SGm3=g_stg-3;
// lane p1001_dead: THE BOUND TEST USES THE **NEW** CURSOR, SO NO VALUE NEEDS TO
// SURVIVE THE BRANCH. The shipped body loads o, stores the payload, and then
// needs the SAME o again for the bound test and the flush -- but o is already
// advanced, so GCC-9 keeps TWO extra register copies per element
// (`movl %r11d,%ebx` and `movq %r11,%rcx`: 2 of the loop's 11 instructions, and
// they exist ONLY to survive the branch). Since 3 and 64 are coprime and the
// block stride is a multiple of 64, (o_old&63)==61 is EXACTLY (o_old+3&63)==0,
// so the test can run on the post-increment value: 9 instructions/element
// (movzbl,movl,movl,leal,movl store,movq,testb,je,movl store) against 11.
#define L2BODY(K,B3) { u32 _v=aa[i+K]; u32 _d; unsigned long long _n; const u32* _p=aa+i; __asm__ ( "movzbl " #B3 "(%[P]), %k[D]\n\t" "movzwl (%[O],%q[D],2), %k[N]\n\t" "leal 3(%k[N]), %k[N]\n\t" "movw %w[N], (%[O],%q[D],2)" : [D]"=&r"(_d),[N]"=&r"(_n) : [P]"r"(_p),[O]"r"(off) : "memory" ); if(__builtin_expect((_n&63u)==0u,0)){ off[_d]=(u16)(_n-BLK); *(u16*)(SG+_n-3)=(u16)_v; SG[_n-1]=(u8)(_v>>16); u32 f=ob[_d]; ob[_d]=f+BLK; u8*_fq=SG+(_n-BLK); u8*_fr=S+f; for(u32 _fk=0;_fk<BLK;_fk+=32) _mm256_stream_si256((__m256i*)(_fr+_fk),_mm256_load_si256((const __m256i*)(_fq+_fk))); } else *(u32*)(SG+_n-3)=_v; }
{ int i=0;
for(;i+8<=n;i+=8){
// lane p1001_lock PROBE P2b: the WRITE touch of `a`'s page p+1, issued at the
// FIRST iteration of page p and placed BEFORE that iteration's loads. Element
// i+1024 is the first element of the NEXT page and is read by no statement until
// iteration i+1024 -- a full page (128 iterations, ~11 000 instructions) later,
// i.e. ~50x the ROB -- so the write-touch ALWAYS retires (and its fault is
// handled, mapping the page writable+dirty) LONG before that page is read.
// P2a put the touch one iteration ahead of the read and LOST THE RACE (measured:
// the process's own minor-fault counter doubles, 268 561 vs 170 905 -- see
// FINDINGS.txt sec. 3), because the scheduler hoists the next iteration's loads
// above it. A write touch that is not the page's FIRST access is worse than none.
if(__builtin_expect((i&1023u)==0u && i+8208<(int)n,0))
__asm__ volatile("orl $0, %0" : "+m"(((u32*)aa)[i+8208]));
L2BODY(0,3) L2BODY(1,7) L2BODY(2,11) L2BODY(3,15) L2BODY(4,19) L2BODY(5,23) L2BODY(6,27) L2BODY(7,31) }
for(;i<n;i++){ L2BODY(0,3) }
}
#undef L2BODY
_mm_sfence();
#ifdef L0ONLY
{ volatile u32 z = off[0]+ob[0]+base[0]+(u32)(size_t)SG[0]; sink64(z); return; }
#endif
int bad=0; u32 tot=0;
for(u32 b=0;b<256;b++){
u32 rem=off[b]%(u32)g_blkst; // off[] is absolute: off[b] = b*BLKST + slot(0..191)
u32 cnt=(ob[b]-base[b])/BLK*BLKREC+rem/REC3;
if(cnt>CAP1M) bad=1;
g_off[b]=tot; tot+=cnt;
}
g_off[256]=tot;
if(bad || tot!=(u32)n){
// ---- EXACT L1 FALLBACK: a counting-sort pass by byte3 instead of
// std::sort on the whole array (which cost ~15 s on any skewed pattern).
// No fixed-capacity assumption; correct for every distribution.
u32 c3[256];
for(u32 b=0;b<256;b++) c3[b]=0;
{ const u8 * __restrict q=(const u8*)a;
for(int i=0;i<n;i++) c3[q[4*(size_t)i+3]]++; }
u32 o3[257]; u32 s3=0;
for(u32 b=0;b<256;b++){ o3[b]=s3; s3+=c3[b]; }
o3[256]=s3;
u32 w3[256];
for(u32 b=0;b<256;b++) w3[b]=o3[b]*REC3;
for(int i=0;i<n;i++){
u32 v=a[i]; u32 d=v>>24; u32 pp=w3[d]; w3[d]=pp+REC3;
u8*q2=g_S8+pp; *(u16*)q2=(u16)v; q2[2]=(u8)(v>>16);
}
for(u32 b=0;b<256;b++){
u32 m=c3[b];
if(!m) continue;
sort_region(g_S8+o3[b]*REC3, m, a+o3[b], b);
}
_mm_sfence(); return;
}
for(u32 b=0;b<256;b++){
u32 m=g_off[b+1]-g_off[b];
if(!m) continue;
u32 rem=off[b]%(u32)g_blkst;
if(rem){ // flush the partial staging block
u8*q=SG+(off[b]-rem); u8*r=g_S8+ob[b];
for(u32 k=0;k<rem;k++) r[k]=q[k];
}
// re-anchor: region data now starts at base[b] and is contiguous? No -
// blocks were flushed at ob[] which is base[b]+BLK*k, and the partial tail
// sits right after the last full block, so base[b] is still the start.
sort_region(g_S8+base[b], m, a+g_off[b], b);
}
_mm_sfence();
volatile u8 l_pad[1920u]; l_pad[0]=1;
sink64(l_pad[0]);
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 633.332 ms | 899 MB + 268 KB | Accepted | Score: 100 | 显示更多 |