c - 二元矩阵 vector 乘法的本质

Question

我正在尝试在二进制字段上实现矩阵 vector 乘法。 vector x 的尺寸为 1xa，矩阵 M 的尺寸为 axb，结果 y = a * M 的尺寸为 1xb。现在，我实现了 x 和 M 的类型为 uint8_t*，即，我连接 M 的列，因为它们也被连续访问。该函数如下所示:

void mul(uint8_t M, size_t a, size_t b, uint8_t* x, uint8_t* y) {
    uint8_t val;
    uint8_t *ptr;
    for(size_t i = 0; i < b; i++) {
        val = 0;
        ptr = M + i * a;
        for(size_t j = 0; j < a; j++) {
            val ^= (x[j] & *ptr++);
        }
        y[i] = bit;
    }
}

M 和 x 已被调用者分配为

M = malloc(sizeof(uint8_t) * a * b);
x = malloc(sizeof(uint8_t) * a);
y = malloc(sizeof(uint8_t) * b);

由于这个例程被调用了数十亿次，我需要对其进行优化；)为此，我正在考虑

• 我可以将“x”和“M”中的所有位打包到更小尺寸的 uint64_t 数组中，例如 ap 和 Mp，而不是将每个 0/1 表示为单独的 uint8_t(即 8 位)，其中

ap = (size_t) ceil ((double) a/64);Mp = (size_t) ceil ((双) (a*b)/64);

• 使用 vector 内在函数。

到目前为止，我完成了 M 的(左对齐)打包(正确对齐)和乘法

typedef uint64_t word;
#define WORD_BITS      (CHAR_BIT * sizeof (word))

void mul_fast(word *M, size_t Mlen, word *x, size_t xlen, size_t b, word *y) {

    for(size_t i = 0; i < Mlen; i++) {
        y[i/xlen] ^= (M[i] & x[i % xlen]);
    }
    for(size_t i = 0; i < b; i++) {
        y[i] = __builtin_popcountll(y[i]) & 1;
    }
}

然而，事实证明上面的方法比 mul() 的直接实现要慢得多。

您有什么想法或引用吗？我不是汇编专家，因此比较 gcc -S 的输出并不能告诉我太多信息:/

谢谢你，最诚挚的问候，汤姆。

Answer 1

汇编器输出的相关差异是:


.L26:
- movq%r10，%rax
- xorl %edx, %edx
-divq%rcx
- movq (%r11,%rdx,8), %rdx
- 和q (%rdi,%r10,8), %rdx
- 添加$1，%r10
- xorq %rdx, (%r9,%rax,8)
- cmpq %r10, %rsi
+ movq %rax, %rcx
+ movq %rax, %r10
+ andl $1, %ecx
+ 缩小 %r10
+ movq (%rdx,%rcx,8), %rcx
+ 和q (%rdi,%rax,8), %rcx
+ 添加$1，%rax
+ xorq %rcx, (%r9,%r10,8)
+ cmpq %rax, %rsi
你能看出罪魁祸首是什么吗？