写点什么

泛型会让你的 Go 代码运行变慢

  • 2022-04-06
  • 本文字数:14383 字

    阅读完需:约 47 分钟

泛型会让你的 Go 代码运行变慢

Go 1.18 已经到来,很多人期盼已久的首个支持泛型实现的版本也就此落地。之前,泛型一直是个热度很高、但在整个 Go 社区中备受争议的话题。


一方面,批评者们担心泛型的引入会增加复杂性,导致 Go 语言最终变得像 Java 那样冗长繁复,也有人害怕 Go 语言退化成 HaskellScript,用 Monad 代替 if。平心而论,这两种担忧都有点极端。另一方面,支持者们则认为要实现大规模代码清洁、可重用的目标,泛型不可或缺。


本文不打算参与这场论战,也不打算探讨哪些情况下适合在 Go 中使用泛型。这里,我们主要着眼于泛型难题的第三个方面:不想用泛型的系统工程师们该怎么办,特别是单态化给性能造成的影响。这样的工程师不少,这类人对泛型的性能表现都相当失望。


Go 1.18 中的泛型实现


我们其实可以用多种不同的方式在编程语言中实现参数多态化(我们常称之为「泛型」)。在切入正题前,我们先聊聊问题背景、明确 Go 1.18 已经采用的解决方案。虽然这是篇关于系统工程的文章,但我会尽量让讨论氛围轻松愉快、通俗易懂。


假设大家想创建一个多态函数,即能对不同事物执行模糊操作的函数。从广义上讲,能够选择的解决思路有两种。


第一种是让一切事物(也就是函数操作对象)保持统一的观感与行为模式。这种方法也称为“装箱”,主要思路就是先进行堆上内容分配、再把相应的指针传递给函数。因为所有操作对象都转化成了指针,我们只需要指针操作就能了解这些对象在哪里。但也因为指针太多,我们还需要创建一份函数指针表,也就是大家常说的“虚拟方法表”或 vtable。这听起来很熟悉吧?Go 接口就是这么实现的,Rust 中的 dyn Traits 以及 C++ 中的虚拟类也是差不多类似的思路。这些多态形式在实践中更加易用,但表达能力和运行时资源消耗都不太乐观。


而第二种是对不同事物进行操作的方法,即“单态化”。这名字听起来很唬人,但实际上相对简单很多。它的基本思路就是为每个独特的操作对象创建一个函数副本。没错,就是这样简单。假设我们的函数能添加两个数字,现在我们想让它添加两个 float64 数,编译器就会为该函数创建副本并将泛型占位符替换为 float64,之后再进行函数编译。这也是目前最简单的多态实现方法(虽然在实际操作中也经常卡住),但会给编译器带来很高的运行压力。


从历史上看,C++、D 乃至 Rust 等系统语言一直采用单态化方法实现泛型。造成这一现实的原因很多,但总体来说就是想用更长的编译时间来换取结果代码的性能提升,并且只要我们能提前把泛型代码中的类型占位符替换成最终类型、再进行编译,就可以极大优化编译流程的性能表现。装箱方法就做不到这一点。另外,我们还可以对函数调用进行去虚拟化以回避 vtable,甚至使用内联代码实现进一步优化。


总之,单态化在系统编程语言领域取得了压倒性的胜利——毕竟它在本质上不会给运行时造成额外负担,有时候甚至反而能提高泛型代码的运行速度。


但作为一个致力于提升大型 Go 应用程序性能水平的从业者,我对在 Go 中引入泛型并不感冒。我比较支持单态化带来的优化潜力,但 Go 编译器在处理接口时根本实现不了这类优化。更让人失望的是,Go 1.18 中的泛型实现依靠的根本不是单态化,至少不完全是。


这实际是一种被称为“GCShape stenciling with Dictionaries”的部分单态化技术。为了方便起见,下面我就向大家简要介绍一下这项技术的基本思路。


这项技术的基本思路如下:既然根据输入参数对各个函数调用进行完全单态化会生成大量额外代码,我们不妨超越参数类型、以更为广泛的单态化减少这些“唯一函数”的数量。因此,在这样的泛型实现思路下,Go 编译器会基于参数的 GCShape(而非类型)执行单态化(我们将其称为「stenciling」)。


类型的 GCShape,是一种特定于 Go 语言及泛型实现的抽象概念。根据设计文档中的说法,对于任意两个具体类型,只要二者具有相同的基础类型、或者皆属于指针类型时,就会被划分在同一 gcshape 分组内。定义中的前半部分很好理解:如果我们要对某个方法的参数执行自述运算,Go 编译器就会根据其类型有效进行单态化。这样,使用整数运算指令生成的 uint32 代码就与使用浮点运算指令的 float64 代码有所不同。另一方面,针对 uint32 类型别名生成的代码则与底层 uint32 的代码相同。


说到这里,一切似乎都很美好。然而,GCShape 的后半部分定义却对性能产生了巨大影响。需要强调的是:所有指向对象的指针都属于同一 GCShape,不论其具体指向哪个对象。这意味着*time.Time 指针跟*uint64 指针、*bytes.Buffer 指针乃至*strings.Builder 指针全都归属于同一 GCShape。


这不禁让我们怀疑“如果我们想在这些对象上调用方法,又会怎么样?这些方法的位置不会也归属于同一 GCShape 吧?”其实这个问题的答案已经蕴藏在 GCShape 这个名称里了:它根本不知道什么叫方法。要解释这一点,我们还得从 GCShape 使用的字典入手。


