我必须计算汉明权重才能获得非常连续的64位数据流，并且使用popcnt汇编指令使我的Intel Core 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位，然后使用 super 压缩的vpsadbw将8个字节添加到64位值(ymm4 = 0)。有人加快了步伐吗？
编辑:
POPCNT失败是由于我在代码中犯了一个错误，该功能在我的Intel Core i7-4650U上有效。请参阅下面显示我的替补成绩的帖子。 最佳答案
我得出的结论是，我不是想要变得“聪明”的人，我替补登台了:
内置的内置popcount:_mm_popcnt_u64
bmi2:__tzcnt_u64(~_pext_u64(data[i],data[i]));针对三个汇编器功能
popcnt，bmi2和avx2。
它们都以您可以将内存移入和移出我的速度运行:
cat /proc/cpuinfo
-英特尔®至强®CPU E3-1275 v3 @ 3.50GHz
供引用:
main.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;
}
引擎
//
// 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结果:
平均数据移动时间:61
平均人口:61
平均bmi2:61
现在测试汇编器功能
平均popcnt_asm:61
平均bmi2_asm:61
平均avx2_asm:61