您当前的位置:首页 > 电脑百科 > 程序开发 > 编程百科

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

时间:2023-04-14 12:18:51  来源:51CTO  作者:陈峻

译者 | 陈峻

51CTO读者成长计划社群招募,咨询小助手(微信号:TTalkxiaozhuli)

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

  • 编译器具有一定智能,可以自动矢量化(auto-vectorize)所有的代码。
  • 编译器自动向量化的能力欠佳,容易受不相关代码变更的影响,因此开发人员需要手动编写明确的SIMD指令。
  • 需要重复为每个不同的CPU架构手工编写SIMD。此时,作为工具的编译器,可以通过更好的指令和约束,以适合向量化的形式,编写出可靠的向量化代码。

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

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

首先,让我们来了解编译器是如何查看代码的。鉴于有着许多结构上相似之处,我们可以参照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: ptr
param xs_len: size
local total: i32
local i: size = 0
local x: i32
local total: i32 = 0
loop:
branch_if i >= xs_len :ret
load x base=xs_ptr offset=i
add total x
add i 1
goto :loop
ret:
return total
}

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

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

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

param n: u32
local i: u32 = 0
local total: u32
local tmp
loop:
branch_if i >= n :ret
set tmp i
mul tmp 4
add t tmp
goto :loop
ret:
return total

它可以推断在每一次循环中,tmp能够保持i * 4,进而会将其优化为:
param n: u32
local i: u32 = 0
local total: u32
local tmp = 0
loop:
branch_if i >= n :ret
add t tmp
add tmp 4  # replace multiplication with addition
goto :loop
ret:
return total

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

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

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

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

第一项核心优化是内联(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: ptr
local len: usize
local cap: usize
load ptr xs.ptr
load len xs.len
load cap xs.cap
...
store xs.ptr ptr
store xs.len len
store xs.cap cap
}

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