在 1.18 版本中的当前泛型实现中,泛型函数的每一次运行时调用都会以透明方式接受静态字典作为其第一条参数,字典中包含了关于传递给函数的参数元数据。该字典放置在 AMD64 的寄存器 AX 当中,而且 Go 编译器目前还无法在这些堆栈中支持基于寄存器的调用约定。


受篇幅所限,这里我们不纠结字典的完整实现。总而言之,字典中包含所有必需的类型元数据,用来将参数进一步传递给其他泛型函数,由此实现函数到 / 自接口的转型。其中对用户影响最大的就是如何在泛型函数上调用方法。


没错,在单态化步骤完成后,生成的函数 shape 需要将所有泛型参数的 vtable 当作运行时输入。从直观感受上,这虽然大大减少了所生成的唯一代码的数量,但过于广泛的单态化思路也消灭了去虚拟化、内联或其他性能优化的实施空间。


事实上,对于大多数 Go 代码而言,泛型机制似乎确实对性能存在影响。但为了证明这个结论的严谨性,我们还要通过基准测试、程序集及行为验证给出实锤。


接口内联


VItess 是 PlanetScale 采用的开源分布式数据库,同时也是一款规模庞大、结构复杂的真实 Go 应用程序,特别适合作为 Go 语言新功能(特别是与性能相关的功能)的测试平台。我碰巧在 Vitess 上找到了一长串手动单态化的函数与实现。其中一部分重复函数是受到多态性所限而无法用接口建模;也有一部分重复函数是因为对性能至关重要,所以避免用接口编译能带来显著的性能提升。


下面我们来看看这份列表中的具体选项:sqltypes 包中的 BufEncodeSQL 函数就不错。我把这些函数复制过来,并附上*strings.Builder 或者*bytes.Buffer 指针,这样就能对缓冲区执行大量调用了。如果缓冲区作为未装箱类型(而非接口类型)进行传递,编译器就能对这些调用进行内联。如此一来,在整个代码库内广泛使用的函数将迎来相当显著的性能增强。


单对这段代码进行泛化还不够,我们还得把函数的泛型版本跟以 io.ByteWriter 为接口的简易版本进行比较。



io.ByteWriter 这边的程序集没什么亮点:所有 WriteByte 调用都通过 itab 发生。我们稍后会具体解释这意味着什么。而另一边的泛型版本却非常有趣,我们首先看到编译器为函数 (BufEncodeStringSQL[go.shape.*uint8_0]) 生成了单一 shape 实例。虽然我们并未在内联视图中显示,但还是得在可访问代码中使用*strings.Builder 才能调用这条泛型函数;否则,编译器根本不会为函数生成任何实例:



因为这里我们使用*strings.Builder 作为调用函数的参数,所以在生成的程序集中看到了*uint8 shape。如前所述,所有将指针作为泛型参数的泛型调用都会被 stencil 为 *uint8 形式,无论具体指向哪种对象。对象的实际属性(最重要的就是其 itab)则存储在大家泛型函数的字典内。


整个过程跟设计文档的说明完全相符:用于传递指向结构的 stenciling 过程会将指针单态化为类似 void 的指针。单态化期间不考虑指向对象的其他属性,因此无法进行内联。对于可以内联的结构,相关方法的具体信息仅在运行时上的字典中可用。简单来讲,这种 stenciling 机制的设计思路就不允许开发者对函数调用进行去虚拟化,也因此消灭了编译器进行内联的空间。但这还不算完。


将生成的程序集调用接口代码中的 WriteByte 方法与泛型代码进行比较,我们就能对泛型代码开展深入性能分析。


中场休息:调用 Go 中的接口方法


在比较两个代码版本的调用之前,我们不妨快速回顾一下 Go 语言中的接口是如何实现的。之前我们已经提到,接口是一种涉及装箱的多态形式,用以确保我们操作的所有对象具有相同的 shape。Go 接口的 shape 是一个 16 字节的胖指针(iface),其中前半部分指向关于装箱值的元数据(我们称之为 itab),后半部分则指向值本身。



itabk 中包含大量关于接口内部类型的信息。inter、_type 及 hash 字段则包含实现接口间转换、接口类型反射及切换的必要元数据。这里我们着重讨论 itab 末尾的 fun 数组:虽然这部分在类型描述中显示为 [1]uintptr,但它实际上却属于变长分配(variable-length allocation)。itab 结构的大小会根据不同接口而变化,结构的末尾则有足够的空间来存储接口内各个方法的函数指针。每次调用接口上的方法,我们都需要访问这些函数指针,所以它们就相当于 Go 版本的 C++ vtable。


考虑到这一点,现在我们就能理解在函数的非泛型实现当中如何调用接口方法的程序集了。下面是第 8 行 buf.WriteByte(’\’) 部分的编译结果:



要在 buf 上调用 WriteByte 方法,我们首先需要一个指向 buf 的 itab 指针。虽然 buf 最初是通过一对寄存器传递至函数中的,但编译器会在函数体开头将其溢出至栈内,以确保它能在其他对象上使用寄存器。要调用 buf 上的方法,我们首先需要将 *itab 从栈中加载回寄存器(CX),之后可以取消引用 CX 中的 itab 指针,借此访问其字段:我们将 offset 24 处的双字移动至 DX 内;回顾一下 itab 原始定义,就会发现 itab 中的第一个函数指针就在 offset 24 处。到这里,整个设计还是很符合逻辑的。


