如何以最优性能对大容量u64向量执行按位或运算？

实验背景与目标 #

我正在做一项思想实验，目标是找出单线程下对1M个u64元素的位掩码执行按位或运算的最高效实现方式。测试硬件为搭载i7-8750H CPU（基础主频2.2GHz，支持AVX2但不支持AVX-512）的x86-64笔记本电脑。我知道将位掩码压缩为Roaring Bitmap格式可能进一步提速，但目前想先明确当前的简单实现是否存在明显性能瓶颈。

理论性能上限估算 #

假设数据已全部加载到寄存器中，_mm256_or_si256指令可一次对4个u64执行按位或运算。按CPU负载下主频3GHz、每周期执行1次运算计算，1M个u64的理论耗时约为83µs。

当前实现与性能现状 #

我生成了核心C++代码，编译命令为：

g++ -O3 -mavx2 -o experiment main.cpp

测试结果显示：10000次迭代耗时约9秒，单次迭代耗时900µs，比理论值慢10倍以上。尝试循环展开后未获得明显性能收益。

作为对比，仅操作寄存器的测试代码（无内存读写）表现接近理论值：100000次迭代耗时约9秒，单次迭代约90µs。

核心代码 #

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <cstdint>
#include <immintrin.h>

std::vector<uint64_t> generate_random_u64s(size_t amount) {
    std::vector<uint64_t> random_u64s;
    random_u64s.reserve(amount);
    std::random_device rd; // Obtain a random number from hardware
    std::mt19937_64 eng(rd()); // Seed the generator
    std::uniform_int_distribution<uint64_t> distr; // Define the range

    for (size_t i = 0; i < amount; ++i) {
        random_u64s.push_back(distr(eng));
    }
    return random_u64s;
}

void avx_bitwise_or(
    const std::vector<uint64_t>& vector1, 
    const std::vector<uint64_t>& vector2, 
    std::vector<uint64_t>& result
) {
    size_t size = vector1.size();
    
    // Ensure result has enough space
    if (result.size() != size) {
        result.resize(size);
    }

    size_t i = 0;
    for (; i + 4 <= size; i += 4) {
        // Prefetch data into CPU cache
        _mm_prefetch(reinterpret_cast<const char*>(&vector1[i + 256]), _MM_HINT_T0);
        _mm_prefetch(reinterpret_cast<const char*>(&vector2[i + 256]), _MM_HINT_T0);

        // Load vectors using AVX
        __m256i vec1 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(&vector1[i]));
        __m256i vec2 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(&vector2[i]));

        // Perform bitwise OR operation
        __m256i vec_result = _mm256_or_si256(vec1, vec2);

        // Use non-temporal store to write result back to memory bypassing CPU cache
        _mm256_stream_si256(reinterpret_cast<__m256i*>(&result[i]), vec_result);
    }

    // Handle remaining elements that don't fit in AVX registers
    for (; i < size; ++i) {
        result[i] = vector1[i] | vector2[i];
    }
}

int main() {
    std::cout << "Starting" << std::endl;
    const size_t size = 1'000'000;
    auto vector1 = generate_random_u64s(size);
    auto vector2 = generate_random_u64s(size);

    auto result = std::vector<uint64_t>(size);

    auto start = std::chrono::high_resolution_clock::now();
    const int repetitions = 10000;

    for (int i = 0; i < repetitions; ++i) {
        avx_bitwise_or(vector1, vector2, result);
    }

    auto duration = std::chrono::high_resolution_clock::now() - start;

    uint32_t popcnt = 0;
    for (const auto& x : result) {
        popcnt += __builtin_popcountll(x); // Count the number of set bits (1s)
    }

    std::cout << "Popcnt is: " << popcnt << std::endl;
    std::cout << "Time elapsed is: " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << " ms" << std::endl;

    return 0;
}

问题 #

如何进一步提升涉及内存读写的按位或运算代码性能？当前实现还有哪些可优化的空间？

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