如何高效计算两个uint64向量的点积？

给定两个尺寸相同的uint64_t向量，我需要计算它们的点积。由于计算过程需要用128位算术存储中间结果，我编写了如下简单函数：

void multiply_acum(uint64_t op1, uint64_t op2, uint128_t& product_acum) {
     product_acum = product_acum + (static_cast<uint128_t>(op1) * static_cast<uint128_t>(op2));
}

并从点积函数中调用该函数（仅作参考，可能无法正常运行）：

void dot_product(int size, vector<uint64> a, vector<uint64> b){
    uint128_t product_acum = 0;
    for (int i = 0; i < size; i++){
        multiply_acum(a[i], b[i], product_acum);
    }
}

该函数可正常工作，但128位算术运算速度较慢。请问是否有优化性能的建议？能否如那篇关于获取64位整数乘法高位的文章所述，避免使用128位算术而改用64位算术？

优化方案与解答 #

一、基础性能优化 #

• 避免不必要的函数调用：把multiply_acum的逻辑直接内联到点积循环中，减少函数调用的栈开销。编译器虽可能自动内联，但显式整合逻辑更可控。
• 传递向量引用：原函数参数vector<uint64> a会触发向量拷贝，改为const vector<uint64_t>& a（注意修正类型为uint64_t），避免大向量的拷贝开销。
• 开启编译器优化：启用最高级别优化（如GCC/Clang的-O3、MSVC的/O2），编译器会自动做循环展开、指令调度、寄存器分配等优化，大幅缩小128位运算与64位运算的性能差距。

二、用64位算术替代128位累加 #

完全可以通过拆分乘积的高低位，用两个uint64_t变量分别存储累加结果的低64位和高64位，模拟128位累加过程，核心是处理每一步的进位：

实现思路

1. 用uint64_t low存储累加结果的低64位，uint64_t high存储高64位；
2. 对每对元素a[i]和b[i]，计算乘积的低64位和高64位；
3. 先累加低64位，判断是否产生进位（若累加后的值小于原low，说明溢出进位），进位则给high加1；
4. 再累加高64位到high中。

代码示例

#include <vector>
#include <cstdint>

void dot_product(int size, const std::vector<uint64_t>& a, const std::vector<uint64_t>& b) {
    uint64_t low = 0, high = 0;
    for (int i = 0; i < size; ++i) {
        const uint64_t op1 = a[i];
        const uint64_t op2 = b[i];
        
        // 用__uint128_t计算乘积的高低位，编译时会被优化为硬件乘法指令
        const __uint128_t prod = static_cast<__uint128_t>(op1) * op2;
        const uint64_t prod_low = static_cast<uint64_t>(prod);
        const uint64_t prod_high = static_cast<uint64_t>(prod >> 64);
        
        // 累加低64位并处理进位
        const uint64_t new_low = low + prod_low;
        if (new_low < low) {
            high += 1;
        }
        low = new_low;
        
        // 累加高64位
        high += prod_high;
    }
    
    // 最终结果可组合为128位值（若需要）
    const __uint128_t final_result = static_cast<__uint128_t>(high) << 64 | low;
}

如果需要完全手动实现64位乘法取高位（不依赖__uint128_t），可以通过拆分32位部分计算，但主流编译器都支持__uint128_t，且会优化为硬件指令，性能更优，无需手动实现复杂逻辑。

三、进阶优化 #

• 循环展开：手动展开循环（如一次处理4组元素），减少循环迭代的分支开销，适合大尺寸向量；
• 向量化优化：开启编译器的向量化选项（如GCC的-mavx2/-mavx512f），让编译器利用SIMD指令同时处理多个64位乘法与累加，大幅提升大向量的计算效率。

内容的提问来源于stack exchange，提问作者CryptoKitty