Получить массив позиций битов в пределах 64-битного целого

Сдвиги битов действительно дешевы. Таблицы поиска стоят кеш-памяти, и ваш поиск также имеет целочисленное умножение. Я полагаю, что грубая сила будет быстрее, чем умные методы.

vector<UINT> DQBitboard::bits(U64 bitboard)
{
vector<UINT> res;
res.reserve(64);
uint_fast8_t pos = 1;

do {
if (bitboard & 1) res.push_back(pos);
++pos;
} while (bitboard >>= 1);

return res;
}

Вы можете немного развернуть цикл, что может сделать его еще быстрее.

std::vector самая дорогая часть на сегодняшний день. Рассмотрите возможность использования битборда напрямую. Например:

struct bitboard_end_iterator{};
struct bitboard_iterator
{
U64 value;
uint_fast8_t pos;

bitboard_iterator(U64 bitboard) : value(bitboard), pos(0)
{
++(*this);
}
UINT operator*() const { return pos + 1; }
bool operator==( bitboard_end_iterator ) const { return pos == 64; }
operator bool() const { return pos < 64; }
bitboard_iterator& operator++()
{
while (U64 prev = value) {
value >>= 1;
++pos;
if (prev & 1) return *this;
}
pos = 64;
return *this;
}
};

Теперь вы можете написать

for( bitboard_iterator it(bitboard); it; ++it )
cout << *it;

и я думаю, что вы получите свой список битов.

Версия 2:

class bitboard_fast_iterator
{
U64 value;
uint_fast8_t pos;

public:
bitboard_fast_iterator(U64 bitboard = 0) : value(bitboard), pos(__builtin_ctzll(value)) {}
UINT operator*() const { return pos + 1; }
operator bool() const { return value != 0; }
bitboard_iterator& operator++()
{
value &= ~(1ULL << pos);
pos = __builtin_ctzll(value);
return *this;
}
};

Мне было интересно, будет ли он работать быстрее с инструкцией по сборке BST. Итак, я попробовал 3 реализации и получил следующие результаты за 10 миллионов итераций:

Ваша реализация (Dr.Kameleon) 1,77 секунды

Реализация log2 () (icepack) 2,17 секунды

Моя сборка реализации (меня) 0,16 секунды

Выход:

bits version:
Function started at 0
ended at 177
spent 177 (1.770000 seconds)
c version:
Function started at 177
ended at 394
spent 217 (2.170000 seconds)
c version:
Function started at 394
ended at 410
spent 16 (0.160000 seconds)

Одно замечание о C / C ++, статика ужасна. На самом деле он скомпилирован в список инструкций процессора (НЕ то, что я ожидал бы !!!). Вместо этого используйте массив вне вашей функции в безымянном пространстве имен. Это будет иметь ожидаемый эффект. Хотя в сборке вы можете использовать .long (или другой размер), а затем% rip для ссылки на данные с IP.

Примечание: после компиляции я не вижу размера (n), используемого в моей версии сборки, поэтому я не слишком уверен, верен ли возвращаемый массив. Помимо этого, сам код становится циклом из 5 инструкций по сборке, отсюда и незначительное увеличение скорости (примерно в 10 раз).

Причина медлительности log2 () заключается в том, что она преобразует число в регистр xmm, а затем вызывает другую функцию. Затем он преобразует регистр xmm обратно в обычный регистр.

#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <unistd.h>
#include <sys/times.h>
#include <string.h>
#include <math.h>
#include <vector>

using namespace std;

namespace
{
const int index64[64] = {
63,  0, 58,  1, 59, 47, 53,  2,
60, 39, 48, 27, 54, 33, 42,  3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22,  4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16,  9, 12,
44, 24, 15,  8, 23,  7,  6,  5  };
const uint64_t debruijn64 = 0x07EDD5E59A4E28C2ULL;
}

int firstBit(uint64_t bitboard)
{
return index64[((bitboard & -bitboard) * debruijn64) >> 58];
}

