Replacing a 32-bit loop counter with 64-bit introduces crazy performance deviations with _mm_popcnt_u64 on Intel CPUs

Replacing a 32-bit loop counter with 64-bit introduces crazy performance deviations with _mm_popcnt_u64 on Intel CPUs

技术背景

在使用 _mm_popcnt_u64 指令时，将 32 位循环计数器替换为 64 位会在 Intel CPU 上引入疯狂的性能偏差。这主要是由于 popcnt 指令存在虚假数据依赖问题，而编译器可能并未意识到这一点。

实现步骤

1. 确认虚假数据依赖

在 Sandy/Ivy Bridge、Haswell 和 Skylake 等处理器上，popcnt src, dest 指令对目标寄存器 dest 存在虚假依赖。尽管该指令只进行写入操作，但它会等待 dest 准备好后才执行。Intel 已将此问题记录为勘误 [HSD146 (Haswell)][1] 和 [SKL029 (Skylake)][2]。

2. 测试不同寄存器使用情况

通过内联汇编绕过编译器，测试不同寄存器使用情况对性能的影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {
    using namespace std;
    uint64_t size = 1 << 20;
    uint64_t* buffer = new uint64_t[size / 8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i = 0; i < size; ++i) charbuffer[i] = rand() % 256;

    uint64_t count, duration;
    chrono::time_point<chrono::system_clock> startP, endP;
    {
        uint64_t c0 = 0;
        uint64_t c1 = 0;
        uint64_t c2 = 0;
        uint64_t c3 = 0;
        startP = chrono::system_clock::now();
        for (unsigned k = 0; k < 10000; k++) {
            for (uint64_t i = 0; i < size / 8; i += 4) {
                uint64_t r0 = buffer[i + 0];
                uint64_t r1 = buffer[i + 1];
                uint64_t r2 = buffer[i + 2];
                uint64_t r3 = buffer[i + 3];
                __asm__(
                    "popcnt %4, %4  \n\t"
                    "add %4, %0     \n\t"
                    "popcnt %5, %5  \n\t"
                    "add %5, %1     \n\t"
                    "popcnt %6, %6  \n\t"
                    "add %6, %2     \n\t"
                    "popcnt %7, %7  \n\t"
                    "add %7, %3     \n\t"
                    : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                    : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                );
            }
        }
        count = c0 + c1 + c2 + c3;
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP - startP).count();
        cout << "No Chain\t" << count << '\t' << (duration / 1.0E9) << " sec \t"
             << (10000.0 * size) / (duration) << " GB/s" << endl;
    }
    {
        uint64_t c0 = 0;
        uint64_t c1 = 0;
        uint64_t c2 = 0;
        uint64_t c3 = 0;
        startP = chrono::system_clock::now();
        for (unsigned k = 0; k < 10000; k++) {
            for (uint64_t i = 0; i < size / 8; i += 4) {
                uint64_t r0 = buffer[i + 0];
                uint64_t r1 = buffer[i + 1];
                uint64_t r2 = buffer[i + 2];
                uint64_t r3 = buffer[i + 3];
                __asm__(
                    "popcnt %4, %%rax   \n\t"
                    "add %%rax, %0      \n\t"
                    "popcnt %5, %%rax   \n\t"
                    "add %%rax, %1      \n\t"
                    "popcnt %6, %%rax   \n\t"
                    "add %%rax, %2      \n\t"
                    "popcnt %7, %%rax   \n\t"
                    "add %%rax, %3      \n\t"
                    : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                    : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                    : "rax"
                );
            }
        }
        count = c0 + c1 + c2 + c3;
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP - startP).count();
        cout << "Chain 4   \t" << count << '\t' << (duration / 1.0E9) << " sec \t"
             << (10000.0 * size) / (duration) << " GB/s" << endl;
    }
    {
        uint64_t c0 = 0;
        uint64_t c1 = 0;
        uint64_t c2 = 0;
        uint64_t c3 = 0;
        startP = chrono::system_clock::now();
        for (unsigned k = 0; k < 10000; k++) {
            for (uint64_t i = 0; i < size / 8; i += 4) {
                uint64_t r0 = buffer[i + 0];
                uint64_t r1 = buffer[i + 1];
                uint64_t r2 = buffer[i + 2];
                uint64_t r3 = buffer[i + 3];
                __asm__(
                    "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                    "popcnt %4, %%rax   \n\t"
                    "add %%rax, %0      \n\t"
                    "popcnt %5, %%rax   \n\t"
                    "add %%rax, %1      \n\t"
                    "popcnt %6, %%rax   \n\t"
                    "add %%rax, %2      \n\t"
                    "popcnt %7, %%rax   \n\t"
                    "add %%rax, %3      \n\t"
                    : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                    : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                    : "rax"
                );
            }
        }
        count = c0 + c1 + c2 + c3;
        endP = chrono::system_clock::now();
        duration = chrono::duration_cast<std::chrono::nanoseconds>(endP - startP).count();
        cout << "Broken Chain\t" << count << '\t' << (duration / 1.0E9) << " sec \t"
             << (10000.0 * size) / (duration) << " GB/s" << endl;
    }

    free(charbuffer);
}

