转换位数组以更快地设置

Question

输入是存储在连续内存中的位数组，每 1 位内存对应 1 位位数组。

输出是位数组的设置位的索引数组。

示例：

bitarray: 0000 1111 0101 1010
setA: {4,5,6,7,9,11,12,14}
setB: {2,4,5,7,9,10,11,12}

获得A组或B组都可以。该集合存储为 uint32_t 的数组，因此集合中的每个元素都是数组中的无符号 32 位整数。

如何在单个 cpu 核心上将此速度提高约 5 倍？

当前代码：

#include <iostream>
#include <vector>
#include <time.h>

using namespace std;

template <typename T>
uint32_t bitarray2set(T& v, uint32_t * ptr_set){
    uint32_t i;
    uint32_t base = 0;
    uint32_t * ptr_set_new = ptr_set;
    uint32_t size = v.capacity();
    for(i = 0; i < size; i++){
        find_set_bit(v[i], ptr_set_new, base);
        base += 8*sizeof(uint32_t);
    }
    return (ptr_set_new - ptr_set);
}

inline void find_set_bit(uint32_t n, uint32_t*& ptr_set, uint32_t base){
    // Find the set bits in a uint32_t
    int k = base;
    while(n){
        if (n & 1){
            *(ptr_set) = k;
            ptr_set++;
        }
        n = n >> 1;
        k++;
    }
}

template <typename T>
void rand_vector(T& v){
    srand(time(NULL));
    int i;
    int size = v.capacity();
    for (i=0;i<size;i++){
        v[i] = rand();
    }
}

template <typename T>
void print_vector(T& v, int size_in = 0){
    int i;

    int size;
    if (size_in == 0){
        size = v.capacity();
    } else {
        size = size_in;
    }
    for (i=0;i<size;i++){
        cout << v[i] << ' ';
    }
    cout << endl;
}

int main(void){
    const int test_size = 6000;
    vector<uint32_t> vec(test_size);
    vector<uint32_t> set(test_size*sizeof(uint32_t)*8);
    rand_vector(vec);
    //for (int i; i < 64; i++) vec[i] = -1;
    //cout << "input" << endl;
    print_vector(vec);
    //cout << "calculate result" << endl;

    int i;
    int rep = 10000;
    uint32_t res_size;

    struct timespec tp_start, tp_end;
    clock_gettime(CLOCK_MONOTONIC, &tp_start);
    for (i=0;i<rep;i++){
        res_size = bitarray2set(vec, set.data());
    }
    clock_gettime(CLOCK_MONOTONIC, &tp_end);
    double timing;
    const double nano = 0.000000001;

    timing = ((double)(tp_end.tv_sec  - tp_start.tv_sec )
           + (tp_end.tv_nsec - tp_start.tv_nsec) * nano) /(rep);

    cout << "timing per cycle: " << timing << endl;
    cout << "print result" << endl;
    //print_vector(set, res_size);
}

结果（用icc -O3 code.cpp -lrt编译）

...
timing per cycle: 0.000739613 (7.4E-4).
print result

0.0008秒转换768000位设置。但是每个周期至少有10,000个768,000位的数组。即每个周期 8 秒。就是慢。

cpu有popcnt指令和sse4.2指令集

谢谢。

更新

template <typename T>
uint32_t bitarray2set(T& v, uint32_t * ptr_set){
    uint32_t i;
    uint32_t base = 0;
    uint32_t * ptr_set_new = ptr_set;
    uint32_t size = v.capacity();
    uint32_t * ptr_v;
    uint32_t * ptr_v_end = &(v[size]);
    for(ptr_v = v.data(); ptr_v < ptr_v_end; ++ptr_v){
        while(*ptr_v) {
           *ptr_set_new++ = base + __builtin_ctz(*ptr_v);
           (*ptr_v) &= (*ptr_v) - 1;  // zeros the lowest 1-bit in n
        }
        base += 8*sizeof(uint32_t);
    }
    return (ptr_set_new - ptr_set);
}

这个更新版本使用了 rhashimoto 提供的内部循环。我不知道内联是否真的使函数变慢（我从没想过会发生这种情况！）。新时序为 1.14E-5（由 icc -O3 code.cpp -lrt 编译，并以随机向量为基准）。

警告：

我刚刚发现保留而不是调整 std::vector 的大小，然后通过原始指向直接写入向量的数据是一个坏主意。先调整大小然后使用原始指针是可以的。在 Resizing a C++ std::vector<char> without initializing data I am going to just use resize instead of reserve and stop worrying about the time that resize wastes by calling constructor of each element of the vector... at least vectors actually uses contiguous memory, like a plain array (Are std::vector elements guaranteed to be contiguous?)

查看 Robᵩ 的回答

Answer 1

我注意到您使用 .capacity() 时可能想使用 .size()。这可能会让你做额外的不必要的工作，并给你错误的答案。

您在 find_set_bit() 中的循环遍历单词中的所有 32 位。您可以改为仅迭代每个设置位并使用 BSF 指令来确定最低位的索引。 GCC 有一个内部函数 __builtin_ctz() 来生成 BSF 或等价物——我认为英特尔编译器也支持它（如果不支持，你可以内联汇编）。修改后的函数如下所示：

inline void find_set_bit(uint32_t n, uint32_t*& ptr_set, uint32_t base){
    // Find the set bits in a uint32_t
    while(n) {
       *ptr_set++ = base + __builtin_ctz(n);
       n &= n - 1;  // zeros the lowest 1-bit in n
    }
}

在我的 Linux 机器上，使用 g++ -O3 编译，替换该函数会将报告的时间从 0.000531434 降低到 0.000101352。

在 this question 的答案中有很多方法可以找到位索引。不过，我确实认为 __builtin_ctz() 将是您的最佳选择。我不相信有一个合理的 SIMD 方法来解决您的问题，因为每个输入词都会产生可变数量的输出。

Answer 2

正如@davidbak 所建议的，您可以使用 table 查找一次处理位图的 4 个元素。

每次查找都会产生一个可变大小的集合成员块，我们可以使用 popcnt 来处理它。

@rhashimoto 基于标量 ctz 的建议可能会更好地处理具有大量零的稀疏位集，但是当有很多设置位时这应该更好。

我在想

// a vector of 4 elements for every pattern of 4 bits.
// values range from 0 to 3, and will have a multiple of 4 added to them.
alignas(16) static const int LUT[16*4] = { 0,0,0,0,  ... };

// mostly C, some pseudocode.
unsigned int bitmap2set(int *set, int input) {
    int *set_start = set;

    __m128i offset = _mm_setzero_si128();

    for (nibble in input[]) {  // pseudocode for the actual shifting / masking
        __m128i v = _mm_load_si128(&LUT[nibble]);
        __m128i vpos = _mm_add_epi32(v, offset);

        _mm_store((__m128i*)set, vpos);

        set += _mm_popcount_u32(nibble);    // variable-length store
        offset = _mm_add_epi32(offset, _mm_set1_epi32(4));  // increment the offset by 4
    }
    return  set - set_start;  // set size
}

当一个半字节不是 1111 时，下一个商店会重叠，但这没关系。

使用 popcnt 计算指针递增多少通常是一项有用的技术

转换位数组以更快地设置

Convert array of bits to set faster

c++

sse

bit-manipulation

set

bitarray