Schnellste 64-Bit-Anzahl (Hamming-Gewicht)

Question

Ich musste das Hamming-Gewicht für einen ziemlich schnellen kontinuierlichen Fluss von 64-Bit-Daten berechnen und die Verwendung der popcnt Montageanleitung wirft mir eine Ausnahme von meinem Intel Core i7-4650U.

Ich überprüfte meine Hacker-Freude und durchsuchte das Internet nach allen Arten von Algorithmen (es ist ein Haufen da draußen, seit sie begannen, dieses "Problem" bei der Geburt des Computers anzugehen).

Ich verbrachte das Wochenende damit, mit einigen eigenen Ideen herumzuspielen und kam zu diesen Algorithmen, bei denen ich fast mit der Geschwindigkeit bin, mit der ich Daten in und aus der CPU bewegen kann.

//64-bit popcnt using BMI2 
_popcnt_bmi2: 
     mov   (%rdi),%r11 
     pext  %r11,%r11,%r11 
     not   %r11 
     tzcnt  %r11,%r11 
     mov   %r11,(%rdx) 
     add   $8h,%rdi 
     add   $8h,%rdx 
     dec   %rsi 
     jnz   _popcnt_bmi2 
     ret 

In dem obigen Code verwende ich pext (BMI2), wo die eingehenden Daten selbst als Maske verwendet wird. Dann werden alle vorhandenen Bits zusammenbrechen, beginnend mit dem am wenigsten signifikanten Bit im Ergebnisregister (wiederum selbst). Dann muss ich die Anzahl der kollabierten Bits berechnen, so dass ich alle Bits invertiere und dann tzcnt verwende, um die Anzahl der jetzt Nullen zu zählen. Ich dachte, das wäre eine ganz nette Idee.

Dann habe ich versucht, auch einen AVX2 Ansatz:

//64-bit popcnt using AVX2 
_popcnt_avx2: 
     vmovdqa  (%rcx),%ymm2 
     add   $20h,%rcx 
     vmovdqa  (%rcx),%ymm3 
     add   $20h,%rcx 
     vmovdqa  (%rcx),%ymm4 
popcnt_avx2_loop: 
     vmovdqa  (%rdi),%ymm0 
     vpand  %ymm0, %ymm2, %ymm1 
     vpandn  %ymm0, %ymm2, %ymm0 
     vpsrld  $4h,%ymm0, %ymm0 
     vpshufb  %ymm1, %ymm3, %ymm1 
     vpshufb  %ymm0, %ymm3, %ymm0 
     vpaddb  %ymm1,%ymm0,%ymm0  //popcnt (8-bits) 
     vpsadbw  %ymm0,%ymm4,%ymm0  //popcnt (64-bits) 
     vmovdqa  %ymm0,(%rdx) 
     add   $20h,%rdi 
     add   $20h,%rdx 
     dec   %rsi 
     jnz   popcnt_avx2_loop 

Im AVX2 Fall, dass ich 32 Byte lesen, dann die Knabbereien maskiert (ymm2), dann verwende ich ymm3 als Nachschlagetabelle für Bit des Zählen knabbert. Dann füge ich die Ergebnisse zu 8-Bit hinzu, und dann verwende ich die superkonsolidierte vpsadbw, um 8 Bytes zu einem 64-Bit-Wert hinzuzufügen (ymm4 = 0).

Wer hat etwas schneller in den Schoß?

Edit:

Das Versagen POPCNT war wegen auf einen Fehler, den ich in meinem Code gemacht, dass die Funktion funktioniert om mein Intel Core i7-4650U. Bitte sehen Sie meinen Post unten, der die Bankergebnisse anzeigt.

Answer 1

OK zu dem Schluss gekommen, dass es keine Idee zu versuchen, 'intelligenten' zu sein, ich benched:

die in Eigen PopCount gebaut: _mm_popcnt_u64

