Najszybsza 64-bitowa liczba populacji (masa Hamminga)

Question

Musiałem obliczyć wagę Hamminga dla dość szybkiego, ciągłego przepływu danych 64-bitowych i za pomocą instrukcji montażu popcnt rzuca mi wyjątek om mojego Intel Core i7-4650U.

Sprawdziłem zachwyt Hackerowskiej Biblii i przeskanowałem stronę internetową pod kątem różnych algorytmów (jest tam sporo, odkąd zaczęli rozwiązywać ten problem przy narodzinach komputerów).

Spędziłem weekend bawiąc się własnymi pomysłami i wymyśliłem te algorytmy, w których jestem prawie na tyle szybki, że mogę przenosić dane do iz procesora.

//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 

W powyższym kod za pomocą pext (BMI2), gdzie dane wejściowe stosuje się jako maska. Wtedy wszystkie istniejące bity zostaną zwinięte zaczynając od najmniej znaczącego bitu w rejestrze wyników (samo w sobie). Następnie muszę obliczyć liczbę zwiniętych bitów, więc odwracam wszystkie bity, a następnie używam tzcnt, aby policzyć liczbę zer teraz. Myślałem, że to całkiem niezły pomysł.

Potem próbowałem również podejście AVX2:

//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 

W przypadku AVX2 czytałem 32 bajtów, a następnie maskować się z przekąski (ymm2), a następnie użyć ymm3 jak patrzeć w górę tabeli nieco licząc Nibbles. Następnie dodałem wyniki do 8-bitowych, a następnie używam super skondensowanego vpsadbw, aby dodać 8 bajtów do wartości 64-bitowej (ymm4 = 0).

Ktoś ma coś szybciej w swoich rękawach?

Edit:

niewydolnego POPCNT był wynikiem błędu zrobiłem w moim kodu, że prace funkcyjne om mój Intel Core i7-4650U. Proszę zobaczyć mój post poniżej wyświetlający wyniki ławki.

Answer 1

OK doszedł do wniosku, że to nie był pomysł starając się być 'inteligentne', ja benched:

wbudowanej wewnętrznej popcount: _mm_popcnt_u64

bmi2: __tzcnt_u64(~_pext_u64(data[i],data[i])); przeciwko trzy funkcje asemblera

popcnt, bmi2 i avx2.

Wszyscy prowadzony z prędkością można poruszać się pamięć i poza moim:

cat /proc/cpuinfo 

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

FYI:

główny.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; 
} 

W 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 

Kompilacja źródeł:

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

ustawienie procesora CPU do wykonywania:

cpufreq-set -g performance

Uruchom ława:

sudo chrt -r 10 ./a.out

Wynik:

Średnia time_to_move_data: 61

Średnia popcnt: 61

Średnia bmi2: 61

Teraz Sprawdź funkcje Assembler

Średnia popcnt_asm: 61

Średnia bmi2_asm: 61

Średnia avx2_asm: 61

Answer 2

Czy próbowałeś podejścia opartego na tabeli, jak:

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]]; 

lub może toczyć go samodzielnie w ASM.