DX 中包含我们要调用的函数地址,但我们还没有它的参数。Go 语言中的“struct-attached 方法”相当于为独立函数加糖,可以使目标函数将接收方设为首个参数,例如将 func (b*Builder) WriteByte(x byte) 加糖成 func “”.(*Builder).WriteByte(b*Builder, x byte)。这样,函数调用的第一个参数就必须是 buf.(*face).data,即指向我们接口内 strings.Builder 的实际指针。该指针在栈内可用,位于我们刚刚加载的 tab 指针的 8 个字节之后。最后,函数中的第二个参数就直接是\, (ASCII 92),我们可以 CALL DX 执行自己的方法。


是的,单单调用一个简单方法就得费这么大劲。但有一说一,代码的实际性能还可以。最大的问题就是接口调用总会影响 incline——因为调用的实际开销来自从 itab 中加载函数地址的单一指针解引用。之后我们会对此进行基准测试,看看解引用到底要占用多少性能。但先让我们看看泛型代码。


回归泛型:指针调用


下面说回泛型函数的程序集。请注意,这里我们要分析 *uint8 生成的实例化 shape,因为所有指针实例化 shape 都会使用相同的、类似于 void 的指针类型。以下为 buf 上的 WriteByte 方法调用方式:



看着很熟悉,但其中最大的区别就是 offset 0x0094 中存在我们不希望出现在函数调用点上的内容:另一个指针解引用。用人话来解释:因为我们把所有指针 shape 都单态化成了*uint8 的单一 shape 实例,所以该 shape 就不再包含可以在指针上调用哪些方法的信息。可这些信息还是必要的,该保存在哪里?理想情况下,自然是放置在与指针相关联的 itab 当中。但因为我们的函数 shape 采用单一 8 字节指针作为 buf 参数——而非接口那样的 16 字节胖指针*itab 与数据字段——所以也就不存在与指针直接关联的 itab。出于这一现实,stenciling 实现才需要向每一个泛型函数调用传递字典:字典中包含的,就是指向函数所有泛型参数的 itab 的指针。


说到这里,大家应该理解为什么我们的程序集要费力使用字典了。使用 CX 中的字典,我们就能实现解引用,并在 offset 64 处找到需要使用的 *itab。很遗憾,现在我们还得到另外一项解引用(24(CX))从 itab 内部加载函数指针。方法调用与之前的代码相同,这里不再赘述。


这种额外的解引用在实践上到底有多大影响?直观来讲,我们可以认定在泛型函数中调用对象的方法,总是要比在直接将接口作为参数的非泛型函数中要慢。这是因为泛型会把之前的指针调用转换成两次间接接口调用,所以速度一定会比常规接口调用慢。



在这项简单的基准测试中,我们使用 3 种略有差异的实现测试同一函数体。GenericWithPointer 会向我们的 EscapeW io.ByteWriter 泛型函数传递*strings.Builder;iface 基准测试则是直接采用接口的 Escape(io.ByteWriter, []byte);monomorphized 使用的是手动单态化的 Escape(*strings.Builder, []byte) 函数。


结果也基本符合预期。直接获取 *strings.Builder 的函数速度最快,因为它允许编译器对 WriteByte 调用进行内联。泛型函数的速度则比将 io.ByteWriter 接口作为参数的最简实现慢得多。可以看到,泛型字典带来的额外性能影响不算太大,毕竟这个基准测试体量很小,itab 与泛型字典的缓存命中率都有保证(别急,后文会讨论缓存争用给泛型代码带来的性能影响)。


这就是我们从分析中得到的第一个结论:在 1.18 中,我们没必要将带有接口的纯函数转换成泛型函数,因为 Go 编译器目前无法生成通过指针调用方法的函数 shape,所以转换只会拖慢代码运行速度。为了适应转换,编译器会引入两次非必要间接接口调用,这跟我们去虚拟化、尽可能内联的优化思路明显是南辕北辙。


在结束本节之前,我们还想聊聊 Go 编译器中逃逸分析的一个细节。可以看到,单态化函数在我们的基准测试中有 2 个 allocs/op。这是因为我们传递了一个指向栈内 strings.Builder 的指针,编译器可以证明它没有逃逸,因此不需要堆分配。而尽管我们也从该栈中传递了一个指针,Iface 基准测试却显示出 3 个 allocs/op。这是因为我们把指针移动到接口,因此总是进行分配。但奇怪的是,GenericWithPointer 实现同样显示 3 个 allocs/op,说明即使直接为函数生成的实例采用指针,转义分析也无法证明其属于非转义,所以就会额外增加一次堆分配。这确实是个问题,但正如前文提到,真正的大麻烦还在后头。


泛型接口调用


在之前几节中 ,我们已经使用*strings.Builder 调用了泛型 Escape 函数,并查看由此生成的 shape 完成了代码分析。大家应该还记得,我们方法的泛型签名为 EscapeW io.ByteWriter,而*strings.Builder 必然满足此约束条件,因此能够产生 *uint8 的实例化 shape。


但如果我们把 *strings.Builder 隐藏的接口之后,情况会发生怎样的变化?



现在,我们泛型函数的参数成了接口,而不再是指针。但调用仍然明显有效,因为我们传递的接口跟我们方法中的约束条件相同。但这时候生成的实例化 shape 会如何变化?这里我们没有嵌入完整的反汇编代码,毕竟太杂乱了;跟之前一样,我们直接对函数中 WriteByte 方法的调用点进行分析:



