利用AVX-512或AVX-2对大内存块执行1比特计数（Population Count）

嘿，这事儿我熟！用AVX-512的VPOPCNTDQ来统计大内存里的1比特总数绝对是效率天花板级的方案，我给你一步步捋清楚怎么实现，从基础概念到可运行的代码都安排明白。

核心原理快速唠明白 #

• VPOPCNTDQ是AVX-512F扩展里的指令，它能一次性处理**512位（也就是64字节）**的内存块：把这512位拆成8个64位双字，分别计算每个双字里的1比特数量，结果直接存在对应的64位位置上。
• 支持AVX-512的CPU（比如Intel Skylake-X及以后的型号）能每周期执行一次这个指令，配合高效的内存加载，处理几GB的内存都不在话下。

实现步骤（用Intel Intrinsics，比手写汇编友好太多） #

我推荐用编译器提供的Intel Intrinsics来写，不用自己抠汇编指令，代码可读性和兼容性都更好。

1. 先搞定编译环境 #

• 确保你的编译器支持AVX-512：GCC 7+、Clang 6+、MSVC 2017+都没问题。
• 编译时要加对应选项：
  • GCC/Clang：加-mavx512f（因为VPOPCNTDQ属于AVX-512F基础扩展）
  • MSVC：加/arch:AVX512

2. 完整可运行代码示例 #

直接上代码，后面给你拆细节：

#include <stdint.h>
#include <immintrin.h>

// 用AVX-512统计内存块中1比特的总数
uint64_t count_bits_avx512(const uint8_t* ptr, size_t size) {
    uint64_t total_bits = 0;
    const size_t vec_bytes = 64; // 512位向量对应64字节
    const size_t full_blocks = size / vec_bytes;

    // 批量处理64字节的整块内存
    for (size_t i = 0; i < full_blocks; ++i) {
        // 加载64字节到512位向量（_loadu支持未对齐内存）
        __m512i mem_vec = _mm512_loadu_si512((const __m512i*)(ptr + i * vec_bytes));
        // 对每个64位元素计算1比特数量，结果存在新的512位向量里
        __m512i popcnt_results = _mm512_popcnt_epi64(mem_vec);
        // 把向量里的8个64位结果累加起来，加到总数里
        total_bits += _mm512_reduce_add_epi64(popcnt_results);
    }

    // 处理剩余的不足64字节的部分
    const uint8_t* remaining_ptr = ptr + full_blocks * vec_bytes;
    size_t remaining_size = size % vec_bytes;
    for (size_t i = 0; i < remaining_size; ++i) {
        // 用编译器内置函数处理单个字节的popcount
        total_bits += __builtin_popcount(remaining_ptr[i]);
    }

    return total_bits;
}

3. 代码细节拆解 #

• _mm512_loadu_si512：加载未对齐的512位内存块。如果你的内存是按64字节对齐的（比如用posix_memalign或_aligned_malloc分配的），可以换成_mm512_load_si512，性能会再提一档。
• _mm512_popcnt_epi64：这就是VPOPCNTDQ指令的直接封装，帮你完成每个64位元素的比特计数。
• _mm512_reduce_add_epi64：把512位向量里的8个64位整数一次性累加起来，编译器会自动生成高效的归约代码，比你手动拆向量加方便多了。
• 剩余部分用__builtin_popcount：这是编译器的内置函数，效率很高，不用自己写字节的比特计数逻辑。

4. 性能优化小技巧 #

• 内存对齐：尽量让你的内存块按64字节对齐，对齐的内存加载指令延迟更低，能进一步提升吞吐量。
• 循环展开：现代编译器一般会自动做循环展开，但如果想手动优化，可以把循环里的几次迭代合并，减少循环控制的开销。
• 并行处理：如果内存块特别大（比如几GB），可以用OpenMP把内存分成多个块并行处理。比如在GCC里加-fopenmp，然后给批量处理的循环加#pragma omp parallel for reduction(+:total_bits)，多核CPU能直接把速度拉满。

5. 验证正确性的小测试 #

写个简单的测试函数，用普通方法和AVX-512方法对比结果，确保没写错：

#include <stdio.h>

// 普通方法（用来验证结果）
uint64_t count_bits_naive(const uint8_t* ptr, size_t size) {
    uint64_t total = 0;
    for (size_t i = 0; i < size; ++i) {
        total += __builtin_popcount(ptr[i]);
    }
    return total;
}

int main() {
    uint8_t test_buffer[256 * 1024] = {0}; // 256 KiB测试内存
    // 随便填充一些测试数据
    for (size_t i = 0; i < sizeof(test_buffer); ++i) {
        test_buffer[i] = i % 255;
    }

    uint64_t naive_count = count_bits_naive(test_buffer, sizeof(test_buffer));
    uint64_t avx512_count = count_bits_avx512(test_buffer, sizeof(test_buffer));

    printf("普通方法计数: %lu\n", naive_count);
    printf("AVX-512方法计数: %lu\n", avx512_count);
    printf("结果是否一致: %s\n", naive_count == avx512_count ? "是" : "否");

    return 0;
}

编译运行后，如果输出“结果是否一致: 是”，就说明代码没问题啦。

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