BMI2: __tzcnt_u64(~_pext_u64(data[i],data[i])); gegen drei Assembler-Funktionen

popcnt, bmi2 und avx2.

Sie alle laufen mit der Geschwindigkeit Sie Speicher in und aus meinem bewegen kann:

cat /proc/cpuinfo 

-Intel (R) Xeon (R) Prozessor E3-1275 v3 @ 3.50GHz

FYI:

Haupt.c:

// Hamming weight bench 

#include <stdio.h> 
#include <string.h> 
#include <stdint.h> 
#include <stdlib.h> 
#include <math.h> 
#include <sys/time.h> 
#include <smmintrin.h> 
#include <immintrin.h> 
#include <x86intrin.h> 
#include <math.h> 

#define DISPLAY_HEIGHT 4 
#define DISPLAY_WIDTH 32 
#define NUM_DATA_OBJECTS 40000000 
#define ITTERATIONS 20 

// The source data (+32 to avoid the quantization out of memory problem) 
__attribute__ ((aligned(32))) static long long unsigned data[NUM_DATA_OBJECTS+32]={}; 
__attribute__ ((aligned(32))) static long long unsigned data_out[NUM_DATA_OBJECTS+32]={}; 
__attribute__ ((aligned(32))) static unsigned char k1[32*3]={ 
    0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f, 
    0x00,0x01,0x01,0x02,0x01,0x02,0x02,0x03,0x01,0x02,0x02,0x03,0x02,0x03,0x03,0x04,0x00,0x01,0x01,0x02,0x01,0x02,0x02,0x03,0x01,0x02,0x02,0x03,0x02,0x03,0x03,0x04, 
    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00 
}; 


extern "C" { 
void popcnt_popcnt(long long unsigned[],unsigned int,long long unsigned[]); 
void popcnt_bmi2(long long unsigned[],unsigned int,long long unsigned[]); 
void popcnt_avx2(long long unsigned[],unsigned int,long long unsigned[],unsigned char[]); 
} 

void populate_data() 
{ 
    for(unsigned int i = 0; i < NUM_DATA_OBJECTS; i++) 
    { 
     data[i] = rand(); 
    } 
} 

void display_source_data() 
{ 
    printf ("\r\nData in(start):\r\n"); 
    for (unsigned int j = 0; j < DISPLAY_HEIGHT; j++) 
    { 
     for (unsigned int i = 0; i < DISPLAY_WIDTH; i++) 
     { 
      printf ("0x%02llux,",data[i+(j*DISPLAY_WIDTH)]); 
     } 
     printf ("\r\n"); 
    } 
} 

void bench_popcnt() 
{ 
    for(unsigned int i = 0; i < NUM_DATA_OBJECTS; i++) 
    { 
     data_out[i] = _mm_popcnt_u64(data[i]); 
    } 
} 

void bench_move_data_memcpy() 
{ 
    memcpy(data_out,data,NUM_DATA_OBJECTS*8); 
} 

// __tzcnt64 ?? 
void bench_bmi2() 
{ 
    for(unsigned int i = 0; i < NUM_DATA_OBJECTS; i++) 
    { 
     data_out[i]=__tzcnt_u64(~_pext_u64(data[i],data[i])); 
    } 
} 

void display_dest_data() 
{ 
    printf ("\r\nData out:\r\n"); 
    for (unsigned int j = 0; j < DISPLAY_HEIGHT; j++) 
    { 
     for (unsigned int i = 0; i < DISPLAY_WIDTH; i++) 
     { 
      printf ("0x%02llux,",data_out[i+(j*DISPLAY_WIDTH)]); 
     } 
     printf ("\r\n"); 
    } 
} 


