数据说话:Go语言的Switch和Map性能实测

在开发pgx(一个针对Go语言的PostgreSQL driver)的时候,有好几次我都需要在20多个代码分支间跳转。通常我会选用switch语句。还有个更加可读的实现方法是使用函数map。我一开始认为用switch语句进行分支跳转比一个map查找和函数调用更快。数据库驱动(database driver)的性能是一个很重要的考量,所以在做任何改动前,有必要对它们的影响做一下慎重地研究。

摘要

性能测试显示它们有很大的差异。但最终的答案是它们对整个程序来说可能是无关紧要的。如果你想了解得出这个结论而做的测试,那么请继续阅读。

初步调查

在互联网上没有找到有用的信息。我找到的几个帖子都认为map在有足够多跳转分支时会更快。一个在2012年对switch优化的讨论包括了Ken Thompson的观点。他认为没有太多优化的空间。我决定写一个benchmark来测试它们在Go语言里的性能。

最基本的测试

取得下面结果的系统配置是:Intel i7-4790K,Ubuntu 14.04,运行的是go1.5.1 linux/amd64。测试的源代码和结果在Github上。

下面是一个对switch的基本测试:

func BenchmarkSwitch(b *testing.B) {
  var n int

  for i := 0; i < b.N; i++ {
      switch i % 4 {
          case 0:
              n += f0(i)
          case 1:
              n += f1(i)
          case 2:
              n += f2(i)
          case 3:
              n += f3(i)
        }
  }
  
  // n will never be < 0, but checking n should ensure that the entire benchmark loop can't be optimized away.
  if n < 0 {
    b.Fatal("can't happen")
  }
}

众所周知,像这样的测试要达到它的目的通常是很困难的。比如,编译优化器会把一段不产生任何效果的代码完全忽略掉。这里的n就是用来防止这整段代码不被优化掉。接下来的文章里还会提到其它几个需要注意的地方。

下面是一个函数map的测试代码:

func BenchmarkMapFunc4(b *testing.B) {
  var n int

  for i := 0; i < b.N; i++ {
    n += Funcs[i%4](i)
  }
  
  // n will never be < 0, but checking n should ensure that the entire benchmark loop can't be optimized away.
  if n < 0 {
    b.Fatal("can't happen")
  }
}

我们使用Ruby erb模版来生成包含4,8,16,32,64,128,256和512个跳转分支的测试。结果显示map版本在4个分支的情况下比switch版本慢了25%。在8个分支的情况下它们的性能相当。map版本在分支越多的情况下越快,在512个分支的测试里它会比switch版本快50%。

内联函数(Inlineable Functions)

之前的测试给出了一些结果,但是它们并不充分。有好几个影响测试的因素都没有考虑进去。首先是函数是否被内联。一个函数可以在switch语句里被内联,但是函数map就不会。我们有必要测试一下函数内联对性能的影响。

下面这个函数做了一些毫无意义的工作,它能保证整个函数内容不会被优化掉,但是Go语言的编译器会把整个函数内联。

func f0(n int) int {
  if n%2 == 0 {
      return n
  } else {
      return 0
  }
}

在写这篇文章的时候,Go编译器还不能内联包含panic的函数。下面这个函数包含了一个不可能被执行到的panic调用,从而防止了函数被内联。

func noInline0(n int) int {
  if n < 0 {
       panic("can't happen - but should ensure this function is not inlined")
  } else if n%2 == 0 {
      return n
  } else {
      return 0
  }
}

当函数不能被内联时,性能有了很大的变化。map版本的代码比switch版本在4个分支的测试里快了大约30%,在512个分支的测试里快了300%。

计算跳转目的地或者查找跳转目的地

上面的测试根据循环的次数来决定跳转分支。

  for i := 0; i < b.N; i++ {
      switch i % 4 {
        // ...
       }
  }

这保证我们测试的仅仅是分支跳转的性能。在现实世界中,分支跳转的选择通常会导致一个内存的读取。为了模拟这个行为,我们使用一个简单的查找来决定跳转分支。

var ascInputs []int

func TestMain(m *testing.M) {
  for i := 0; i < 4096; i++ {
    ascInputs = append(ascInputs, i)
  }

  os.Exit(m.Run())
}

func BenchmarkSwitch(b *testing.B) {  // ...
  for i := 0; i < b.N; i++ {
      switch ascInputs[i%len(ascInputs)] % 4 {
      // ...
        }
       // ...
    }
}

这个改变大大的降低了性能。表现最好的switch测试性能从1.99 ns/op下降到了8.18 ns/op。表现最好的map测试性能从2.39 ns/op下降到了10.6 ns/op。具体的数据在不同的测试中会有一些差别,但是查找操作增加了大约7 ns/op。

不可预测的分支跳转顺序

厉害的读者肯定已经注意到了,这些测试里的分支跳转是高度可预测的,这不符合现实。它总是按照分支0,然后分支1,然后分支2的顺序来。为了解决这个问题,分支跳转的选择被随机化了。

var randInputs []int

func TestMain(m *testing.M) {
  for i := 0; i < 4096; i++ {
    randInputs = append(randInputs, rand.Int())
  }

  os.Exit(m.Run())
}

