Bit popcount pour un tampon important, avec processeur Core 2 (SSSE3)

Je cherche le moyen le plus rapide de décompter un grand tampon de 512 octets ou plus. Je peux garantir n’importe quel alignement requirejs, et la taille de la mémoire tampon est toujours une puissance de 2. La mémoire tampon correspond à des affectations de blocs, de sorte que les bits sont généralement tous définis, aucun ensemble ou principalement définis en faveur de la “gauche” du tampon trous occasionnels.

Certaines solutions que j’ai envisagées sont:

  • __builtin_popcount de GCC
  • Bitslice popcount_24words
  • Le comptage de bits défini, à la manière de Brian Kernighan

Je suis intéressé par la solution la plus rapide, elle doit fonctionner sur un chipset 32bit x86 appartenant à core2 ou plus récent. SSE et SIMD présentent un grand intérêt. Je vais tester sur le processeur quad core suivant:

 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: 

Reportez-vous à la version 32 bits du Guide d’optimisation des logiciels AMD , page 197 pour une implémentation. Cela vous donne directement le code d’assemblage pour un x86.

Voir une variante à Stanford bidouilles bidirectionnelles La version de Stanford ressemble à la meilleure pour moi. Il semble très facile de coder en tant que x86 asm.

Ni l’un ni l’autre n’utilise d’instructions de twig

Celles-ci peuvent être généralisées aux versions 64 bits.

Avec les versions 32 ou 64 bits, vous pouvez envisager de faire une version SIMD. SSE2 fera 4 doubles-mots ou deux quadwords (128 bits) à la fois. Ce que vous voulez faire, c’est implémenter le popcount pour 32 ou 64 bits dans chacun des 2 ou 4 registres disponibles. Lorsque vous avez terminé, vous obtiendrez 2 ou 4 séries de compteurs pop-up dans les registres XMM. La dernière étape consiste à stocker et à additionner ces popcounts pour obtenir la réponse finale. En fait, je m’attendrais à ce que vous le fassiez légèrement mieux en faisant 4 popcount parallèles 32 bits plutôt que 2 parallèles popcount 64 bits, car ce dernier est susceptible de prendre 1 ou 2 instructions supplémentaires à chaque itération, et il est facile d’append 4, 32 bits valeurs ensemble la fin.

Je décris ci-dessous les meilleures fonctions d’assemblage / C que j’ai trouvées pour la numération de population / le poids de Hamming des grands tampons.

La fonction d’assemblage la plus rapide est ssse3_popcount3 , décrite ici . Il nécessite SSSE3 , disponible sur les processeurs Intel Core 2 et ultérieurs, et les chipsets AMD arrivant en 2011. Il utilise les instructions SIMD pour décompter des fragments de 16 octets et dérouler 4 itérations de boucle à la fois.

La fonction C la plus rapide est popcount_24words , décrite ici . Il utilise l’algorithme de tranchage de bits. Il est à noter que j’ai découvert que clang pouvait en réalité générer des instructions d’assemblage de vecteurs appropriées, ce qui donnait des gains de performances impressionnants. Cela dit, l’algorithme est encore extrêmement rapide.

Je suggérerais de mettre en œuvre l’une des routines popcnt 32 bits optimisées de Hacker’s Delight , mais que vous le fassiez pour des éléments entiers 4 x 32 bits dans un vecteur SSE. Vous pouvez ensuite traiter 128 bits par itération, ce qui devrait vous donner un débit d’environ 4x par rapport à une routine scalaire 32 bits optimisée.