为什么Go的map和slice性能有10倍的速度差异?

Question

我刚刚解决了Project Euler中的问题23，但是我注意到map[int]bool和[]bool在性能方面有很大的不同。

我有一个函数，可以把一个数的固有因子加起来:

func divisorsSum(n int) int {
    sum := 1
    for i := 2; i*i <= n; i++ {
        if n%i == 0 {
            sum += i
            if n/i != i {
                sum += n / i
            }
        }
    }
    return sum
}

然后在main中我这样做:

func main() {
    start := time.Now()
    defer func() {
        elapsed := time.Since(start)
        fmt.Printf("%sn", elapsed)
    }()
    n := 28123
    abundant := []int{}
    for i := 12; i <= n; i++ {
        if divisorsSum(i) > i {
            abundant = append(abundant, i)
        }
    }
    sums := map[int]bool{}
    for i := 0; i < len(abundant); i++ {
        for j := i; j < len(abundant); j++ {
            if abundant[i]+abundant[j] > n {
                break
            }
            sums[abundant[i]+abundant[j]] = true
        }
    }
    sum := 0
    for i := 1; i <= 28123; i++ {
        if _, ok := sums[i]; !ok {
            sum += i
        }
    }
    fmt.Println(sum)
}

这段代码在我的计算机上花费了450ms。但是如果我把主代码改成下面的slice of bool而不是map，就像这样:

func main() {
    start := time.Now()
    defer func() {
        elapsed := time.Since(start)
        fmt.Printf("%sn", elapsed)
    }()
    n := 28123
    abundant := []int{}
    for i := 12; i <= n; i++ {
        if divisorsSum(i) > i {
            abundant = append(abundant, i)
        }
    }
    sums := make([]bool, n)
    for i := 0; i < len(abundant); i++ {
        for j := i; j < len(abundant); j++ {
            if abundant[i]+abundant[j] < n {
                sums[abundant[i]+abundant[j]] = true
            } else {
                break
            }
        }
    }
    sum := 0
    for i := 0; i < len(sums); i++ {
        if !sums[i] {
            sum += i
        }
    }
    fmt.Println(sum)
}

现在只需要40ms，低于之前速度的1/10。我还以为地图应该查得更快呢。这里的性能差异是怎么回事?

Answer 1

您可以分析代码并查看，但通常有两个主要原因:

1. 在第二个示例中预先分配sums到所需的大小。这意味着它永远不需要增长，所有这些都是非常有效的，没有GC压力，没有reallocs，等等。试着提前创建理想尺寸的地图，看看它有多大的改善。

2. 我不知道Go的哈希映射的内部实现，但一般来说，通过整数索引随机访问数组/切片是超级高效的，而哈希表会增加开销，特别是如果它对整数进行哈希(它可能这样做是为了创建更好的分布)。