Bit popcount per buffer grande, con Core 2 CPU (SSSE3)

Question

sto cercando il modo più veloce per popcount sul buffer di grandi dimensioni di 512 o più byte. Posso garantire qualsiasi allineamento richiesto, e la dimensione del buffer è sempre una potenza di 2. I corrisponde tampone di bloccare allocazioni, così tipicamente i bit sono o tutti insieme, nessuna insieme, o prevalentemente impostare favorire la "sinistra" del tampone, con fori occasionali.

Alcune soluzioni ho prese in considerazione sono:

• __builtin_popcount
• BitSlice popcount_24words
• conteggio bit set, modo di Brian Kernighan

Mi interessa la soluzione più veloce, deve lavorare su 32bit x86 chipset appartenenti a Core2 o più recente. SSE e SIMD sono di grande interesse. Sarò testato sui seguenti CPU quad core:

matt@stanley:~/anacrolix/public/stackoverflow$ cat /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz
stepping        : 11
cpu MHz         : 1600.000
cache size      : 4096 KB
physical id     : 0
siblings        : 4
core id         : 0
cpu cores       : 4
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 10
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm tpr_shadow vnmi flexpriority
bogomips        : 4800.21
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Answer 1

I delineare il miglior C / assemblaggio funzioni che ho trovato per conteggio popolazione / peso di Hamming di grandi dimensioni tamponi indicati.

La funzione più veloce assemblaggio è ssse3_popcount3 , descritto qui . Richiede SSSE3 , disponibili sul processore Intel Core 2 e versioni successive e chipset AMD in arrivo nel 2011. Esso utilizza SIMD istruzioni per popcount in 16 blocchi di byte e srotola 4 iterazioni del ciclo alla volta.

La funzione più veloce C è popcount_24words , descritto qui . Si utilizza l'algoritmo bit-slicing. Da segnalare ho scoperto che clang potrebbe effettivamente generare adeguate istruzioni di montaggio vettore, che ha dato notevoli aumenti di prestazioni. A parte questo, l'algoritmo è ancora estremamente veloce.

Answer 2

Vedere una versione a 32 bit nella AMD Software Optimization guide , pagina 195 per un'implementazione. Questo ti dà il montaggio codice per un sistema x86 direttamente.

Vedere una variante al Stanford bit-giocherellando hack La versione sguardi Stanford piace il migliore per me. Sembra molto facile da codice come asm x86.

Nessuna di queste istruzioni uso filiali.

Si può essere generalizzato per le versioni a 64 bit.

Con le versioni a 32 o 64 bit, si potrebbe prendere in considerazione di fare una versione SIMD. SSE2 farà 4 doppie parole o due quadwords (in entrambi i casi 128 bit) in una sola volta. Che cosa si vuole fare è attuare la popcount per 32 o 64 bit in ciascuno dei 2 o 4 registri disponibili. Vi ritroverete con 2 o 4 set di popcounts nei registri XMM quando hai finito; passo finale è quello di memorizzare e aggiungere quelli popcounts insieme per ottenere la risposta finale. indovinando, Mi aspetto lo fate un po 'meglio fare 4 parallelo 32 popcounts bit anziché 2 parallela a 64 bit, popcounts in quanto quest'ultimo rischia di prendere 1 o 2 ulteriori istruzioni in ogni iterazione, e la sua facile aggiungere 4, 32 valori di bit insieme la fine.

Answer 3

Se had POPCNT:

http: // kent-Vandervelden .blogspot.com / 2009/10 / conteggio-bits-popolazione-count-and.html

http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011/compiler_c/intref_cls/common/intref_sse42_ATA.htm

Answer 4

vorrei suggerire attuare uno dei ottimizzati 32 routine POPCNT bit da Hacker , ma farlo per 4 x 32 bit integer elementi in un vettore SSE. È quindi possibile elaborare 128 bit per iterazione, che dovrebbe dare in giro 4x rendimento rispetto ad un ottimizzato routine di scalare a 32 bit.