int main() { 
    struct timeval t0; 
    struct timeval t1; 
    long elapsed[ITTERATIONS]={0}; 
    long avrg=0; 

    for (unsigned int i = 0; i < ITTERATIONS; i++) 
    { 
     populate_data(); 
     // display_source_data(); 
     gettimeofday(&t0, 0); 
     bench_move_data_memcpy(); 
     gettimeofday(&t1, 0); 
     elapsed[i]= (((t1.tv_sec-t0.tv_sec)*1000000 + t1.tv_usec-t0.tv_usec)/1000); 
     printf ("Time_to_move_data_without_processing: %ld\n",elapsed[i]); 
    } 

    avrg=0; 
    for (unsigned int i = 1; i < ITTERATIONS; i++){ 
     avrg+=elapsed[i]; 
    } 
    printf ("Average time_to_move_data: %ld\n",avrg/(ITTERATIONS-1)); 

    //display_dest_data(); 

    for (unsigned int i = 0; i < ITTERATIONS; i++) 
    { 
     populate_data(); 
     // display_source_data(); 
     gettimeofday(&t0, 0); 
     bench_popcnt(); 
     gettimeofday(&t1, 0); 
     elapsed[i] = ((t1.tv_sec-t0.tv_sec)*1000000 + t1.tv_usec-t0.tv_usec)/1000; 
     printf ("popcnt: %ld\n",elapsed[i]); 
    } 

    avrg=0; 
    for (unsigned int i = 1; i < ITTERATIONS; i++){ 
     avrg+=elapsed[i]; 
    } 
    printf ("Average popcnt: %ld\n",avrg/(ITTERATIONS-1)); 

    //display_dest_data(); 

    for (unsigned int i = 0; i < ITTERATIONS; i++) 
    { 
     populate_data(); 
     // display_source_data(); 
     gettimeofday(&t0, 0); 
     bench_bmi2(); 
     gettimeofday(&t1, 0); 
     elapsed[i] = ((t1.tv_sec-t0.tv_sec)*1000000 + t1.tv_usec-t0.tv_usec)/1000; 
     printf ("bmi2: %ld\n",elapsed[i]); 
    } 

    avrg=0; 
    for (unsigned int i = 1; i < ITTERATIONS; i++){ 
     avrg+=elapsed[i]; 
    } 
    printf ("Average bmi2: %ld\n",avrg/(ITTERATIONS-1)); 

    //display_dest_data(); 


    printf ("Now test the assembler functions\n"); 

    for (unsigned int i = 0; i < ITTERATIONS; i++) 
    { 
     populate_data(); 
     // display_source_data(); 
     gettimeofday(&t0, 0); 
     popcnt_popcnt(data,NUM_DATA_OBJECTS,data_out); 
     gettimeofday(&t1, 0); 
     elapsed[i] = ((t1.tv_sec-t0.tv_sec)*1000000 + t1.tv_usec-t0.tv_usec)/1000; 
     printf ("popcnt_asm: %ld\n",elapsed[i]); 
    } 

    avrg=0; 
    for (unsigned int i = 1; i < ITTERATIONS; i++){ 
     avrg+=elapsed[i]; 
    } 
    printf ("Average popcnt_asm: %ld\n",avrg/(ITTERATIONS-1)); 

    //display_dest_data(); 

    for (unsigned int i = 0; i < ITTERATIONS; i++) 
    { 
     populate_data(); 
     // display_source_data(); 
     gettimeofday(&t0, 0); 
     popcnt_bmi2(data,NUM_DATA_OBJECTS,data_out); 
     gettimeofday(&t1, 0); 
     elapsed[i] = ((t1.tv_sec-t0.tv_sec)*1000000 + t1.tv_usec-t0.tv_usec)/1000; 
     printf ("bmi2_asm: %ld\n",elapsed[i]); 
    } 

    avrg=0; 
    for (unsigned int i = 1; i < ITTERATIONS; i++){ 
     avrg+=elapsed[i]; 
    } 
    printf ("Average bmi2_asm: %ld\n",avrg/(ITTERATIONS-1)); 

    //display_dest_data(); 

    for (unsigned int i = 0; i < ITTERATIONS; i++) 
    { 
     populate_data(); 
     // display_source_data(); 
     gettimeofday(&t0, 0); 
     popcnt_avx2(data,(unsigned int)ceil((NUM_DATA_OBJECTS*8)/32.0),data_out,k1); 
     gettimeofday(&t1, 0); 
     elapsed[i] = ((t1.tv_sec-t0.tv_sec)*1000000 + t1.tv_usec-t0.tv_usec)/1000; 
     printf ("avx2_asm: %ld\n",elapsed[i]); 
    } 

    avrg=0; 
    for (unsigned int i = 1; i < ITTERATIONS; i++){ 
     avrg+=elapsed[i]; 
    } 
    printf ("Average avx2_asm: %ld\n",avrg/(ITTERATIONS-1)); 

    //display_dest_data(); 

    return 0; 
} 

