使用 AVX 但不使用 AVX2，分别计算许多 64 位位掩码上的每个位位置

Question

(相关:How to quickly count bits into separate bins in a series of ints on Sandy Bridge? 是这个的早期副本，有一些不同的答案。编者注:这里的答案可能更好。

另外，一个类似问题的 AVX2 版本，整行位的许多 bin 比一个 uint64_t 宽得多:Improve column population count algorithm )

---

我正在用 C 开发一个项目，我需要遍历数千万个掩码(类型为 ulong(64 位))并更新一个 64 位短数组(称为 target)基于简单规则的整数 (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 秒。希望让它在 200 毫秒内运行。

#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, j;
    unsigned long x = 123;
    unsigned long m = 1;
    char *p = malloc(8 * 10000000);
    if (!p) {
        printf("failed to allocate\n");
        exit(0);
    }
    memset(p, 0xff, 80000000);
    printf("p=%p\n", p);
    unsigned long *pLong = (unsigned long*)p;
    double start = getTS();
    for (j = 0; j < 10000000; j++) {
        m = 1;
        for (i = 0; i < 64; i++) {
            if ((pLong[j] & m) == m) {
                target[i]++;
            }
            m = (m << 1);
        }
    }
    printf("took %f secs\n", getTS() - start);
    return 0;
}

提前致谢!

Answer 1

在我的系统上，一台使用了 4 年的 MacBook(2.7 GHz 英特尔酷睿 i5)和 clang-900.0.39.2 -O3，您的代码运行时间为 500 毫秒。

只需将内部测试更改为 if ((pLong[j] & m) != 0) 即可节省 30%，运行时间为 350 毫秒。

进一步将内部部分简化为 target[i] += (pLong[j] >> i) & 1;，无需测试将其降低到 280 毫秒。

进一步的改进似乎需要更先进的技术，例如将位解压缩为 8 个 ulong 的 block 并并行添加这些 block ，一次处理 255 个 ulong。

这是使用此方法的改进版本。它在我的系统上运行时间为 45 毫秒。

#include <stdint.h>
#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;
}

int main(int argc, char *argv[]) {
    unsigned int target[64] = { 0 };
    unsigned long *pLong = malloc(sizeof(*pLong) * 10000000);
    int i, j;

    if (!pLong) {
        printf("failed to allocate\n");
        exit(1);
    }
    memset(pLong, 0xff, sizeof(*pLong) * 10000000);
    printf("p=%p\n", (void*)pLong);
    double start = getTS();
    uint64_t inflate[256];
    for (i = 0; i < 256; i++) {
        uint64_t x = i;
        x = (x | (x << 28));
        x = (x | (x << 14));
        inflate[i] = (x | (x <<  7)) & 0x0101010101010101ULL;
    }
    for (j = 0; j < 10000000 / 255 * 255; j += 255) {
        uint64_t b[8] = { 0 };
        for (int k = 0; k < 255; k++) {
            uint64_t u = pLong[j + k];
            for (int kk = 0; kk < 8; kk++, u >>= 8)
                b[kk] += inflate[u & 255];
        }
        for (i = 0; i < 64; i++)
            target[i] += (b[i / 8] >> ((i % 8) * 8)) & 255;
    }
    for (; j < 10000000; j++) {
        uint64_t m = 1;
        for (i = 0; i < 64; i++) {
            target[i] += (pLong[j] >> i) & 1;
            m <<= 1;
        }
    }
    printf("target = {");
    for (i = 0; i < 64; i++)
        printf(" %d", target[i]);
    printf(" }\n");
    printf("took %f secs\n", getTS() - start);
    return 0;
}

将字节扩展为 64 位长的技术在答案中进行了调查和解释:https://stackoverflow.com/a/55059914/4593267 .我将 target 数组和 inflate 数组设为局部变量，并打印结果以确保编译器不会优化计算。在生产版本中，您将单独计算 inflate 数组。

直接使用 SIMD 可能会以牺牲可移植性和可读性为代价提供进一步的改进。这种优化通常最好留给编译器，因为它可以为目标架构生成特定代码。除非性能至关重要并且基准测试证明这是一个瓶颈，否则我总是赞成通用解决方案。

njuffa 的另一种解决方案提供了类似的性能，而无需预先计算的数组。根据您的编译器和硬件细节，它可能会更快。