为何LLVM无法自动向量化数组比较并写入std::vector<bool>的代码？

为什么std::vector<bool>版本无法被向量化？ #

std::vector<bool>是C++标准库中特化的位压缩容器，它并非真正的数组——每个"元素"仅占用1个比特位，而非普通bool数组中每个元素占用的1字节（或更多）。

这种位级别的存储带来了两个阻碍向量化的问题：

• 访问单个元素需要额外的位操作（移位、掩码运算），SIMD指令通常以字节/字/双字为粒度批量处理，对位级别的零散操作难以生成高效的向量化代码。
• 位压缩存储的内存访问模式是非对齐、非连续的（相对于字节粒度），编译器无法轻易识别出可批量处理的内存块，自然无法触发向量化优化。

而普通bool数组的每个元素是独立的字节，内存访问连续且对齐友好，编译器可以直接用SIMD指令批量比较数组元素，并将结果直接写入内存，因此能顺利完成向量化。

最高效的实现方案 #

方案1：先向量化比较，再打包到位容器 #

先使用字节粒度的数组（如std::vector<uint8_t>）完成可向量化的比较，再将结果打包到std::vector<bool>中。这种方式兼顾了向量化的性能和位容器的内存效率：

#include <vector>
#include <cstdint>

void compare_and_pack(int* lhs, int* rhs, int len, std::vector<bool>& dst) {
    dst.resize(len);
    std::vector<uint8_t> temp(len);

    // 这部分会被编译器自动向量化
    for (int i = 0; i < len; ++i) {
        temp[i] = static_cast<uint8_t>(lhs[i] == rhs[i]);
    }

    // 将字节数组打包到位容器
    for (int i = 0; i < len; ++i) {
        dst[i] = temp[i];
    }
}

如果要进一步优化打包步骤，可以按字节批量处理，减少逐位操作的开销：

#include <vector>
#include <cstdint>

void compare_and_pack(int* lhs, int* rhs, int len, std::vector<bool>& dst) {
    dst.resize(len);
    const int bits_per_byte = 8;
    int full_bytes = len / bits_per_byte;
    int remaining_bits = len % bits_per_byte;

    std::vector<uint8_t> temp(full_bytes + (remaining_bits > 0 ? 1 : 0), 0);

    // 向量化比较并直接生成位掩码
    for (int i = 0; i < len; ++i) {
        if (lhs[i] == rhs[i]) {
            temp[i / bits_per_byte] |= (1 << (i % bits_per_byte));
        }
    }

    // 将位掩码写入目标容器（兼容所有STL实现）
    for (int i = 0; i < len; ++i) {
        dst[i] = (temp[i / bits_per_byte] >> (i % bits_per_byte)) & 1;
    }
}

方案2：手动使用SIMD指令（性能最优，可移植性稍差） #

如果目标平台支持AVX2等SIMD指令集，可以直接手动实现向量化比较和位打包，跳过编译器的优化限制：

#include <vector>
#include <immintrin.h>

void compare_and_pack_avx2(int* lhs, int* rhs, int len, std::vector<bool>& dst) {
    dst.resize(len);
    int i = 0;
    const int simd_batch = 8; // AVX2一次处理8个int元素

    // 批量处理可向量化的部分
    for (; i <= len - simd_batch; i += simd_batch) {
        __m256i lhs_vec = _mm256_loadu_si256(reinterpret_cast<__m256i*>(lhs + i));
        __m256i rhs_vec = _mm256_loadu_si256(reinterpret_cast<__m256i*>(rhs + i));
        // 比较相等，相等的元素对应位为全1
        __m256i eq_mask = _mm256_cmpeq_epi32(lhs_vec, rhs_vec);
        // 将每个元素的最高位提取为掩码（1表示相等）
        int bit_mask = _mm256_movemask_ps(_mm256_castsi256_ps(eq_mask));

        // 将掩码写入位容器
        for (int j = 0; j < simd_batch; ++j) {
            dst[i + j] = (bit_mask >> j) & 1;
        }
    }

    // 处理剩余的零散元素
    for (; i < len; ++i) {
        dst[i] = lhs[i] == rhs[i];
    }
}

方案3：改用字节粒度容器（最简单高效） #

如果内存开销不是瓶颈，直接用std::vector<uint8_t>代替std::vector<bool>，编译器会自动完成向量化，代码最简单且性能接近最优：

#include <vector>
#include <cstdint>

void compare_to_byte_array(int* lhs, int* rhs, int len, std::vector<uint8_t>& dst) {
    dst.resize(len);
    for (int i = 0; i < len; ++i) {
        dst[i] = static_cast<uint8_t>(lhs[i] == rhs[i]);
    }
}

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