无分支编程：当 if 成为性能杀手

if (x > 0) {
    y = a + b;  // 路径 A
} else {
    y = a - b;  // 路径 B
}

    cmp  x, 0
    jle  .path_b    ; 条件跳转
    ; path A
    add  eax, ebx
    jmp  .done
.path_b:
    ; path B
    sub  eax, ebx
.done:

$ perf stat -e branches,branch-misses ./sorted_binary_search
 Performance counter stats for './sorted_binary_search':
     1,234,567,890      branches
        12,345,678      branch-misses      #    1.00% of all branches

$ perf stat -e branches,branch-misses ./random_binary_search
 Performance counter stats for './random_binary_search':
     1,234,567,890      branches
       185,185,185      branch-misses      #   15.00% of all branches

cmovcc dst, src    ; if (condition) dst = src; else dst unchanged

cmove   ; ZF=1   (equal / zero)
cmovne  ; ZF=0   (not equal / not zero)
cmovg   ; ZF=0 && SF=OF  (greater, signed)
cmovge  ; SF=OF  (greater or equal, signed)
cmovl   ; SF!=OF (less, signed)
cmovle  ; ZF=1 || SF!=OF (less or equal, signed)
cmova   ; CF=0 && ZF=0   (above, unsigned)
cmovae  ; CF=0   (above or equal, unsigned)
cmovb   ; CF=1   (below, unsigned)
cmovbe  ; CF=1 || ZF=1   (below or equal, unsigned)

// 编译器通常会自动转换为 cmov
int min(int a, int b) {
    return a < b ? a : b;
}

// GCC -O2 生成的代码：
// cmp  edi, esi
// cmovle eax, esi    ; 如果 a <= b，eax = b（即返回 a）
// 注：实际生成可能因版本略有不同

// 告诉编译器：x == 0 不太可能发生
if (__builtin_expect(x == 0, 0)) {
    handle_error();
}

// Linux 内核中常见的宏封装
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

if (unlikely(ptr == NULL)) {
    return -EINVAL;
}

if (x > 0) [[likely]] {
    // 编译器会把这个分支放在直通路径上
    process(x);
} else [[unlikely]] {
    handle_error();
}

// condition 为 0 或 1
// -0 = 0x00000000（全 0）
// -1 = 0xFFFFFFFF（全 1）
int32_t mask = -(int32_t)(condition);

// branchless: result = condition ? a : b
int32_t mask = -(int32_t)(a < b);
int32_t result = (a & mask) | (b & ~mask);

// branchless select: result = condition ? a : b
static inline int32_t select_branchless(int32_t condition, int32_t a, int32_t b) {
    // condition 必须是 0 或 1
    int32_t mask = -condition;
    return (a & mask) | (b & ~mask);
}

// 或者用异或的方式（可能少一条指令）
static inline int32_t select_xor(int32_t condition, int32_t a, int32_t b) {
    int32_t mask = -condition;
    return b ^ ((a ^ b) & mask);
}

// 标准版（带分支）
int min_branch(int a, int b) {
    return a < b ? a : b;
}

// 无分支版（纯算术）
int min_branchless(int a, int b) {
    int diff = a - b;
    // 如果 a < b，diff 为负数，算术右移得全 1
    int mask = diff >> 31;  // 算术右移：负数得 0xFFFFFFFF，非负得 0
    return b + (diff & mask);
    // a < b: mask = 0xFFFFFFFF, diff & mask = diff = a - b
    //        result = b + (a - b) = a ✓
    // a >= b: mask = 0, diff & mask = 0
    //         result = b + 0 = b ... 但 a >= b 时应返回 b ✓
}

// 无分支 max
int max_branchless(int a, int b) {
    int diff = a - b;
    int mask = diff >> 31;
    return a - (diff & mask);
}

// 安全的无分支 min（依赖编译器生成 cmov）
int min_safe(int a, int b) {
    int result = a;
    __asm__ volatile(
        "cmp %[b], %[result]\n\t"
        "cmovg %[b], %[result]\n\t"
        : [result] "+r" (result)
        : [b] "r" (b)
        : "cc"
    );
    return result;
}

// 标准版
int abs_branch(int x) {
    return x < 0 ? -x : x;
}

