c++ - purposes - "Aislar" una fila/columna/diagonal específica a partir de un número de 64 bits

tagblender

Question

Bien, consideremos un número de 64 bits, con sus bits formando una tabla de 8x8.

P.ej

0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 0

Escrito como

a b c d e f g h
----------------
0 1 1 0 1 0 1 0
0 1 1 0 1 0 1 1
0 1 1 1 1 0 1 0
0 1 1 0 1 0 1 0
1 1 1 0 1 0 1 0
0 1 1 0 1 0 1 0
0 1 1 0 1 1 1 0
0 1 1 0 1 0 1 0

Ahora, ¿y si queremos aislar JUST, por ejemplo, la columna d ( 00100000 ) (o cualquier fila / diagonal para el caso)?

Se puede hacer esto? Y si es así, ¿cómo?

CONSEJOS:

• (a) Mi objetivo principal aquí -aunque no mencionado inicialmente- es la velocidad bruta. Estoy buscando el algoritmo más rápido, ya que la función de "recuperación" se realiza millones de veces por segundo .

• (b) Esto es lo que se acerca a lo que quiero decir: http://chessprogramming.wikispaces.com/Kindergarten+Bitboards

Answer 1

Éste es de la Wiki de Programación de Ajedrez . Transpone el tablero, después de lo cual aislar una sola fila es trivial. También te permite volver al otro lado.

/**
* Flip a bitboard about the antidiagonal a8-h1.
* Square a1 is mapped to h8 and vice versa.
* @param x any bitboard
* @return bitboard x flipped about antidiagonal a8-h1
*/
U64 flipDiagA8H1(U64 x) {
U64 t;
const U64 k1 = C64(0xaa00aa00aa00aa00);
const U64 k2 = C64(0xcccc0000cccc0000);
const U64 k4 = C64(0xf0f0f0f00f0f0f0f);
t = x ^ (x << 36) ;
x ^= k4 & (t ^ (x >> 36));
t = k2 & (x ^ (x << 18));
x ^= t ^ (t >> 18) ;
t = k1 & (x ^ (x << 9));
x ^= t ^ (t >> 9) ;
return x;
}

Answer 2

Aquí hay una solución con solo 4 pasos principales:

const uint64_t column_mask = 0x8080808080808080ull;
const uint64_t magic = 0x2040810204081ull;
int get_col(uint64_t board, int col) {
uint64_t column = (board << col) & column_mask;
column *= magic;
return (column >> 56) & 0xff;
}

Funciona así:

• el tablero se desplaza para alinear la columna con el lado izquierdo
• está enmascarado para contener solo la columna requerida (0..8)
• se multiplica por un número mágico que resulta en todos los bits originales empujados hacia el lado izquierdo
• el byte más a la izquierda se desplaza a la derecha

El número mágico se elige para copiar solo los bits necesarios y dejar que el resto caiga en lugares no utilizados / desbordamiento sobre el número. El proceso se parece a esto (los dígitos son "ID" de bits, en lugar del número en sí):

original column: ...1.......2.......3.......4.......5.......6.......7.......8....
aligned column: 1.......2.......3.......4.......5.......6.......7.......8.......
multiplied: 123456782345678.345678..45678...5678....678.....78......8.......
shifted to right:........................................................12345678

Si agrega las palabras clave const , el ensamblaje se vuelve bastante bueno en realidad:

get_col:
.LFB7:
.cfi_startproc
movl %esi, %ecx
movabsq $-9187201950435737472, %rax
salq %cl, %rdi
andq %rax, %rdi
movabsq $567382630219905, %rax
imulq %rax, %rdi
shrq $56, %rdi
movl %edi, %eax
ret

Sin ramificación, sin datos externos, alrededor de 0.4ns por cálculo.

Editar: toma alrededor de la sexta parte del tiempo usando la solución de NPE como línea de base (el más rápido uno)

Answer 3

Aquí hay una solución que puede ejecutarse una vez por ciclo (si el valor y la máscara están en los registros), si está dispuesto a usar el intrínseco para la instrucción PEXT en Intel (y si está haciendo cosas de bitboard, probablemente lo esté):

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

Eso es para la columna 0: si desea otra, simplemente desplace la máscara de manera apropiada. Por supuesto, esto es trampa mediante el uso de una instrucción específica de hardware, pero las tablas de bits se trata de hacer trampa.

Answer 4

Bien, para "resolver" el debate sobre qué es más rápido / lento / etc, he puesto todo el código en un programa [y espero que le haya dado el crédito por el fragmento de código correcto a la persona correcta].

El código se puede encontrar a continuación, para comprobar que he incorporado correctamente el código cuando lo he hecho en funciones. Lo ejecuté con la salida adecuada y verifiqué que cada función da el mismo resultado [teniendo en cuenta que el orden es ligeramente diferente en algunos casos, por lo que hice una variación para ejecutar la otra forma de mi código, solo para ver que da el resultado "correcto"]. Así que sin más preámbulos, aquí están los resultados:

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

(Resultados de viraptor del núcleo 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

(Resultados de viraptor del 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

Eso es ciclos de reloj en un AMD Athlon2 de 3.4GHz. No tengo una máquina Intel moderna. Si alguien desea ejecutar el código en ese punto, me interesaría ver qué aspecto tiene. Estoy bastante seguro de que todo funciona bien dentro del caché, quizás aparte de buscar algunos de los valores para verificar.

Entonces, el ganador es claramente viraptor, en aproximadamente un 40% - "mi" código es el segundo. El código de Alex no tiene saltos / ramas, pero parece funcionar más lento que las otras alternativas. No estoy seguro de por qué los resultados de npe son mucho más lentos que los míos; hace casi lo mismo (y el código parece muy similar al mirar la salida del ensamblador de 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();
}
}

Answer 5

Codifíquelo con bucles directos y deje que el optimizador realice la alineación y el despliegue del bucle por usted.

Compilado con 4.7.2 con -O3 , en mi caja, lo siguiente puede realizar unos 300 millones de llamadas get_col() por segundo.

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() {}

Si observa el código de ensamblaje para get_col() , verá que contiene cero bucles y es probablemente tan eficiente como cualquier otra cosa que pueda hacer a mano:

__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

Esto no significa una implementación completa, solo una ilustración aproximada de la idea. En particular, el orden de los bits puede ser opuesto a lo que espera, etc.

Answer 6

En su caso (especializado para tablas de 8x8 = 64 bits), debe realizar el cambio de bits para extraer los bits específicos y reorganizarlos en una nueva variable entera, también utilizando el cambio de bits:

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
}

Vea aquí: http://ideone.com/UlWAAO

Answer 7

Puedes transpose el número, y luego simplemente seleccionar la columna relevante, que ahora es una fila, y por lo tanto bits contiguos, como quisieras.

En mis pruebas, no fue mucho mejor que hacer OR juntos 8 bits seleccionados individualmente, pero es mucho mejor si tiene la intención de seleccionar varias columnas (ya que la transposición es el factor limitante).

Answer 8

Qué tal esto...

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;

Answer 9

#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);

Quizás una idea algo más optimizada:

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

Si b es una constante, esto funcionará ligeramente mejor.

Otra forma puede ser:

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

Hacer uno "y" en lugar de muchos ayuda a acelerarlo.