go中的map vs switch性能

Question

考虑这个基准,我们比较地图访问与交换机

var code = []int32{0, 10, 100, 100, 0, 10, 0, 10, 100, 14, 1000, 100, 1000, 0, 0, 10, 100, 1000, 10, 0, 1000, 12}
var mapCode = map[int32]int32{
    0:    1,
    10:   2,
    100:  3,
    1000: 4,
}

func BenchmarkMap(b *testing.B) {
    success := int32(0)
    fail := int32(0)
    for n := 0; n < b.N; n++ {
        // for each value in code array, do a specific action
        for _, v := range code {
            c, ok := mapCode[v]
            if !ok {
                fail++
            } else {
                success += c
            }
        }
    }
}

func BenchmarkSwitch(b *testing.B) {
    success := int32(0)
    fail := int32(0)
    for n := 0; n < b.N; n++ {
        // for each value in code array, do a specific action
        for _, v := range code {
            switch v {
            case 0:
                success++
            case 10:
                success += 2
            case 100:
                success += 3
            case 1000:
                success += 4
            default:
                fail++
            }
        }
    }
}

结果如下:

BenchmarkMap-2           5000000           277 ns/op           0 B/op          0 allocs/op
BenchmarkSwitch-2       30000000            48.2 ns/op         0 B/op          0 allocs/op

所以使用map似乎比switch更慢.

我目前正在尝试使用类似的代码来优化函数BenchmarkMap(),其中地图访问是瓶颈,但我不能使用switch,因为当程序启动时动态生成映射(即它可能根据输入参数而改变)

有没有办法获得switch x {}与动态生成的地图类似的性能？

Answer 1

不使用映射,因为索引映射是在运行时计算的,并且从映射获取元素涉及的操作多于单个(切片)索引.某些switches(具有case具有常量表达式的分支)可以/即使在编译时也可以优化.

但地图并不是唯一的"动态"结构.对于另一个,有切片.切片可以编入索引,就像地图一样.

是的,切片是底层数组的连续段的描述符.这意味着如果你有一个索引1000,那么切片至少需要有1000+1 = 1001元素.

因此,如果您愿意为了性能而牺牲一些内存并使用切片而不是地图,您甚至可以使用比使用switch语句更快的解决方案:

var sliceCode = []int32{
    0:    1,
    10:   2,
    100:  3,
    1000: 4,
}

func BenchmarkSlice(b *testing.B) {
    success := int32(0)
    fail := int32(0)
    for n := 0; n < b.N; n++ {
        // for each value in code array, do a specific action
        for _, v := range code {
            c := sliceCode[v]
            if c == 0 {
                fail++
            } else {
                success += c
            }
        }
    }
}

基准测试结果如下:

BenchmarkMap-4          10000000               148 ns/op
BenchmarkSlice-4        100000000               17.6 ns/op
BenchmarkSwitch-4       50000000                31.0 ns/op

这个具体例子中的切片解决方案的速度是switch解决方案的两倍!

笔记:

我上面提到过,如果你有一个索引1000,你至少需要1001元素.这部分是正确的.例如,如果你有类似的索引990..1000,你可以有一个简单的索引转换逻辑index - 990,然后只有11个元素的切片就足够了.

另请注意,在使用逗号成语索引地图时,我们可以判断元素是否在地图中.对于切片,我们没有这个选项.所以我们必须从元素类型的有效集合中指定一个值,并将其用作"缺失"信号.在上面的例子中,0对于我们来说是完美的,因为没有使用(并且0默认情况下未明确列出的所有元素都设置为).如果在您的示例中int32可以使用所有有效值,则另一个选项是使用包装器或指针类型作为可能具有nil值的切片的元素类型,指示索引的元素缺失.

Answer 2

五年后，这些结果在 go 1.19 版本上仍然成立（在最近对 switch 语句进行优化之后）：

BenchmarkMap-10         14947908                76.78 ns/op
BenchmarkSwitch-10      49444435                23.01 ns/op
BenchmarkSlice-10       100000000               10.74 ns/op