// lane p1001_layout ARM P96
// lane p1001_ovl ARM OVPIPE_C2 (C2_noinline + the pipelined head)
// 1001 -- sol_v133_bsortdepth (lane p1001_chain, 2026-09-26)
//
// ROW: 363.879 ms, sid 95819, rank 2. Previous row 364.012 ms (sid 95761,
// sol_v132_mx12.cpp). Gap 12.281 -> 12.148 ms.
//
// THE CHANGE SHORTENS bsort8h's DEPENDENCY CHAIN BY TWO LEVELS AT ZERO INSTRUCTION COST, AND
// IT EXISTED ONLY AFTER A REGISTER WAS FREED. Instruction count per sort FALLS: 4 074 833 229
// -> 4 073 183 353 (-1.65 M), all of it from the SHREV removal below.
//
// (1) FREEING A YMM -- SHREV. The b1 loop hoists seven mask constants; six are used many
// times per group, but SHREV is used exactly ONCE per wide group. It leaves the register
// budget because K5 = g_mp2r is ALREADY built as g_mp2[g_shrev[i]+off], i.e. exactly
// K2 o SHREV -- that is why the merge uses it -- so
// vpshufb(vpshufb(x,K2), SHREV) == vpshufb(x, K5)
// and the mx<=12 arm sorts AND reverses in one shuffle via bsort8x3hR. The rare mx>12 arm
// keeps the general bsort8h and takes SHREV as a fresh load inside the ternary, so it is
// never live across the loop.
//
// (2) THE DEPTH REDUCTION, DONE RIGHT. A d=1 stage leaves m0 = vpminuw(v, vpshufb(v,S1)) and
// the NEXT stage's partner is t2 = vpshufb(v1,S2) with v1 = vpshufb(m0,K0), so
// t2 == vpshufb(m0, K0 o S2)
// -- one level earlier for free. The SAME applies to stage 3 -> stage 4 with K2 o S4.
// Both composed masks are precomputed in init_bmasks().
// IT IS ONLY FREE IF STAGE 1 PUBLISHES m0: my first three attempts (DP1/DP2/DP5) let
// stage 1 overwrite v and then RECOMPUTED vpminuw, which is why they GAINED instructions
// (+8.7 M, +21.9 M, +7.0 M) instead of holding the count. DP9's count is BELOW the base's.
//
// BOARD EVIDENCE -- four samples, two chains, same window, MXS submitted as the control
// (/status Pending=0 before every submission):
// chain F: CTRL 364.157 | DP9 363.935 | CTRL 364.129 | CTRL 364.221 | CTRL 364.175
// chain G: CTRL 364.075 | DP9 363.894 | CTRL 364.207 | DP9 363.981 | CTRL 364.201 |
// DP9 363.879 | CTRL 364.162
// => 4/4 DP9 samples (363.879-363.981) BELOW ALL 4 controls (364.075-364.221).
// Same-window siblings: DP8 (stage 1/2 fusion only) 364.368 = +0.20 LOSS;
// SHR4 (SHREV removal only) 364.035 = -0.16, inside the 0.15 ms control span.
//
// CORRECTNESS: byte-exact vs std::sort with the fleet's xe.cpp at n=1e8 x patterns {0,1,6}
// x 3 seeds, plus n=2e7 over patterns {0,1,2,3,6,7}; AC on the board. THIS FILE IS PROVED BY
// OBJECT IDENTITY (objcopy --only-section=.text -O binary + cmp) TO THE BOARDED ARM
// work/p1001_chain/arms/DP9.cpp -- see work/p1001_chain/ship2.py.
//
// CREDIT: the base codegen and the d=1 select = lanes p1001_p5 / p1001_bi; the mx<=12 merge
// specialization this is stacked on = this lane (sol_v132_mx12); the composed-mask convention
// (g_mp0s / g_mp2s) was already in the row, unused.
// ============================================================================
// 1001 -- lane p1001_bi, artifact. THE ROW (sol_v129_pos22.cpp) WITH THE
// d=1 COMPARE-EXCHANGE STAGES' SELECT REWRITTEN AT A COARSER TRUE GRANULARITY,
// AND A 16-BYTE POSITION-PAD MOVE.
// ----------------------------------------------------------------------------
// BOARD: 364.787 ms, sid 95291 (sample 1 of 3), AC 100, mem_kb 685736.
// LADDER: 365.287 (the row it replaces) -> 364.787 = -0.500 ms. Gap to rank 1
// (pdoom 351.731) 13.556 -> 13.056 ms.
// THE CHANGE, AND WHY IT IS BIT-IDENTICAL (proved standalone BEFORE any build):
// A d=1 bitonic stage is t = vpshufb(v,S1); v = blend_epi16(min_uw(v,t),max_uw(v,t),IMM)
// -- 4 uops. But min_uw(v,t) and max_uw(v,t) are BYTE-SWAPS OF EACH OTHER (each word
// lands ascending or descending), so the SELECT is not a select at all: it is a
// PERMUTATION of the min result. Hence
// blend_epi16(min_uw(v,t),max_uw(v,t),IMM) == vpshufb(min_uw(v,t), MP(IMM))
// -- 3 uops, where MP(IMM) swaps the two bytes of every word whose IMM bit is set.
// This is the p5 lane's own axis (a select whose true granularity is coarser than the
// instruction's) carried one step further: there the byte-granular VPBLENDVB became a
// WORD-granular VPBLENDW; here the WORD-granular VPBLENDW becomes a SHUFFLE, because the
// two operands it chooses between are permutations of one another.
// The IMM->word mapping was derived EMPIRICALLY (work/p1001_bi/immmap.cpp), never from
// the intrinsic's name; the identity was proved over 20 000 random vectors x {bsort8h,
// bsort8x3h+SHREV, the 0xFF-padded shape the arm actually feeds} before a single build.
// Sites rewritten: bsort8h stages 1 and 3, bsort8x3h stages 1 and 3 (4 sites; -4 static
// instructions in the emit loop, -2.9 dynamic uops/group).
// POSITION PAD: pospad()'s `.fill 12` -> `.fill 28`, which moves the hot loop's head from
// .text 2742 (mod 64 = 54) to .text 2758 (mod 64 = 6). THIS IS NOT A FREE TUNING KNOB:
// the new codegen's four reachable cells are {6: 364.787, 22: 364.989, 38: 365.239,
// 54: 364.964} (all four submitted; the pad is quantised to 16 bytes by the .p2align
// before the next function). Residue 6 is the optimum OF THIS CODEGEN and the ordering
// is DIFFERENT from the old codegen's (22 < 6 < 38 < 54) -- a further refutation of any
// transferable residue rule.
// ATTRIBUTION, RESIDUE-MATCHED: at the ROW'S OWN residue (22) the new codegen reads
// 364.989 / 365.094 against same-window controls 365.249 / 365.261 / 365.232, i.e. the
// CODEGEN change alone is worth -0.20...-0.27 ms; the residue cell adds ~-0.20 ms more.
// A SHAPE FINDING ALONGSIDE IT: the same bits spelled as max_uw + the complementary,
// S1-composed pattern (BI3) is a BOARD LOSS at every sample (365.524 / 365.435 against
// the same controls) although it has the identical instruction count -- the p5 lane's
// "bank the number, do not explain it" applies here too.
// CORRECTNESS: xe.cpp byte-exact vs std::sort, n = 1e8 x patterns {0,1,6} (3 seeds each =
// 9/9 runs), plus the 16-byte pad which is a never-called dead function. THIS FILE WAS
// VERIFIED BY OBJECT IDENTITY (objcopy -O binary + cmp) AGAINST THE BOARDED ARM
// work/p1001_bi/BI2P28.cpp -- not by "the header is only comments".
// ============================================================================
// ============================================================================
// 1001 -- lane p1001_cg, artifact 2: THE ROW + ONE ADDED PRAGMA LINE, and then the
// POSITION PAD MOVED BY -32 BYTES so that the build lands on a different front-end
// residue. THE CODEGEN IS IDENTICAL TO sol_v125_nocrossjump.cpp:
// #pragma GCC optimize("-fno-crossjumping") (added under the row's pragma)
// `.fill 75` -> `.fill 44` in `pospadB()` (the never-called position pad)
// NOT ONE LINE OF ENGINE CODE IS TOUCHED.
// WHY THE PAD MOVED: `-fno-crossjumping` moves the hot loop's head from residue 40
// to residue 30 (mod 64) and the arm's reachable residues are {14,30,46,62}, DISJOINT
// from the row's {8,24,40,56}. Chain 10 priced the SAME flag at all four and the
// board separates them: residue 14 = -0.114, 30 = -0.20 (the row at 367.466, sid
// 94464), 46 = -0.265, 62 = -0.327 ms against same-window controls.
// BOARD (chain 10, sid 94561): 367.453 ms against controls 367.780 / 367.744 -- the
// lowest sample this problem has ever held. CHAIN 11 IS THE REPLICATION BRACKET --
// read work/p1001_cg/results11.txt before quoting this build.
// CORRECTNESS: byte-exact vs std::sort with the fleet's xe.cpp; the pad is a
// volatile dead local whose value is sinked, so the semantics are the row's.
// ============================================================================
// ============================================================================
// 1001 -- lane p1001_cg: THE ROW (sol_v124_st3reset.cpp md5 25780c4fa22f...) WITH
// EXACTLY ONE LINE ADDED, and it is not engine code:
// #pragma GCC optimize("-fno-crossjumping") (inserted under the row's pragma)
// NOT ONE BYTE OF sort() CHANGES -- the row is a codegen local optimum and this is
// the ONE arm of 407 that the board put below it.
// BOARD, interleaved same-window, all AC, mem_kb 685736 (every sample):
// chain 5 (sids 94449..94471, controls 367.685 / 367.691 / 367.703 / 367.731 / ...):
// N_crossjumping 367.466 vs the chain's control MINIMUM 367.685 = -0.219 ms,
// and -0.219 against its own immediately-preceding control 367.685; the chain's
// 7 controls span 0.096 ms, so the effect is 2.3x the chain's own spread.
// chain 8 = the REPLICATION BRACKET (4 samples + 5 controls) -- see
// work/p1001_cg/results8.txt; read it before quoting this number.
// FINGERPRINT: it is NOT a smaller build -- .text +275 B, sort() +33 instructions,
// largest backward region +157 -- i.e. AN ARM WITH MORE INSTRUCTIONS THAT IS
// FASTER, the t2 class, on the one axis the fleet's retracted count screen
// cannot rank. Frame total 8512 = the row's (frame-matched by construction).
// VERIFICATION: xe.cpp byte-exact vs std::sort, n = 8e6 patterns 0/1/2/3/6/7
// (ALL BYTE-EXACT); re-verify at n = 1e8 before shipping.
// ============================================================================
// p1001_fixed G1 -- the ROW with ONE TOKEN DELETED: the `lock ` prefix
// removed from pretouch_a's two `lock orl $0, %0` asm statements. `orl $0` reads the
// location, ORs 0, and writes the SAME value back: the pretouch's semantics (fault the
// page, make it present and dirty) are unchanged, and the machine is single-core, so
// atomicity buys nothing. NOT ONE OTHER BYTE OF THE ROW IS TOUCHED.
// p1001_2x2 LANE: p1001_2x2 -- late pad 1920 (declared after every hot loop)
// ============================================================================
// 1001 -- lane p1001_ports build 2 (HOIST). THE A HALF IS SORTED ONCE, NOT TWICE.
//
// BASE: problems/1001/sol_v104_union_rs3.cpp (the row, 382.908 ms sid 91626).
//
// CHANGE 1 (identical to sol_v105_ports_pre.cpp): delete the dead `u32 pre[256]`
// build (written 65536 times per run, never read: `pre[` occurs exactly once in
// the row source, at its declaration; the .s keeps the loop -- sort() 2811 instr
// with it vs 2765 without, -8 vpslld -8 vpor -8 vpaddd -8 vmovdqa).
// CHANGE 2 (NEW): `A = bsort8(packA)` is hoisted ABOVE the `mx<=8` branch.
// BOTH paths computed it separately before -- the packed path inside emit4b, the
// merge arm inside emit4b2 -- and emit4b2 ALSO rebuilt packA and ALSO filled an
// `__m256i O[4]` that the arm NEVER READS: the STK macro's 4th argument is an
// UNUSED parameter (`#define STK(CC,MV,XV,OO,PB)`, OO appears nowhere in its
// body), so the arm was paying 4 vpmovzxbd + 2 vpsrldq + 1 vextracti128 for
// nothing. .s census of the shipped row: the arm block carries 16 vpshufb +
// 16 vpmaxub + 16 vpminub -- i.e. the whole 6-stage A network ON TOP of
// bsort8x3(B) and the two bmerge8b.
// THE HOIST IS A SEMANTIC NO-OP: the packed path runs an IDENTICAL instruction
// sequence (same 4 loads, same 2 vpunpcklqdq + vinserti128, same bsort8, same
// 4 vpmovzxbd + 2 vpsrldq + 1 vextracti128), so only the arm can change -- it
// stops paying ~30 uops and ~18 cycles of latency that are EXPOSED, because the
// arm is entered through an unpredictable 15.3 %-taken branch and cannot be
// overlapped across it. The 16-byte loads stay inside g_U (the last bucket's
// load ends at U+256*RS3 exactly).
// VERIFICATION: byte-exact vs std::sort, same driver as every 1001 lane
// (work/e1001l/xe.cpp): full scale n=1e8 uniform (3 seeds) + n=8e6 over the
// degenerate patterns 0/1/2/3/6/7 that exercise the fallbacks.
// ============================================================================
// ============================================================================
// 1001 — ROW SOURCE, lane e1001o union, 2026-09-26.
//
// BOARD: 382.908 ms (sid 91626), AC 100, mem_kb 685736.
// Base: problems/1001/sol_v103_abscursor.cpp (sister lane, 387.059 sid 91560)
// Leader iMMIQ 368.66 ms — gap was 26.22 ms at lane start; now 14.25 ms.
//
// SAME-WINDOW CHAINS, CONTROLS BRACKETING BOTH ENDS, ALL AC, n = 1e8:
// 1) on sol_v101_u8.cpp: sid 91599 ctrl 394.835 | 91600 w8 390.822 |
// sid 91603 ctrl 394.942 = -4.06 ms (38x spread)
// 2) on sol_v103_abscursor.cpp (the sister lane's row):
// sid 91622 ctrl 386.999 | 91623 UNION 382.949 | 91624 ctrl 387.093
// = -4.09 ms (43x spread) -- the two lanes touch
// DISJOINT code and compose EXACTLY additively.
// 3) sid 91625 ctrl 382.934 | 91626 THIS FILE 382.908 | 91627 ctrl 382.947
// = -0.033 ms for the g_U alignment (small; included
// because it is instruction-identical and cannot hurt).
//
// THE CHANGES (all one idea: RS3 is a POWER OF TWO, so b*RS3 is a shift):
// 1. const u32 RS3 = RS3MAX = 32, replacing `(m2>>8)+SLK3` + clamp.
// (a) the per-(region,b2) cnt3 teardown -- 256 entries rebuilt 65536
// times, 53 instructions / 8 entries -- used 8 vpmulld per 8 entries
// (2 uops each, latency 10, p01 only) to UN-DERIVE a product that was
// materialised two hundred lines earlier to build st3[]. That pass is
// PURE INDEX RE-DERIVATION and it is the largest non-kernel item I
// could find that is actually removable.
// (b) with RS3 a compile-time constant GCC ALSO stops emitting per-bucket
// imul/lea address arithmetic for U + b1*RS3 in the emit: the
// packed-path emit loop falls 96 -> 87 instructions with NO edit to
// the emit code. This half was not predicted and is as large as (a).
// (c) the +(m2>>8) slack, the clamp and the retry logic disappear, and the
// insertion-sort overflow fallback becomes unreachable for realistic
// input (P(Poisson(5.96) > 32) ~ 1e-12).
// COST: memset(U,0xFF,256*RS3) grows 5888 -> 8192 bytes (ERMSB, ~+1.3 ms).
// 2. the emit's mx<=8 test hoisted ABOVE the 16-byte loads / B-half assembly,
// so the 54 % of groups on the packed path use emit4b (8-byte loads, no B):
// 87 -> 84 instructions and the two register-pressure vmovaps spills go.
// 3. alignas(32) on g_U: with RS3 == 32 every bucket starts at U + 32*b, so a
// 32-byte-aligned g_U makes every bucket load 32-byte aligned. (The
// fleet's earlier alignas(64) test on g_U was NULL -- but that was with the
// old RS3 = 23, where the bucket addresses were arbitrary anyway.)
//
// MEASURED NEGATIVES on this axis (each a correct, byte-exact build):
// sid 91601 RS3=16 + retry-at-32 fallback 395.462 = +0.5 ms on the v101 base
// (the 4 %-of-pairs rescatter costs more than the 30 % smaller
// memset saves)
// sid 91605 w8 minus the teardown's vpsllvd 391.124 = +0.29 vs w8 (the shift
// was NOT the cost; the p01 uop pressure was)
// u2 = this + emit4q (two 32-byte loads + four permutes for the group's A/B
// halves instead of four 16-byte loads + six unpacks/inserts):
// .s-verified INSTRUCTION-NEUTRAL (merge path 160 -> 160). Not
// submitted.
// vA = this minus `unroll-loops`: halves sort()'s static size (2802 -> 1622
// instructions) but re-shapes the L1/L2/L3 loops; not submitted.
//
// VERIFICATION: byte-exact vs std::sort at FULL scale n = 1e8 (3 seeds, uniform
// u32) AND at n = 8e6 over 8 input patterns incl. the degenerate ones that
// exercise the fallbacks. An instrumented build printed 0 last-resort
// insertion sorts. Every .s claim above was counted, not assumed.
// Full decomposition + instruments: work/e1001o/FINDINGS.txt
// md5 (payload below the header, i.e. from the #pragma onward) 29f8aa95fff1f25c36ba4b6ff7ed54a1
// The submitted artifact is that payload; this file is it with this header prepended.
// ============================================================================
#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")
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <immintrin.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 100000000u
#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 320u // 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 SLK3 18u
#define RS3MAX 32u
// ---- lane ac1: PQR -------------------------------------------------------
// The b1 group's four buckets are laid out at SIXTEEN-byte granularity inside a
// 96-byte group block: [PAD(32) | 4g(16) | 4g+2(16) | 4g+1(16) | 4g+3(16)]
// so that
// X = load32(G+32) = [4g | 4g+2] Y = load32(G+64) = [4g+1 | 4g+3]
// and unpacklo_epi64(X,Y) is AP and unpackhi_epi64(X,Y) is B, in NATURAL bucket
// order -- the two `vinserti128` (p5) per group that the old 32-byte slots forced
// (the 16-byte halves were 64 bytes apart) are simply gone.
// The 32-byte PAD in front of each group absorbs the only spill that can leave a
// group (bucket 4g+3's bytes 16..32); every other spill lands on a bucket of the
// SAME group, which is why the mx>16 group takes the emit_b1range fallback anyway.
// PQR2: a 32-byte PAD follows each PAIR of regions, so a bucket's overflow lands in
// a pad -- unless the bucket is the FIRST of its pair. Regions within a 128-byte group:
// 4g+0 @ +0 4g+2 @ +16 [PAD 32] 4g+1 @ +64 4g+3 @ +80 [PAD 32]
// X = load32(G+0) = [4g+0 | 4g+2] Y = load32(G+64) = [4g+1 | 4g+3]
// unpacklo_epi64(X,Y) is AP in NATURAL bucket order; 2 vinserti128 are gone.
// => 4g+2 and 4g+3 can overflow harmlessly (their data is then CONTIGUOUS into their
// pad), so when ONLY they overflow no repair scan is needed at all (~50 % of events).
#define GSTR 128u
alignas(32) static u8 g_U[64u*GSTR + RS2MAX + 256u];
// used ONLY by the d3==255 path when some bucket exceeds 16; 32-byte slots, exactly the
// pre-PQR layout, so that fallback path stays byte-for-byte the old one.
alignas(32) static u8 g_U2[256u*32u + 256u];
static u32 g_base[256];
static void init_u16layout(void){
for(u32 b=0;b<256u;b++) g_base[b]=((b>>2)*GSTR)+((b&1u)*64u)+(((b>>1)&1u)*16u);
}
static u32 g_off[257];
static volatile u32 g_y;
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));
}
// ---- lane ac1: PQR's fallback. A group with mx>16 has at least one bucket whose
// data overran its 16-byte slot (into a same-group neighbour's slot), so the packed
// array cannot be read back for that group. Re-scatter the FOUR buckets of this one
// group, from p, into a 32-byte-slot scratch and take the unchanged per-bucket emit.
// Fires on 0.066 % of groups (2762 per 4 177 920-group sort, measured at the board's
// own Lambda = 5.9623); the scan is over this b2's m2 elements (~1526).
static __attribute__((noinline)) u32 *emit_b1range(u32 b1,const u16 *p,u32 m2,const u32 *cnt3,u32 hi24,u32 *o){
// PQR2 fast repair: the two buckets at the START of a pair (4g+0 and 4g+1) are the only
// ones whose overflow can land on a neighbour's data. If NEITHER of them exceeds 16, no
// data was lost: every bucket's bytes are contiguous (each pair's second bucket runs into
// its own 32-byte pad), so the group is emitted straight out of the packed array with NO
// scan at all. Measured on the board, this path is worth ~1.4 ms of the 2.78 ms the scan
// cost in PQR1.
if(cnt3[b1]<=16u && cnt3[b1+1]<=16u){
u8 *G=g_U+((b1>>2)*GSTR);
u32 *q=o;
{ u32 c=cnt3[b1]; if(c){ emit(G ,c,hi24|(b1<<8),q); q+=c; } }
{ u32 c=cnt3[b1+1]; if(c){ emit(G+64u ,c,hi24|((b1+1)<<8),q); q+=c; } }
{ u32 c=cnt3[b1+2]; if(c){ emit(G+16u ,c,hi24|((b1+2)<<8),q); q+=c; } }
{ u32 c=cnt3[b1+3]; if(c){ emit(G+80u ,c,hi24|((b1+3)<<8),q); q+=c; } }
return q;
}
alignas(32) u8 sc[4*32];
u32 cur[4]={0u,32u,64u,96u};
// ---- SIMD pre-filter: 92 % of the scan is rejection. Sixteen u16 per iteration,
// one vptest-style mask, and only the chunks with a hit fall through to the scalar
// extract. (The scalar form measured 3.5 cyc/element on this box, i.e. 5.3 k cycles
// per repair call -- more than the 2 p5/group the fast path buys back.)
{ const __m256i b1v=_mm256_set1_epi16((short)b1);
const __m256i n1=_mm256_set1_epi16(-1);
const __m256i fo=_mm256_set1_epi16(4);
u32 i=0;
for(;i+16u<=m2;i+=16u){
__m256i v=_mm256_loadu_si256((const __m256i*)(p+i));
__m256i d=_mm256_sub_epi16(_mm256_srli_epi16(v,8),b1v);
__m256i mk=_mm256_and_si256(_mm256_cmpgt_epi16(d,n1),_mm256_cmpgt_epi16(fo,d));
u32 m=(u32)_mm256_movemask_epi8(mk)&0x55555555u;
while(m){ u32 k=(u32)__builtin_ctz(m)>>1; u32 r=p[i+k];
sc[cur[(r>>8)-b1]++]=(u8)r; m&=m-1u; } }
for(;i<m2;i++){ u32 k=(u32)(p[i]>>8)-b1; if(k<4u) sc[cur[k]++]=(u8)p[i]; } }
for(u32 b=b1;b<b1+4;b++){ u32 c=cnt3[b]; if(!c) continue;
emit(sc+(((u32)(b-b1))<<5),c,hi24|(b<<8),o); o+=c; }
return o;
}
// 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
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;
T[st2[b2]++]=lo;
}
}
for(u32 b=0;b<256;b++) if(st2[b]-b*RS2>RS2){ 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; }
u32 pos=0;
alignas(32) u32 st3[256];
{ for(u32 b=0;b<256;b++) st3[b]=g_base[b]; }
for(u32 b2=0;b2<256;b2++){
u32 m2=st2[b2]-b2*RS2;
if(!m2) continue;
const u16 *p=T+b2*RS2;
u32 hi24=(b2<<16)|(d3<<24);
if(m2<=8){
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;
{ const __m256i mx=_mm256_set1_epi8(-1);
for(u32 gg=0;gg<64u;gg++){ u8*qq=U+gg*GSTR;
_mm256_store_si256((__m256i*)qq,mx); _mm256_store_si256((__m256i*)(qq+64u),mx); } }
#pragma GCC unroll 16
for(u32 i=0;i<m2;i++){ u32 r=p[i]; u32 b1=r>>8; U[st3[b1]++]=(u8)r; }
alignas(32) u32 cnt3[256];
u32 bad=0, gmax3=0;
{ __m256i stp=_mm256_set1_epi32(8);
__m256i mx=_mm256_setzero_si256();
for(u32 b=0;b<256;b+=8){ __m256i bv=_mm256_load_si256((const __m256i*)(g_base+b));
__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 g_base[b] */
mx=_mm256_max_epu32(mx,v); }
__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);
gmax3=(u32)_mm256_extract_epi32(mr,0); if(gmax3>RS3) bad=1; }
if(bad){
u32 *o=out+pos;
for(u32 i=0;i<m2;i++){ u32 v=((u32)p[i])|hi24; u32 j=i;
while(j&&o[j-1]>v){ o[j]=o[j-1]; j--; } o[j]=v; }
pos+=m2; continue;
}
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);
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=_mm256_load_si256((const __m256i*)(U+((b1>>2)*128u)));
__m256i Q=_mm256_load_si256((const __m256i*)(U+((b1>>2)*128u)+64u));
__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,m2,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 {
// ---- lane ac1: PQR. The 16-byte packed slots hold only the FIRST 16 bytes of a
// bucket, so this path is valid only while every bucket fits (gmax3<=16). When one
// does not, re-scatter this one b2 into a 32-byte-slot array and keep the loop verbatim.
// d3==255 is ONE region in 256 and max(cnt3)>16 needs ~4 % of b2's, so the extra
// scatter is ~0.2 % of the b1 scatters.
u8 * __restrict U2=U;
if(gmax3>16u){
U2=g_U2;
static u32 st2[256];
for(u32 b=0;b<256u;b++) st2[b]=b<<5;
for(u32 i=0;i<m2;i++){ u32 r=p[i]; U2[st2[r>>8]++]=(u8)r; }
}
for(u32 b1=0;b1<256;b1++){
u32 c=cnt3[b1];
if(!c) continue;
u32 _s=b1&3u,_o=((_s&1u)*64u)+((_s>>1u)*16u);
const u8 *g=(gmax3>16u)?(U2+(b1*32u)):(U+((b1>>2)*128u)+_o);
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;
}
}
}
}
__attribute__((noinline)) void pospad(void) {
__asm__ __volatile__(".fill 139,1,0x90 ; ret");
}
__attribute__((noinline)) void pospadB(void) {
__asm__ __volatile__(".fill 75,1,0x90 ; ret");
}
void sort(unsigned *a,int n){
static int initt=0;
if(!initt){ initt=1; init_pb1(); init_bmasks(); init_u16layout(); }
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).
// --------------------------------------------------------------------------
u32 off[256]; u32 base[256], ob[256];
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;
// 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) { u32 v=aa[i+(K)], d=((const u8*)aa)[4*(i+(K))+3]; u32 o=off[d]; u32 _n=o+REC3; off[d]=_n; if(__builtin_expect((_n&63u)==0u,0)){ off[d]=_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+o)=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+8192<(int)n,0))
__asm__ volatile("orl $0, %0" : "+m"(((u32*)aa)[i+8192]));
L2BODY(0) L2BODY(1) L2BODY(2) L2BODY(3)
L2BODY(4) L2BODY(5) L2BODY(6) L2BODY(7) }
for(;i<n;i++){ L2BODY(0) }
}
#undef L2BODY
_mm_sfence();
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){ std::sort(a,a+n); 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);
}
volatile u8 l_pad[1856u]; l_pad[0]=1;
sink64(l_pad[0]);
}
}
// m100 hpad H0_static