performance - 最快的 64 位人口计数(汉明权重)

Question

我必须为 64 位数据的快速连续流计算汉明权重，并使用 popcnt汇编指令在我的英特尔酷睿 i7-4650U 上抛出了一个异常。

我检查了我的圣经黑客的喜悦，并在网上扫描了各种算法(因为他们在计算诞生时就开始解决这个“问题”，所以那里有很多算法)。

我整个周末都在玩我自己的一些想法并提出了这些算法，我几乎可以将数据移入和移出 CPU。

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

在上面的代码中，我使用 pext (BMI2)，其中传入数据使用自身作为掩码。然后所有存在的位将从结果寄存器中的最低有效位(再次本身)开始崩溃。然后我需要计算折叠位的数量，所以我反转所有位然后使用 tzcnt计算数量，现在为零。我认为这是一个很好的主意。

然后我也尝试了一种 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

在 AVX2 的情况下，我读取 32 个字节，然后屏蔽掉半字节( ymm2 )，然后我使用 ymm3作为位计数半字节的查找表。然后我将结果添加到 8 位，然后我使用超浓缩 vpsadbw将 8 个字节添加到 64 位值 ( ymm4 = 0)。

任何人都更快地掌握了一些东西？

编辑:

失败的 POPCNT是由于我在代码中犯的错误，该功能在我的英特尔酷睿 i7-4650U 上工作。请参阅我下面的帖子，其中显示了工作台结果。

Answer 1

OK 得出的结论是，试图变得“聪明”是没有办法的，我站了起来:

内置的内在 popcount:_mm_popcnt_u64
bmi2:__tzcnt_u64(~_pext_u64(data[i],data[i]));针对三个汇编函数

popcnt、bmi2 和 avx2。

它们都以您可以将内存移入和移出我的速度运行:

cat /proc/cpuinfo

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

供引用:

主文件:

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

发动机.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

编译源:
g++ -march=native -mavx -mpopcnt -O3 main.c engine.s
将 CPU 设置为性能:
cpufreq-set -g performance
运行板凳:
sudo chrt -r 10 ./a.out
结果:

平均 time_to_move_data:61

平均popcnt:61

平均 bmi2:61

现在测试汇编函数

平均 popcnt_asm:61

平均 bmi2_asm:61

平均 avx2_asm:61