// 无分支版
int abs_branchless(int x) {
    int mask = x >> 31;        // 负数: 0xFFFFFFFF, 非负: 0x00000000
    return (x + mask) ^ mask;  // 负数: (x - 1) ^ (-1) = ~(x - 1) = -x
                               // 非负: (x + 0) ^ 0 = x
}

// 等价写法
int abs_branchless_v2(int x) {
    int mask = x >> 31;
    return (x ^ mask) - mask;
    // 负数: (x ^ -1) - (-1) = ~x + 1 = -x
    // 非负: (x ^ 0) - 0 = x
}

// clamp(x, lo, hi) = min(max(x, lo), hi)
int clamp_branchless(int x, int lo, int hi) {
    // 先 max(x, lo)
    int diff1 = x - lo;
    int mask1 = diff1 >> 31;
    int clamped_lo = lo - (diff1 & mask1);  // 如果 x < lo 则 lo，否则 x
    // 实际上这里有个巧妙之处：
    // x >= lo: mask1 = 0, result = lo - 0 = lo ... 错了！
    // 让我们用另一种方式：

    // 用 select 方式更清晰
    int t = x;
    // max(t, lo)
    int d1 = t - lo;
    int m1 = d1 >> 31;
    t = t - (d1 & m1);   // if t < lo: t = t - (t-lo) = lo; else t unchanged

    // min(t, hi)
    int d2 = t - hi;
    int m2 = ~(d2 >> 31); // 注意这里取反：非负时为 0xFFFFFFFF
    t = t - (d2 & m2);    // 错了，让我重新推导

    // 更直接的方式：组合两个无分支 min/max
    return min_branchless(max_branchless(x, lo), hi);
}

// 更实用的写法：直接用条件掩码
int clamp_v2(int x, int lo, int hi) {
    int mask_lo = -((int32_t)(x < lo));  // x < lo 时全 1
    int mask_hi = -((int32_t)(x > hi));  // x > hi 时全 1
    // x < lo: 返回 lo
    // x > hi: 返回 hi
    // 否则: 返回 x
    x = (lo & mask_lo) | (x & ~mask_lo);
    x = (hi & mask_hi) | (x & ~mask_hi);
    return x;
}

// sign(x) = -1 if x < 0, 0 if x == 0, 1 if x > 0
int sign_branchless(int x) {
    // (x > 0) - (x < 0)
    // x > 0:  1 - 0 =  1
    // x == 0: 0 - 0 =  0
    // x < 0:  0 - 1 = -1
    return (x > 0) - (x < 0);
    // 注意：编译器通常会把 (x > 0) 和 (x < 0) 编译为
    // 不带分支的 set 指令（setg, sets）
}

// 另一种方式：利用算术右移
int sign_branchless_v2(int x) {
    return (x >> 31) | ((unsigned)(-x) >> 31);
    // x < 0:  (0xFFFFFFFF) | (正数 >> 31) = -1 | 0或1 = -1
    // x > 0:  0 | ((-x) >> 31) = 0 | 1 = 1 （因为 -x 为负数，无符号右移最高位为 1... 不对）
    // 这个版本有陷阱，用第一种更安全
}

// if (condition) x += delta;
// 无分支版：
x += delta & (-(int32_t)condition);
// condition = 1: mask = -1 = 0xFFFFFFFF, delta & mask = delta, x += delta
// condition = 0: mask = 0, delta & mask = 0, x += 0

// 常见应用：计数
int count_positives_branchless(const int *arr, int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        count += (arr[i] > 0);  // 无分支：(arr[i] > 0) 产生 0 或 1
    }
    return count;
}

// 标准二分查找
int binary_search_standard(const int *arr, int n, int key) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == key) return mid;      // 分支 1
        else if (arr[mid] < key) lo = mid + 1; // 分支 2
        else hi = mid - 1;
    }
    return -1;
}

// 无分支二分查找（lower_bound 语义）
int binary_search_branchless(const int *arr, int n, int key) {
    const int *base = arr;
    int len = n;

    while (len > 1) {
        int half = len / 2;
        // 无分支：如果 base[half] < key，base 前进 half 步
        // __builtin_expect 提示编译器不要对此做分支预测优化
        base += (base[half] < key) * half;
        len -= half;
    }
    return (*base < key) + (base - arr);
}

