// 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")
#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 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)
#define CNSH 4u
#define CSPO 8u
static u8 g_sco[256u*CSPO] __attribute__((aligned(64)));
#define CAP (1u<<CNSH)
#define CNSZ (256u<<CNSH)
static u8 g_sc2[CNSZ] __attribute__((aligned(64)));
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 TSZ (256u*RS2MAX + CAP1M + 8192u)
#define SCZ (CAP1M + 8192u)
static u16 * const g_sc = g_T + (256u*RS2MAX);
#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 + CAP1M + 8192u + 1024u];
static u32 g_off[257];
static volatile int g_drepL0=1, g_drepT=1, g_drepM=1, g_drepA=1, g_drepB=1;
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));
}
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;
}
// 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;
// AK-Z5: pin the destination base in a register. GCC-9 re-materialises
// `leaq _ZL3g_T(%rip)` on EVERY iteration of this loop (1 wasted uop/element =
// 1.34e8 instructions). An empty asm with "+r" forbids that.
asm volatile("" : "+r"(T));
#pragma GCC unroll 32
for(u32 i=0;i<m;i++){
u32 lo=*(const u16*)sp; u32 b2=sp[2]; sp+=REC3;
T[st2[b2]++]=lo;
}
asm volatile("" : "+r"(T));
}
// ---- 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{
// AK27: cb2[] was ALREADY computed by the overflow scan above (st2[b]-b*RS2 is
// exactly the byte2 count), so the re-histogram of src here was a redundant
// pass over the whole region. Same values, one less pass.
u32 cs[256];
u32 s=0;
for(u32 b=0;b<256;b++){ u32 c=cb2[b]; 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(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){
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
alignas(32) u32 cnt3[256];
alignas(32) u32 hbuf[256];
alignas(32) u32 off1[256];
u32 bad=0;
// ---- ARM-13: ONE merged 256-entry pass replaces (byte1 screen + byte1-hist
// extraction). It yields cnt3, off1 (the byte1 output prefix) AND the byte0
// histogram in one read of p[], and the "is any byte1 bucket > RS3" test is a
// running max instead of a 32-wide SIMD reduce over st3.
u32 ovf=0;
{ u32 mxv=0;
for(u32 k=0;k<256u;k++){ cnt3[k]=0; hbuf[k]=0; }
#pragma GCC unroll 32
// AK35: DELETE the per-element `if(c>mxv) mxv=c` (a cmp+cmov on EVERY one of the
// m2 iterations, and a cadence-1 loop-carried chain). The same maximum is read
// off cnt3 afterwards with an 8-wide reduce: 32 loads + 29 ops per BUCKET instead
// of 2 ops per ELEMENT (2048 of them here). It is exactly the pattern the
// original code already used on st3.
for(u32 i=0;i<m2;i++){ u32 r=p[i]; u32 b0=r&255u; u32 j=hbuf[b0]++;
cnt3[r>>8]++;
if(__builtin_expect(j<CAP,1)) g_sc2[(b0<<CNSH)+j]=(u8)(r>>8);
else { u32 _k=j-CAP; if(__builtin_expect(_k<CSPO,1)) g_sco[(b0<<3)+_k]=(u8)(r>>8); else ovf=1u; } }
{ __m256i mx=_mm256_setzero_si256();
for(u32 b=0;b<256u;b+=8) mx=_mm256_max_epu32(mx,_mm256_load_si256((const __m256i*)(cnt3+b)));
__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);
mxv=(u32)_mm256_extract_epi32(mr,0); }
{ // AK-Z1: the two 256-entry scalar prefix loops (off1 from cnt3, hbuf counts -> hbuf
// offsets) become ONE 8-wide AVX2 exclusive scan. Same values, same order.
const __m256i HIM=_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1);
// AK-Z6: seed the off1 scan's carry with `pos` so the emit address is
// `out + off1[..]` with NO per-element `addq` (1 uop/element, 1.34e8).
__m256i c0=_mm256_set1_epi32((int)pos), c1=_mm256_setzero_si256();
for(u32 k=0;k<256u;k+=8){
__m256i aa=_mm256_load_si256((const __m256i*)(cnt3+k));
__m256i ta=_mm256_add_epi32(aa,_mm256_slli_si256(aa,4));
ta=_mm256_add_epi32(ta,_mm256_slli_si256(ta,8));
__m256i la=_mm256_shuffle_epi32(_mm256_permute2x128_si256(ta,ta,0x00),_MM_SHUFFLE(3,3,3,3));
ta=_mm256_add_epi32(ta,_mm256_and_si256(la,HIM));
__m256i ia=_mm256_add_epi32(ta,c0);
_mm256_store_si256((__m256i*)(off1+k),_mm256_sub_epi32(ia,aa));
c0=_mm256_add_epi32(c0,_mm256_shuffle_epi32(_mm256_permute2x128_si256(ta,ta,0x11),_MM_SHUFFLE(3,3,3,3)));
} }
if(mxv>RS3) bad=1; }
u8 * __restrict U=g_U;
if(!bad){
{ __m256i mx=_mm256_set1_epi8(-1);
for(u32 bb=0;bb<256u;bb++){ st3[bb]=bb<<RSH; _mm_store_si128((__m128i*)(U+(bb<<RSH)),_mm256_castsi256_si128(mx)); } }
#pragma GCC unroll 32
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; }
}
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; // AK-Z7: off1 already carries `pos` (seeded in the scan)
if(__builtin_expect(!ovf,1)){
for(u32 b0=0;b0<256u;b0++){ u32 n=hbuf[b0]; const u8 *q=g_sc2+(b0<<CNSH);
u32 pfx=hi24|b0; u32 m1=(n<CAP)?n:CAP;
for(u32 j=0;j<m1;j++){ u32 b1=q[j]; o[off1[b1]++] = pfx | (b1<<8u); }
if(n>CAP){ const u8 *sx=g_sco+(b0<<3); u32 m2b=n-CAP; if(m2b>CSPO) m2b=CSPO;
for(u32 k=0;k<m2b;k++){ u32 b1=sx[k]; o[off1[b1]++] = pfx | (b1<<8u); } } }
} else {
u32 s=0; for(u32 b=0;b<256u;b++){ u32 c=hbuf[b]; hbuf[b]=s; s+=c; }
u16 *sc=g_sc; u32 *h=hbuf;
for(u32 i=0;i<m2;i++){ u32 v=p[i]; sc[h[v&255u]++] = (u16)v; }
for(u32 i=0;i<m2;i++){ u32 v=sc[i]; o[off1[v>>8]++] = hi24 | 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);
__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;
}
}
}
}
__attribute__((noinline)) void pospad(void) {
__asm__ __volatile__(".fill 123,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(); }
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=(v>>24); 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){
// ---- 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.
// AK27: c3 IS ALREADY KNOWN. cnt[b] = (ob[b]-base[b])/BLK*BLKREC + (off[b]%BLKST)/REC3
// is exactly the number of records the L0 staging wrote into bucket b, i.e. the
// byte3 histogram; the scan above stored it into g_off as a running prefix, so
// c3[b] = g_off[b+1]-g_off[b]. The re-scan of the whole input was a redundant pass.
u32 c3[256];
if(tot==(u32)n){ for(u32 b=0;b<256;b++) c3[b]=g_off[b+1]-g_off[b]; }
else { 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);
}
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[1920u]; l_pad[0]=1;
sink64(l_pad[0]);
}
}