这跟之前生成的代码完全不一样了。看来测量各个调用点上的额外解引用不是什么好办法,那我们该怎么掌握额外的函数调用?


先看看目前的状况:我们可以在 Go 运行时中找到 runtime.assert|2|方法,它是在接口间对转换做出断言的帮助器。它会接收*interfacetype 与*itab 作为两项参数,并仅当给定 itab 中的接口也实现了我们的目标接口时、才返回给定 interfacetype 的 itab。不知道大家能否明白?


假设我们有如下接口:



这个接口并没有提到 io.ByteWriter 或者 io.Writer,但任何实现 IBuffer 的类型也将隐式实现这两个接口。这自然会影响到我们泛型函数的编译:因为我们函数的泛型约束为 [W io.ByteWriter],所以可以将任何实现 io.ByteWriter 的接口作为参数进行传递——其中也包括 IBuffer。


但当我们需要在参数上调用 WriteByte 方法时,该如何判断此方法在我们接到的接口 itab.fun 数组上的具体位置?这个说不好。因为如果我们将 *strings.Builder 以 io.ByteWriter 接口的形式传递,那么该接口中的 itab 必然会把方法放置在 fun[0] 处;如果作为 IBuffer 传递,那它就在 fun[1] 处。所以我们需要一个帮助器,它可以将 itab 用作 IBuffer,并为 io.ByteWriter 返回一个 itab,其中我们的 WriteByte 函数指针始终处于 fun[0] 位置。


这就是 assert|2|的意义所在,函数内的每一个调用点也都是如此。下面咱们一步步具体分析。



首先,它会把 io.ByteWriter(因为属于我们在约束中定义的接口类型,所以属于全局硬编码)的 interfacetype 加载到 AX 中。之后,它将我们传递给函数的接口的实际 itab 加载至 BX 中。到这里,assert|2|就获得了两个必要参数;调用 assert|2|后,我们就得到了 AX 中 io.ByteWriter 的 itab,可以像在之前的编译代码中那样继续调用接口函数,并保证函数指针永远处在 itab 内的 offset 24 处。本质上,这一 shape 实例就是把每项方法调用从 buf.WriteByte(ch) 转换为 buf.(io.ByteWriter).WriteByte(ch)。


没错,一听就很费性能,而且看起来也很多余。难道不能在函数开始时只获取一次 io.ByteWriter itab,再在后续的所有函数调用中重复使用吗?答案是在大多数情况下不行,只有少数函数 shape 能够安全采取这种方法(例如我们目前正在分析的函数)。


这是因为 buf 接口中的值永远不会改变,所以我们不需要执行类型切换、或者将 buf 接口向下传递至栈内其他函数处。Go 编译器肯定还有优化空间,所以我们从基准数据出发,看看这样的优化思路能产生多大影响:



效果一般。assert|2|调用明显很费性能,就连在我们这个不再进一步调用其他函数的函数中也能看得出来。执行速度几乎是直接调用 WriteByte 手动单态函数的两倍,比直接使用无泛型 io.ByteWriter 接口也要慢 30%。这肯定是个需要注意的性能问题:相同的泛型函数、相同的参数,相较于直接以指针形式传递参数,在接口内部传递参数会显著影响性能。


还没结束。事实证明,我们的 GenericWithExactIface 基准测试才是最好的方案,因为函数中的约束为 [W io.ByteWriter],而且我们将参数以 io.ByteWriter 接口的形式传递。如此一来,runtime.assert|2|调用会立即返回我们传递给它的 itab,因为它与我们 shape 实例正在寻找的 itab 完全匹配。但是,如果我们将参数作为先前定义的 IBuffer 接口进行传递,情况会有何不同?照理说不会有影响,毕竟 *strings.Builder 可以实现 IBuffer 与 io.ByteWriter,但在运行时中,函数中的每一次方法调用都会在 assert|2|尝试从 IBuffer 参数中获取 io.ByteWriter itab 时产生一个全局 hash 表。



这个发现非常重要,我们可以看到性能问题已经快变成性能黑洞了,具体影响取决于我们传递给泛型函数的接口匹配的是它的约束、还是约束的超集。


所以,我们得到一个明确的结论:千万别把接口传递给 Go 中的泛型函数。即使在最理想的情况下,即接口与约束完全匹配时,指向类型的每一次方法调用都会产生大量开销。而如果接口属于约束的超集,那么每一次方法调用都需要通过 hash 表进行动态解析,而且这项功能根本无法被纳入缓存。


在本节结束之前,我们再来整理一下思路。要想确定 Go 泛型是否适合您的用例,我们还需要明确以下几点:


上述基准测试中的数字还是理想条件下的结果,特别是在接口调用方面,这些结果无法代表现实应用程序中的函数调用开销。我们的小型基准测试完全是在实验环境下进行,泛型函数的 itab 与字典拥有很高的缓存命中率,而且启用 assert|2|的全局 itabTable 为空且不存在争用。但在实际生产服务中必然存在缓存争用,而且全局 itabTable 往往包含几十甚至上百万个条目,具体取决于服务运行了多长时间、编译代码中包含多少唯一类型 / 接口。总之,代码库的复杂度越高,Go 程序中泛型方法的调用开销就越大,而这种性能降级会对 Go 程序中的所有接口检查造成影响,只不过这些接口检查不会像函数调用那样始终以紧密循环的形式执行。


