写点什么

你可以信任由编译器优化的代码吗?

  • 2023-08-16
    福建
  • 本文字数:4359 字

    阅读完需:约 14 分钟

你可以信任由编译器优化的代码吗?

一、前言


不知您是否了解单指令流多数据流,也就是我们常听说的 SIMD(Single Instruction Multiple Data)?它是采用单个控制器来控制多个处理器,同时对一组数据中的每一个分别执行相同的操作,从而实现空间上的并行性的一种技术。就 SIMD 的工作原理而言,我们可以将其理解为三个层次:


  • 编译器具有一定智能,可以自动矢量化(auto-vectorize)所有的代码。

  • 编译器自动向量化的能力欠佳,容易受不相关代码变更的影响,因此开发人员需要手动编写明确的 SIMD 指令。

  • 需要重复为每个不同的 CPU 架构手工编写 SIMD。此时,作为工具的编译器,可以通过更好的指令和约束,以适合向量化的形式,编写出可靠的向量化代码。


在日常工作中,我们的开发场景通常处于第二级和第三级,需要用编译器来优化模型。下面,我将和您讨论静态语言(如 Rust 或 C++)编译器优化的一般框架,以及如何将该框架应用于自动矢量化。

二、从编译器的视角看问题


首先,让我们来了解编译器是如何查看代码的。鉴于有着许多结构上相似之处,我们可以参照 WebAssembly 规范(https://webassembly.github.io/spec/core/)来了解编译器在优化方面的核心规范。如下方简单代码段所示,一个优化单元往往就是一个函数:


fn sum(xs: &[i32]) -> i32 {let mut total = 0;for i in 0..xs.len() {total = total.wrapping_add(xs[i]);}total}在一些伪IR(指令寄存器)中,上述代码表现为:fn sum return i32 {param xs_ptr: ptrparam xs_len: sizelocal total: i32local i: size = 0local x: i32local total: i32 = 0loop:branch_if i >= xs_len :retload x base=xs_ptr offset=iadd total xadd i 1goto :loopret:return total}
复制代码


此处出现了两个重要的特征实体:

  • 作为粗略字节数组的程序内存,编译器往往无法很好地推断出内存中的内容。而且由于它们是由所有函数共享的,因此不同的函数可能会以不同的方式去解释内存中的内容。

  • 作为整数形式的局部变量,它们遵循编译器可推理的数学属性。

例如,如果编译器看到了如下循环:


param n: u32local i: u32 = 0local total: u32local tmploop:branch_if i >= n :retset tmp imul tmp 4add t tmpgoto :loopret:return total
复制代码


它可以推断在每一次循环中,tmp 能够保持 i * 4,进而会将其优化为:


param n: u32local i: u32 = 0local total: u32local tmp = 0loop:branch_if i >= n :retadd t tmpadd tmp 4  # replace multiplication with additiongoto :loopret:return total
复制代码


不过,如果我们进行相同的计算,但所有数字都位于内存中,那么编译器将很难推断出转换的正确性。如果针对 n 的存储和 total 实际是重叠的,而 tmp 与某些不在当前函数中的数据重叠了,该怎么办呢?


其实,load 和 store 指令可以作为数学局部变量和内存字节的桥梁。也就是说,load 指令在内存中获取一系列字节,将字节解释为整数,并将该整数存储到局部变量中。而 store 指令的执行操作正好相反。通过将某些内容从内存加载到本地,编译器可以获得对其进行精确推理的能力。因此,编译器无需跟踪内存的基本内容,只需检查在特定时间点,从内存进行的加载是否正确即可。可见,编译器一次只能真正推理一个函数,而且只能推理该函数中的局部变量。

三、将代码向编译器推近些


通过为编译器提供更多的上下文,我们可以实现两项核心的优化任务:


第一项核心优化是内联(inlining)。它使用被调用者去代替特定的调用。据此,调用者和被调用者的局部变量都在同一个框架中,编译器可以一起优化它们。


让我们看一段 Rust 代码:


fn sum(xs: &[i32]) -> i32 {
let mut total = 0;for i in 0..xs.len() {total = total.wrapping_add(xs[i]);}total}
复制代码


其中的表达式 xs[i]实际上是一个函数调用。索引函数在访问数组元素之前,会进行边界检查。将其内联到 sum 中后,编译器可以看到其代码并消除之。毕竟,在内联之后,函数倾向于处理一般情况,并在特定的调用站点(call-site),使用足够的约束,来消除各种边缘情况。


第二项核心优化是聚合的标量替换(scalar replacement of aggregates,SROA)。我们使用 load 避免对内存进行推理,而是对本地进行推理。


例如,有如下这样一个函数:


fn permute(xs: &mut Vec<i32>) {...}
复制代码


编译器会收到一个指向某段内存的指针。由于该内存包含了一个复杂的结构(即:ptr、len、capacity triple),因此它很难推理出该结构的演变。对此,编译器可以从内存中加载该结构,并使用一堆标量局部变量,来进行替换聚合:


fn permute(xs: &mut Vec<i32>) {local ptr: ptrlocal len: usizelocal cap: usizeload ptr xs.ptrload len xs.lenload cap xs.cap...store xs.ptr ptrstore xs.len lenstore xs.cap cap}
复制代码


如此,编译器再次获得了推理能力。虽然与内联类似,但是 SROA 主要用于内存,而不是代码。

四、不可能与可能


使用编译器模型的主要优势在于:

  • 在每个函数的基础上进行优化

  • 可以进行内联函数的调用

  • 擅长发现局部变量之间的关系,并据此重新排列代码

  • 能够对内存进行有限的推理(即,决定何时适合 load 或 store)。


当然,我们需要描述哪些代码可以被可靠地优化,哪些代码无法被优化,从而解释零成本抽象(zero cost abstractions)。针对启用内联的情况,编译器需要知道有哪个函数被实际调用了。如果属于直接调用,编译器则会尝试着与之内联;如果是间接调用(即:通过函数指针或通过虚函数表进行调用),那么在一般情况下,编译器将无法与之内联。对于间接调用而言,编译器有时也可以推断指针的值,并对调用进行去虚拟化(de-virtualize)。不过,这往往依赖于在其他地方已实现了成功的优化。


这也就是为什么在 Rust 中,每个函数都有一个唯一的、大小为零(zero-sized)的类型,而且并没有运行时(runtime)的表示。它静态的方式保证了编译器始终可以内联到代码上,以使得抽象的成本为零,毕竟任何优化编译器都会将其“融化”为零。


当然,更高级别的语言则可能会选择始终使用函数指针去表示函数。实际上,在许多情况下,它们生成的代码就等效为可优化的。不过,在源代码中是不会有任何迹象来表明这是一个可优化的情况(实际指针在编译时是可知的),还是真正的动态调用状况。因此,使用 Rust 就保证了可优化和潜在可优化之间的区别,能够反映在源语言之中,请参见如下代码段:


// Compiler is guaranteed to be able to inline call to `f`.fn call1<F: Fn()>(f: F) {f()}// Compiler _might_ be able to inline call to `f`.fn call2(f: fn()) {f()}
复制代码


由上述代码可知,其第一条规则便是使大多数调用可以被静态解析,以允许内联。而函数指针和动态调度则会防止内联。此外,内存中的间接寻址也会给编译器带来如下麻烦:


struct Foo {bar: Bar,baz: Baz,}
复制代码


显然,上述 Foo 结构对编译器是完全透明的。不过,让我们稍作如下修改:


struct Foo {bar: Box<Bar>,baz: Baz,}
复制代码


上述结果就不那么明确了。也就是说,被 Foo 占用的内存一般不会转移到被 Bar 占用的内存处。同样,在许多情况下,鉴于唯一性,编译器可以通过 box 进行“不保证”的推理。


如下代码段展示了 map 是如何被签名和定义的。


#[inline]fn map<B, F>(self, f: F) -> Map<Self, F>whereSelf: Sized,F: FnMut(Self::Item) -> B,{Map::new(self, f)}
复制代码


关于内存的另一个重点是,一般而言,编译器不能改变整体布局。SROA 可以将一些数据结构加载到一堆局部变量中,然后可以用“一对指针”代替“一个指针和一个索引”的表示。不过,SROA 最终将不得不具体化“一个指针和一个索引”,并将该表示存储回内存之中。这是因为内存布局是在所有函数之间共享的,因此函数不能单方面地指定更优化的表示。


总之,只要能够“看到”代码,编译器就能够更擅长推理代码。因此,请确保大多数调用在编译时可以实现内联。

五、SIMD


让我们将前面讨论的、为编译器提供可优化代码的通用框架,应用到自动矢量化上。下面是我们优化计算两个字节片之间最长公共前缀的函数。


use std::iter::zip;// 650 millisecondsfn common_prefix(xs: &[u8], ys: &[u8]) -> usize {let mut result = 0;for (x, y) in zip(xs, ys) {if x != y { break; }result += 1}result}
复制代码


如果您已经有了自动矢量化的模型,或者已查看了汇编的输出,那么就会发现一次仅处理一个字节的函数,效率非常慢。我们该如何解决这个问题呢?


SIMD 既然可以同时处理多个值,那么我们就希望编译器能够同时比较一堆字节。例如,我们通过如下代码段,先一次性处理 16 个字节,然后分别处理剩余部分,以便使得结构更加显式化:


// 450 millisecondsfn common_prefix(xs: &[u8], ys: &[u8]) -> usize {let chunk_size = 16;let mut result = 0;'outer: for (xs_chunk, ys_chunk) inzip(xs.chunks_exact(chunk_size), ys.chunks_exact(chunk_size)){for (x, y) in zip(xs_chunk, ys_chunk) {if x != y { break 'outer; }result += 1}}for (x, y) in zip(&xs[result..], &ys[result..]) {if x != y { break; }result += 1}result}
复制代码


其实,上述代码在速度上的提升是远远不够的。具体来说,SIMD 需要以相同的方式,并行处理块中的所有值。在上述代码中,我们用到了一个 break。这意味着第 n 对字节的处理,取决于第 n-1 对。我们可以通过禁用短路(short-circuiting),来检查整个字节块是否匹配。当然,我们并不关心具体哪个特定字节出现了不匹配:


// 80 millisecondsfn common_prefix3(xs: &[u8], ys: &[u8]) -> usize {let chunk_size = 16;let mut result = 0;for (xs_chunk, ys_chunk) inzip(xs.chunks_exact(chunk_size), ys.chunks_exact(chunk_size)){let mut chunk_equal: bool = true;for (x, y) in zip(xs_chunk, ys_chunk) {// NB: &, unlike &&, doesn't short-circuit.chunk_equal = chunk_equal & (x == y);}if !chunk_equal { break; }result += chunk_size;}for (x, y) in zip(&xs[result..], &ys[result..]) {if x != y { break; }result += 1}result}
复制代码


至此,矢量化已成功开始,而且几乎减少了一个数量级的运行时间。我们现在可以使用迭代器来进行压缩了。


// 80 millisecondsfn common_prefix5(xs: &[u8], ys: &[u8]) -> usize {let chunk_size = 16;let off =zip(xs.chunks_exact(chunk_size), ys.chunks_exact(chunk_size)).take_while(|(xs_chunk, ys_chunk)| xs_chunk == ys_chunk).count() * chunk_size;off + zip(&xs[off..], &ys[off..]).take_while(|(x, y)| x == y).count()}
复制代码


显然,此时的代码已与我们开始时有了显著不同。可见,我们不应盲目依赖编译器的优化,而需要知道在何种情况下进行特定优化,以触发它们编写代码的方式。例如,对于 SIMD 而言,我们需要根据处理元素块来表达算法。而且在每个块中,我们应确保没有分支,让所有元素都能以相同的方式处理。

发布于: 刚刚阅读数: 5
用户头像

还未添加个人签名 2023-06-19 加入

还未添加个人简介

评论

发布
暂无评论
你可以信任由编译器优化的代码吗?_编译器_互联网工科生_InfoQ写作社区