Go:通过切片切片访问数组时的意外性能(2D切片)

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
}

从线性数组中,我创建了表示矩阵行的多个切片.

版本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; OS X 10.10.3; 2 GHz四核i7.

Answer 1

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

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

因此,在版本1的情况下,间接寻址是主要问题.我还建议在多次迭代中运行2个代码以实现缓存升温惩罚,因为我在上面已经解释过,所以版本1可能会更高.