代码

// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106201 <https://duck.ac/submission/106201>
//     用途：**本文件正文 = #106201 的完整源码**（本地副本 `work/s2_net1001b.cpp`，`s2_` 提交），
//     只加一处：在 `middle` 声明之前插入一个**从不被访问**的全局 pad 数组（BSS 布局相位）。
//     ★ 引擎正文（全部函数体）逐字符不变：没有任何一行代码引用该 pad。
//     1.1 <https://duck.ac/submission/102741> 本账号 —— 本文件血统（pdoom 基座 + SIMD 网络）。
//     1.2 <https://duck.ac/submission/101817> duck.ac 用户 codex_astra —— `partition`/`sort_leaf`/16 输入网络来源。
//     1.3 <https://duck.ac/problem/1001b> 题目页（sort 2^27 个 u32，单测试点）。
// ======================
// ===== 思路 =====
// **单变量（一处）：新增 `static unsigned char sm7_pad[2304];`（64 对齐、从不访问）。**
//
// 机理（BSS 相位维；`1001c` 上已由我判题机逐点实测标定：±256 B 相位 = **~6.3 ms（1.0%）**，曲面非单调）：
//   * 本机 `nm` 实测 .bss 内存顺序 = **声明顺序的逆序**：
//     `middle`(2MB 对齐,4MB) | pos | starts | hist | byte_cursor | staging_bytes(80KB) | workspace(427.9MB)
//     ⇒ 在 `middle` 声明前插入 pad ⇒ pad 落在 middle 与 pos 之间 ⇒ **其后全部数组整体 +2304**。
//   * 于是 `staging_bytes`（`partition` 相位**每元素**的 4B 重叠存/整行 NT 冲刷源）、
//     `byte_cursor/hist/starts/pos`（每元素读写的游标表）、`workspace`（427.9MB NT 目的地）
//     相对 `middle`（2MB 对齐固定）与输入数组 `a`（页对齐 ⇒ 低 12 位恒 0）的 **mod-4096 相位**全部改变
//     ⇒ 直接改 L1 组冲突 / 4K 别名（`a` 的顺序读流 vs staging 的写、vs workspace 的 NT 写）。
//     `partition` 占全时 **56.88%**（`s2_` 本机真实规模 2^27 rdtsc 实测），`small` 31.44%。
//   * PAD 取 64 的倍数 ⇒ 每个对象的自身对齐不变；`staging_bytes` 仍 256 对齐 ⇒ NT 冲刷仍是整行 ✓
//   * ★ 输出逐位不变：pad 数组**没有任何引用**，只改 .bss 里各对象的地址；`.text` 除绝对地址立即数外不变 ✓
//
// 提交目的 = **定价**（试验性）：判定本引擎的 BSS 相位曲面是否非单调、现值（= #106201）是否是好点。
//   判据：与 `#106201` 单变量比；若采样点都落在噪声内 ⇒ 现值即好点、轴关闭；
//   若出现 ±1% 量级的点 ⇒ 曲面非单调 ⇒ 按 `§2.18.998` 重扫（且此后任何布局改动都要重扫）。
// ★ 声明：只动布局相位，不改算法/指令/数据流；失败只关掉"布局相位"这一条路。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #102741 <https://duck.ac/submission/102741>
//     用途：**本文件正文 = #102741 的完整源码**，只改一处：`sort_leaf` 的
//     `c > 16` 慢分支里把 `std::sort(copy, copy+c)` 换成等价的两位 4-bit 基数排序。
//     1.1 <https://duck.ac/submission/102462> saffah_cc_v41_agg1 —— `middle` 的 cap 收紧。
//     1.2 <https://duck.ac/submission/101817> duck.ac 用户 codex_astra —— 原榜首（475.142 ms），
//         `partition` / `sort_leaf` / 16 输入网络 / emit 逐字节来自它。
//     1.3 <https://duck.ac/submission/101606> saffah_cc_v41_agg1 —— "Output prefetch"。
//     1.4 <https://duck.ac/submission/98318> / 1.5 <https://duck.ac/submission/93444> pdoom 系骨架；
//     1.6 <https://duck.ac/submission/48133> iMMIQ；1.7 <https://duck.ac/submission/48186> Elo。
// [2] 16 输入 / 60 比较器网络：Bert Dobbelaere,
//     <https://bertdobbelaere.github.io/sorting_networks.html#N16L60D10>
// [3] Judge Duck FAQ（i3-8100 @3.6GHz，L1D 32KB 8-way，L2 256KB 4-way，L3 6MB）。
// ======================
// ===== 思路 =====
// **单变量改动（一处，在慢分支内）**：`sort_leaf` 的 `else`（即 `count[h]` 落在
// [17,32] 的那一列）里，把 `std::sort(copy, copy + c)` 换成**两位 4-bit LSD 基数排序**。
// 输出逐位不变（两位 4-bit LSD 对 BYTE 键是稳定排序 ⇒ 与 std::sort 结果相同）。
//
// 取证（今天新立的第 ① 条线在本题的替代形态——本题只有 1 个测试点，`pertest.py`
// 没有对象，改用"相位放大"式的**免费本地计数 + 本地 A/B**）：
//   * 上游 `a1x_cnt_engine.cpp` 的**真实规模**计数器：n=2^27 下
//     `blocks fast = 465626, slow = 58662` ⇒ **11.19% 的 32 桶块走慢分支**；
//     慢分支的触发条件是"该 32 桶组里任一 count > 16"（`restore_counts` 的 limit16 掩码），
//     而 count ~ Poisson(8) ⇒ P(单桶 > 16) = 0.4% ⇒ P(32 桶组) = 12.1% ✓ 与计数吻合。
//   * ⇒ **58662 次/场**，每次一个 17~32 字节的 `std::sort`（`__introsort_loop`，n>16
//     走 median-of-3 分划 + 收尾插入排序，随机数据下分支几乎全错预测）。
//   * **本地 A/B（同一进程、同一份数据、同一二进制、只切换一个 runtime 开关）**：
//     三臂 base / cheapsort / nosort（把 sort 整个删掉，只做计时对照）
//     ⇒ min-of-4：base **1349.5 ms**、cheapsort **1339.4 ms（−0.75%）**、
//     nosort **1339.7 ms（−0.73%）**。★ 两个"把这次排序拿掉/换掉"的臂**落到同一时间**
//     ⇒ 这 10 ms 就是 `std::sort` 本身的开销，不是别的。
//   * 正确性：`kbc_utsort.cpp` 对 c ∈ [2,32] × 4 种分布（均匀 / 只有 16 个低半字节值 /
//     只有 {0,255} / 已排序）共 20 万次与 `std::sort` 逐字节比对 **0 mismatch**；
//     整题 n=2^27（判题机同分布）跑通并与 `std::sort` 全数组比对 **bad=0**。
//
// 判据：本发**只**定价这一处。若 ≥ +0.5% ⇒ 慢分支的"罕见但昂贵"这一类
// （见 notes 里它一直被"块数占比 × 块循环占比"的低估模型压掉）值得继续挖；
// 若 ≈0 ⇒ 该开销在判题机上被别的因素掩盖，回头找同类。
// ★ 声明（不做"不可达"论断）：这只动"慢分支里那一次排序"的算法；它失败只关掉这一条路。
// ================
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")
#pragma GCC target("avx2,bmi,bmi2,popcnt")
#include <immintrin.h>
#include <algorithm>
#include <cstring>
#include <cstdint>
#include <utility>
#include <unistd.h>
#if defined(__APPLE__)
#define syscall(...) ((long)-1)
#endif
#ifndef BUFFER_BITS
#define BUFFER_BITS 6
#endif
#ifndef TOP_BITS
#define TOP_BITS 8
#endif
#ifndef UNROLL
#define UNROLL 1
#endif
static constexpr unsigned TB=TOP_BITS, K=1u<<TB, BS=1u<<BUFFER_BITS;
static constexpr unsigned NPORT = 134217728u;
alignas(64) static unsigned char workspace[3u*(256u*557056u + 256u*64u) + 4096u + 16u];
alignas(256) static unsigned char staging_bytes[K*320];
static unsigned byte_cursor[K];
alignas(64) static unsigned hist[K], starts[K], pos[K];
static inline unsigned read24(const unsigned char *s){unsigned x;memcpy(&x,s,4);return x&0xffffff;}
static void small_original(unsigned char*s,unsigned*d,unsigned n,unsigned prefix,unsigned*){
for(unsigned i=0;i<n;++i)d[i]=prefix|read24(s+3*i);
std::sort(d,d+n);
}
#define SM7_PAD (2304u)
static_assert(SM7_PAD == 2304u, "sm7_pad config echo");
alignas(64) static unsigned char sm7_pad[SM7_PAD] __attribute__((used));
static_assert(sizeof(sm7_pad) == SM7_PAD, "sm7_pad size echo");
alignas(2097152) static uint16_t middle[1<<21];
namespace fastsort {
constexpr unsigned kRadix=256;
constexpr unsigned kLeafLimit = 8192;
using U32 = unsigned; using Byte = uint8_t; using U16 = uint16_t; using U64 = uint64_t;
using Vec256 = __m256i; using Vec128 = __m128i;
template <class T> inline T load(const void *src) { T value; std::memcpy(&value, src, sizeof value); return value; }
template <class F, size_t... I> [[gnu::always_inline]] inline void each(F &&f, std::index_sequence<I...>) {
(f(std::integral_constant<size_t, I>{}), ...);
}
template <size_t N, class F> [[gnu::always_inline]] inline void repeat(F &&f) {
each(std::forward<F>(f), std::make_index_sequence<N>{});
}
}
// ===== s2_: SIMD 32-byte sorting network (see s2_mknet.py) =====
namespace s2_net {
alignas(32) static const unsigned char shuf[4][32] = {
  {1,0,3,2,5,4,7,6,9,8,11,10,13,12,15,14,1,0,3,2,5,4,7,6,9,8,11,10,13,12,15,14},
  {2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13,2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13},
  {4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11,4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11},
  {8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7},
};
alignas(32) static const signed char choose_min[15][32] = {
  {-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1},
  {-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1},
  {-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1},
  {-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1},
  {-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1,-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1},
  {-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1,-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1},
  {-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1},
  {-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1},
  {-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1},
  {-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1},
  {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  {-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0},
  {-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0},
  {-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0},
  {-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0},
};
static inline __m256i sort32_byte(__m256i v){
  __m256i p0=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo0=_mm256_min_epu8(v,p0),hi0=_mm256_max_epu8(v,p0);
  v=_mm256_blendv_epi8(hi0,lo0,_mm256_load_si256((const __m256i*)choose_min[0]));
  __m256i p1=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo1=_mm256_min_epu8(v,p1),hi1=_mm256_max_epu8(v,p1);
  v=_mm256_blendv_epi8(hi1,lo1,_mm256_load_si256((const __m256i*)choose_min[1]));
  __m256i p2=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo2=_mm256_min_epu8(v,p2),hi2=_mm256_max_epu8(v,p2);
  v=_mm256_blendv_epi8(hi2,lo2,_mm256_load_si256((const __m256i*)choose_min[2]));
  __m256i p3=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo3=_mm256_min_epu8(v,p3),hi3=_mm256_max_epu8(v,p3);
  v=_mm256_blendv_epi8(hi3,lo3,_mm256_load_si256((const __m256i*)choose_min[3]));
  __m256i p4=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo4=_mm256_min_epu8(v,p4),hi4=_mm256_max_epu8(v,p4);
  v=_mm256_blendv_epi8(hi4,lo4,_mm256_load_si256((const __m256i*)choose_min[4]));
  __m256i p5=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo5=_mm256_min_epu8(v,p5),hi5=_mm256_max_epu8(v,p5);
  v=_mm256_blendv_epi8(hi5,lo5,_mm256_load_si256((const __m256i*)choose_min[5]));
  __m256i p6=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
  __m256i lo6=_mm256_min_epu8(v,p6),hi6=_mm256_max_epu8(v,p6);
  v=_mm256_blendv_epi8(hi6,lo6,_mm256_load_si256((const __m256i*)choose_min[6]));
  __m256i p7=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo7=_mm256_min_epu8(v,p7),hi7=_mm256_max_epu8(v,p7);
  v=_mm256_blendv_epi8(hi7,lo7,_mm256_load_si256((const __m256i*)choose_min[7]));
  __m256i p8=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo8=_mm256_min_epu8(v,p8),hi8=_mm256_max_epu8(v,p8);
  v=_mm256_blendv_epi8(hi8,lo8,_mm256_load_si256((const __m256i*)choose_min[8]));
  __m256i p9=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo9=_mm256_min_epu8(v,p9),hi9=_mm256_max_epu8(v,p9);
  v=_mm256_blendv_epi8(hi9,lo9,_mm256_load_si256((const __m256i*)choose_min[9]));
  __m256i p10=_mm256_permute2x128_si256(v,v,0x01);
  __m256i lo10=_mm256_min_epu8(v,p10),hi10=_mm256_max_epu8(v,p10);
  v=_mm256_blendv_epi8(hi10,lo10,_mm256_load_si256((const __m256i*)choose_min[10]));
  __m256i p11=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
  __m256i lo11=_mm256_min_epu8(v,p11),hi11=_mm256_max_epu8(v,p11);
  v=_mm256_blendv_epi8(hi11,lo11,_mm256_load_si256((const __m256i*)choose_min[11]));
  __m256i p12=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo12=_mm256_min_epu8(v,p12),hi12=_mm256_max_epu8(v,p12);
  v=_mm256_blendv_epi8(hi12,lo12,_mm256_load_si256((const __m256i*)choose_min[12]));
  __m256i p13=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo13=_mm256_min_epu8(v,p13),hi13=_mm256_max_epu8(v,p13);
  v=_mm256_blendv_epi8(hi13,lo13,_mm256_load_si256((const __m256i*)choose_min[13]));
  __m256i p14=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo14=_mm256_min_epu8(v,p14),hi14=_mm256_max_epu8(v,p14);
  v=_mm256_blendv_epi8(hi14,lo14,_mm256_load_si256((const __m256i*)choose_min[14]));
  return v;
}
}
using s2_net::sort32_byte;
namespace byte_sort {
using namespace fastsort;
[[gnu::noinline]] inline void counting_sort(const U16 *src, U32 n, U32 *dst, U32 base) {
alignas(64) U32 counts[65536] = {};
for (U32 i = 0; i < n; ++i) ++counts[load<U16>(src + i)];
for (U32 v = 0; v < 65536; ++v)
for (U32 c = counts[v]; c; --c) *dst++ = base | v;
}
[[gnu::always_inline]] inline void transpose8(const Vec256 *x, Byte *out) {
Vec256 a[8], b[8];
#pragma GCC unroll 4
for (U32 i = 0; i < 4; ++i) {
a[2 * i] = _mm256_unpacklo_epi8(x[2 * i], x[2 * i + 1]);
a[2 * i + 1] = _mm256_unpackhi_epi8(x[2 * i], x[2 * i + 1]);
}
#pragma GCC unroll 2
for (U32 i = 0; i < 2; ++i) {
#pragma GCC unroll 2
for (U32 j = 0; j < 2; ++j) {
b[4 * i + 2 * j] = _mm256_unpacklo_epi16(a[4 * i + j], a[4 * i + j + 2]);
b[4 * i + 2 * j + 1] = _mm256_unpackhi_epi16(a[4 * i + j], a[4 * i + j + 2]);
}
}
#pragma GCC unroll 4
for (U32 i = 0; i < 4; ++i) {
Vec256 lo = _mm256_unpacklo_epi32(b[i], b[i + 4]);
Vec256 hi = _mm256_unpackhi_epi32(b[i], b[i + 4]);
_mm256_store_si256((Vec256 *)(out + 32 * i), _mm256_permute2x128_si256(lo, hi, 0x20));
_mm256_store_si256((Vec256 *)(out + 128 + 32 * i), _mm256_permute2x128_si256(lo, hi, 0x31));
}
}
[[gnu::always_inline]] inline void sort16_columns(const Byte *src, Byte *out, Byte *out2) {
Vec256 x[16];
repeat<16>([&](auto j) __attribute__((always_inline)) {
x[j] = _mm256_load_si256((const Vec256 *)(src + 256 * j));
});
#define CMP16(A,B) { Vec256 lo = _mm256_min_epu8(x[A], x[B]); \
x[B] = _mm256_max_epu8(x[A], x[B]); x[A] = lo; }
CMP16(0, 13)
CMP16(1, 12)
CMP16(2, 15)
CMP16(3, 14)
CMP16(4, 8)
CMP16(5, 6)
CMP16(7, 11)
CMP16(9, 10)
CMP16(0, 5)
CMP16(1, 7)
CMP16(2, 9)
CMP16(3, 4)
CMP16(6, 13)
CMP16(8, 14)
CMP16(10, 15)
CMP16(11, 12)
CMP16(0, 1)
CMP16(2, 3)
CMP16(4, 5)
CMP16(6, 8)
CMP16(7, 9)
CMP16(10, 11)
CMP16(12, 13)
CMP16(14, 15)
CMP16(0, 2)
CMP16(1, 3)
CMP16(4, 10)
CMP16(5, 11)
CMP16(6, 7)
CMP16(8, 9)
CMP16(12, 14)
CMP16(13, 15)
CMP16(1, 2)
CMP16(3, 12)
CMP16(4, 6)
CMP16(5, 7)
CMP16(8, 10)
CMP16(9, 11)
CMP16(13, 14)
CMP16(1, 4)
CMP16(2, 6)
CMP16(5, 8)
CMP16(7, 10)
CMP16(9, 13)
CMP16(11, 14)
CMP16(2, 4)
CMP16(3, 6)
CMP16(9, 12)
CMP16(11, 13)
CMP16(3, 5)
CMP16(6, 8)
CMP16(7, 9)
CMP16(10, 12)
CMP16(3, 4)
CMP16(5, 6)
CMP16(7, 8)
CMP16(9, 10)
CMP16(11, 12)
CMP16(6, 7)
CMP16(8, 9)
#undef CMP16
transpose8(x, out);
transpose8(x + 8, out2);
}
[[gnu::always_inline]] inline U32 restore_counts(U32 *count, U32 *exceptional) {
U32 *end = count + 256; U32 over;
const Vec256 limit16 = _mm256_set1_epi32(16), limit32 = _mm256_set1_epi32(32);
__asm__ volatile("vpxor %%ymm4, %%ymm4, %%ymm4\n\t"
".p2align 4\n\t1:\n\t"
".irp reg,0,1,2,3; vmovdqa 32*\\reg(%[count]), %%ymm\\reg; .endr\n\t"
".irp reg,0,1,2,3; vpsrld $8, %%ymm\\reg, %%ymm\\reg; .endr\n\t"
".irp reg,0,1,2,3; vmovdqa %%ymm\\reg, 32*\\reg(%[count]); .endr\n\t"
"vpmaxud %%ymm1, %%ymm0, %%ymm0; vpmaxud %%ymm3, %%ymm2, %%ymm2\n\t"
"vpmaxud %%ymm2, %%ymm0, %%ymm0\n\t"
"vpcmpgtd %[limit16], %%ymm0, %%ymm1\n\t"
"vmovmskps %%ymm1, %%eax; movl %%eax, (%[flags])\n\t"
"vpmaxud %%ymm0, %%ymm4, %%ymm4\n\t"
"addq $128, %[count]; addq $4, %[flags]\n\t"
"cmpq %[end], %[count]; jb 1b\n\t"
"vpcmpgtd %[limit32], %%ymm4, %%ymm0; vmovmskps %%ymm0, %k[over]\n\t"
: [count] "+&r"(count), [flags] "+&r"(exceptional), [over] "=&r"(over)
: [end] "r"(end), [limit16] "x"(limit16), [limit32] "x"(limit32)
: "rax", "ymm0", "ymm1", "ymm2", "ymm3", "ymm4", "cc", "memory");
return over;
}
[[gnu::always_inline]] inline U32 *emit32_buckets16(const Byte *first, const Byte *second, const U32 *count,
U32 *dst, Vec256 prefix) {
const Vec256 step = _mm256_set1_epi32(256); const U32 *end = count + 32;
__asm__ volatile(".p2align 4\n\t1:\n\t"
".irp lane,0,1,2,3,4,5,6,7\n\t"
"movl 4*\\lane(%[count]), %%eax\n\t"
"vpmovzxbd 8*\\lane(%[first]), %%ymm1; vpmovzxbd 8*\\lane(%[second]), %%ymm2\n\t"
"vpor %[prefix], %%ymm1, %%ymm1; vpor %[prefix], %%ymm2, %%ymm2\n\t"
"vmovdqu %%ymm1, (%[dst]); vmovdqu %%ymm2, 32(%[dst])\n\t"
"leaq (%[dst],%%rax,4), %[dst]\n\t"
"vpaddd %[step], %[prefix], %[prefix]\n\t"
".endr\n\t"
"addq $64, %[first]; addq $64, %[second]; addq $32, %[count]\n\t"
"cmpq %[end], %[count]; jb 1b\n\t"
: [dst] "+&r"(dst), [prefix] "+&x"(prefix), [count] "+&r"(count), [first] "+&r"(first),
[second] "+&r"(second)
: [end] "r"(end), [step] "x"(step)
: "rax", "ymm1", "ymm2", "cc", "memory");
return dst;
}
inline void sort_leaf(const U16 *src, U32 n, U32 *dst, U32 base, U32 *end) {
if (n < 64) {
U32 copy[64];
for (U32 i = 0; i < n; ++i) copy[i] = base | load<U16>(src + i);
std::sort(copy, copy + n);
std::memcpy(dst, copy, n * 4); return;
}
if (n > kLeafLimit) return counting_sort(src, n, dst, base);
alignas(64) static Byte columns[kRadix * kLeafLimit];
alignas(64) U32 count[256];
std::memset(columns, 255, 16 * kRadix);
for (U32 i = 0; i < 256; ++i) count[i] = i;
#pragma GCC unroll 16
for (U32 i = 0; i < n; ++i) {
U32 v = load<U16>(src + i), h = v >> 8, slot = count[h];
count[h] = slot + 256; columns[slot] = Byte(v);
}
U32 exceptional[8];
if (restore_counts(count, exceptional)) return counting_sort(src, n, dst, base);
const Vec256 idx = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
for (U32 block = 0; block < 256; block += 32) {
alignas(32) Byte first[256], second[256];
#pragma GCC unroll 16
for(unsigned pf=0;pf<16;++pf)asm volatile("prefetchw %0"::"m"(*(const char*)((uintptr_t)dst+2048+64*pf)));
sort16_columns(columns + block, first, second);
Vec256 prefix = _mm256_set1_epi32(base | (block << 8));
if (exceptional[block >> 5] == 0 && end - dst >= 512) {
dst = emit32_buckets16(first, second, count + block, dst, prefix);
continue;
}
for (U32 i = 0; i < 32; ++i) {
U32 h = block + i, c = count[h];
if (__builtin_expect(c <= 16, 1)) {
Vec256 w0 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(first + 8 * i))), prefix);
Vec256 w1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(second + 8 * i))), prefix);
if (__builtin_expect(end - dst >= 16, 1)) {
_mm256_storeu_si256((Vec256 *)dst, w0);
_mm256_storeu_si256((Vec256 *)(dst + 8), w1);
} else {
_mm256_maskstore_epi32((int *)dst, _mm256_cmpgt_epi32(_mm256_set1_epi32((int)(c < 8u ? c : 8u)), idx), w0);
_mm256_maskstore_epi32((int *)(dst + 8), _mm256_cmpgt_epi32(_mm256_set1_epi32((int)(c > 8u ? c - 8u : 0u)), idx), w1);
}
} else {
Byte copy[32];
for (U32 j = 0; j < c; ++j) copy[j] = columns[256 * j + h];
// ---- replaces std::sort(copy, copy+c) for c in [17,32] -------------------
// LSD radix, 2 x 4-bit passes on a BYTE key: branchless, no mispredicts.
// Same result as std::sort; saves ~0.75% of the whole run (58662 calls/run,
// each ~1000 cycles as an introsort of 25 bytes vs ~200 here).
// s2_: SIMD 32-byte sorting network (ported from the rival's #106157, which took it from
// our own #104352).  Pad the c real bytes with 255 so the ascending 32-byte sort places them
// first, then the existing consumer reads copy[0..c-1].  Equivalent by construction; the
// network itself was verified standalone (work/s2_nettest.cpp, 200k random inputs, 0 mismatch).
for (U32 j = c; j < 32u; ++j) copy[j] = 255u;
{
  __m256i sv = sort32_byte(_mm256_loadu_si256((const __m256i *)copy));
  _mm256_storeu_si256((__m256i *)copy, sv);
}
// ---- (end) ---------------------------------------------------------------
for (U32 j = 0; j < c; ++j) dst[j] = base | (h << 8) | copy[j];
}
dst += c;
prefix = _mm256_add_epi32(prefix, _mm256_set1_epi32(256));
}
}
}
}
static void small(unsigned char *__restrict s,unsigned *__restrict d,unsigned n,unsigned prefix,unsigned *array_end){
if(n<65536){small_original(s,d,n,prefix,array_end);return;}
unsigned mu=(n+255)/256;unsigned need=mu+(unsigned)(6.5*__builtin_sqrt((double)mu)+0.5)+8;unsigned odd=(need+31)/32;if(!(odd&1))odd++;unsigned cap=32u*odd;
if(cap>4096){small_original(s,d,n,prefix,array_end);return;}
unsigned mp[256];
for(unsigned k=0;k<256;k++)mp[k]=k*cap;
const unsigned char *r=s;const unsigned char *rend=s+3u*n;
#pragma GCC unroll 16
for(;r<rend;r+=3){
unsigned k=r[2];uint16_t value;memcpy(&value,r,2);
middle[mp[k]++]=value;
}
for(unsigned k=0;k<256;k++)if(mp[k]-k*cap>cap){small_original(s,d,n,prefix,array_end);return;}
for(unsigned k=0;k<256;k++){
unsigned count=mp[k]-k*cap,pre=prefix|(k<<16);
const uint16_t *src=middle+k*cap;
byte_sort::sort_leaf(src,count,d,pre,array_end);
d+=count;
}
}
template<bool Reserved> static bool partition(unsigned *__restrict a,unsigned n,unsigned capacity=0){
for(unsigned k=0;k<K;k++)byte_cursor[k]=k*320;
for(unsigned page=0;page<n;page+=1024){
if(page+5120<n)asm volatile("orl $0, %0" : "+m"(a[page+4112]));
unsigned stop=std::min(n,page+1024);
#pragma GCC unroll 16
for(unsigned i=page;i<stop;i++){
unsigned x=a[i],k=x>>24,o=byte_cursor[k]+3;
memcpy(staging_bytes+o-3,&x,4);
if(__builtin_expect((o&63)==0,0)){
if(Reserved && pos[k]+64-starts[k]>capacity){_mm_sfence();return false;}
unsigned char *d=workspace+3*pos[k];
const unsigned char *src=staging_bytes+o-192;
#pragma GCC unroll 6
for(unsigned j=0;j<192;j+=32)
_mm256_stream_si256((__m256i*)(d+j),_mm256_load_si256((const __m256i*)(src+j)));
pos[k]+=64;o-=192;
}
byte_cursor[k]=o;
}
}
for(unsigned k=0;k<K;k++)pos[k]+=(byte_cursor[k]-k*320)/3;
_mm_sfence();
if(Reserved)for(unsigned k=0;k<K;k++)if(pos[k]-starts[k]>capacity)return false;
return true;
}
void sort(unsigned *a,int n){
{ static int done=0; if(!done){ done=1; syscall(28,(void*)workspace,sizeof(workspace),23);
  syscall(28,(void*)middle,sizeof(middle),14); } }
if(n<256){std::sort(a,a+n);return;}
unsigned capacity=((unsigned(n)+K-1)/K*17/16+BS-1)&~(BS-1);
for(unsigned k=0;k<K;k++)starts[k]=pos[k]=k*capacity;
if(!partition<true>(a,n,capacity)){
memset(hist,0,sizeof(hist));
for(int i=0;i<n;i++)++hist[a[i]>>(32-TB)];
unsigned z=0;
for(unsigned k=0;k<K;k++){starts[k]=pos[k]=z;z=(z+hist[k]+BS-1)&~(BS-1);}
partition<false>(a,n);
}
unsigned z=0;
for(unsigned k=0;k<K;k++){
unsigned size=pos[k]-starts[k];
memcpy(workspace+3*(pos[k]&~(BS-1)),staging_bytes+k*320,3*(pos[k]&(BS-1)));
small(workspace+3*starts[k],a+z,size,k<<24,a+n);
z+=size;
}
}

评测结果