3、不可能与可能

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

  • 在每个函数的基础上进行优化
  • 可以进行内联函数的调用
  • 擅长发现局部变量之间的关系,并据此重新排列代码
  • 能够对内存进行有限的推理(即,决定何时适合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>
where
Self: Sized,
F: FnMut(Self::Item) -> B,
{
Map::new(self, f)
}

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

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

四、SIMD

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

use std::iter::zip;
// 650 milliseconds
fn 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 milliseconds
fn common_prefix(xs: &[u8], ys: &[u8]) -> usize {
let chunk_size = 16;
let mut result = 0;
'outer: for (xs_chunk, ys_chunk) in
zip(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 milliseconds
fn common_prefix3(xs: &[u8], ys: &[u8]) -> usize {
let chunk_size = 16;
let mut result = 0;
for (xs_chunk, ys_chunk) in
zip(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 milliseconds
fn 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而言,我们需要根据处理元素块来表达算法。而且在每个块中,我们应确保没有分支,让所有元素都能以相同的方式处理。

原文链接:https://matklad.github.io/2023/04/09/can-you-trust-a-compiler-to-optimize-your-code.html

译者介绍

陈峻 (Julian Chen),51CTO社区编辑,具有十多年的IT项目实施经验,善于对内外部资源与风险实施管控,专注传播网络与信息安全知识与经验。



Tags:代码   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
跳转链接代码怎么写?
在网页开发中,跳转链接是一项常见的功能。然而,对于非技术人员来说,编写跳转链接代码可能会显得有些困难。不用担心!我们可以借助外链平台来简化操作,即使没有编程经验,也能轻松实...【详细内容】
2024-03-27  Search: 代码  点击:(13)  评论:(0)  加入收藏
为何大语言模型不会取代码农?
译者 | 布加迪审校 | 重楼生成式人工智能(GenAI)会取代人类程序员吗?恐怕不会。不过,使用GenAI的人类可能会取代程序员。但是如今有这么多的大语言模型(LLM),实际效果不一而足。如...【详细内容】
2024-03-21  Search: 代码  点击:(23)  评论:(0)  加入收藏
如何从头开始编写LoRA代码,这有一份教程
选自 lightning.ai作者:Sebastian Raschka机器之心编译编辑:陈萍作者表示:在各种有效的 LLM 微调方法中,LoRA 仍然是他的首选。LoRA(Low-Rank Adaptation)作为一种用于微调 LLM(大...【详细内容】
2024-03-21  Search: 代码  点击:(12)  评论:(0)  加入收藏
如何编写高性能的Java代码
作者 | 波哥审校 | 重楼在当今软件开发领域,编写高性能的Java代码是至关重要的。Java作为一种流行的编程语言,拥有强大的生态系统和丰富的工具链,但是要写出性能优异的Java代码...【详细内容】
2024-03-20  Search: 代码  点击:(24)  评论:(0)  加入收藏
微软AI程序员登场,10倍AI工程师真来了?996自主生成代码,性能超GPT-4 30%
新智元报道编辑:桃子 润【新智元导读】全球首个AI程序员Devin诞生之后,让码农纷纷恐慌。没想到,微软同时也整出了一个AI程序员&mdash;&mdash;AutoDev,能够自主生成、执行代码等...【详细内容】
2024-03-18  Search: 代码  点击:(17)  评论:(0)  加入收藏
对JavaScript代码压缩有什么好处?
对JavaScript代码进行压缩主要带来以下好处: 减小文件大小:通过移除代码中的空白符、换行符、注释,以及缩短变量名等方式,可以显著减小JavaScript文件的大小。这有助于减少网页...【详细内容】
2024-03-13  Search: 代码  点击:(2)  评论:(0)  加入收藏
如何进行Python代码的代码重构和优化?
Python是一种高级编程语言,它具有简洁、易于理解和易于维护的特点。然而,代码重构和优化对于保持代码质量和性能至关重要。什么是代码重构?代码重构是指在不改变代码外部行为的...【详细内容】
2024-02-22  Search: 代码  点击:(35)  评论:(0)  加入收藏
18个JavaScript技巧:编写简洁高效的代码
本文翻译自 18 JavaScript Tips : You Should Know for Clean and Efficient Code,作者:Shefali, 略有删改。在这篇文章中,我将分享18个JavaScript技巧,以及一些你应该知道的示例...【详细内容】
2024-01-30  Search: 代码  点击:(68)  评论:(0)  加入收藏
C++代码优化攻略
今天我们将深入探讨C++性能优化的世界。在当今软件开发的浪潮中,高性能的代码是必不可少的。无论是开发桌面应用、移动应用,还是嵌入式系统,性能都是关键。1. 选择合适的数据结...【详细内容】
2024-01-26  Search: 代码  点击:(115)  评论:(0)  加入收藏
手把手教你为开源项目贡献代码
背景前段时间无意间看到一篇公众号 招贤令:一起来搞一个新开源项目,作者介绍他想要做一个开源项目:cprobe 用于整合目前市面上散落在各地的 Exporter,统一进行管理。比如我们常...【详细内容】
2024-01-26  Search: 代码  点击:(71)  评论:(0)  加入收藏
▌简易百科推荐
Netflix 是如何管理 2.38 亿会员的
作者 | Surabhi Diwan译者 | 明知山策划 | TinaNetflix 高级软件工程师 Surabhi Diwan 在 2023 年旧金山 QCon 大会上发表了题为管理 Netflix 的 2.38 亿会员 的演讲。她在...【详细内容】
2024-04-08    InfoQ  Tags:Netflix   点击:(0)  评论:(0)  加入收藏
即将过时的 5 种软件开发技能!
作者 | Eran Yahav编译 | 言征出品 | 51CTO技术栈(微信号:blog51cto) 时至今日,AI编码工具已经进化到足够强大了吗?这未必好回答,但从2023 年 Stack Overflow 上的调查数据来看,44%...【详细内容】
2024-04-03    51CTO  Tags:软件开发   点击:(6)  评论:(0)  加入收藏
跳转链接代码怎么写?
在网页开发中,跳转链接是一项常见的功能。然而,对于非技术人员来说,编写跳转链接代码可能会显得有些困难。不用担心!我们可以借助外链平台来简化操作,即使没有编程经验,也能轻松实...【详细内容】
2024-03-27  蓝色天纪    Tags:跳转链接   点击:(13)  评论:(0)  加入收藏
中台亡了,问题到底出在哪里?
曾几何时,中台一度被当做“变革灵药”,嫁接在“前台作战单元”和“后台资源部门”之间,实现企业各业务线的“打通”和全域业务能力集成,提高开发和服务效率。但在中台如火如荼之...【详细内容】
2024-03-27  dbaplus社群    Tags:中台   点击:(9)  评论:(0)  加入收藏
员工写了个比删库更可怕的Bug!
想必大家都听说过删库跑路吧,我之前一直把它当一个段子来看。可万万没想到,就在昨天,我们公司的某位员工,竟然写了一个比删库更可怕的 Bug!给大家分享一下(不是公开处刑),希望朋友们...【详细内容】
2024-03-26  dbaplus社群    Tags:Bug   点击:(5)  评论:(0)  加入收藏
我们一起聊聊什么是正向代理和反向代理
从字面意思上看,代理就是代替处理的意思,一个对象有能力代替另一个对象处理某一件事。代理,这个词在我们的日常生活中也不陌生,比如在购物、旅游等场景中,我们经常会委托别人代替...【详细内容】
2024-03-26  萤火架构  微信公众号  Tags:正向代理   点击:(11)  评论:(0)  加入收藏
看一遍就理解:IO模型详解
前言大家好,我是程序员田螺。今天我们一起来学习IO模型。在本文开始前呢,先问问大家几个问题哈~什么是IO呢?什么是阻塞非阻塞IO?什么是同步异步IO?什么是IO多路复用?select/epoll...【详细内容】
2024-03-26  捡田螺的小男孩  微信公众号  Tags:IO模型   点击:(9)  评论:(0)  加入收藏
为什么都说 HashMap 是线程不安全的?
做Java开发的人,应该都用过 HashMap 这种集合。今天就和大家来聊聊,为什么 HashMap 是线程不安全的。1.HashMap 数据结构简单来说,HashMap 基于哈希表实现。它使用键的哈希码来...【详细内容】
2024-03-22  Java技术指北  微信公众号  Tags:HashMap   点击:(11)  评论:(0)  加入收藏
如何从头开始编写LoRA代码,这有一份教程
选自 lightning.ai作者:Sebastian Raschka机器之心编译编辑:陈萍作者表示:在各种有效的 LLM 微调方法中,LoRA 仍然是他的首选。LoRA(Low-Rank Adaptation)作为一种用于微调 LLM(大...【详细内容】
2024-03-21  机器之心Pro    Tags:LoRA   点击:(12)  评论:(0)  加入收藏
这样搭建日志中心,传统的ELK就扔了吧!
最近客户有个新需求,就是想查看网站的访问情况。由于网站没有做google的统计和百度的统计,所以访问情况,只能通过日志查看,通过脚本的形式给客户导出也不太实际,给客户写个简单的...【详细内容】
2024-03-20  dbaplus社群    Tags:日志   点击:(4)  评论:(0)  加入收藏
站内最新
站内热门
站内头条