（相关：如何在Sandy Bridge上的一系列int中快速将位计数到单独的bin中？是对此的早期复制，带有一些不同的答案。编者注：这里的答案可能更好。
同样，是类似问题的AVX2版本，整行位的许多bin比一个宽得多uint64_t：改进列填充计数算法）
我正在C中的一个项目中，我需要经历数千万个掩码（ulong类型（64位）），并target基于一个简单规则更新64个短整数（uint16）的数组（称为）：
// for any given mask, do the following loop
for (i = 0; i < 64; i++) {
if (mask & (1ull << i)) {
target[i]++
}
}
问题是我需要在数以百万计的蒙版上执行上述循环，并且我需要在不到一秒钟的时间内完成。想知道是否有任何方法可以加快它的速度，例如使用某种表示上述循环的特殊汇编指令。
目前，我在ubuntu 14.04（i7-2670QM，支持AVX，而不是AVX2）上使用gcc 4.8.4来编译和运行以下代码，大约需要2秒钟。很想让它在200ms以下运行。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <sys/stat.h>
double getTS() {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec / 1000000.0;
}
unsigned int target[64];
int main(int argc, char *argv[]) {
int i, …我有一大块内存,比如256 KiB或更长.我想计算整个块中的1位数,或者换句话说:为所有字节添加"种群计数"值.
我知道AVX-512有一个VPOPCNTDQ指令,它计算512位向量中每个连续64位的1位数,而IIANM应该可以在每个周期发出其中一个(如果一个适当的SIMD向量寄存器是可用) - 但我没有任何编写SIMD代码的经验(我更像是一个GPU人).此外,我不是100%确定AVX-512目标的编译器支持.
在大多数CPU上,仍然没有(完全)支持AVX-512; 但AVX-2广泛可用.我无法找到类似于VPOPCNTDQ的低于512位的向量化指令,所以即使理论上我也不确定如何使用支持AVX-2的CPU快速计算位数; 也许这样的事情存在,我只是错过了它？
无论如何,对于两个指令集中的每一个,我都很欣赏一个简短的C/C++函数 - 使用一些内部包装库或内联汇编.签名是
uint64_t count_bits(void* ptr, size_t size);
笔记:
解释这一点的最佳方式是演示.
有一组数字.它们可能会重复,因此:
1110,0100,0100,0010,0110 ......
我正在寻找的数字是有点设置的数字,不会出现在任何其他数字中.结果是数字(在这种情况下为1 - 第一个数字)和位位置(或掩码很好)所以1000(第4位).可能有多个解决方案,但为此目的,它可能是贪婪的.
我可以通过迭代来做...对于每个数字N,它是:
N&〜(其他数字也在一起)
但是比特的本质是,如果你在盒子外思考,总有一种更好的方法.例如,出现多次的数字永远不会有唯一的位,并且对ORing没有影响.
对于我正在处理的项目，我需要计算翻录PDF图像数据中每列的设置位数。
我正在尝试获取整个PDF作业（所有页面）中每一列的总设置位数。
数据一旦被翻录，就会存储在一个MemoryMappedFile没有后备文件（在内存中）中。
PDF 页面尺寸为 13952 像素 x 15125 像素。生成的翻录数据的总大小可以通过将PDF像素的长度（高度）乘以字节的宽度来计算。翻录的数据是1 bit == 1 pixel. 因此，以字节为单位的翻录页面的大小是(13952 / 8) * 15125.
请注意，宽度始终是 的倍数64 bits。
PDF在被翻录后，我必须计算 a 的每一页（可能是数万页）中每一列的设置位。
我首先用一个基本的解决方案来解决这个问题，即循环遍历每个字节并计算设置位的数量并将结果放在vector. 从那以后，我将算法缩减为如下所示。我的执行时间从 ~350ms 到 ~120ms。
static void count_dots( )
{
using namespace diag;
using namespace std::chrono;
std::vector<std::size_t> dot_counts( 13952, 0 );
uint64_t* ptr_dot_counts{ dot_counts.data( ) };
std::vector<uint64_t> ripped_pdf_data( 3297250, 0xFFFFFFFFFFFFFFFFUL );
const uint64_t* ptr_data{ ripped_pdf_data.data( ) };
std::size_t …