地图与切换性能的关系 [英] map vs switch performance in go

问题描述

考虑此基准，我们在其中比较地图访问与切换

Consider this benchmark, where we compare map access vs switch

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慢得多.

So using map seems to be way slower than switch.

我目前正在尝试使用类似于BenchmarkMap()的代码优化功能，其中的地图访问权限 是瓶颈，但是我不能使用switch，因为在程序启动时会动态生成地图(即 可能会根据输入参数而变化)

I'm currently trying to optimize a function using a code similar to BenchmarkMap(), where the map access is the bottleneck, but I can't use switch as the map is dynamically generated when the program start (ie it may change according to input arguments)

是否可以通过动态生成的映射获得与switch x {}类似的性能?

Is there a way to get similar performance as switch x {} with dynamically generated map ?

推荐答案

不带地图，因为索引映射是在运行时评估的，从映射中获取元素涉及的操作不仅仅是单个(切片)索引.某些switch es(具有case个具有常量表达式的分支)甚至可以在编译时进行优化.

Not with a map, since indexing maps are evaluated at runtime, and getting an element from a map involves more operations than just a single (slice-)indexing. Certain switches (with case branches having constant expressions) can / may be optimized even at compile-time.

但是地图并不是唯一的动态"结构.另外，还有切片.切片可以像地图一样建立索引.

But map is not the only "dynamic" structure. For another one, there's slices. Slices can be indexed, just like maps.

是的，切片是基础数组的连续段的描述符.这意味着，如果您具有类似1000的索引，则该切片至少需要包含1000+1 = 1001个元素.

Yes, a slice is a descriptor for a contiguous segment of an underlying array. Which means if you have an index like 1000, the slice needs to have at least 1000+1 = 1001 elements.

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

So if you're willing to sacrifice some memory for the sake of performance and use a slice instead of a map, you can even make your solution faster than the one using the switch statement:

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解决方案！

The slice solution in this concrete example outperforms the switch solution by being twice as fast!

注释:

我在上面提到过，如果您有一个像1000这样的索引，则至少需要1001个元素.这部分是正确的.例如，如果您有像990..1000这样的索引，则可以有像index - 990这样的简单索引转换逻辑，那么只有11个元素的切片就足够了.

I mentioned above that if you have an index like 1000, you need at least 1001 elements. This is partly true. For example if you'd have indices like 990..1000, you could have a simple index transformation logic like index - 990, and then a slice with just 11 elements would be perfectly enough.

还请注意，在使用逗号分隔的习惯用法为地图编制索引时，我们能够判断元素是否在地图中.对于切片，我们没有该选项.因此，我们必须从有效的元素类型集中指定一个值，并将其用作丢失"信号.在上面的示例中，0对我们来说是完美的，因为它没有被使用(默认情况下，所有未明确列出的元素都设置为0).如果在您的示例中可以使用所有有效的int32值，则另一种选择是使用包装器或指针类型作为切片的元素类型，该类型可以具有nil值，指示缺少索引的元素

Also note that while indexing a map using the comma-ok idiom we were able to tell if the element was in the map. With slices we don't have that option. So we have to designate a value from the valid set of the element type, and use that as the "missing" signal. In the above example, 0 was perfect for us as that wasn't used (and all elements not explicitly listed are set to 0 by default). If in your example all valid int32 values could be used, another option would be to use a wrapper or pointer type as the element type of the slice which could have a nil value, indicating that the element for the index is missing.

这篇关于地图与切换性能的关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！