核心代码解释

  • 不同寄存器使用情况：
    • 不同寄存器：每个 popcnt 指令使用不同的寄存器，避免了虚假依赖，性能较高。
    • 相同寄存器：所有 popcnt 指令使用相同的寄存器，引入了虚假依赖，性能较低。
    • 相同寄存器但打破依赖链：在每次迭代开始时将寄存器清零，打破了跨迭代的依赖，性能有所提升。

最佳实践

  • 使用 __builtin 内联函数：使用 __builtin_popcountll 可以避免因虚假依赖导致的意外长循环依赖。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdint.h>
#include <stddef.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>

uint64_t builtin_popcnt(const uint64_t* buf, size_t len) {
    uint64_t cnt = 0;
    for (size_t i = 0; i < len; ++i) {
        cnt += __builtin_popcountll(buf[i]);
    }
    return cnt;
}

int main(int argc, char** argv) {
    if (argc != 2) {
        printf("Usage: %s <buffer size in MB>\n", argv[0]);
        return -1;
    }
    uint64_t size = atol(argv[1]) << 20;
    uint64_t* buffer = (uint64_t*)malloc((size / 8) * sizeof(*buffer));

    // Spoil copy-on-write memory allocation on *nix
    for (size_t i = 0; i < (size / 8); i++) {
        buffer[i] = random();
    }
    uint64_t count = 0;
    clock_t tic = clock();
    for (size_t i = 0; i < 10000; ++i) {
        count += builtin_popcnt(buffer, size / 8);
    }
    clock_t toc = clock();
    printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0 * size) / (((double)(toc - tic) * 1e+9) / CLOCKS_PER_SEC)));
    return 0;
}
  • 拆分计数变量：将计数结果累加到不同的变量中，最后再求和，避免虚假依赖。

常见问题

  • 编译器未意识到虚假依赖：大多数编译器（如 Clang、MSVC 和 Intel 的 ICC）尚未意识到 popcnt 指令的虚假依赖问题，不会生成补偿代码。
  • CPU 存在虚假依赖的原因：popcnt 与 bsf / bsr 在同一执行单元运行，而 bsf / bsr 存在输出依赖，可能是为了方便硬件设计而导致 popcnt 也存在虚假依赖。
  • static 变量改变性能的原因：推测是由于 static 变量存储在全局数据空间，而普通局部变量存储在栈上，编译器对栈上内存位置的引用方式可能导致性能差异。

性能评估建议

  • 估算峰值性能：参考 Intel 架构优化手册，查看 POPCNT 指令的延迟和吞吐量，计算最佳可能带宽。
  • 分析编译器生成的代码：查看循环中所有指令的吞吐量，评估生成代码的最佳性能。
  • 考虑数据依赖：分析指令之间的数据依赖关系，避免因数据依赖导致的延迟。

总结

在使用 _mm_popcnt_u64 指令时，要注意 popcnt 指令的虚假依赖问题。通过合理使用寄存器、拆分计数变量和使用 __builtin 内联函数等方法，可以避免虚假依赖，提高性能。同时，不同编译器对该问题的处理能力不同，在选择编译器时需要考虑这一点。此外，在进行性能评估时，要综合考虑指令的延迟、吞吐量和数据依赖等因素。

系统编程 > 性能优化
#C++ #系统编程 #Intel CPU #popcnt指令 #性能偏差
Replacing a 32-bit loop counter with 64-bit introduces crazy performance deviations with _mm_popcnt_u64 on Intel CPUs
https://119291.xyz/posts/replacing-32-bit-loop-counter-with-64-bit-performance-deviations/
作者
ww
发布于
2025年5月29日
许可协议