c++ - ¿Cuál es la forma más rápida de devolver las posiciones de todos los bits configurados en un entero de 64 bits?
performance optimization (10)
¿Se ha encontrado que esto es demasiado lento?
Pequeño y crudo, pero está todo en los registros de caché y CPU;
void mybits(uint64_t x, unsigned char *idx)
{
unsigned char n = 0;
do {
if (x & 1) *(idx++) = n;
n++;
} while (x >>= 1); // If x is signed this will never end
*idx = (unsigned char) 255; // List Terminator
}
Todavía es 3 veces más rápido para desenrollar el bucle y producir una matriz de 64 valores verdadero / falso (que no es exactamente lo que se quiere)
void mybits_3_2(uint64_t x, idx_type idx[])
{
#define SET(i) (idx[i] = (x & (1UL<<i)))
SET( 0);
SET( 1);
SET( 2);
SET( 3);
...
SET(63);
}
Necesito una forma rápida de obtener la posición de todos los bits en un entero de 64 bits. Por ejemplo, dado x = 123703 , me gustaría llenar una matriz idx[] = {0, 1, 2, 4, 5, 8, 9, 13, 14, 15, 16} . Podemos suponer que conocemos la cantidad de bits a priori. Esto se llamará 10 ^ 12 - 10 ^ 15 veces, por lo que la velocidad es esencial. La respuesta más rápida que he encontrado hasta ahora es la siguiente monstruosidad, que utiliza cada byte del entero de 64 bits como un índice en tablas que dan el número de bits establecidos en ese byte y las posiciones de los que están:
int64_t x; // this is the input
unsigned char idx[K]; // this is the array of K bits that are set
unsigned char *dst=idx, *src;
unsigned char zero, one, two, three, four, five; // these hold the 0th-5th bytes
zero = x & 0x0000000000FFUL;
one = (x & 0x00000000FF00UL) >> 8;
two = (x & 0x000000FF0000UL) >> 16;
three = (x & 0x0000FF000000UL) >> 24;
four = (x & 0x00FF00000000UL) >> 32;
five = (x & 0xFF0000000000UL) >> 40;
src=tab0+tabofs[zero ]; COPY(dst, src, n[zero ]);
src=tab1+tabofs[one ]; COPY(dst, src, n[one ]);
src=tab2+tabofs[two ]; COPY(dst, src, n[two ]);
src=tab3+tabofs[three]; COPY(dst, src, n[three]);
src=tab4+tabofs[four ]; COPY(dst, src, n[four ]);
src=tab5+tabofs[five ]; COPY(dst, src, n[five ]);
donde COPY es una instrucción switch para copiar hasta 8 bytes, n es una matriz del número de bits establecidos en un byte y tabofs da la compensación en tabX , que contiene las posiciones de los bits establecidos en el byte X-th. Esto es aproximadamente 3 veces más rápido que los métodos basados en bucle desenrollados con (Ver abajo.) Actualmente estoy iterando __builtin_ctz() en mi Xeon E5-2609. x en orden lexicográfico para un número determinado de bits establecidos.
¿Hay una mejor manera?
EDITAR : Agregué un ejemplo (que he arreglado posteriormente). El código completo está disponible aquí: http://pastebin.com/79X8XL2P . Nota: GCC con -O2 parece optimizarlo, pero el compilador de Intel (que solía componerlo) no ...
Además, permítanme dar algunos antecedentes adicionales para abordar algunos de los comentarios a continuación. El objetivo es realizar una prueba estadística sobre cada subconjunto posible de variables K fuera de un universo de N posibles variables explicativas; el objetivo específico en este momento es N = 41, pero puedo ver algunos proyectos que necesitan N hasta 45-50. La prueba básicamente implica factorizar la submatriz de datos correspondiente. En pseudocódigo, algo como esto:
double doTest(double *data, int64_t model) {
int nidx, idx[];
double submatrix[][];
nidx = getIndices(model, idx); // get the locations of ones in model
// copy data into submatrix
for(int i=0; i<nidx; i++) {
for(int j=0; j<nidx; j++) {
submatrix[i][j] = data[idx[i]][idx[j]];
}
}
factorize(submatrix, nidx);
return the_answer;
}
Codifiqué una versión de esto para una placa Intel Phi que debería completar la caja N = 41 en aproximadamente 15 días, de los cuales ~ 5-10% del tiempo se gasta en una ingenua getIndices() así que de inmediato una getIndices() más rápida la versión podría salvar un día o más. También estoy trabajando en una implementación para NVidia Kepler, pero desafortunadamente el problema que tengo (números ridículos de operaciones de matriz pequeña) no es ideal para el hardware (operaciones de matriz ridículamente grandes). Dicho esto, este documento presenta una solución que parece lograr cientos de GFLOPS / s en matrices de mi tamaño mediante bucles de desenrollado agresivo y realizando la factorización completa en registros, con la advertencia de que las dimensiones de la matriz se definan en tiempo de compilación. (Este despliegue del bucle también debería ayudar a reducir la sobrecarga y mejorar la vectorización en la versión de Phi, ¡así que getIndices() será más importante!) Así que ahora estoy pensando que mi kernel debería verse más como:
double *data; // move data to GPU/Phi once into shared memory
template<unsigned int K> double doTestUnrolled(int *idx) {
double submatrix[K][K];
// copy data into submatrix
#pragma unroll
for(int i=0; i<K; i++) {
#pragma unroll
for(int j=0; j<K; j++) {
submatrix[i][j] = data[idx[i]][idx[j]];
}
}
factorizeUnrolled<K>(submatrix);
return the_answer;
}
La versión Phi resuelve cada modelo en un ciclo `cilk_for ''del modelo = 0 a 2 ^ N (o, más bien, un subconjunto para pruebas), pero ahora para trabajar por lotes para la GPU y amortizar la sobrecarga de inicio del kernel, tengo que iterar los números de modelo en orden lexicográfico para cada uno de K = 1 a 41 bits establecidos (como notó Doynax).
EDIT 2: Ahora que las vacaciones han terminado, aquí hay algunos resultados en mi Xeon E5-2602 usando icc versión 15. El código que utilicé como punto de referencia está aquí: http://pastebin.com/XvrGQUat . Realizo la extracción de bits en enteros que tienen exactamente K bits establecidos, por lo que hay una sobrecarga para la iteración lexicográfica medida en la columna "Base" en la tabla a continuación. Estos se realizan 2 ^ 30 veces con N = 48 (repitiendo según sea necesario).
"CTZ" es un ciclo que usa el gcc intrinseco __builtin_ctzll para obtener el conjunto de bits de orden más bajo:
for(int i=0; i<K; i++) {
idx[i] = __builtin_ctzll(tmp);
lb = tmp & -tmp; // get lowest bit
tmp ^= lb; // remove lowest bit from tmp
}
Mark es el bucle sin marca de Mark:
for(int i=0; i<K; i++) {
*dst = i;
dst += x & 1;
x >>= 1;
}
Tab1 es mi código original basado en tablas con la siguiente macro de copia:
#define COPY(d, s, n) /
switch(n) { /
case 8: *(d++) = *(s++); /
case 7: *(d++) = *(s++); /
case 6: *(d++) = *(s++); /
case 5: *(d++) = *(s++); /
case 4: *(d++) = *(s++); /
case 3: *(d++) = *(s++); /
case 2: *(d++) = *(s++); /
case 1: *(d++) = *(s++); /
case 0: break; /
}
Tab2 es el mismo código que Tab1, pero la macro de copia solo mueve 8 bytes como una sola copia (tomando ideas de doynax y Lưu Vĩnh Phúc ... pero tenga en cuenta que esto no asegura la alineación):
#define COPY2(d, s, n) { *((uint64_t *)d) = *((uint64_t *)s); d+=n; }
Aquí están los resultados. Supongo que mi afirmación inicial de que Tab1 es 3 veces más rápido que CTZ solo se cumple para K grande (donde estaba probando). El ciclo de Mark es más rápido que mi código original, pero deshacerse de la rama en la macro COPY2 lleva el pastel para K> 8.
K Base CTZ Mark Tab1 Tab2
001 4.97s 6.42s 6.66s 18.23s 12.77s
002 4.95s 8.49s 7.28s 19.50s 12.33s
004 4.95s 9.83s 8.68s 19.74s 11.92s
006 4.95s 16.86s 9.53s 20.48s 11.66s
008 4.95s 19.21s 13.87s 20.77s 11.92s
010 4.95s 21.53s 13.09s 21.02s 11.28s
015 4.95s 32.64s 17.75s 23.30s 10.98s
020 4.99s 42.00s 21.75s 27.15s 10.96s
030 5.00s 100.64s 35.48s 35.84s 11.07s
040 5.01s 131.96s 44.55s 44.51s 11.58s
Aquí hay algo muy simple que podría ser más rápido: no hay forma de saberlo sin probarlo. Mucho dependerá de la cantidad de bits configurados frente al número no establecido. Podrías desenrollar esto para eliminar por completo la bifurcación, pero con los procesadores de hoy no sé si se aceleraría en absoluto.
unsigned char idx[K+1]; // need one extra for overwrite protection
unsigned char *dst=idx;
for (unsigned char i = 0; i < 50; i++)
{
*dst = i;
dst += x & 1;
x >>= 1;
}
PD su resultado de muestra en la pregunta es incorrecto, vea http://ideone.com/2o032E
Aquí hay un código ajustado, escrito para 1 byte (8 bits), pero debería expandirse fácilmente, obviamente, a 64 bits.
int main(void)
{
int x = 187;
int ans[8] = {-1,-1,-1,-1,-1,-1,-1,-1};
int idx = 0;
while (x)
{
switch (x & ~(x-1))
{
case 0x01: ans[idx++] = 0; break;
case 0x02: ans[idx++] = 1; break;
case 0x04: ans[idx++] = 2; break;
case 0x08: ans[idx++] = 3; break;
case 0x10: ans[idx++] = 4; break;
case 0x20: ans[idx++] = 5; break;
case 0x40: ans[idx++] = 6; break;
case 0x80: ans[idx++] = 7; break;
}
x &= x-1;
}
getchar();
return 0;
}
La matriz de salida debe ser:
ans = {0,1,3,4,5,7,-1,-1};
Asumiendo la escasez en el número de bits establecidos,
int count = 0;
unsigned int tmp_bitmap = x;
while (tmp_bitmap > 0) {
int next_psn = __builtin_ffs(tmp_bitmap) - 1;
tmp_bitmap &= (tmp_bitmap-1);
id[count++] = next_psn;
}
Como una modificación mínima:
int64_t x;
char idx[K+1];
char *dst=idx;
const int BITS = 8;
for (int i = 0 ; i < 64+BITS; i += BITS) {
int y = (x & ((1<<BITS)-1));
char* end = strcat(dst, tab[y]); // tab[y] is a _string_
for (; dst != end; ++dst)
{
*dst += (i - 1); // tab[] is null-terminated so bit positions are 1 to BITS.
}
x >>= BITS;
}
La elección de BITS determina el tamaño de la tabla. 8, 13 y 16 son elecciones lógicas. Cada entrada es una cadena, terminada en cero y contiene posiciones de bit con 1 desplazamiento. Es decir, la pestaña [5] es "/x03/x01" . El lazo interno corrige este desplazamiento.
Ligeramente más eficiente: reemplace el strcat y el bucle interno por
char const* ptr = tab[y];
while (*ptr)
{
*dst++ = *ptr++ + (i-1);
}
El desenrollado del bucle puede ser un poco molesto si el bucle contiene bifurcaciones, porque copiar esas instrucciones bifurcadas no ayuda al pronosticador de bifurcación. Felizmente dejaré esa decisión al compilador.
Una cosa que estoy considerando es que tab[y] es una matriz de punteros a cadenas. Estos son muy similares: "/x1" es un sufijo de "/x3/x1" . De hecho, cada cadena que no comienza con "/x8" es un sufijo de una cadena que sí lo hace. Me pregunto cuántas cadenas únicas necesitas, y hasta qué punto se necesita tab[y] de hecho. Por ejemplo, mediante la lógica anterior, tab[128+x] == tab[x]-1 .
[editar]
No importa, definitivamente necesita entradas de 128 pestañas que comiencen con "/x8" ya que nunca son el sufijo de otra cadena. Aún así, la tab[128+x] == tab[x]-1 significa que puede guardar la mitad de las entradas, pero a costa de dos instrucciones adicionales: char const* ptr = tab[x & 0x7F] - ((x>>7) & 1) . (Configure la tab[] para señalar después de /x8 )
Creo que la clave del rendimiento aquí es centrarse en el problema más grande en lugar de en la micro optimización de la extracción de las posiciones de bits de un entero al azar.
A juzgar por el código de muestra y la pregunta SO anterior, enumera todas las palabras con K bits establecidos en orden, y extrae los índices de bits de estos. Esto simplifica enormemente las cosas.
Si es así, en lugar de reconstruir la posición del bit en cada iteración, intente aumentar las posiciones en la matriz de bits directamente. La mitad de las veces esto implicará una iteración e incremento de un solo bucle.
Algo en esta línea:
// Walk through all len-bit words with num-bits set in order
void enumerate(size_t num, size_t len) {
size_t i;
unsigned int bitpos[64 + 1];
// Seed with the lowest word plus a sentinel
for(i = 0; i < num; ++i)
bitpos[i] = i;
bitpos[i] = 0;
// Here goes the main loop
do {
// Do something with the resulting data
process(bitpos, num);
// Increment the least-significant series of consecutive bits
for(i = 0; bitpos[i + 1] == bitpos[i] + 1; ++i)
bitpos[i] = i;
// Stop on reaching the top
} while(++bitpos[i] != len);
}
// Test function
void process(const unsigned int *bits, size_t num) {
do
printf("%d ", bits[--num]);
while(num);
putchar(''/n'');
}
No particularmente optimizado, pero se entiende la idea general.
La pregunta es: ¿qué vas a hacer con la colección de posiciones?
Si tiene que iterar muchas veces sobre él, entonces sí, podría ser interesante reunirlos una vez como lo está haciendo ahora, e iterar muchos.
Pero si se trata de iterar solo una o varias veces, entonces podría pensar en no crear una matriz intermedia de posiciones, e invocar una función / cierre de bloque de procesamiento en cada 1 encontrado al iterar en bits.
Aquí hay un ejemplo ingenuo del iterador de bits que escribí en Smalltalk:
LargePositiveInteger>>bitsDo: aBlock
| mask offset |
1 to: self digitLength do: [:iByte |
offset := (iByte - 1) << 3.
mask := (self digitAt: iByte).
[mask = 0]
whileFalse:
[aBlock value: mask lowBit + offset.
mask := mask bitAnd: mask - 1]]
Un LargePositiveInteger es un Entero de longitud arbitraria compuesto de dígitos de bytes. El lowBit responde al rango de bit más bajo y se implementa como una tabla de búsqueda con 256 entradas.
En C ++ 2011 puede aprobar fácilmente un cierre, por lo que debe ser fácil de traducir.
uint64_t x;
unsigned int mask;
void (*process_bit_position)(unsigned int);
unsigned char offset = 0;
unsigned char lowBitTable[16] = {0,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0}; // 0-based, first entry is unused
while( x )
{
mask = x & 0xFUL;
while (mask)
{
process_bit_position( lowBitTable[mask]+offset );
mask &= mask - 1;
}
offset += 4;
x >>= 4;
}
El ejemplo se muestra con una tabla de 4 bits, pero puede ampliarlo fácilmente a 13 bits o más si cabe en la memoria caché.
Para la predicción de bifurcación, el bucle interno podría reescribirse como for(i=0;i<nbit;i++) con una tabla adicional nbit=numBitTable[mask] luego desenrollarse con un conmutador (¿el compilador podría hacerlo?), Pero yo le permite medir cómo se realiza primero ...
Si tomo "Necesito una forma rápida de obtener la posición de todos los bits en un entero de 64 bits", literalmente ...
Me doy cuenta de que esto tiene algunas semanas, sin embargo, y por curiosidad, recuerdo mucho en mis días de asamblea con el CBM64 y Amiga utilizando un cambio aritmético y luego examinando la bandera de acarreo: si está configurada, el bit desplazado era 1, si claro, entonces es cero
por ejemplo, para un desplazamiento aritmético a la izquierda (examinando desde el bit 64 al bit 0) ....
pseudo code (ignore instruction mix etc errors and oversimplification...been a while):
move #64+1, counter
loop. ASL 64bitinteger
BCS carryset
decctr. dec counter
bne loop
exit
carryset.
//store #counter-1 (i.e. bit position) in datastruct indexed by counter
jmp decctr
...Espero que captes la idea.
No he usado el ensamblaje desde entonces, pero me pregunto si podríamos usar un ensamblado C ++ en línea similar al anterior para hacer algo similar aquí. Podríamos hacer toda la conversión en conjunto (muy pocas líneas de código), creando una estructura de datos adecuada. C ++ podría simplemente examinar la respuesta.
Si esto es posible, me imagino que será bastante rápido.
Su código está usando una tabla de índice de 1 byte (256 entradas). Puede acelerarlo en un factor de 2 si usa una tabla de índice de 2 bytes (65536 entradas).
Desafortunadamente, es probable que no pueda extenderlo más, ya que el tamaño de la tabla de 3 bytes sería de 16 MB, no es probable que se ajuste a la memoria caché local de la CPU, y solo haría las cosas más lentas.
Usar char no lo ayudaría a aumentar la velocidad, pero de hecho a menudo necesita más ANDing y extensión de signo / cero al calcular. Solo en el caso de arreglos muy grandes que deberían caber en la memoria caché, se deben usar tipos int más pequeños
Otra cosa que puedes mejorar es la macro COPY. En lugar de copiar byte a byte, copie la palabra completa si es posible
inline COPY(unsigned char *dst, unsigned char *src, int n)
{
switch(n) { // remember to align dst and src when declaring
case 8:
*((int64_t*)dst) = *((int64_t*)src);
break;
case 7:
*((int32_t*)dst) = *((int32_t*)src);
*((int16_t*)(dst + 4)) = *((int32_t*)(src + 4));
dst[6] = src[6];
break;
case 6:
*((int32_t*)dst) = *((int32_t*)src);
*((int16_t*)(dst + 4)) = *((int32_t*)(src + 4));
break;
case 5:
*((int32_t*)dst) = *((int32_t*)src);
dst[4] = src[4];
break;
case 4:
*((int32_t*)dst) = *((int32_t*)src);
break;
case 3:
*((int16_t*)dst) = *((int16_t*)src);
dst[2] = src[2];
break;
case 2:
*((int16_t*)dst) = *((int16_t*)src);
break;
case 1:
dst[0] = src[0];
break;
case 0:
break;
}
Además, como tabofs [x] yn [x] suelen tener acceso cercano, intente cerrarlo en la memoria para asegurarse de que siempre estén en caché al mismo tiempo.
typedef struct TAB_N
{
int16_t n, tabofs;
} tab_n[256];
src=tab0+tab_n[b0].tabofs; COPY(dst, src, tab_n[b0].n);
src=tab0+tab_n[b1].tabofs; COPY(dst, src, tab_n[b1].n);
src=tab0+tab_n[b2].tabofs; COPY(dst, src, tab_n[b2].n);
src=tab0+tab_n[b3].tabofs; COPY(dst, src, tab_n[b3].n);
src=tab0+tab_n[b4].tabofs; COPY(dst, src, tab_n[b4].n);
src=tab0+tab_n[b5].tabofs; COPY(dst, src, tab_n[b5].n);
Por último, pero no menos importante, gettimeofday no es para contar el rendimiento. Use QueryPerformanceCounter en QueryPerformanceCounter lugar, es mucho más preciso