Преобразовать массив битов, чтобы установить быстрее

Ввод — это битовый массив, хранящийся в смежной памяти с 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-разрядное целое число без знака в массиве.

Как сделать это примерно в 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 секунд за цикл. Это медленно.

У процессора есть инструкция 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, а затем запись непосредственно в данные вектора посредством необработанного наведения — плохая идея. Изменение размера сначала и затем использование необработанного указателя хорошо, хотя. См ответ Робо на Изменение размера C ++ std :: vector<голец> без инициализации данных Я собираюсь просто использовать изменение размера вместо резерва и перестать беспокоиться о времени, которое изменяет размер отходов, вызывая конструктор каждого элемента вектора … по крайней мере, векторы фактически используют непрерывную память, как простой массив (Гарантируются ли элементы std :: vector смежными?)