那有没有办法在合成环境下,对这种性能降级开展基准测试?当然有,但结果也不是特别可靠。我们可以用条目污染全局 itabTable,同时不断从一个单独的 Goroutine 中丢弃 L2 CPU 缓存。这种方法确实能随机增加基准测试中泛型代码的方法调用开销,但没法在 itabTable 中准确重现我们在实时生产服务中看到的争用模式,所以测量出的开销很难跟真实场景联系起来。


尽管如此,基准测试还是给了我们不少启发。我们至少了解到 Go 1.18 中不同编译代码中的方法调用,各自在小规模基准测试中产生了怎样的开销(每次调用以纳秒计)。受试方法包含一个非内联空主体,因此能够保证单纯是在测量调用开销。基准测试共运行 3 次,分别为:理想条件,L2 缓存连续丢弃,丢弃缓存且加大全局 itabTable(其中包含 itab 查找争用)。



可以看到,理想条件下的方法调用开销跟我们在 Escape 基准测试中看到的基本类似,而一旦加入争用,情况就会发生有趣的变化:如大家所料,非泛型方法的调用性能不受 L2 缓存争用的影响,而所有泛型代码的开销则会因争用而小幅增长(即使不访问全局 itabTable 也是如此,这可能是因为所有泛型方法调用都必须访问更大的运行时字典)。


当我们进一步增加 itabTable 的大小与 L2 缓存丢弃时,真正的灾难发生了:每一次方法调用都会引发大量开销,这是因为全局 itabTable 过大、根本无法放入缓存,而且相关条目也无法命中。再次强调,我们这次小型基准测试属于定性测量,无法给出有意义的开销增量,具体还是要看生产环境中 Go 应用程序的复杂性与负载强度。


总之,这次实验的最大收获,就是提醒大家 Go 泛型代码中潜藏着这种性能“杀手”,必须想办法加以排除。


字节序列


在 Go 代码库,还有另一种常见的模式,甚至在标准库中也时有出现。这就是某一函数在将一段 []byte 作为自己函数的同时,还会保留一个与之等价的字符串。


这种模式真的无处不在(例如 (*Buffer).Write 和 (*Buffer).WriteString),这里我们以 encoding/utf8 包为例:其中约 50% 的 API 表面为重复方法,已经进行手动单态化以支持 []byte 和 string。



需要强调的是,这种重复本身其实是一种性能优化:API 很可能只提供 []byte 函数以操作 UTF8 数据,相当于强制用户在调用包前将 string 输入转换为 []byte 。这虽然更符合使用习惯,但也相当吃性能。由于 Go 中的字节切片是可变的,而字符串不可变,所以二者之间的相互转换将始终强制执行分配。


泛型存在的意义,就是消除这类随处可见的代码重复,但这里的重复代码是为了防止额外分配,所以在统一具体实现之前,我们先得保证生成的 shape 实例在行为上与预期相符。


下面,我们来比较 Valid 函数的两个不同版本:encoding/utf8 中的原始函数以 []byte 为输入,而新的泛型函数则受 byteseq 约束——这是一个非常简单的 string | []byte 约束,允许我们对这两种参数类型进行互换。



在查看新泛型函数的 shape 之前,我们应该先看看非泛型编译中的一些优化细节,通过比较确定这些优化在泛型实例化的过程中是否仍然存在。从中,我们能发现两项好优化和一项烂优化:


首先,Go 1.16 版本引入了基于寄存器的 Go 调用约定,这就特别适合优化我们的 []byte 参数。现在,切片头的 24 个字节不会被推送进栈,而是作为 3 个指针在 3 个寄存器中单独传递:切片的 *byte 指针驻留在整个函数体的 AX 内,长度驻留在 BX 内,而且绝不会溢出。这样我们就能高效使用寄存器来实现相对复杂的表达式,例如把 len§ >= 8 编译成 CMPQ BX, $8。同样的,从 p 中加载 32/64 bit 也会被优化成从 AX 中加载 MOVL + ORL 。


这条编译函数中唯一不好的部分出现在主 for 循环中:第 19 行的 pi := p[i] 加载包含一项边界检查,但这步检查本该通过以上循环头中的 i < n 实现。从生成的程序集中可以看到,我们实际上是连续链接了两次跳转:一次是 JGE(有符号比较指令)、一次是 JAE(无符号比较指令)。这个问题比较隐蔽,根源是 Go 语言中 len 的返回值是经过签名的。也许我们可以单开一文,具体讲讲这个问题。


总之,这个 Valid 函数的非泛型编译代码还是挺不错的,接下来就是跟泛型实例进行比较。这里我们只看 []byte 参数的 shape;使用 string 参数调用泛型函数会生成不同的 shape,这是因为二者的内存布局不同(string 为 16 字节,而 []byte 为 24 字节),所以即使二者在实例化 shape 中的使用方式相同,区别也仍然存在。这里,我们仅以只读方式访问字节序列。


结果很好,甚至可以说是相当好。我们发现在这个用例中,泛型确实能帮助代码实现重复部分删除,而且不会造成性能减退。这个结果令人兴奋:从头到尾,可以看到所有优化仍然成立(这里没有显示,但 string shape 也得到了优化)。基于寄存器的调用约定在泛型实例中仍然存在,只是现在 []byte 参数的长度现在驻留在 CX、而非 BX 中:所有寄存器都向右移动了一个 slot,这是因为 AX 现在由泛型负责实现。