.loop:
    mov   ecx, edx        ; ecx = len
    shr   ecx, 1          ; half = len / 2
    mov   eax, [rdi + rcx*4] ; load base[half]
    cmp   eax, esi        ; compare with key
    lea   rax, [rdi + rcx*4] ; rax = base + half（预计算）
    cmovl rdi, rax        ; if base[half] < key: base = base + half
    sub   edx, ecx        ; len -= half
    cmp   edx, 1
    jg    .loop

// 将排序数组转换为 Eytzinger 布局
void build_eytzinger(const int *sorted, int *eyt, int n, int i, int *k) {
    if (i <= n) {
        build_eytzinger(sorted, eyt, n, 2 * i, k);
        eyt[i] = sorted[(*k)++];
        build_eytzinger(sorted, eyt, n, 2 * i + 1, k);
    }
}

// Eytzinger 布局的无分支二分查找
int eytzinger_search(const int *eyt, int n, int key) {
    int i = 1;
    while (i <= n) {
        // 预取下一层的两个孩子节点
        __builtin_prefetch(&eyt[2 * i]);
        __builtin_prefetch(&eyt[2 * i + 1]);

        // 无分支：i = 2*i + (eyt[i] < key)
        // 如果 eyt[i] < key，走右孩子 (2*i+1)
        // 否则走左孩子 (2*i)
        i = 2 * i + (eyt[i] < key);
    }
    // i 现在指向叶子下方，需要回溯找到实际位置
    // 右移直到 i 是偶数位（从左孩子来的）或者 i 回到根
    i >>= __builtin_ffs(~i);  // 找到最低的 0 bit
    return (i <= n) ? i : -1;
}

// 标准 Lomuto partition
int lomuto_partition(int *arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {       // 这个分支几乎不可预测！
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[hi]);
    return i;
}

// 无分支 Lomuto partition（简化版）
int branchless_lomuto(int *arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo;

    for (int j = lo; j < hi; j++) {
        // 无分支交换：总是做"交换"操作，但当条件不满足时
        // 交换的是 arr[i] 和 arr[i] 自己（no-op）
        int should_swap = (arr[j] <= pivot);

        // 无条件交换 arr[i] 和 arr[j]
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;

        // 无分支递增：i += should_swap
        // 如果 should_swap = 0，下一次循环会把 arr[i]（刚放入的值）
        // 再换走，相当于撤销了这次交换
        i += should_swap;
    }
    // 最后把 pivot 放到正确位置
    int tmp = arr[i];
    arr[i] = arr[hi];
    arr[hi] = tmp;
    return i;
}

#define BLOCK_SIZE 64
unsigned char offsets[BLOCK_SIZE];
int num = 0;

for (int k = start; k < start + BLOCK_SIZE; k++) {
    offsets[num] = (unsigned char)(k - start);
    num += (arr[k] >= pivot);  // 无分支递增
}

#include <immintrin.h>

// SSE2：比较 4 个 int
__m128i a = _mm_set_epi32(10, -5, 3, -8);
__m128i zero = _mm_setzero_si128();
__m128i mask = _mm_cmpgt_epi32(a, zero);
// mask = [0xFFFFFFFF, 0x00000000, 0xFFFFFFFF, 0x00000000]
//         (10 > 0)    (-5 > 0)    (3 > 0)     (-8 > 0)

// 用掩码选择：正数保留，负数置零
__m128i result = _mm_and_si128(a, mask);
// result = [10, 0, 3, 0]

// 向量化的 min
__m256i vec_min(__m256i a, __m256i b) {
    // 直接用 _mm256_min_epi32 即可，这里展示原理
    __m256i mask = _mm256_cmpgt_epi32(a, b);  // a > b 的位置为全 1
    return _mm256_blendv_epi8(a, b, mask);     // mask 为 1 的位置选 b
    // 等价于：逐元素 (a > b) ? b : a = min(a, b)
}

// 计数数组中正数的个数（SIMD 版）
int count_positives_simd(const int *arr, int n) {
    __m256i count = _mm256_setzero_si256();
    __m256i zero = _mm256_setzero_si256();

    int i = 0;
    for (; i + 8 <= n; i += 8) {
        __m256i v = _mm256_loadu_si256((__m256i *)(arr + i));
        __m256i mask = _mm256_cmpgt_epi32(v, zero);
        // mask 中每个元素为 0xFFFFFFFF（-1）或 0x00000000（0）
        // 减去 mask 就是加 1 或加 0
        count = _mm256_sub_epi32(count, mask);
    }

    // 水平求和
    int result[8];
    _mm256_storeu_si256((__m256i *)result, count);
    int total = 0;
    for (int j = 0; j < 8; j++) total += result[j];

    // 处理剩余元素
    for (; i < n; i++) total += (arr[i] > 0);

    return total;
}