vector<int> bits(uint64_t bitboard)
{
vector<int> res;
res.reserve(64);

while(bitboard)
{
int first = firstBit(bitboard);
res.push_back(first);

bitboard &= ~(1ULL << first);
}
return res;
}vector<int> bits_c(uint64_t bitboard)
{
int n;
vector<int> res;
res.reserve(64);
for (n = 0; bitboard != 0; n++, bitboard &= (bitboard - 1))
{
res.push_back(log2(bitboard & ~(bitboard - 1)));
}
return res;
}vector<int> bits_asm(uint64_t bitboard)
{
int64_t n(0);
int res[64];
asm(
"bsf %[b], %%rax\n\t""je exit\n\t"".align 16\n""loop:\n\t""mov %%eax, (%[r],%[n],4)\n\t""btr %%rax, %[b]\n\t""inc %[n]\n\t""bsf %[b], %%rax\n\t""je loop\n""exit:\n\t": /* output */ "=r" (n)
: /* input */ [n] "r" (n), [r] "r" (res), [b] "r" (bitboard)
: /* state */ "eax", "cc");
return vector<int>(res, res + n);
}class run_timer
{
public:
run_timer()
{
}

void start()
{
times(&f_start);
}

void stop()
{
times(&f_stop);
}

void report(const char *msg)
{
printf("%s:\n""Function started at %ld\n""           ended at %ld\n""              spent %ld (%f seconds)\n",
msg,
f_start.tms_utime,
f_stop.tms_utime,
f_stop.tms_utime - f_start.tms_utime,
(double)(f_stop.tms_utime - f_start.tms_utime)/(double)sysconf(_SC_CLK_TCK));
}

struct tms f_start;
struct tms f_stop;
};int main(int argc, char *argv[])
{
run_timer t;

t.start();
for(int i(0); i < 10000000; ++i)
{
bits(rand());
}
t.stop();
t.report("bits version");

t.start();
for(int i(0); i < 10000000; ++i)
{
bits_c(rand());
}
t.stop();
t.report("c version");

t.start();
for(int i(0); i < 10000000; ++i)
{
bits_asm(rand());
}
t.stop();
t.report("c version");

return 0;
}

Скомпилировано с g ++ с помощью этой командной строки:

c++ -msse4.2 -O2 -o bits -c bits.cpp

Хотя вы можете подумать, что -msse4.2 может быть проблемой с версией log2 (), я пробовал без нее, а log2 () медленнее.

Кстати, я не рекомендую этот метод, так как он не является переносимым. Только компьютеры на базе Intel будут понимать эти инструкции.

Замените свой firstBit функция с внутренним, используя BSF или же BSR Инструкция по массовому ускорению.

В gcc это было бы __builtin_ffsll а также __builtin_ctzll

С Visual C +, _BitScanForward а также _BitScanReverse

Самое быстрое, о чем я могу подумать сейчас, это использовать предварительно сгенерированный map массив всех чисел (это не обязательно должны быть все числа, вы можете, например, разбить числа на 8-битные или 16-битные части, а затем объединить возвращаемые массивы с некоторыми надлежащими дополнениями для учета фактической позиции битов ).

Я попробовал наивную версию, которая работала примерно в 2-3 раза быстрее, но зарезервировала () сначала вектор. Применяя резерв к оригинальному алгоритму, он побил наивный.

Поэтому я подозреваю, что векторные операции здесь стоят дороже, чем битовые манипуляции (или даже умножение, используемое в функции следующего бита).

Есть некоторые другие ускорения, касающиеся поиска младшего установленного бита. Моя локальная версия log2 была плохой, и функция, указанная в оригинальном посте, не супер дешевая.

Вот моя лучшая попытка:

void bits(uint64 bitboard, vector<int> &res)
{
res.resize(64);
int i = 0;
while (bitboard)
{
int first;
_BitScanForward64((DWORD *)&first, bitboard);
res[i++] = first;
bitboard &= ~(1ULL<<first);
}
res.resize(i);
}

Заменена функция firstBit на встроенную в asm. Использование встроенного дал большой толчок здесь. (Это явно не переносимый код, хотя я подозреваю, что вариант GCC не должен быть слишком хитрым).

Также предполагается, что вектор является достаточно постоянным, а не динамически распределяемым / копируемым, и просто изменяет его размер соответствующим образом.

const size_t size = sizeof(U64)*8;
U64 val = 1;

vector<UINT> res;
res.reserve(size);

for ( size_t i = size; i > 0; --i ) {
if ( ( val & bitboard ) != 0 ) {
res.push_back(i);
}
val <<= 1;
}

Я на самом деле думаю, что самый быстрый и простой метод — это просто циклическое повторение, но если мы передадим вектор вместо того, чтобы позже сделать копию, он должен быть немного быстрее.

void DQBitboard::bits(U64 bitboard, vector<UINT> &res)
{
res.clear();   // Make sure vector is empty. Not necessary if caller does this!
int bit = 0;
while (bitboard)
{
if (bitboard & 1)
res.push_back(bit);
bit++;
bitboard >>= 1;
}

return res;
}

Умножение в findfirst будет стоить немного, поэтому я сомневаюсь, что оно того стоит.