其他一切就非常整洁精练了:32/64 bit 加载仍然分为两条指令,非泛型版本中省略的少数边界检查在这里仍然省略,而且完全没有引入任何额外开销。


下面来看两种实现的简单基准测试结果:



这两种实现间的性能差异基本属于正常的误差范畴,所以可以算是最理想的结果了:[]byte | string 约束可用于 Go 泛型,能够减少负责处理字节序列的函数中的代码重复,而且不会引入任何额外开销。但这里也有例外:在运行 ASCII 基准测试时,即使二者的程序集功能完全相同,string 的泛型 shape 还是要比非泛型实现快不少(约 4%)。这种情况着实令人费解,而且只能在输入为 ASCII 的基准测试中重现。


函数回调


从最早的版本起,Go 对匿名函数的支持就相当友好。作为 Go 语言的核心特性,匿名函数允许在不改变语言语法的前提下大大增加多种模式的长度来强化表达能力。例如,用户代码无法通过扩展在自定义结构或接口上调用范围运算符时,就可以使用匿名函数。所以为了支持迭代,我们的数据结构就必须要实现自定义迭代器结构(开销很大),或者使用速度更快、基于函数回调的迭代 API。下面来看个小例子,这里使用函数回调遍历 UTF-9 编码字节切片中的所有有效符文(即 Unicode 代码点):



抛开基准测试:与使用 for _, cp := range string§ 的常规迭代相比,大家觉得这个函数的性能是更好还是更差?没错,答案是更差。这是因为 string 上的范围循环包含内联迭代主体,所以只有最理想的情况(即纯 ASCII 字符串)才能在不调用任何函数的情况下完成。而在我们的自定义函数中,必须要为每个符文(rune)发出回调。


如果我们能用某种方法为函数内的每个回调实现内联,就能把性能拉升至类似 ASCII 字符串范围循环的水平,甚至在处理 Unicode 字符串时实现速度反超!但是,如何才能让 Go 编译器对我们的回调进行内联?这确实是个难解的问题,毕竟我们传递的回调并不会在本地函数中执行、而是作为迭代的一部分在 ForEachRune 内部执行。为了将回调内联至迭代器中,我们必须使用特定回调对 ForEachRune 副本进行实例化。但 Go 编译器并没有这项功能,也没有哪款常见的编译器会生成一个以上的纯函数实例,除非……


除非我们“骗骗”编译器。这个过程跟单态化非常相似:传说有一种跟 C++ 一样古老的绝技,能根据接收到的回调类型对数据进行参数化。如果大家用过 C++ 代码库,就会注意到其中接受回调的函数往往是泛型的,也就是将函数回调的类型当作参数。在对封闭函数进行单态化时,该函数调用的特定回调会被替换为 IR,这样就无所谓内不内联了——特别是在纯函数(即不捕捉任何参数回调)的情况下。依托于这种可靠的优化方法,lmabda 与模板的组合已经成为现代 C++ 中最高效的抽象基础,也给 Go 这类本身比较僵化的语言带来了更强的表达力,在无需引入新语法或运动时开销的前提下、实现了对迭代及其他函数构造的支持。


问题在于:我们在 Go 里能实现相同的效果吗?或者说,能根据回调函数对函数进行参数化吗?虽然我能找到的一切泛型文档中都没提过,但答案仍然是肯定的。我们可以将迭代器函数的签名写成以下形式,它仍然可以顺利编译并运行:



没错,我们可以使用函数签名作为泛型约束,这种约束不一定得是接口,请大家牢记这点。至于这次优化的结果可能大家已经猜到了,基本没任何效果。实例化泛型函数的 shape 并不特定于我们的回调,而是 func(rune) 回调的泛型 shape,同样不支持任何类型的内联。


所以,这说明函数回不回调其实无所谓?不完全是。事实证明,自 1.0 版本以来,Go 编译器的内联功能已经相当强大。只要泛型不来碍事,它其实完全可以实现更好的优化效果。


来看下面这个例子:假定我们正开发一个库,用于为 Go 添加函数构造。为什么要这么干?我也不太清楚,但很多人就是这么干的,可能是为了赶时髦吧。总之,我们还是从简单的用例出来:设置一个“Map”函数,它对切片内的每个元素进行一次回调,再把结果存储在适当位置。



在讨论泛型 map 之前,我们先来看看被硬编码为 int 切片形式的 MapInt,思考 Go 编译器能用这段代码做点什么。事实证明,能做的很多:MapInt 的程序集看起来很棒。从示例中,可以看到主 IntMapTest 中没有 CALL:我们从加载全局 input1 切片直接推进到进行迭代,而且只需要使用一条指令就能执行映射操作(在本示例中为简单乘法)。很明显,此函数已经完全扁平化,而且 MapInt 与 IntMapTest 内部的匿名回调在编译代码中都不见踪影。


只要大家过去十年来一直关注 Go 的性能演变,就能感受到这具有多大的现实意义!


例子中的这个简单 MapInt 函数,实际上代表着 Go 编译器中一个启发式的内联压力测试:它不是叶子函数(因为它会在其中调用另一个函数),而且包含一个带有范围的 for 循环。这两个细节,让该函数无法针对截至目前的任何一个 Go 版本进行优化。栈中内联功能直到 Go 1.10 版本才趋于稳定,而对包含循环的函数进行内联则是个已经持续存在六年多的难题。事实上,Go 1.18 是第一个能够对范围循环进行内联的版本;所以哪怕再提前几个月,MapInt 的编译结果都会大不相同。