// 场景：过滤稀疏数组中的非零元素
// 大部分元素为 0，所以 (arr[i] != 0) 大约 99% 为 false
void filter_sparse_branch(const int *arr, int *out, int n, int *count) {
    int c = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] != 0) {  // 高度可预测！保留分支
            out[c++] = arr[i];
        }
    }
    *count = c;
}

// 如果用无分支版本：
void filter_sparse_branchless(const int *arr, int *out, int n, int *count) {
    int c = 0;
    for (int i = 0; i < n; i++) {
        out[c] = arr[i];
        c += (arr[i] != 0);  // 无分支，但总是写 out[c]
    }
    *count = c;
}
// 无分支版本总是写入 out[c]，即使不需要
// 这增加了不必要的存储带宽开销
// 而且 cmov 引入的数据依赖链会限制乱序执行

// 分支版本：CPU 可以推测执行一条路径
if (expensive_condition) {
    result = complex_computation_a();  // 即使 condition 未知，CPU 可以推测执行这个
} else {
    result = complex_computation_b();
}

// cmov 版本：两个计算都必须完成
int a = complex_computation_a();  // 必须执行
int b = complex_computation_b();  // 也必须执行
result = expensive_condition ? a : b;

// 编译器知道 p != NULL 在这个路径上
if (p != NULL) {
    // 编译器可以假设 p != NULL，省略后续的 NULL 检查
    // 向量化器也可以更激进
    for (int i = 0; i < n; i++) {
        p[i] *= 2;
    }
}

// 带分支版本
long long sum_branch(const int *arr, int n, int threshold) {
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] < threshold) sum += arr[i];
    }
    return sum;
}

// 无分支版本
long long sum_branchless(const int *arr, int n, int threshold) {
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        int mask = -(arr[i] < threshold);
        sum += arr[i] & mask;
    }
    return sum;
}
// 数组元素为 rand() % 256，threshold 从 0 变到 256

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h>

/* 无分支 lower_bound */
static int branchless_lower_bound(const int *arr, int n, int key) {
    const int *base = arr;
    int len = n;
    while (len > 1) {
        int half = len / 2;
        base += (base[half] < key) * half;
        len -= half;
    }
    return (int)(base - arr) + (*base < key);
}

/* 标准 lower_bound（对照组） */
static int standard_lower_bound(const int *arr, int n, int key) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

/* Eytzinger 布局构建与查找 */
static void eytzinger_build_impl(const int *sorted, int *eyt,
                                  int n, int node, int *idx) {
    if (node <= n) {
        eytzinger_build_impl(sorted, eyt, n, 2 * node, idx);
        eyt[node] = sorted[*idx]; (*idx)++;
        eytzinger_build_impl(sorted, eyt, n, 2 * node + 1, idx);
    }
}

static int eytzinger_lower_bound(const int *eyt, int n, int key) {
    int i = 1;
    while (i <= n) {
        __builtin_prefetch(&eyt[2 * i]);
        i = 2 * i + (eyt[i] < key);
    }
    i >>= __builtin_ctz(~(unsigned)i);
    return (i == 0) ? n : i;
}

/* 无分支 Lomuto partition */
static inline void swap_int(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

static int branchless_partition(int *arr, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] < arr[lo]) swap_int(&arr[lo], &arr[mid]);
    if (arr[hi] < arr[lo])  swap_int(&arr[lo], &arr[hi]);
    if (arr[mid] < arr[hi]) swap_int(&arr[mid], &arr[hi]);
    int pivot = arr[hi];
    int i = lo;
    for (int j = lo; j < hi; j++) {
        int should_swap = (arr[j] <= pivot);
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        i += should_swap;
    }
    swap_int(&arr[i], &arr[hi]);
    return i;
}

/* 无分支快排（含 insertion sort 收尾） */
#define INSERTION_THRESHOLD 24

static void insertion_sort(int *arr, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++) {
        int key = arr[i], j = i - 1;
        while (j >= lo && arr[j] > key) { arr[j + 1] = arr[j]; j--; }
        arr[j + 1] = key;
    }
}