func BenchmarkSwitch(b *testing.B) {
  // ...
  for i := 0; i < b.N; i++ {
      switch randInputs[i%len(ascInputs)] % 4 {
          // ...
        }
      // ...
    }
}

这个改变继续降低了性能。在32个跳转分支的测试里,map查找延迟从11ns涨到了22ns。具体的数据根据跳转分支的数目以及函数是否被内联会有变化,但是性能基本都下降了一半。

更进一步

从计算跳转分支目的地到查找跳转目的地的性能损失是在预料之中的,因为有了额外的内存读取。但是从顺序跳转到随机跳转的性能影响却出乎意料。为了了解其中的原因,我们使用Linux perf工具。它可以提供例如cache miss和分支跳转预测错误(branch-prediction misses)等CPU层面的统计。

为了避免对测试程序编译过程的profiling,可以将测试代码预先编译好。

go test -c

然后我们让perf工具为我们提供其中一个顺序查找测试的统计数据。

$ perf stat -e cache-references,cache-misses,branches,branch-misses ./go_map_vs_switch.test -test.bench=PredictableLookupMapNoInlineFunc512 -test.benchtime=5s

输出结果里有意思的部分是分支跳转预测错误的统计:

9,919,244,177      branches
10,675,162         branch-misses  # 0.11% of all branches

所以当跳转顺序可预测时分支跳转预测工作得非常好。但不可预测分支跳转测试里的结果就截然不同。

$ perf stat -e cache-references,cache-misses,branches,branch-misses ./go_map_vs_switch.test -test.bench=UnpredictableLookupMapNoInlineFunc512 -test.benchtime=5s

相关的输出:

3,618,549,427 branches
  451,154,480 branch-misses  # 12.47% of all branches

分支跳转预测的错误率涨了100倍。

结论

我最初想回答的问题是,用函数map来替换switch语句对性能是否会有影响。我假设switch语句会快一点。但是我错了。Map通常会更快,而且快好几倍。

这是否意味着我们应该选择使用map而不是switch语句呢?不!虽然从百分比来看改变非常大,但绝对的时间差异其实很小。只有在每秒钟执行上百万次分支跳转而没有其它实际工作量时,这个差异才会显现出来。即使是这样,内存访问和分支跳转的成功率对性能影响更大,而不是选择switch语句或者map。

对switch语句或者map的选择标准应该是谁能产生最干净的代码,而不是性能。

原文发布于微信公众号 - Golang语言社区(Golangweb)

原文发表时间:2017-10-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吉浦迅科技

DAY57:阅读Execution Configuration

Any call to a __global__ function must specify the execution configuration for t...

753
来自专栏前端杂货铺

[译] Cookbook of QUnit

本篇文章是QUnit的简介,可以作为很好的入门教程。文章原址 介绍 自动化测试时软件开发过程中必不可少的一部分,而单元测试则是自动化测试的最为基本的一块,软件的...

30211
来自专栏吉浦迅科技

在cuda的核函数中可以按地址调用普通变量么?

请问在cuda的核函数中可以按地址调用普通变量么? GPU世界论坛 bbs.gpuworld.cn Hi, 楼主, 完全无问题,从Fermi起引入卡内统...

3787
来自专栏linux驱动个人学习

Linux CFS调度器之虚拟时钟vruntime与调度延迟--Linux进程的管理与调度(二十六)

CFS为了实现公平,必须惩罚当前正在运行的进程,以使那些正在等待的进程下次被调度。

2234
来自专栏互联网杂技

Angular2 脏检查过程

在本文中我将会深入讨论Angular 2 中的变更检测系统。 高层次概览 一个Angular 2 应用就是一颗组件树。 ? Angular 2 应用是一个反馈系...

4268
来自专栏XAI

【定制化图像开放平台】入门实例之手写数字模型训练

本帖主要用手写数字为例进行一个简单入门实例总结(非官方) 平台网站:http://ai.baidu.com/customize/app/model/ 定制化图像...

42116
来自专栏Golang语言社区

【golang】调优工具 pprof

Golang 提供了 pprof 包(runtime/pprof)用于输出运行时的 profiling 数据,这些数据可以被 pprof 工具(或者 go to...

1493
来自专栏mukekeheart的iOS之旅

MySQL学习笔记(一)

一、MySQL基础知识 MySQL 是一个真正的多用户、多线程 SQL 数据库服务器。 SQL(结构化查询语言)是世界上最流行的和标准化的数据库语言。MySQL...

2498
来自专栏木子昭的博客

<技巧>python模块性能测试以python列表的内置函数append和insert为例以python列表insert方法和append方法快速创建1至1000的列表为例:

算法是程序的灵魂,优秀的算法能给程序的效率带来极大的提升,而算法的优劣,往往要经过大量的测试. 在硬件环境基本不变的前提下,对算法实验的次数越多,测试算法运...

3286
来自专栏PHP在线

MongoDB数据结构设计中6条重要的经验法则

很多初学者认为在MongoDB中针对一对多建模唯一的方案就是在父文档中内嵌一个数组子文档,但是这是不准确的。因为你可以在MongoDB内嵌一个文档不代表你就必须...

3267

扫码关注云+社区

领取腾讯云代金券