这对 Go 编译器的代码生成能力确实意义重大,所以我们得继续观察这个函数的泛型实现,但其实并不存在这样的实现。由于栈中内联,MapAny 的主体已经在其父函数中完成了内联。所以现在位于泛型 shape 后的实际回调已经以独立函数的形式生成,而且必须在循环的每一次迭代中进行显式调用。


不过别担心,不妨试试我们刚刚讨论过的模式,也就是对回调的类型进行参数化。秘密就在这里!我们又得到了一个完全扁平化的函数,而且这可不是魔术。内联毕竟是一种启发式方法。在这个特定示例中,我们用正确的方式实现了这种启发式方法。因为我们的 MapAny 非常简单,所以整个主体都可以内联。要想进一步测试,我们就能为泛型函数的 shape 添加更多特异性。只要对函数的回调不等于对泛型 shape 的回调,而是 func(rune) 回调的一个单态化实例,那 Go 编译器就能展开整个调用。


到这里,大家猜到我想做什么了吗?在这个示例中,内联函数体其实是一种非常特殊的单态化形式,这种特殊性体现在它的实例化 shape 本质上就是一个完整的单态:因为封闭函数不是泛型,所以它就只能是单态。在这种代码可以完全单态化的情况下,Go 编译器将带来非常有趣的优化效果。


总体来讲,如果大家正在编写使用回调的函数式帮助器,例如迭代器或者 Monad,那最好能根据回调类型进行参数化。当且仅当帮助器本身足够简单且可以完全内联时,这步参数化操作将使 inliner 完全扁平化该调用,这也就是我们需要的函数式帮助器。但如果大家的帮助器不够简单、无法内联,那么参数化将毫无意义。因为实例化的泛型 shape 会太过粗糙,无法实现任何优化。


最后需要强调的是,尽管这个完整的单态化示例在很多情况下可能并不可靠,但它确实给我们指明了性能优化的新方向:Go 编译器已经非常擅长内联,只要能把它指向非常具体的代码实例,它就能生成极好的汇编结果。Go 编译器自身已经包含大量优化选项,只待泛型实现给它一点发挥的空间。



这次实验真的很有趣,希望大家跟我一样乐在其中。下面,让我们用一份简短的清单结束这篇文章,看看 Go 1.18 中那些关于性能优化与泛型实现的“要”和“不要”:


  • 要尽量使用 ByteSeq 约束对,同时使用 string 与 []byte 的相同方法进行重复部分的删除。由此生成的 shape 实例将非常接近于手动编写两个几乎相同的函数。

  • 要在数据结构中使用泛型,这也是泛型目前最理想的用例。以往使用 interface{}实现的泛型数据结构太过复杂、也不符合大多数人的思维习惯。只要删除类型断言、以类型安全的方式存储未装箱类型,就能让这些数据结构更易用、运行更快。

  • 要尽量通过回调类型对函数帮助器进行参数化。在某些情况下,Go 编译器有可能将其展平。

  • 不要试图用泛型对方法调用进行去虚拟化或内联。这样没用,因为所有指针类型都拥有同一个可传递至泛型函数的 shape;相关方法信息放置在运行时字典当中。

  • 在任何情况下,都不要将接口传递给泛型函数。因为 shape 实例化更适应接口(而非去虚拟化),所以我们需要添加额外的虚拟化层,由该层提供一份用于查找各方法调用的全局 hash 表。如果您的项目对性能比较敏感,请保证只在泛型中使用指针、不用接口。

  • 不要重写基于接口的 API 来使用泛型。受制于当前实现,只要继续使用接口,所有使用非空接口的代码都将更简单、并带来更可预测的性能。在方法调用方面,泛型会将指针转化为两次间接接口,再把接口转换成……总之,特别麻烦、也毫无必要。

  • 不要失望,毕竟 Go 泛型在语言设计上没有任何技术限制,所以未来的内联或去虚拟化方法调用一定会迎来更好用的单态化实现。


说了这么多,可能期待着能在 Go 1.18 中利用泛型优化代码性能的朋友们已经大失所望。确实很遗憾,至少在 1.18 的泛型实现中,大多数只会让代码运行速度变得更慢。但也有一些反例,告诉我们希望还会出现。不管大家是不是把 Go 看作“面向系统”语言,都很难理解为什么要把运行时字典塞进编译语言技术实现。虽然 Go 编译器的复杂度不高,但它自 1.0 版本以来的代码生成质量一直在稳步提高,而且到现在为止始终保持着这种改善势头。


从 Go 1.18 说明文档中关于完全单态化的风险来看,选择使用字典来实现泛型的理由,似乎是代码单态化的速度很慢。但这又带来了新问题:真的吗?既然从来就没有过 Go 代码单态化方案,怎么判断它很慢?


我总觉得这种复杂的技术权衡背后,是有某种顽固的误导性假设在作祟。这种假设在开发者脑袋里普遍存在,例如“单态 C++ 代码就很慢”。但还是那个问题:真的吗?有多少 C++ 编译开销真的来自单态化,又有多少是代码编写者的问题?另外,单态化代码难道没有优化方案吗?C++ 模板实例化性能不佳,所以 Go 编译器就肯定性能不佳?Go 编译器优化通道较少、模块系统相对简单,难道不能防止大量冗余代码的产生?在编译 Kubernetes 或者 Vitess 这类大型 Go 项目时,单态化到底会带来怎样的性能影响?这些都是没有定论的问题,最好别粗暴做出假设。