static void bqsort(int *arr, int lo, int hi, int depth) {
    while (hi - lo >= INSERTION_THRESHOLD) {
        if (depth == 0) break;
        depth--;
        int p = branchless_partition(arr, lo, hi);
        if (p - lo < hi - p) { bqsort(arr, lo, p - 1, depth); lo = p + 1; }
        else                  { bqsort(arr, p + 1, hi, depth); hi = p - 1; }
    }
    if (hi > lo) insertion_sort(arr, lo, hi);
}

static void branchless_quicksort(int *arr, int n) {
    if (n <= 1) return;
    int d = 0; for (int t = n; t > 0; t >>= 1) d++;
    bqsort(arr, 0, n - 1, d * 2);
}

/* 基准测试 */
static double ms(clock_t s, clock_t e) {
    return (double)(e - s) / CLOCKS_PER_SEC * 1000.0;
}

int main(void) {
    const int N = 1 << 23, Q = 1 << 20;
    int *sorted = malloc(N * sizeof(int));
    int *eyt    = calloc(N + 1, sizeof(int));
    int *queries = malloc(Q * sizeof(int));

    for (int i = 0; i < N; i++) sorted[i] = 2 * i + 1;
    int idx = 0;
    eytzinger_build_impl(sorted, eyt, N, 1, &idx);
    srand(42);
    for (int i = 0; i < Q; i++) queries[i] = rand() % (2 * N);

    volatile int sink = 0;
    clock_t s, e;

    s = clock();
    for (int i = 0; i < Q; i++) sink += standard_lower_bound(sorted, N, queries[i]);
    e = clock();
    printf("standard:    %7.2f ms\n", ms(s, e));

    s = clock();
    for (int i = 0; i < Q; i++) sink += branchless_lower_bound(sorted, N, queries[i]);
    e = clock();
    printf("branchless:  %7.2f ms\n", ms(s, e));

    s = clock();
    for (int i = 0; i < Q; i++) sink += eytzinger_lower_bound(eyt, N, queries[i]);
    e = clock();
    printf("eytzinger:   %7.2f ms\n", ms(s, e));

    /* 排序测试 */
    int *data = malloc(N * sizeof(int));
    int *copy = malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) data[i] = rand();

    memcpy(copy, data, N * sizeof(int));
    s = clock(); branchless_quicksort(copy, N); e = clock();
    printf("bqsort:      %7.2f ms\n", ms(s, e));

    int ok = 1;
    for (int i = 1; i < N; i++) if (copy[i] < copy[i-1]) { ok = 0; break; }
    printf("correctness: %s\n", ok ? "PASS" : "FAIL");

    free(sorted); free(eyt); free(queries); free(data); free(copy);
    return 0;
}

# GCC：-O2 即可生成 cmov，-O3 更激进
gcc -O2 -march=native -o bench bench.c

# Clang：通常比 GCC 更倾向于使用 cmov
clang -O2 -march=native -o bench bench.c

# PGO（Profile-Guided Optimization）：让编译器根据实际运行数据决定
gcc -O2 -fprofile-generate -o bench bench.c
./bench                                  # 运行生成 profile 数据
gcc -O2 -fprofile-use -o bench bench.c   # 用 profile 数据重新编译

// 计数器循环递增：i = (i + 1) % n
// n 是 2 的幂时用掩码
i = (i + 1) & (n - 1);

// n 不是 2 的幂时
int next = i + 1;
i = next - (n & -(next == n));

// 并行归约（无分支，无循环）
int popcount_branchless(uint32_t x) {
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    return (x * 0x01010101) >> 24;
}
// 现代 CPU 直接用 __builtin_popcount 编译为 popcnt 指令

// ceil(a / b)，a >= 0, b > 0
int ceildiv(int a, int b) {
    return a / b + (a % b != 0);  // (a % b != 0) 产生 0 或 1，无分支
}

// 替代多路 if-else
int utf8_byte_length(unsigned char c) {
    static const uint8_t table[256] = {
        // 0x00-0x7F: 1, 0x80-0xBF: 1, 0xC0-0xDF: 2, 0xE0-0xEF: 3, 0xF0-0xFF: 4
        [0x00 ... 0xBF] = 1, [0xC0 ... 0xDF] = 2,
        [0xE0 ... 0xEF] = 3, [0xF0 ... 0xFF] = 4,
    };
    return table[c];
}