golang 中的多维切片访问性能

Question

我正在 Golang 中开发一个简单的小游戏，并在切片访问期间偶然发现了性能问题。

这是游戏的主要数据结构：

type Neighbor struct {
    X, Y int
}

type Grid struct {
    Data          [][]uint8      // a cell
    NeighborCount [][]int        // how many neighbors a cell has
    Neighbors     [][][]Neighbor // the list of neighbors per cell, setup once during init
    Empty         bool
    Config        *Config
}

所以，我已经尝试避免使用指针等。切片在启动时初始化一次，并且在整个游戏中永远不会改变。

现在，当我运行游戏时，它运行得很好，但在网格尺寸为 1500x1500 及以上时，性能显着下降。

我分析了游戏，到目前为止花费最多时间的代码是

CountNeighbors(x,y)

函数，如下所示：

// count the living neighbors of a cell
func (grid *Grid) CountNeighbors(x, y int) uint8 {
    var count uint8

    for idx := 0; idx < grid.NeighborCount[y][x]; idx++ {
        count += grid.Data[grid.Neighbors[y][x][idx].Y][grid.Neighbors[y][x][idx].X]
    }

    return count
}

游戏在该函数中花费了整个运行时间的 44%。这真的很简单，它迭代一个单元格的所有邻居并添加它们的内容，因为单元格只是

uint8

，其中活的单元格用 1 表示。

这是我在探查器中看到的有关该函数的内容：

  Total:      22.10s     22.10s (flat, cum) 44.84%
    107            .          .            
    108            .          .           // count the living neighbors of a cell 
    109            .          .           func (grid *Grid) CountNeighbors(x, y int) uint8 { 
    110            .          .             var count uint8 
    111            .          .            
    112        6.59s      6.59s             for idx := 0; idx < grid.NeighborCount[y][x]; idx++ { 
    113       15.51s     15.51s                 count += grid.Data[grid.Neighbors[y][x][idx].Y][grid.Neighbors[y][x][idx].X] 
    114            .          .             } 
    115            .          .            
    116            .          .             return count 
    117            .          .           } 
    118            .          .  

根据简介，GC 并没有发挥任何重要作用。同样有趣的是，为第 113 行生成的程序集：

230ms      230ms   829cb0:   MOVZX 0(DI)(R13*1), R13      grid.go:113
                      ⋮
190ms      190ms   829cb8:   ADDL R13, DX                 grid.go:113
                      ⋮
250ms      250ms   829cf8:   MOVQ 0x38(SI), R13           grid.go:113
100ms      100ms   829cfc:   NOPL 0(AX)                   grid.go:113
670ms      670ms   829d00:   CMPQ R13, AX                 grid.go:113
    .          .   829d03:   JBE 0x829ddc                 grid.go:113
 70ms       70ms   829d09:   MOVQ 0x30(SI), R13           grid.go:113
210ms      210ms   829d0d:   MOVQ 0x8(R13)(R11*8), R15    grid.go:113
190ms      190ms   829d12:   MOVQ 0(R13)(R11*8), R13      grid.go:113
640ms      640ms   829d17:   NOPW 0(AX)(AX*1)             grid.go:113
 20ms       20ms   829d20:   CMPQ CX, R15                 grid.go:113
    .          .   829d23:   JAE 0x829dd1                 grid.go:113
260ms      260ms   829d29:   LEAQ 0(CX)(CX*2), R15        grid.go:113
 40ms       40ms   829d2d:   MOVQ 0x8(R13)(R15*8), DI     grid.go:113
1.27s      1.27s   829d32:   MOVQ 0(R13)(R15*8), R13      grid.go:113
200ms      200ms   829d37:   NOPW 0(AX)(AX*1)             grid.go:113
150ms      150ms   829d40:   CMPQ BX, DI                  grid.go:113
    .          .   829d43:   JAE 0x829dc6                 grid.go:113
150ms      150ms   829d49:   LEAQ 0(BX)(BX*2), DI         grid.go:113
570ms      570ms   829d4d:   MOVQ 0x8(R13)(DI*8), R15     grid.go:113
5.69s      5.69s   829d52:   CMPQ R15, R9                 grid.go:113
    .          .   829d55:   JAE 0x829dbb                 grid.go:113
820ms      820ms   829d57:   LEAQ 0(R15)(R15*2), R15      grid.go:113
 20ms       20ms   829d5b:   MOVQ 0x8(R10)(R15*8), R12    grid.go:113
   3s         3s   829d60:   MOVQ 0(R13)(DI*8), DI        grid.go:113
170ms      170ms   829d65:   MOVQ 0(R10)(R15*8), R13      grid.go:113
600ms      600ms   829d69:   CMPQ DI, R12                 grid.go:113
    .          .   829d6c:   JB 0x829cb0                  grid.go:113
    .          .   829d72:   JMP 0x829db0                 grid.go:113
                      ⋮
    .          .   829db0:   MOVQ DI, AX                  grid.go:113
    .          .   829db3:   MOVQ R12, CX                 grid.go:113
    .          .   829db6:   CALL runtime.panicIndex(SB)  grid.go:113
    .          .   829dbb:   MOVQ R15, AX                 grid.go:113
    .          .   829dbe:   MOVQ R9, CX                  grid.go:113
    .          .   829dc1:   CALL runtime.panicIndex(SB)  grid.go:113
    .          .   829dc6:   MOVQ BX, AX                  grid.go:113
    .          .   829dc9:   MOVQ DI, CX                  grid.go:113
    .          .   829dcc:   CALL runtime.panicIndex(SB)  grid.go:113
    .          .   829dd1:   MOVQ CX, AX                  grid.go:113
    .          .   829dd4:   MOVQ R15, CX                 grid.go:113
    .          .   829dd7:   CALL runtime.panicIndex(SB)  grid.go:113
    .          .   829ddc:   MOVQ R13, CX                 grid.go:113
    .          .   829ddf:   NOPL                         grid.go:113
    .          .   829de0:   CALL runtime.panicIndex(SB)  grid.go:113

这有很多适合我口味的东西。

但是。我不明白为什么 go 在简单的切片访问过程中浪费了这么多时间。我还尝试使用数组

[2]int

来存储邻居位置，而不是上面显示的

struct Neighbor

。但结果是一样的。

最后一件事：我在单元状态计算期间使用 goroutine（其中上面概述的内容是其中的一部分）：准确地说，每行一个 goroutine，没有锁定。这是有效的，因为切片只能用于读取。不过，我也尝试过不使用 goroutine。那么整个游戏就会变慢（25 FPS vs. 带有 goroutine 的 40 FPS），但在

CountNeighbors()

上花费的时间更少：只有 22%。但多维切片访问仍然是瓶颈。

那么，这里发生了什么以及如何（如果可能）加快速度？

PS：完整的源代码可以在这里看到

Answer 1

当您的性能受到限制时，您需要密切关注访问模式并根据时间和空间局部性安排数据。另外，对每个访问进行边界检查可能不是您想要的。

如果可以，请尝试通过

a[x + N * y]

访问一个数组，具体取决于您的循环顺序。分析（您已经做的事情）是个好主意。