随机输入下分支操作为何比查表操作更快？

近期我在为将随机值数组buf原地转换为十六进制字符序列的代码做基准测试，用于PRNG（伪随机数生成器）相关场景。原本预期输入完全随机时，分支预测器失效，查表操作会更快，但测试结果却显示带分支的实现远快于查表实现，想请教原因。

测试代码 #

#define _POSIX_C_SOURCE 199309L

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

static const char HEX_CHARS[16] = "0123456789ABCDEF";

static void a(size_t n, char buf[static n]) {
    // 单循环，带分支
    for (size_t i = 0; i < n; i++) {
        buf[i] &= 15;
        buf[i] = buf[i] < 10
                ? buf[i] + '0'
                : buf[i] + 'A' - 10;
    }
}

static void b(size_t n, char buf[static n]) {
    // 双循环，带分支
    for (size_t i = 0; i < n; i++)
        buf[i] &= 15;
    for (size_t i = 0; i < n; i++)
        buf[i] = buf[i] < 10
                ? buf[i] + '0'
                : buf[i] + 'A' - 10;
}

static void c(size_t n, char buf[static n]) {
    // 单循环，查表
    for (size_t i = 0; i < n; i++)
        buf[i] = HEX_CHARS[buf[i] & 15];
}

static void d(size_t n, char buf[static n]) {
    // 双循环，查表
    for (size_t i = 0; i < n; i++)
        buf[i] &= 0xF;
    for (size_t i = 0; i < n; i++)
        buf[i] = HEX_CHARS[(size_t)buf[i]];
}

static void test(
    const size_t n,
    const char input[const static n],
    const char *const name,
    void (*const fn)(size_t n, char buf[static n])
) {
    const size_t M = 1 << 16;

    char *buf = calloc(n, 1);
    memmove(buf, input, n);

    double ns_total = 0;
    for (size_t i = 0; i < M; i++) {
        struct timespec t_start, t_end;
        clock_gettime(CLOCK_MONOTONIC, &t_start);
        fn(n, buf);
        clock_gettime(CLOCK_MONOTONIC, &t_end);
        double ns_start = (double)t_start.tv_sec * 1e9 + (double)t_start.tv_nsec;
        double ns_end = (double)t_end.tv_sec * 1e9 + (double)t_end.tv_nsec;
        double ns_dur = ns_end - ns_start;
        ns_total += ns_dur;
    }

    printf("%s() took %f sec (avg %f ms)\n", name, ns_total * 1e-9, ns_total / (double) M * 1e-6);

    free(buf);
}

int main(void) {
    const size_t N = 1UL << 24;

    // 生成随机数据
    char *input = calloc(N, 1);
    FILE *file = fopen("/dev/urandom", "r");
    if (fread(input, 1, N, file) != N) {
        perror("fread");
        abort();
    }
    fclose(file);

    test(N, input, "a", a);
    test(N, input, "b", b);
    test(N, input, "c", c);
    test(N, input, "d", d);

    free(input);
}

测试结果 #

测试平台：Ryzen 9 7940HS

-O3优化 #

a() took 41.452250 sec (avg 0.632511 ms)
b() took 68.869114 sec (avg 1.050859 ms)
c() took 323.392966 sec (avg 4.934585 ms)
d() took 365.612924 sec (avg 5.578810 ms)

-O3 -march=native优化 #

a() took 30.370241 sec (avg 0.463413 ms)
b() took 59.591973 sec (avg 0.909301 ms)
c() took 315.819261 sec (avg 4.819019 ms)
d() took 332.411909 sec (avg 5.072203 ms)

• 分支被编译器优化为无分支指令：在-O3优化级别下，编译器会把代码里的三元分支转换成cmov（条件移动）这类无分支算术指令，而非真正的跳转分支。条件移动不会触发分支预测失败的惩罚，执行效率和无分支计算完全一致，这是分支版本快的核心原因。
• 查表的内存访问瓶颈：虽然HEX_CHARS只有16字节，能完全放进L1缓存，但随机输入导致查表索引完全无规律，CPU的预取机制彻底失效，每次查表都要等待缓存读取完成。而分支版本的代码只需要寄存器级的算术运算，完全不需要额外内存访问，速度自然碾压查表。
• 双循环的额外开销：不管是分支还是查表版本，双循环（b()、d()）都比单循环慢——双循环需要遍历数组两次，带来额外的内存遍历、循环初始化和条件判断开销。
• 指令级并行的差异：分支版本被优化为条件移动后，指令间依赖关系弱，CPU可以通过超标量执行同时处理多条指令；而查表版本受限于内存访问延迟，指令级并行度被严重限制，整体执行效率下降。

内容的提问来源于stack exchange，提问作者Anon