performance - Go:通过 slice slice (二维 slice )访问数组时出现意外性能

Question

我在 Go 中使用矩阵乘法进行一些性能实验并遇到了一些意想不到的结果。

版本 1:

func newMatrix(n int) [][]int {
    m := make([][]int, n)
    buf := make([]int, n*n)

    for i := range m {
        m[i] = buf[i*n : (i+1)*n]
    }

    return m
}

func mult1(m1, m2, res [][]int) [][]int {
    for i := range m1 {
        for k := range m1[0] {
            for j := range m2[0] {
                res[i][j] += m1[i][k] * m2[k][j]
            }
        }
    }

    return res
}

我从线性阵列创建多个表示矩阵行的 slice 。

版本 2:

func mult2(m1, m2, res []int, n int) []int {
    for i := 0; i < n; i++ {
        for k := 0; k < n; k++ {
            for j := 0; j < n; j++ {
                res[i*n+j] += m1[i*n+k] * m2[k*n+j]
            }
        }
    }

    return res
}

在这个版本中，我简单地使用一个线性数组并通过乘法对其进行索引。

将 2 个 2048x2048 矩阵相乘得到以下执行时间:

 version 1: 35.550813801s
 version 2: 19.090223468s

版本 2 的速度几乎是原来的两倍。

我使用以下方法进行测量:

start := time.Now()
mult(m1, m2, m3)
stop := time.Now()

我知道使用 slice 会提供另一层间接访问，这可能会影响缓存性能，但我没想到会有如此大的差异。不幸的是，我还没有找到任何适用于 Mac 的好工具，可以分析 Go 中的缓存效率，所以我不能确定这是否是导致性能差异的原因。

所以我想我问的是这种预期行为还是我遗漏了什么？

软硬件: 转到版本 1.4.2 darwin/amd64；操作系统 X 10.10.3； 2 GHz 四核 i7。

Answer 1

您的版本 1 代码中的主要问题似乎是间接寻址。尽管两个版本中矩阵在内存中的布局相同，但使用间接寻址会导致:

• 为同一代码生成更多指令。编译器可能无法确定何时使用 SIMD 指令的打包版本(例如 SSE、AVX)。您可以通过转储汇编代码来验证这一点，查找 XMM 或 YMM 寄存器并检查操作寄存器的指令是否已打包。
• 您让编译器很难添加软件预取。因为是间接寻址，所以编译器很难检测到如何添加软件预取。您可以在汇编代码中查找 vprefetch 指令。
• 由于间接寻址，硬件预取器的效率会降低。您首先需要访问行起始地址，然后访问行元素，因此很难观察到硬件预取器应该只获取连续的地址。这只能通过像 perf 这样的分析来衡量。

因此对于版本 1，间接寻址 是主要问题。我还建议在多次迭代中运行这 2 个代码以消除缓存预热惩罚，因为我在上面解释过，这对于版本 1 来说可能更高。