& Quot; изолят & Quot; конкретная строка / столбец / диагональ от 64-разрядного числа

Правильно, поэтому, чтобы «уладить» дискуссию о том, что быстрее / медленнее / и т.д., я поместил весь код в одну программу [и я надежда Я зачислил правильного человека за правильный фрагмент кода].

Код можно найти ниже, для проверки того, что я правильно интерпретировал код, когда превратил его в функции. Я запустил его без правильного вывода и проверил, что каждая функция дает одинаковый результат [учитывая, что в некоторых случаях порядок немного отличается — поэтому я сделал вариант, чтобы запустить другой код моего кода, просто чтобы убедиться, что он дает «правильный» результат. Итак, без лишних слов, вот результаты:

mats1 time in clocks per iteration 10.3457
mats2 time in clocks per iteration 10.4785
mats3 time in clocks per iteration 10.5538
viraptor time in clocks per iteration 6.24603
lemees time in clocks per iteration 14.4818
npe time in clocks per iteration 13.1455
alex time in clocks per iteration 24.8272

(результаты viraptor от core i5, g ++ 4.7)

mats1 time in clocks per iteration 7.62338
mats2 time in clocks per iteration 7.36226
mats3 time in clocks per iteration 7.45361
viraptor time in clocks per iteration 2.09582
lemees time in clocks per iteration 9.43744
npe time in clocks per iteration 7.51016
alex time in clocks per iteration 19.3554

(результаты viraptor от core i5, clang ++ 3.2)

mats1 time in clocks per iteration 12.956
mats2 time in clocks per iteration 13.4395
mats3 time in clocks per iteration 13.3178
viraptor time in clocks per iteration 2.12914
lemees time in clocks per iteration 13.9267
npe time in clocks per iteration 16.2102
alex time in clocks per iteration 13.8705

Это тактовые частоты на AMD Athlon2 с частотой 3,4 ГГц — у меня нет современной машины Intel — если кто-то захочет запустить код на этом, мне было бы интересно посмотреть, как он выглядит. Я вполне уверен, что все это хорошо работает в кеше — возможно, кроме извлечения некоторых значений для проверки.

Итак, победителем явно становится вираптор, примерно на 40% — «мой» код — второй. В коде Алекса нет переходов / переходов, но он работает медленнее, чем другие альтернативы. Не уверен, почему результаты npe намного медленнее, чем у меня — он делает почти то же самое (и код выглядит очень похоже, если посмотреть на вывод ассемблера из g ++).

#include <iostream>
#include <fstream>
#include <cstdint>

using namespace std;

const int SIZE = 1000000;

uint64_t g_val[SIZE];

ofstream nulloutput;

static __inline__ unsigned long long rdtsc(void)
{
unsigned hi, lo;
__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

#define BITA_TO_B(x, a, b) (((x) >> (a-b)) & (1 << b))

unsigned char get_col_mats1(uint64_t val, int col)
{
return BITA_TO_B(val, 56+col, 7) |
BITA_TO_B(val, 48+col, 6) |
BITA_TO_B(val, 40+col, 5) |
BITA_TO_B(val, 32+col, 4) |
BITA_TO_B(val, 24+col, 3) |
BITA_TO_B(val, 16+col, 2) |
BITA_TO_B(val, 8+col, 1) |
BITA_TO_B(val, 0+col, 0);
}

unsigned char get_col_mats2(uint64_t val, int col)
{
return BITA_TO_B(val, 63-col, 7) |
BITA_TO_B(val, 55-col, 6) |
BITA_TO_B(val, 47-col, 5) |
BITA_TO_B(val, 39-col, 4) |
BITA_TO_B(val, 31-col, 3) |
BITA_TO_B(val, 23-col, 2) |
BITA_TO_B(val, 15-col, 1) |
BITA_TO_B(val, 7-col, 0);
}unsigned char get_col_viraptor(uint64_t board, int col) {
const uint64_t column_mask = 0x8080808080808080ull;
const uint64_t magic = 0x2040810204081ull ;
uint64_t column = board & (column_mask >> col);
column <<= col;
column *= magic;
return (column >> 56) & 0xff;
}unsigned char get_col_alex(uint64_t bitboard, int col)
{
unsigned char result;
result |= (bitboard & (1ULL << 63-col)) ? 0x80 : 0;
result |= (bitboard & (1ULL << 55-col)) ? 0x40 : 0;
result |= (bitboard & (1ULL << 47-col)) ? 0x20 : 0;
result |= (bitboard & (1ULL << 39-col)) ? 0x10 : 0;
result |= (bitboard & (1ULL << 31-col)) ? 0x08 : 0;
result |= (bitboard & (1ULL << 23-col)) ? 0x04 : 0;
result |= (bitboard & (1ULL << 15-col)) ? 0x02 : 0;
result |= (bitboard & (1ULL << 7-col))  ? 0x01 : 0;

return result;
}

unsigned char get_col_lemees(uint64_t val, int column)
{
int result = 0;
int source_bitpos = 7 - column; // "point" to last entry in this column
for (int target_bitpos = 0; target_bitpos < 8; ++target_bitpos)
{
bool bit = (val >> source_bitpos) & 1;  // "extract" bit
result |= bit << target_bitpos;            // add bit if it was set
source_bitpos += 8;                        // move one up in table
}
return result;
}

int get(uint64_t board, int row, int col) {
return (board >> (row * 8 + col)) & 1;
}

uint8_t get_col_npe(uint64_t board, int col) {
uint8_t ret = 0;
for (int i = 0; i < 8; ++i) {
ret = (ret << 1) + get(board, i, col);
}
return ret;
}#define BITA_TO_B2(x, a, b) (((x) >> (a-b)) & (1 << b))

unsigned char get_col_mats3(uint64_t val, int col)
{
return BITA_TO_B2(val, 63-col, 7) |
BITA_TO_B2(val, 55-col, 6) |
BITA_TO_B2(val, 47-col, 5) |
BITA_TO_B2(val, 39-col, 4) |
BITA_TO_B2(val, 31-col, 3) |
BITA_TO_B2(val, 23-col, 2) |
BITA_TO_B2(val, 15-col, 1) |
BITA_TO_B2(val, 7-col, 0);
}

template<unsigned char (*f)(uint64_t val, int col)>
void runbench(const char *name)
{
unsigned char col[8]  = {0};
uint64_t long t = rdtsc();
for(int j = 0; j < SIZE; j++)
{
uint64_t val = g_val[j];
for(int i = 0; i < 8; i++)
{
col[i] += f(val, i);
}
//  __asm__ __volatile__("":::"memory");
}
t = rdtsc() - t;
for(int i = 0; i < 8; i++)
{
nulloutput<< "col " << i << " has bits " << hex << (int)col[i] << endl;
}
cout << name << " time in clocks per iteration " << dec << t / (8.0 * SIZE) << endl;
}

#define BM(name) void bench_##name() { runbench<get_col_##name>(#name); }

BM(mats1);
BM(mats2);
BM(mats3);
BM(viraptor);
BM(lemees);
BM(npe);
BM(alex);

struct function
{
void (*func)(void);
const char *name;
};#define FUNC(f) { bench_##f, #f }

function funcs[] =
{
FUNC(mats1),
FUNC(mats2),
FUNC(mats3),
FUNC(viraptor),
FUNC(lemees),
FUNC(npe),
FUNC(alex),
};int main()
{
unsigned long long a, b;
int i;
int sum = 0;

nulloutput.open("/dev/nul");
for(i = 0; i < SIZE; i++)
{
g_val[i] = rand() + ((long)rand() << 32L);
}
unsigned char col[8];

for(i = 0; i < sizeof(funcs)/sizeof(funcs[0]); i++)
{
funcs[i].func();
}
}

Закодируйте его с помощью простых циклов, и пусть оптимизатор сделает за вас вставку и развертывание цикла.

Скомпилировано с использованием 4.7.2 с -O3на моей коробке следующее может выполнить около 300 миллионов get_col() звонков в секунду.

bitboard.cpp:

#include <cinttypes>
#include <iostream>

int get(uint64_t board, int row, int col) {
return (board >> (row * 8 + col)) & 1;
}

uint8_t get_col(uint64_t board, int col) {
uint8_t ret = 0;
for (int i = 0; i < 8; ++i) {
ret = (ret << 1) + get(board, i, col);
}
return ret;
}

extern uint64_t board;
extern int sum;

extern void f();

int main() {
for (int i = 0; i < 40000000; ++i) {
for (int j = 0; j < 8; ++j) {
sum += get_col(board, j);
}
f();
}
std::cout << sum << std::endl;
}

bitboard_b.cpp:

#include <cinttypes>

uint64_t board = 0x1234567890ABCDEFull;
int sum = 0;

void f() {}

Если вы посмотрите на код сборки для get_col()вы увидите, что он содержит ноль циклов и, вероятно, так же эффективен, как и все, что вы можете сделать вручную:

__Z7get_colyi:
LFB1248:
movl    %esi, %ecx
movq    %rdi, %rax
movq    %rdi, %rdx
shrq    %cl, %rax
leal    8(%rsi), %ecx
andl    $1, %eax
shrq    %cl, %rdx
leal    16(%rsi), %ecx
andl    $1, %edx
leal    (%rdx,%rax,2), %eax
movq    %rdi, %rdx
shrq    %cl, %rdx
leal    24(%rsi), %ecx
andl    $1, %edx
leal    (%rdx,%rax,2), %eax
movq    %rdi, %rdx
shrq    %cl, %rdx
leal    32(%rsi), %ecx
andl    $1, %edx
leal    (%rdx,%rax,2), %eax
movq    %rdi, %rdx
shrq    %cl, %rdx
leal    40(%rsi), %ecx
andl    $1, %edx
leal    (%rdx,%rax,2), %edx
movq    %rdi, %rax
shrq    %cl, %rax
leal    48(%rsi), %ecx
andl    $1, %eax
leal    (%rax,%rdx,2), %edx
movq    %rdi, %rax
shrq    %cl, %rax
leal    56(%rsi), %ecx
andl    $1, %eax
leal    (%rax,%rdx,2), %eax
shrq    %cl, %rdi
andl    $1, %edi
leal    (%rdi,%rax,2), %eax
ret

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

В вашем случае (специализированном для 8×8 = 64-битных таблиц) вам необходимо выполнить сдвиг битов, чтобы извлечь конкретные биты и переставить их в новую целочисленную переменную, также используя битовый сдвиг:

uint64_t matrix = ... // input
int column = 3; // "d"-column

int result = 0;
int source_bitpos = 7 - column; // "point" to last entry in this column
for (int target_bitpos = 0; target_bitpos < 8; ++target_bitpos)
{
bool bit = (matrix >> source_bitpos) & 1;  // "extract" bit
result |= bit << target_bitpos;            // add bit if it was set
source_bitpos += 8;                        // move one up in table
}

Посмотреть здесь: http://ideone.com/UlWAAO

#define BITA_TO_B(x, a, b) (((x) >> (a)) & 1) << b;

unsigned long long x = 0x6A6B7A6AEA6E6A;

unsigned char col_d = BITA_TO_B(x, 60, 7) |
BITA_TO_B(x, 52, 6) |
BITA_TO_B(x, 44, 5) |
BITA_TO_B(x, 36, 4) |
BITA_TO_B(x, 28, 3) |
BITA_TO_B(x, 20, 2) |
BITA_TO_B(x, 12, 1) |
BITA_TO_B(x,  4, 0);

Возможно, несколько более оптимизированная идея:

#define BITA_TO_B(x, a, b) (((x) >> (a-b)) & (1 << b));

Если b является константой, это будет работать немного лучше.

Другой способ может быть:

unsigned long xx = x & 0x10101010101010;
col_d = (xx >> 53) | (xx >> 46) | (xx >> 39) ... (xx >> 4);

Выполнение одного «и» вместо многих помогает ускорить его.

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

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

Вот решение, которое может выполняться один раз за цикл (если значение и маска находятся в регистрах), если вы хотите использовать встроенную функцию для PEXT инструкция по Intel (и если вы делаете что-то на доске, скорее всего):

int get_col(uint64_t board) {
return _pext_u64(board, 0x8080808080808080ull);
}

Это для 0-го столбца — если вы хотите еще один, просто сдвиньте маску соответствующим образом. Конечно, это обман с использованием аппаратной инструкции, но битборды — это все об обмане.

Как насчет этого…

uint64_t bitboard = ...;
uint8_t result = 0;

result |= (bitboard & (1ULL << 60)) ? 0x80 : 0;
result |= (bitboard & (1ULL << 52)) ? 0x40 : 0;
result |= (bitboard & (1ULL << 44)) ? 0x20 : 0;
result |= (bitboard & (1ULL << 36)) ? 0x10 : 0;
result |= (bitboard & (1ULL << 28)) ? 0x08 : 0;
result |= (bitboard & (1ULL << 20)) ? 0x04 : 0;
result |= (bitboard & (1ULL << 12)) ? 0x02 : 0;
result |= (bitboard & (1ULL <<  4)) ? 0x01 : 0;