更靠谱的办法自然就是把握当下、尽快测试。同样地,我们也可以测量 stenciling+ 字典在现实应用代码中的性能影响,这就是本次分析的目标。从结果来看,为了帮 Go 编译器省下一点开销,我们好像把负担都转嫁给程序本身了吧。


综合目前的结论,特别是现有泛型实现对代码运行性能造成的真实影响,我希望 Go 团队能重新审视“用运行时字典缩短编译时间”这套方案,在未来的 Go 版本中使用更积极的单态化实现。必须承认,向 Go 中引入泛型确实是个艰难的任务。从功能设计层面看,这是野心勃勃的一步,但也把语言复杂性推向了新的高点。如果未来能出现一种适应大部分开发场景、没有运行时开销,不仅能够实现参数多态性、还能带来深层次优化的实现方案,相信整个 Go 社区都将从中大大受益。


原文链接:


https://planetscale.com/blog/generics-can-make-your-go-code-slower


好文推荐


HTML5崛起之时,Java桌面时代就已经终结了


互联网企业给被裁员工发“毕业须知”;孟晚舟担任华为轮值董事长;腾讯员工被曝偷看创业公司工作文档 | Q资讯


云端开发是个坑!4年后,我们又回到了本地环境


不用任何框架开发 Web 应用程序,可能吗?


2022-04-06 17:3512967

评论

发布
暂无评论
发现更多内容

上线半天下载量破100W!美团大佬的Java性能调优实战手册,超详细

Java你猿哥

Java 数据库 JVM java编程 Java性能优化

GPTCache:LLM 应用必备的【省省省】利器

Zilliz

Milvus Zilliz ChatGPT LLM 语义检索

深度学习基础入门篇[四]:激活函数介绍:tanh、sigmoid、ReLU、PReLU、ELU、softplus、softmax、swish等

汀丶人工智能

人工智能 机器学习 深度学习 激活函数

selenium源码通读·4 |webdriver/common分析

Python 源码 测试 自动化测试 selenium

selenium源码通读·5 |webdriver/common/action_chains.py-ActionChains类分析

Python 源码 测试 自动化测试 selenium

Nautilus Chain 上首个 DEX PoseiSwap 通证经济学模型解析

股市老人

面试官:说说MySQL主从复制原理

Java永远的神

MySQL 数据库 程序员 面试 主从复制

自阿里P8爆出内部1031道java面试题后,在Boss直聘狂拿千份Offer

做梦都在改BUG

Java java面试 Java八股文 Java面试题 Java面试八股文

GitHub程序调优「黑马」!阿里大牛的Java性能优化实战笔记已上线

做梦都在改BUG

Java 面试 性能优化 性能调优

解决事务隔离产生问题的MVCC

做梦都在改BUG

Netty服务开发及性能优化

做梦都在改BUG

Java Netty

看了我常用的IDEA插件,同事也开始悄悄安装了

Java你猿哥

Java 程序员 ssm IDEA 架构师

软件测试如何自我提升

FunTester

软件测试/测试开发丨Pytest 结合 Allure 生成测试报告

测试人

软件测试 自动化测试 测试开发 pytest Allure

手把手教你,从零开始搭建Spring Cloud Alibaba!这份笔记太牛了

Java你猿哥

spring Spring Cloud ssm 架构师

GitHub数据库榜单第一:Redis核心原理实践

做梦都在改BUG

Java 数据库 redis 缓存

火山引擎DataLeap推出全链路智能监控报警平台

字节跳动数据平台

数据中台 SLA 数据监控 企业号 4 月 PK 榜

商汤版ChatGPT「商量」来了!开放API,基于千亿参数大模型,体验实录在此

Openlab_cosmoplat

开源社区 ChatGPT

PC GWP-ASan方案原理 | 堆破坏问题排查实践

字节跳动终端技术

问题排查 PC

OpenTelemetry 正在改变我们跟踪和设计应用的方式

NGINX开源社区

nginx 云原生

春风送暖,好久不见

BinTools图尔兹

版本发布

Spring全家桶思维笔记导图(Spring Boot+Cloud+IOC+AOP+MVC等)

Java你猿哥

spring Spring Cloud Spring Boot aop ioc

对标大厂的技术派方案设计,带你了解一个项目从0到1实现的全过程

Java你猿哥

Java 架构 ssm 项目设计

重磅官宣,OpenHarmony开发者大会来了!

OpenHarmony开发者

OpenHarmony

阿里独家「操作系统和计算机网络」,GitHub标星超百万

做梦都在改BUG

Java 程序员 计算机网络 操作系统

MyBatis整合Springboot多数据源实现

做梦都在改BUG

Java Spring Boot mybatis

火山引擎数智平台协助洞察美图类APP新增长 付费用户转化超过124%

字节跳动数据平台

大数据 增长 产品增长 企业号 4 月 PK 榜 美图

博睿学院 | 本周四:OpenTelemetry技术在数据标准化中应用实践

博睿数据

可观测性 智能运维 博睿数据 前沿技术 博睿学院

数据开发提效有秘诀!离线开发BatchWorks 六大典型场景拆解

袋鼠云数栈

大数据 离线开发

阿里内部热捧“Spring全线笔记”,不止是全家桶,太完整了

Java你猿哥

spring Spring Cloud Spring Boot Spring MVC

泛型会让你的 Go 代码运行变慢_语言 & 开发_Vicent Marti_InfoQ精选文章