Die engine.s

// 
// avx2_bmi2_popcnt bench 
// 

.global popcnt_bmi2 , popcnt_avx2, popcnt_popcnt 
.align 2 

//64-bit popcnt using the built-in popcnt instruction 
popcnt_popcnt: 
     popcntq  (%rdi), %r11 
     mov   %r11,(%rdx) 
     add   $8,%rdi 
     add   $8,%rdx 
     dec   %rsi 
     jnz   popcnt_popcnt 
     ret 

//64-bit popcnt using BMI2 
popcnt_bmi2: 
     mov   (%rdi),%r11 
     pextq  %r11,%r11,%r11 
     not   %r11 
     tzcnt  %r11,%r11 
     mov   %r11,(%rdx) 
     add   $8,%rdi 
     add   $8,%rdx 
     dec   %rsi 
     jnz   popcnt_bmi2 
     ret 

//64-bit popcnt using AVX2 
popcnt_avx2: 
     vmovdqa  (%rcx),%ymm2 
     add   $0x20,%rcx 
     vmovdqa  (%rcx),%ymm3 
     add   $0x20,%rcx 
     vmovdqa  (%rcx),%ymm4 
popcnt_avx2_loop: 
     vmovdqa  (%rdi),%ymm0 
     vpand  %ymm0, %ymm2, %ymm1 
     vpandn  %ymm0, %ymm2, %ymm0 
     vpsrld  $4,%ymm0, %ymm0 
     vpshufb  %ymm1, %ymm3, %ymm1 
     vpshufb  %ymm0, %ymm3, %ymm0 
     vpaddb  %ymm1,%ymm0,%ymm0 
     vpsadbw  %ymm0,%ymm4,%ymm0 
     vmovdqa  %ymm0,(%rdx) 
     add   $0x20,%rdi 
     add   $0x20,%rdx 
     dec   %rsi 
     jnz   popcnt_avx2_loop 
     ret 

Kompilieren der Quellen:

g++ -march=native -mavx -mpopcnt -O3 main.c engine.s

eingestellt, um die Leistung der CPU:

cpufreq-set -g performance

Führen Sie die Bank:

sudo chrt -r 10 ./a.out

Ergebnis:

Durchschnittliche time_to_move_data: 61

Durchschnittliche popcnt: 61

Durchschnittliche BMI2: 61

Testen Sie nun die Assembler-Funktionen

Durchschnittliche popcnt_asm: 61

Durchschnittliche bmi2_asm: 61

Durchschnittliche avx2_asm: 61

Answer 2

Haben Sie eine tabellenbasierte Ansatz versucht, wie:

unsigned char bitcnt[256] = {0,1,1,2,1, ... ,7,8}; 

unsigned char* p = &the64bitWord; 

nbits = bitcnt[p[0]] 
    + bitcnt[p[1]] 
    + bitcnt[p[2]] 
    ... 
    + bitcnt[p[7]]; 

oder es vielleicht rollen sich in nh.