矩阵与向量相乘：为何双层for循环比单层循环更快？

我在测试矩阵与向量相乘的不同实现方式时，对比了双层for循环、逐行点积和内置向量化操作的耗时与加速比。代码运行正常，但意外发现**方法2（逐行计算点积）**是最慢的——我原本以为带有更多数组索引操作的双层for循环（方法1）会是最慢的。

测试代码 #

using LinearAlgebra
function matrix_vector()
    n = 10000

    A = rand(Float64, (n,n))
    x = rand(Float64, (n))
    b = zeros(n)
    bb = zeros(n)

    # Method 1：双层for循环手动累加
    t1 = @elapsed begin
        for i in range(1,n)
            for j in range(1,n)
                b[i] = b[i] + A[i,j]*x[j]
            end
        end
    end

    # Method 2：逐行计算点积
    t2 = @elapsed begin
        for i in range(1,n)
            bb[i] = A[i,:]'x
        end
    end

    # Method 3：内置向量化操作
    t3 = @elapsed begin
        bbb = A*x
    end

    println("Method 1 Time: ", t1)
    println("Method 2 Time: ", t2)
    println("Method 3 Time: ", t3, "\n")

    println("Speedup1: ", t1/t2)
    println("Speedup2: ", t2/t3)
    println("Speedup3: ", t1/t3)
    
end    

matrix_vector()

示例输出 #

Method 1 Time: 0.723233
Method 2 Time: 1.0166901
Method 3 Time: 0.0235032

Speedup1: 0.7113603250390655
Speedup2: 43.25751812519146
Speedup3: 30.771682153919468

原因分析 #

• 临时数组的额外开销：方法2中每次执行A[i,:]都会生成一个临时的行向量副本，数组的分配、拷贝和回收会占用大量额外的内存操作时间。而方法1直接通过索引访问元素，完全不需要创建临时数组，内存操作更高效。
• 点积操作的冗余开销：A[i,:]'x调用了点积函数，这个过程除了核心的累加计算，还包含函数调用调度、边界检查等额外逻辑，相比方法1中手动的累加操作，多了不少冗余开销。
• 编译器优化的差异：Julia的JIT编译器对方法1这种手动双层循环的优化能力很强，它可以识别循环模式，自动进行循环展开、向量化、内存预取等优化，让手动循环的效率接近底层优化代码。而方法2的逐行点积模式，编译器很难将外层循环和内层点积的逻辑合并优化，导致整体效率打折扣。

另外，方法3的A*x是LinearAlgebra库调用BLAS实现的，BLAS库利用了多线程并行和高度优化的内存访问模式，所以效率远高于手动实现的两种方法。

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