Хорошо, это может показаться немного сложным, но вот что я пытаюсь сделать:
10101010101
{ 0, 2, 4, 6, 8, 10 }
— массив со всеми позициями битов, которые установленыЭто мой код:
UINT DQBitboard::firstBit(U64 bitboard)
{
static 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 };
static const U64 debruijn64 = 0x07EDD5E59A4E28C2ULL;
#pragma warning (disable: 4146)
return index64[((bitboard & -bitboard) * debruijn64) >> 58];
}
vector<UINT> DQBitboard::bits(U64 bitboard)
{
vector<UINT> res;
while (bitboard)
{
UINT first = DQBitboard::firstBit(bitboard);
res.push_back(first);
bitboard &= ~(1ULL<<first);
}
return res;
}
И код обязательно работает.
Моя точка зрения такова:
Подсказки:
UINT
является определением типа unsigned int
U64
является определением типа unsigned long long
static inline
,Вот еще одно предложение, которое можно профилировать (можно объединить с другими предложениями для дальнейшей оптимизации). Обратите внимание, цикл здесь O(number of set bits)
,
vector<UINT> bits_set (UINT64 data)
{
UINT n;
vector<UINT> res;
res.reserve(64);
for (n = 0; data != 0; n++, data &= (data - 1))
{
res.push_back(log2(data & ~(data-1)));
}
return res;
}
Сдвиги битов действительно дешевы. Таблицы поиска стоят кеш-памяти, и ваш поиск также имеет целочисленное умножение. Я полагаю, что грубая сила будет быстрее, чем умные методы.
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
Самое быстрое, о чем я могу подумать сейчас, это использовать предварительно сгенерированный массив всех чисел (это не обязательно должны быть все числа, вы можете, например, разбить числа на 8-битные или 16-битные части, а затем объединить возвращаемые массивы с некоторыми надлежащими дополнениями для учета фактической позиции битов ).map
Я попробовал наивную версию, которая работала примерно в 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 будет стоить немного, поэтому я сомневаюсь, что оно того стоит.