安全的本机代码(Safe Native Code)
在我的第一篇 Midori 文章中,我描述了安全如何成为我们做的所有东西的基础。我提到我们用安全代码搭建了一个操作系统,而且与用 C 和 C++ 写的操作系统如 Windows 和 Linux 相比仍然保持竞争力。在许多方面,系统架构扮演了一个关键的角色,我会在以后的文章中继续讨论怎么做到的。但是,在基础上,一个经常能从原本“托管”的、类型和内存安全的代码获得本机代码性能的优化的编译器,是我们最重要的武器之一。在这篇文章中,我会描述一些对我们成功至关重要的关键的理解和技术。
概述
当人们想到 C#、Java 以及相关的语言,他们通常想到的是即时(Just-In-Time(JIT))编译。特别是在 Midori 开始时的 2000 年代中期。但 Midori 是不同的,从一开始就使用了更加类似 C++ 的提前(Ahead-Of-Time(AOT))编译。
跟 C 和 C++ 相比,AOT 编译托管的垃圾收集代码)提出了一些独特的挑战。因此,很多 AOT 的努力并没有达到跟本机同行对等的水平。.NET 的 NGEN 技术就是一个很好的例子。实际上,.NET 中的大多数工作都是专门针对启动时间这个目标;这当然是一个关键的指标,但当你正在构建一个操作系统和之上的所有一切,启动时间只是勉强触及到了表面而已。
在 8 年的过程中,我们已经可以显著缩小我们的 C# 版本的系统和经典的 C/C++ 系统之间的差距,在基本代码的质量上,不管是大小还是速度,将 Midori 的性能与现有负载比较,已经很少称为决定的因素。事实上,还有些反直觉的事情出现了。语言、runtime、框架和编译器一同设计的能力 —— 在一个领域的折衷以获得其他领域的优势 —— 在关于程序的语义上给编译器提供了比以往任何时候更多的符号信息,所以,我敢说,能在不少的情形下超过 C 和 C++ 的性能。
在深入之前,我得提醒你。架构决定 —— 像异步一切和零拷贝 IO(很快会提到)—— 更多在“整个系统”的层面缩小差距。特别是我们更少 GC 饥饿的写系统代码的方式。但高度优化的编译器的基础,知道和利用安全的优点,是我们成果中至关紧要的东西。
我得坦率地指出,与我们同时,外部世界在这一领域也取得了相当大的进展。Go 在系统性能和安全性之间有一个优雅的界限。Rust 就是纯粹的超赞。.NET Native 和相关的 Android Runtime 项目已经用一种限制更多的方式给 C# 和 Java 带来良好的 AOT 体验,作为一种“静默的”优化技术,以避免移动应用因为 JIT 时造成的卡顿。最近,我们正在致力于通过 CoreRT 项目将 AOT 带到更广泛的 .NET 环境中。通过这一努力,我希望我们能够将下面的一些经验教训带到现实世界中。由于打破了微妙的平衡,我们能走得多远还需要观望。我们花了好几年才让一切东西和谐工作起来,以数十人年为单位,然而,将知识转授也需要花费很多时间。
首先的首先,让我们先快速回顾一下:本机语言和托管语言的区别到底是什么?
相同之处是什么?
我鄙视“本机和托管”这种错误的二分法,所以我得为使用了这种说法而道歉。读了这篇文章之后,我希望能让你相信这是一个连续的东西。C++ 现在比以往变得更安全,与之对应的是 C# 的性能。有趣的是到底有多少经验教训被直接应用到我们团队这些天正在致力的安全 C++ 工作上。
因此,让我们从考虑哪些是一样的开始。
所有龙书的基本主题跟本机代码一样适用于托管代码。
基本上,编译代码是一种平衡行为,一方面为目标架构平台生成最有效率的指令序列,以快速地执行程序;另一方面,为目标架构平台生成最小的指令编码,以将程序紧凑地存储并有效地使用目标设备的内存系统。你最喜爱的编译器上有无数的旋钮,它们根据你的场景在两方面中拨动。在移动设备,你可能想要更小的代码,而在多媒体工作站上,你可能想要最快的代码。
选择托管代码不会改变这里的任何一点。你仍然需要同样的灵活性。你在 C 和 C++ 编译器中使用来达成这个目的的技术绝大程度上跟使用在安全代码上的一样。
你需要一个很棒的内联处理器(inliner)。你想要公共子表达式消除(common subexpression elimination (CSE)),常量传播和折叠(constant propagation and folding),强度降低(strength reduction),以及一个优秀的循环优化器(loop optimizer)。现在,你可能想要使用静态单赋值形式(static single assignment form (SSA)),以及一些独特的 SSA 优化如全局值编号(global value numbering)(虽然在到处使用 SSA 时你需要小心工作集和编译器吞吐量)。你需要对你很重要的目标架构的特定机器依赖的优化器,包括寄存器分配器(register allocators)。最终,你将需要一个全局分析器来做过程间优化,链接时代码生成以扩展跨过程的过程间优化,一个应对现代处理器(SSE、NEON、AVX 等等)的矢量化器(vectorizer),以及定义良好的剖析引导优化(profile guided optimizations (PGO))来在真实世界的场景中应用上面说的这些技术。
虽然面对安全语言会在你的行进路上扔出一些独特有趣的香蕉球 —— 我下面会提及 —— 你仍需要所有的标准的优化编译器的东西。
我不想这样说,但将所有这些东西都做好是“桌面筹码”。早在 2000 年代中,我们不得不手写所有的东西。谢天谢地,现在你可以得到一个极好的现成的优化编译器,如 LLVM,其中大部分已经经过实战测试,准备就绪,而且并为你的改进做好了准备。
不同之处是什么?
不过当然,有不同之处,很多。要不然这篇文章就没啥意思了。
不同之处更多在于,在抛给优化器的代码和数据结构中,你所期望的“形状(shape)”会有什么不一样。这些形状来自于不同的指令序列、代码中不存在 C++ 等效的逻辑操作(如更多的边界检查)、数据结构布局差异(如额外的对象头或接口表),以及在大多数情况下,更多的支持 runtime 数据结构。
相比在譬如 C 中的朴素的数据类型,在大多数托管语言中,对象有“更多的东西”。(注意 C++ 的数据结构并没有你想象的那么朴素,可能跟你直觉不一样,更加接近 C#。)在 Java 中,每个对象都在它对象头有个 vtable
指针。在 C# 中,大多数也如此,虽然 struct
不是。GC 可以强加额外的布局限制,例如填充和几个字节来完成它的簿记。注意这些没有一个是限定在托管语言的 —— C 和 C++ 分配器也可以插入它们自己的字节,而且当然,很多 C++ 对象也带有 vtable
—— 然而可以公平地说,大多数 C 和 C++ 实现在这些方面往往是倾向于更经济的。在大多数情况下,是出于文化因素而不是硬性的技术因素。在堆中添加了好几千个对象,特别是当你的系统是像 Midori 那样用许多使用隔离堆的小进程搭建起来时,对象增加很快。
在 Java 中,你有更多的虚拟调用,因为默认方法就是虚拟的。在 C# 中,谢天谢地方法默认是非虚拟的。(我们甚至将类默认设置成 sealed
。)太多的虚拟调用可以全部拧起来内联,这是一个对小函数的关键优化。在托管语言中,你倾向于使用更多的小函数,基于两个理由:1) 属性,和 2) 高级程序员倾向于过度抽象。
虽然很少正式地提及,有一个“ABI
”(应用程序二进制接口(Application Binary Interface))用于组织代码和 runtime 的交互。ABI 就是轮胎接触路面的地方。它是诸如调用约定、异常处理、以及最突出的,机器码中的 GC 清单这样的东西。这不是托管代码独有的!C++ 有一个“runtime”因此也有一个 ABI
。它只是主要由 header
、像分配器的库等的组合,相比于经典的运行时是不可妥协的(而且在 JIT 情形下是相当笨重的) C# 和 Java 虚拟机,能够更加透明地链接到程序中。这样想对我很有帮助,因为这跟 C++ 的同构性立刻变得明显起来。
真正的大头是数组边界检查。传统的方式在访问前,不管是加载还是存储,检查索引是在数组的边界范围内。这是一个额外的字段读取、比较、以及条件分支。分支预测现在可以做得很好了,然而如果你干了更多的活,那么你一定要付出更多,这是纯物理定律。有意思的是,我们使用 C++ 的 array_view<T>
来干这个,因此开销是相同的。
与此相关,也有在 C++ 中不存在的 null
检查。举个例子,如果你在 C++ 的 null
对象指针上执行方法调用,你最终会运行那个函数。如果函数尝试访问 this
,它被绑定到 AV,但在 Java 和 .NET 中,在这种情况下,编译器被要求(每个规范)显式检查并抛出一个异常,在调用发生之前。这些小的分支也会累加起来。我们在优化的构建中消除了这种检查,转而支持 C++ 语义。
在 Midori 中,我们默认使用溢出检查选项编译。这跟现在的 C# 不同,在 C# 中你必须显式传入 /checked
标记来达成这个行为。在我们的经验中,意料不到的溢出被捕获的数目和出乎意料的程度,是非常值得这种不方便和成本的。但这也意味着我们的编译器需要在理解如何消除不必要的溢出检查上做的非常好。
静态变量在 .NET 和 Java 中是非常昂贵的。比你想象的更厉害。它们是可变的,因此不能保存在只读的镜像段中以在不同的进程中共享。而且注入到结果代码中的惰性初始化检查的数量是超出天际突破想象的。在 .NET 中从 preciseinit
切换到 beforefieldinit
语义有点帮助,因为初始化检查不需要在每次访问一个静态成员时都需要发生 —— 只需要访问正在使用中的静态变量 —— 但与使用常量和用心的全局初始化结合的精心编写的 C 程序相比,还是令人不爽的。
最后一个主要的领域特定于 .NET 的:struct
。虽然 struct
有助于缓解 GC 压力,因此对于大多数程序是一件好事,但它们也有一些微妙的问题。例如,CLI 在它们初始化时指定了令人奇怪的行为。即如果在构造过程中一个异常发生了,整个结构槽必须保持初始化为 0。结果是大多数编译器都使用了防御性的复制。另一个例子是编译器必须在任何时候你在一个只读的 struct
上调用函数时都执行防御性复制。struct
到处被复制是相当常见的,对你的计算时间周期损害特别厉害,因为通常时间都花在 memcpy
上。我们有很多技术来解决这个问题,而且有趣的是,我很肯定当所有的这些被说出来并搞定,我们的代码质量会比 C++ 的更好,考虑到它的 RAII
,复制构造函数,构析函数等等的惩罚。
编译架构
我们的架构涉及三大主要组件:
- C# 编译器:执行词法分析、语句分析和语义分析。最终将 C# 文本源代码转化为基于 CIL 的中间表示(intermediate representation (IR))。
- Bartok):接受给定的
IR
进行高层次的基于MSIL
的分析、转换和优化,最终将IR
降低到更接近于更具体的机器表示。例如,使用 Bartok 处理完IR
后,泛型就消失了。 - Phoenix):接受上面的更低层次的
IR
,并尽可能地处理它。这是大部分“油门到底”的优化发生的地方。输出是机器代码。
这里跟 Swift 的编译器设计,尤其是 SIL 的相似之处是显而易见的。.NET Native 项目也多少照抄了这个架构。坦率地说,大多数针对高层次语言的 AOT 编译器都这样做。
在大多数地方,编译器的内部表示使用了静态单赋值形式(SSA)。SSA
一直保留直到编译的很后期。这促进并改善了前面提到的很多经典编译器优化的使用。
这个架构的目标包括:
- 促进快速的原型和实验。
- 生成跟商业 C/C++ 编译器同等水平的高质量机器代码。
- 支持调试优化的机器代码以提高生产力。
- 促进基于采样或/和检测的剖析引导优化代码。
- 适合自托管(self-host):
- 编译出来的编译器是足够快的。
- 足够快以让编译器开发人员乐于使用它。
- 当编译器出现情况时容易调试问题。
最后,一个简短的警告。我们尝试过很多东西,我没法把它们都记起来。早在我参与其中前 Bartok 和 Phoenix 就已经存在好几年了。Bartok 是托管语言研究的沃土 —— 从优化到 GC 到软件事务内存 —— 而 Phoenix 是为了取代 Visual C++ 编译器的。所以不管怎样,我是没法讲出全部完整的故事的。但我会尝试做到最好。
优化
让我们深入探讨一些特定的经典编译器优化领域,扩展到覆盖安全代码。
消除边界检查
C# 数组是带边界检查的。Midori 的也是。虽然在常规的 C# 代码中消除多余的边界检查非常重,在我们的情况下就更是如此了,因为即使系统的最底层也使用边界检查的数组。例如,在 Windows 和 Linux 内核内部,你会见到的是 int*
,在 Midori 中你会见到的是 int[]
。
要看看边界检查是什么样子,考虑这个简单的例子:
var a = new int[100];
for (int i = 0; i < 100; i++) {
... a[i] ...;
}
这里是作为存在边界检查的循环内部访问生成的机器码的例子:
; 首先,将数组的长度放入 EAX:
3B15: 8B 41 08 mov eax,dword ptr [rcx+8]
; 如果 EDX >= EAX,访问越界;跳到 error:
3B18: 3B D0 cmp edx,eax
3B1A: 73 0C jae 3B28
; 否则,访问正常;计算元素地址并赋值:
3B1C: 48 63 C2 movsxd rax,edx
3B1F: 8B 44 81 10 mov dword ptr [rcx+rax*4+10h],r8d
; ...
; 错误处理;只是调用 runtime helper 进行 throws:
3B28: E8 03 E5 FF FF call 2030
若你在每个循环迭代中都做这个簿记(bookkeeping),你不会得到非常紧凑的循环代码。那你当然不会有任何向量化它的希望。所以,我们花了很多时间和精力来尝试消除这样的检查。
在上面的例子中,人类一眼就能看出,没有必要进行边界检查。然而,对于编译器来说分析并不是那么简单。它需要证明关于范围的各种事实。它还需要知道 a 不是可能在循环体中某刻被修改的别名。这个问题很快就会变得令人惊奇的如此困难。
我们系统有多层的边界检查消除。
首先要注意的是,CIL 严格约束了优化器在某些领域的精确性。例如,越界访问数组会抛出一个 IndexOutOfRangeException
,跟 Java 的 ArrayOutOfBoundsException
类似。而且 CIL 规范它应该精确地在抛出异常的地方这样做。我们稍后会看到,我们的错误模型更加宽松。它是基于快速失败(fail-fast)的并允许导致不可避免的失败比较其他情况“更快”地发生的代码移动。没有这个,我们的手就会被束缚在我要讨论的很多事情上。
在 Bartok 的最高层上,IR
仍然是相对接近程序输入的。所以一些简单的模式可以被匹配和消除。在更进一步底层化之前,ABCD 算法 —— 一种基于 SSA
的直接值范围分析 —— 开始运行来消除更常见的模式,使用比模式匹配更好的更原则性的方法。由于过程内的长度和控制流事实传播,我们也能够在全局分析阶段使用 ABCD
。
接下来,Phoenix 循环优化器开始着手处理东西。这层执行各种循环优化,以及跟本节内容最相关的范围分析。例如:
- 循环实体化:这种分析实际上创建循环。它识别出若表示为循环会更理想的代码的重复模式,并在有收益时重写它们为循环。这包括展开( unroll)手工(hand-rolled)的循环以便向量器能够处理它们,即使它们可能稍后会被重新展开(re-unroll)。
- 循环克隆、展开以及版本化:这种分析创建循环的多个复制以进行专门化。包括循环展开、创建向量化的循环的特定架构的版本,等等。
- 归纳(Induction)范围优化:这是我们在这节最关注的阶段。除了做经典的例如拓宽(widening)的归纳变量优化之外,的它使用归纳范围分析来消除不必要的检查。作为这一阶段的副产品,边界检查被消除和将它们提升到循环之外来合并。
这些原则性的分析比前面所展示的更有威力。例如,有一些方法可以编写可以很容易“欺骗”前面所讨论的更基本的技术的早期循环代码:
var a = new int[100];
// Trick #1: use the length instead of constant.
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
// Trick #2: start counting at 1.
for (int i = 1; i <= a.length; i++) {
a[i-1] = i-1;
}
// Trick #3: count backwards.
for (int i = a.length - 1; i >= 0; i--) {
a[i] = i;
}
// Trick #4: don't use a for loop at all.
int i = 0;
next:
if (i < a.length) {
a[i] = i;
i++;
goto next;
}
你了解了这点。显然在某种程度上,你可以压榨优化器的能力来做任何事情,特别是当你开始在循环内部进行虚拟调用时,其中会丢掉别名信息。显然,当数组的长度不能静态地获知的时候,情况就变得更加困难,如上面例子的 100 所示。然而,如果你能证明循环范围和数组的关系,则所有的这些都不会丢失。这些分析的大部分都需要C# 的数组长度是不可变的事实的特别知识。
在这些日子的最终,优化做得很好,这里是区别:
; Initialize induction variable to 0:
3D45: 33 C0 xor eax,eax
; Put bounds into EDX:
3D58: 8B 51 08 mov edx,dword ptr [rcx+8]
; Check that EAX is still within bounds; jump if not:
3D5B: 3B C2 cmp eax,edx
3D5D: 73 13 jae 3D72
; Compute the element address and store into it:
3D5F: 48 63 D0 movsxd rdx,eax
3D62: 89 44 91 10 mov dword ptr [rcx+rdx*4+10h],eax
; Increment the loop induction variable:
3D66: FF C0 inc eax
; If still < 100, then jump back to the loop beginning:
3D68: 83 F8 64 cmp eax,64h
3D6B: 7C EB jl 3D58
; ...
; Error routine:
3D72: E8 B9 E2 FF FF call 2030
以及下面的,完全优化的,没有边界检查的,循环:
; Initialize induction variable to 0:
3D95: 33 C0 xor eax,eax
; Compute the element address and store into it:
3D97: 48 63 D0 movsxd rdx,eax
3D9A: 89 04 91 mov dword ptr [rcx+rdx*4],eax
; Increment the loop induction variable:
3D9D: FF C0 inc eax
; If still < 100, then jump back to the loop beginning:
3D9F: 83 F8 64 cmp eax,64h
3DA2: 7C F3 jl 3D97
有趣的是,当我们使用 C++ 新的 array_view<T>
类型进行同样的运用时,我感到似曾相识。有时候我和我的前 Midori 同事开玩笑,我们注定要在接下来的 10 年里慢慢地、耐心地重复自己的人生了。我知道这听起来很傲慢。但我几乎每天都有这种感觉。
溢出检查
如前所述,我们在 Midori 中默认使用 checked
运算(通过 C# 中的 /checked
标志)。这消除了开发人员没有预料到的那些错误,因此代码从溢出中更正过来。当然我们保留了显示的 checked
和 unchecked
作用域构造,以在适当的时候覆盖默认情况,不过这是更可取的,因为程序员声明了他的意图。
不管如何,如你所料,这同时也会降低代码质量。
作为对比,假设我们将两个变量加起来:
int x = ...;
int y = ...;
int z = x + y;
现在假设 x
在 ECX
中,而 y
在 EDX
中。下面是标准的 unchecked
加操作:
03 C2 add ecx,edx
或者你想要更花哨一些,那个使用同一 LEA
指令也将结果存储在 EAX
寄存器中,跟很多现代编译器可能会做的那样:
8D 04 11 lea eax,[rcx+rdx]
嗯,下面是插入了一个边界检查的等效代码:
3A65: 8B C1 mov eax,ecx
3A67: 03 C2 add eax,edx
3A69: 70 05 jo 3A70
; ...
3A70: E8 B3 E5 FF FF call 2028
多出了那些可恶的条件跳转(JO
)跟错误处理例程(CALL 2028
)。
事实证明,前面提到的许多证明边界检查多余的分析也适用于证明溢出检查是多余的。这都是关于证明关于范围的事实。例如,如果你可以证明某些检查是由之前的某些检查控制)的,而且更早的检查是后面检查的超集,那么后面的检查就是不必要的。如果恰好相反 —— 即前面的检查是后面检查的子集,如果后面块的超出之前的那个,你可能要将更强的检查移到程序的前面。
另一个常见的模式是一样或者相似的,算术运算一而再多次出现:
int p = r * 32 + 64;
int q = r * 32 + 64 - 16;
很显然如果 p
赋值不会溢出,那么 q
肯定也不会。
在现实世界的代码中还有一个神奇的现象经常出现。在同样相邻的代码中同时有边界检查和算术检查是很常见的。设想一些代码从一个数组中读取一组值:
int data0 = data[dataOffset + (DATA_SIZE * 0)];
int data1 = data[dataOffset + (DATA_SIZE * 1)];
int data2 = data[dataOffset + (DATA_SIZE * 2)];
int data3 = data[dataOffset + (DATA_SIZE * 3)];
.. and so on ...
C# 数组不能有负的边界。如果编译器知道 DATA_SIZE
是足够小的,溢出的计算不会小于 0,那么它可以为边界检查消除范围检查。
还有许多你可以覆盖的其他的模式和特殊情况。但上面示例了一个真正好的与循环优化器集成的范围优化器的力量。它可以覆盖一系列的场景,包括数组边界和算术运算。它需要大量的工作,但最后它是值得的。
内联
在大多数情况下,内联跟真正的本机代码是相同的。而且是同样的重要。经常是更为重要,因为 C# 开发人员倾向于编写大量小的方法(像属性访问器)。由于本文中的许多主题,要得到小的代码会比在 C++ 中更难 —— 更多的分支、更多的检查等等 —— 因此,实际上大多数托管代码的编译器比本机代码的编译器内联得少得多,或者至少需要做相当不同的调整。这回实际上严重影响和破坏性能。
也有一些习惯性的膨胀的方面。在 MSIL 中 lambda 编码的方式对于一个本机后端编译器是无法理解的,除非这个事实使工程师幡然醒悟。例如,我们有一个优化接受这样的代码:
void A(Action a) {
a();
}
void B() {
int x = 42;
A(() => x++);
...
}
而在内联之后,可以将 B
转化为这样:
void B() {
int x = 43;
...
}
Action
参数是个 lambda 表达式,如果你知道 C# 编译器是如何将 lambda 编码成 MSIL,就会了解这个技巧是多么困难。作为例子,下面是 B
生成的代码:
.method private hidebysig instance void
B() cil managed
{
// Code size 36 (0x24)
.maxstack 3
.locals init (class P/'<>c__DisplayClass1' V_0)
IL_0000: newobj instance void P/'<>c__DisplayClass1'::.ctor()
IL_0005: stloc.0
IL_0006: nop
IL_0007: ldloc.0
IL_0008: ldc.i4.s 42
IL_000a: stfld int32 P/'<>c__DisplayClass1'::x
IL_000f: ldarg.0
IL_0010: ldloc.0
IL_0011: ldftn instance void P/'<>c__DisplayClass1'::'<B>b__0'()
IL_0017: newobj instance void [mscorlib]System.Action::.ctor(object,
native int)
IL_001c: call instance void P::A(class [mscorlib]System.Action)
IL_0021: nop
IL_0022: nop
IL_0023: ret
}
要获得这个魔术般的结果,需要常量传播 ldftn
,识别出委托构造是如何工作的(IL_0017
),利用这信息来内联 B
并一起消除 lambda/delegate,然后再主要通过常量传播,折叠算术到用常数 42
做 x
的初始化。这种“掉到”多个不同关注点的优化的组合的情况,我总是发现的它的优雅。
与本机代码一样,剖析引导优化(PGO
)方式使我们的内联决策更加有效。
结构(Struct)
CLI 结构几乎就跟 C 的结构一样,除了它们不是。CLI 强制了一些引起开销的语义。这些开销几乎总是表现为过度复制。更糟糕的是,这些复制通常在你的程序中是隐藏起来的。这是毫无意义的。因为复制构造和构析,C++ 也有一些真正的问题,通常比我要描述的更糟。
也许最烦人的是,用 CLI 的方式初始化一个结构需要一个防卫性的复制。例如,考虑这个程序,S
的初始函数抛出了一个异常:
class Program {
static void Main() {
S s = new S();
try {
s = new S(42);
}
catch {
System.Console.WriteLine(s.value);
}
}
}
struct S {
public int value;
public S(int value) {
this.value = value;
throw new System.Exception("Boom");
}
}
这个程序的行为必须是值 0
被写到控制台中。在实践中,这意味着赋值操作 s = new S(42)
必须首先在栈上创建一个新的 S
类型的槽,构造它,并且然后而且只有在然后才将这个值复制回 s
变量中。对于这样的只有一个 int
的结构,这没什么大不了的。对于大的结构,这意味着要诉诸于 memcpy
。在 Midori 中,由于我们的错误模型(以后会讲及更多),我们知道什么方法会 throw
,而哪些不会,意味着我们可以在几乎所有情况下避免这种开销。
另一个烦人的情况像下面这样:
struct S {
// ...
public int Value { get { return this.value; } }
}
static readonly S s = new S();
每一次我们读取 s.Value
:
int x = s.Value;
我们都会得到一个本地的副本。这项实际上只会在 MSIL 中才能看出来。这是没有 readonly
的:
ldsflda valuetype S Program::s
call instance int32 S::get_Value()
而这个是有 readonly
的:
ldsfld valuetype S Program::s
stloc.0
ldloca.s V_0
call instance int32 S::get_Value()
请注意编译器选择使用 ldsfld
,再跟一个 ldloca.s
,而不是像第一个示例那样用 ldsflda
直接加载地址。由此产生的机器代码甚至更加糟糕。正如我后面会提及的那样,我也不能通过引用来传递结构,必须复制它,也可能出现问题。
在 Midori 中我们解决了这个问题,因为我们的编译器知道不会改变成员的方法。所有的静态变量首先就是不可变的,所以上面的 s
不会需要防御性复制。或者,除此之外,这个 struct
可以被声明为 immutable
的,如下:
immutable struct S {
// As above ...
}
或者反正所有的静态值都是不可变的。或者相关的属性或者方法可以被声明为 readable
,即它们不能触发变更所以不需要防御性复制。
我提到了通过引用传递。在 C++ 中,开发人员知道通过引用传递大的结构体,用 *
或者 &
,来避免过多的复制。我们也同样养成了这样做的习惯。作为例子,我们有 in
参数,如下:
void M(in ReallyBigStruct s) {
// 读取, 但不赋值到, s ...
}
我承认我们可能将这个做到了极限,到了那个我们 API 难以忍受的点。如果我能够重来一次,我会回到过去消除 C# 中 class
和 struct
的根本区别。事实证明,指针并没有那么糟糕,对于系统代码,你确实希望深入了解“近”(值)和“远”(指针)之间的区别。我们的确在 C# 中实现了相当于 C++ 中的引用,但这还不够。在我即将到来的深入挖掘我们的编程语言中会有更多相关内容。
代码大小(Code Size)
我们在代码大小上压制得很狠。甚至比我知道的 C++ 编译器狠得多。
泛型实例化知识一些花哨的带一些替代的代码的复制和粘贴。很显然,与开发人员实际编写的代码相比,这意味着编译器要处理的代码激增。我之前已经写过很多关于泛型的性能挑战。一个重要的问题是传递闭包问题。.NET 中看起来简单直接的 List<T>
实际上在它的传递闭包种创建了 28 种类型!还没说每个类型种的所有方法。泛型是代码大小快速激增的原因。
我忘记不了我重构我们 LINQ 实现的那天。不像在 .NET 中使用扩展方法的方式,我们在我们集合类型层次的最基类上将所有的 LINQ 操作实现为实例方法。这意味着大约 100 个内嵌类,每个 LINQ 操作都有一个,对于每一个实例化的集合!重构这个是在整个 Midori “工作站”操作系统镜像中节省超过 100MB 代码大小的简单办法。是的,100MB!
我们学会了更周到地使用泛型。例如,嵌套在外部泛型中的类型通常不是个好主意。我们还积极共享泛型实例化,甚至比 CLR 所做的还多。即我们还共享 GC 指针在相同位置的值类型泛型。因此,例如考虑一个结构 S
:
struct S {
int Field;
}
我们会在 List<S>
跟 List<int>
共享相同的代码表示。以及相似的,考虑:
struct S {
object A;
int B;
object C;
}
struct T {
object D;
int E;
object F;
}
我们会在 List<S>
和 List<T>
中共享实例化。
你也许没有意识到这一点,但 C# 生成保证 struct
有 sequential
布局的 IL:
.class private sequential ansi sealed beforefieldinit S
extends [mscorlib]System.ValueType
{
...
}
因此,我们不能让 List<S>
和 List<T>
与某些例如的 List<U>
共享实例化:
struct U {
int G;
object H;
object I;
}
因为这个,除了其他原因之外 —— 像给编译器在填充、缓存对齐等等方面更多的灵活性 —— 我们在我们的语言中将 struct
默认设为 auto
。事实上,sequential
只在如果你在用 unsafe
代码时才有关系,而在我们的编程模型中,这是不允许的。
在 Midori 中我们不支持反射。原则上,我们有最终完成它的计划,作为一个纯可选的特性。在实践中,我们从来就不需要它。我们发现代码生成从来都是更为适合的方案。通过这样我们最好情况下比 C# 的镜像大小剔掉至少 30%。如果你在系统中跟大多数情况一样保留所有的 MSIL,还会显著更多,即使是在 NGen 和 .NET AOT 方案中。
实际上,我们还删掉了 System.Type
中的一大块。没有 Assembly
,没有 BaseType
,而且甚至没有 FullName
。.NET Framework 的 mscorlib.dll
包含了约 100KB 的净的类型名称。当然,名称是有用,但我们的事件框架利用代码生成来生成在运行时实际需要的那些东西。
在某个时刻,我们意识到我们镜像大小的 40% 是 vtable。我们不停地努力琢磨这个,在这之后,我们仍然有很多改进的余地。
每个 vtable
都使用镜像的空间来保存在调用时使用的虚函数的指针,当然还有运行时的表示。每个拥有 vtable
的对象同时还有一个嵌入它的 vtable
指针。所以,如果你对大小(镜像的和运行时的)很在意,你得注意 vtable
。
在 C++ 中,你只会在你的类型是多态时才会有 vtable
。在 C# 和 Java 这样的语言中,即使你不想、不需要或者不去使用它,也还是会有一个 vtable
。在 C# 中,至少你可以用一个 struct
类型来去掉它们。我真的很喜欢 Go 的这方面,其中你通过接口来得到类似虚拟调用的东西,而不需要每个类型都有 vtable
的花销;你只需要为你使用的东西付出,在将某个东西硬变成 interface
的时候。
C# 中另一个 vtable
问题是所有的对象都从 System.Object
中继承了三个虚拟方法:Equals
、GetHashCode
和 ToString
。除了这点,这些方法通常不会用正确的方法干正确的事情 —— Equals
需要反射来用到值类型上,GetHashCode
是不确定的并且标记对象头(或者同步块;迟点会谈更多),而 ToString
没有提供格式化和本地化控制 —— 它们也给每个 vtable
膨胀了三个槽。这可能听起来好像不是太多,但它肯定比没有这种开销的 C++ 多。
我们还剩下的主要苦恼来源是 C# 中的假定,坦率地说大多数 OOP 语言如 C++ 和 Java,RTTI 对向下转换总是可用的。因为上面的那些原因,这在泛型中就特别痛苦。虽然我们积极地共享实例化,但我们不可能完全折叠这些家伙的类型结构,即使不同的实例化往往是相同的,或者至少是非常相似的。如果我可以从头全部再来一次,我会干掉 RTTI
。在 90% 情况下,可区分类型联合(type discriminated union)或模式匹配(pattern matching)是更合适的解决方案。
剖析引导优化(Profile guided optimizations (PGO))
我已经提到过剖析引导优化(PGO)。这是在几乎所有其他这篇文章中的东西都完全做了之后的最后一公里的关键因素。这让我们的浏览器程序在像 SunSpider 和 Octane 之类的基准测试中获得了将近 30-40% 的提升。
大多数使用 PGO 的方式跟经典的本机 profiler 一样,不过有两个大的不同。
首先,我们教会了 PGO 关于本文中列出的许多独特的优化,譬如异步栈探查、泛型实例化、lambda、以及更多。跟其他很多事情一样,这里我们可以永远干下去。
其次,除了普通的检查分析(instrumented profiling)外,我们试验了采样分析(sample profiling)。从开发人员的角度来看,这就好得多 —— 它们不需要两次 build —— 而且也让你从真实的、活生生在数据中心跑着的系统上收集数据。一个关于能达到什么样的可能性的好例子来自这篇 Google-Wide Profiling(GWP) 论文。
系统架构
上面描述的基础都很重要。但一些更具影响力的领域需要更深层次的跟语言、runtime、framework 以及操作系统自身的架构的协同设计和协同进化。我曾经写过这种“整个系统”方法的巨大好处。这是一种魔法般的不可思议。
GC
Midori 是完全 GC 的。这是我们整个模型的安全以及生产力的关键因素。实际上,在某个时候,我们有 11 种不同的收集器,每个有它独特的特点。(例如,看这个研究)。我们有了一些方法来克服常见的问题,如长时间的停顿。我会在将来的文章种详细讨论这个。现在,让我们先坚持代码质量的领域。
一个 top-level 的决定是:是要保守,还是要精确?一个保守的收集器更容易切入现有的系统,但它会在某些方面造成麻烦。它经常需要扫描更多的堆来完成同样的工作。而且它会错误地保持对象存活。我们觉得这两点对于系统编程环境是都不能接受的。这是一个简单快速的决定:我们追求精确。
然而,精确会让你在代码生成器中付出一些代价。一个精确的收集器需要得到指示去哪里找到它的根集。这根集包括堆中数据结构的字段偏移量,还有栈上的位置,或者还有某些情况下的寄存器。它需要找到这些以便它不会错过一个对象,错误地回收它或者在重新定位期间无法调整指针,这两种情况都会导致内存安全问题。除了 runtime 和代码生成器之间的紧密,没有什么神奇的技巧可以使这变得高效。
这引出了协作(cooperative) 对比抢占(preemptive) 的主题,以及 GC 安全点的概念。在协作模式下的 GC 操作只会在当线程到达被称为“安全点”的时候才进行收集。而另一方面,在抢占模式下的 GC 操作可以随意通过抢占和线程挂起将线程停止在它们的轨道中,以便它可以强制回收。一般来说,抢占式需要更多的簿记,因为必需在更多的地方识别根,包括那些溢出到寄存器中的东西。它也使某些你可能在操作系统内核中找到的底层次代码难以编写,因为对象会在任意指令之间移动。这很难解释。(如果你不信我,看这个文件,以及它在 CLR 代码库中的相关用法。)因此,我们使用协作模式作为我们的默认选项。我们试验了由编译器插入的自动安全点探针,例如在循环的后端,但一定程度上劣化了代码质量。这的确意味着 GC “活锁”是可能的,但实际情况中我们很少碰到这个。
我们使用一个分代收集器。这有减少暂停时间的优点,因为在特定的回收中需要检查的堆更少。从代码生成器的角度来看它的确有个缺点,即需要在代码中插入写屏障(write barrier)。如果一个较老代的对象指向回一个较年轻代的对象,然后收集器 —— 通常会选择将它的范围限制在较年轻代 —— 必须知道也去查看更老的代。否则它会漏掉一些东西。
写屏障作为在特定的写操作后的额外指令出现;例如,看看这个调用:
48 8D 49 08 lea rcx,[rcx+8]
E8 7A E5 FF FF call 0000064488002028
这屏障只简单得更新卡表(card table)中的一个条目,以让 GC 知道在它下次扫描堆时去查看该段。大多数情况下,这最后成为内联的汇编代码,不过这依赖于情况的细节。看这段代码作为它对于 CLR on x64 会是怎么样的例子。
编译器很难优化这些,因为写屏障本质上是“时序(temporal)”的。虽然,我们的确对栈分配的对象做了积极的消除。而且编写或者转换代码到少些需要屏障的风格是有可能的。例如,考虑写这同一个 API 的两种方式:
bool Test(out object o);
object Test(out bool b);
在生成的 Test
方法体中,你会发现前者有一个写屏障,但在后者中没有。为什么?因为前者正在写一个堆对象引用(object
类型的),而编译器在单独分析这个方法时并不知道,它是不是会写入另一个堆对象。它必须在分析中保守,假设最坏的情况。当然,后者没有这样的问题,因为 bool
不是 GC 需要扫描的东西。
另一个 GC 会影响代码质量的方面是在使用并发收集时,可选的更重量级的并发读写屏障。并发的 GC 在用户程序行进时并发地执行一些回收活动。这通常是多核处理器的很好的使用方式,它可以减少暂停时间并帮助用户代码在给定的时段中跑得更多。
构建并发 GC 有许多挑战,但其中一个是所产生的屏障的成本很高。最初的由 Henry Baker 带来的并发 GC 是一种复制式 GC,有“旧”与“新”空间的概念。所有的读和写都要被检查,并且任何对旧空间的操作必须转发到新空间。随后对于 DEC Firefly 的研究使用硬件内存保护来减少这开销,但断层情况仍然相当昂贵。最糟糕的是,对堆的访问时间是不可预知的。已经有了很多解决这个问题的好的研究,不过我们放弃了复制式。
相反,我们使用了一个并发标记清除压缩收集器。这意味着在正常的程序执行中只需要写屏障,但一些代码被克隆以当程序跑进对象移动情形时就会出现读屏障。我们的主要 GC 家伙的研究已经发表了,你可以阅读全部关于它的内容。CLR 也有一个并发收集器,但它没有那么好。它使用复制来收集最年轻的代,标记清除来收集老点的代,标记阶段是并行的。不幸的是,有几个条件会导致连续的停顿(像一个大的“锁”),有时候会超过 10 毫秒:1) 所有的线程必须停止和扫描,一个操作的界限只跟线程的数量和它们栈的尺寸相关;2) 复制最年轻的代的界限只跟那代的尺寸有关(谢天谢地,大多数情况下它很小);以及 3) 在最坏的情况条件下,甚至最老的代的压缩和碎片整理,可能同时发生。
单独编译
作为开始的基本模型是静态链接。在这模型中,你将所有的内容编译为单个可执行文件。这样做的好处是显而易见的:它简单,易于理解,服务的概念直接,而且整个编译工具链的工作更少。老实说,鉴于到以 Docker 容器作为服务单元的转移,这种模型现在越来越有意义了。但对于整个操作系统,在某种程度上,你需要单独编译。不只是因为当静态链接一整个操作系统会导致编译时间相当长,还因为生成的进程的工作集和占用空间会有大量重复。
单独编译面向对象的 API 很困难。实话说,很少有人真的让它做成了。问题包括脆弱基类问题,这对于弹性版本库是真正的杀手。因此,大多数现实的系统在组件的边界之间使用一个简化的“C ABI”。作为例子,这是为什么 Windows,历史上使用扁平的 C Win32 API,而且即使通过 WinRT 变得更加面向对象,还是所有东西的下面使用 COM 。付出一些运行时的开销后,ObjectiveC runtime 解决了这个挑战。就像大多数计算机科学里的东西一样,几乎所有的问题都可以用多的间接的一层来解决;这个问题也可以。
我们在 Midori 中使用的设计支点是所有的进程都是 sealed
的。没有动态加载,所以没有看起来像经典的 dll 和 SO 的东西。对于那些场景,我们使用异步一切的编程模型,使得动态连接到以及使用分开编译和版本化的进程很容易。
然而我们的确想要单独编译二进制文件,纯粹作为开发人员生产力和代码共享(工作集)起作用。呃,我撒谎了。我们最终得到的是增量编译的二进制文件,其中根节点的改动会触发级联依赖它的项的重编译。但对于叶子节点,譬如应用程序,生活就很美好。随着时间推移,我们的工具链变得更聪明了,它准确理解了哪些类型的变化会触发镜像的级联失效。例如,一个被得知永远没有在模块中被内联的函数,可以让它的实现 —— 但不是它的签名 —— 改变,而不会需要触发 rebuild。这类似于传统的 C/C++ 编译模型中的头和对象的区别。
我们的编译模型跟 C++ 的非常类似,有静态和动态链接。当然,运行时模型就相当不同。我们还有“库群”的概念,它让我们将多个逻辑上单独但相关的库组合成一个单一的物理上的二进制文件。这让我们能做更积极的模块优化,像内联、去虚拟化、异步栈优化以及更多。
参数多态(又称:泛型)
这把我带到了泛型。它们将一个扳手扔到了所有东西里。
问题在于,除非你实现一个擦除模型 —— 这由于装箱分配、间接性、或这两者会有,在性能表现上很糟 —— 你没有办法有可能在 AOT 时实现实例化所有可能的版本。譬如,假设你提供了一个 List<T>
,你怎么知道使用你的库的人需要的是 List<int>
、List<string>
还是 List<SomeStructYouveNeverHeardOf>
?
解决方案是丰富多彩的:
- 不特化。擦除所有类型。
- 只特化实例化的一个子集,对于其余的创建擦除实例化。
- 特化所有的东西。这有最佳的性能,但有些复杂。
Java 使用了 #1 方案(实际上,擦除被烤进了语言中)。很多 ML 编译器使用了 #2 号方案。.NET 的 NGen 编译模型是 #2 变体的一种,其中可以进行琐碎特化的东西是特化的,而其他的东西是 JIT 编译的。.NET Native 尚未对这个问题给出一个解决方案,这意味着第三方库、单独编译以及泛型是一个巨大的待定。跟 Midori 中的所有东西一样,我们选择了最艰难的道路,也是最有利的,这就是 #3。实际上我有点油滑了;我们团队中有几个 ML 编译器的传奇,而 #2 是充满危险的;只需要埋头看看一些这个会多难(和多巧妙)几篇论文。先验很难知道哪个实例化会是一个程序的性能关键。我自己的在 Longhorn 时候试图让 C# 跑进 Windows 心脏的经验也加强了这一点;我们不希望在 JIT 进行时,在那个世界关于什么泛型你能用什么不能的规则让人头大,它们最终会导致天书一般的东西。
不管怎么说,Midori 的方法比一开始听起来更难。
假设你有一个菱形。库 A
导出一个 List<T>
类型,而库 B
和 C
都实例化了 List<int>
。程序 D
同时使用 B
和 C
而且可能将返回的 List<T>
对象在它们两个中传递。这样我们应该如何确保 List<int>
的版本是兼容的?
我们称这个问题为潜在的多样实例化(potentially multiply instantiated)问题,简称 PMI
。
CLR 通过在运行时统一实例化来解决这个问题。所有的 RTTI
数据结构、vtable
诸如此类的东西,都是在运行时构建和/或积极补丁的。在 Midori,走了另一条路,我们希望所有这些数据结构位于只读的代码段中,从而在有可能的时候能够跨进程共享。
再一次,所有东西都可以通过一个间接来解决。但不想上面的 #2 号方案,#3 允许你只在你需要它们的很少地方采用间接性。对于这个,这意味着只是那些可能已经隶属于 PMI
的泛型类型的 RTTI
和静态变量访问。首先,这作用于代码的巨大的子集(对比 #2 的通常作用于实例字段的加载)。其次,通过将状态和操作附加到已有的作为隐藏参数传递的泛型字典,可以对已知的不具有 PMI
的实例化进行优化。最后,因为上述的这些,它是按需付出(pay for play)的。
但真他妈的复杂!
这很有趣,但对于模板实例化的 C++ RTTI
实际上也存在许多相同的问题。事实上,微软的 Visual C++ 编译器诉诸类型名称的 strcmp
来解决菱形问题!(幸好有众所周知的,更有效的方法来做到这一点,我们正积极为 VC++ 的下一版本而努力。)
虚拟调用(Virtual dispatch)
虽然在第一次从 Java 切换到 C# 时我有不同的感觉,Midori 让我喜欢 C# 默认让方法是非虚(non-virtual
)的,否则,我们就不得不将它改成那样了。实际上,我们甚至更进一步,使类默认是 sealed
的,如果你想要进行子类化,你得显式将它们标记为 virtual
。
积极的去虚拟化是优秀性能的关键。每一个虚拟都意味着一次间接。而且影响更大的是,失去了内联的机会(对于小函数是非常必要的)。我们当然对去虚拟化进行了全局的模块内分析,不过也将这个扩展到跨模块中,通过当多个库被组合进同一个库群时使用整个程序编译。
虽然我们的默认设定是对的,但 C# 开发人员的经验是他们对虚拟和过度抽象代码有些狂热。我觉得围绕高度多态抽象爆炸式的 API 生态系统,像 LINQ 和 Reactive Extension,鼓励了这种做法并且灌输了一些不良行为(“没来由的过度抽象”)。我猜你可以对 C++ 中的高度模板化的代码做类似的论证。正如你所猜想的那样,在我们代码库的最底层没有太多的 virtual
—— 那里每一个分配和指令都很要紧 —— 但在高层次代码中,特别是在那些倾向于由高异步操作控制的应用程序中,虚拟调用的开销是可以接受的,而且这样生产力很高。一个通过代码审查、性能测试以及积极的静态分析检查的围绕识别和铲除过胖代码的强有力的文化,能够保证这样的特性得到适当的使用。
接口是一个挑战。
.NET Framework 总是有一些设计糟糕效率低下的模式。IEnumerator<T>
需要两个接口调用只是为了提取下一项!将它跟 C++ 的迭代器比较一下,后者可以编译为一个指针增量加上解引用。很多这样的问题可以通过简单地使用更好的类库设计来解决。(我们对枚举的最终设计甚至一点都不需要调用接口。)
另外,调用 C# 的接口也很棘手。已有的系统不像 C++ 那样使用指针调整,所以通常一次接口调用需要一次表搜索。首先有使用 vtable
的一层间接性,然后再一层是找到去要的接口的接口表。一些系统试图对单态调用做调用点缓存;也就是缓存最后一次调用,希望同一类的对象一次又一次地经过调用点。然而,这需要可变的桩模块(stub),更别提这是相当复杂的型式转换注意此类的系统。在 Midori 中,我们从来没有违反过 W^X(写抑或执行);而且我们避免可变的运行时数据结构,因为它们抑制共享 —— 不论在时期还是工作集,而且还摊薄了 TLB
和数据缓存压力。
我们的解决方案利用了先前的内存顺序模型。我们使用所谓的“胖”接口指针。一个胖接口指针有两个字(word
):第一个指向对象本身;第二个是一个对那个对象的接口 vtable
的指针。这使得转换为接口稍微慢一点 —— 因为接口 vtable
查找必须发生 —— 但对于你调用它一次或多次的情况,它就变快了,通常很显著。Go 也干了类似这样的一些事情,但有两方面的不同:一方面在于它们生成接口表飞快,因为它的接口是鸭子类型(duck typed)的,第二方面是胖接口指针会受到撕裂,所以在 Go 中可能会违反内存安全,跟 Midori 不同,由于我们的强悍的并发模型。
此目录中的最后一个挑战是泛型虚方法,简称 GVM
。开门见山吧,我们禁止了它们。即使你在 .NET 中 NGen 一个镜像,所有它需要的只是调用一个 LINQ 查询 .Where(...
) .Select(...)
,而你就被拉进 JIT 编译器中。即使是在 .NET Native 中,碰到这种情况也会惰性创建大量的运行时数据结构。简而言之,没有已知的可以 AOT 编译 GVM 们以让它们可以在运行时高效的方法。所以,我们甚至懒得提供它们。这是编程模型中一个稍微令人不爽的限制,但由于这带给我们的效率,若再来的话我会再一次这样做。真正令人震惊的是有多少 GVM
潜伏在 .NET 中。
静态(Statics)
当我知道我们代码大小的 10% 用于静态初始化检查时,我惊呆了。
很多人可能没意识到 CLI 规范提供了两种静态初始化模式。默认模式和 beforefieldinit
。默认模式跟 Java 的一样,而且很可怕。静态初始化程序必须只在访问类型的任何静态字段、类型的任何静态方法、类型的任何实例或者虚拟方法(如果是值类型)、或者任何构造函数之前运行。“何时”部分没有它要做的“什么”那么重要;现在所有这些地方在生成的机器代码中都需要使用显式的惰性初始化检查来保证!
beforefieldinit
稍微宽松点。它保证初始程序将在实际访问类型的静态字段之前的某个时刻运行。这给编译器在决定这个位置时有较大的回旋余地。幸运的是 C# 编译器将自动为你选择 beforefieldinit
,你应该坚持只用字段初始化。然而,大多数人没有意识到选择取代之以静态构造函数的难以置信的代价,特别是对于值类型,其中突然所有的方法调用都会引致初始化防御。代码上只是有一点区别:
struct S {
static int Field = 42;
}
及
struct S {
static int Field;
static S() {
Field = 42;
}
}
现在,假如这个 struct
有一个属性:
struct S {
// As above...
int InstanceField;
public int Property { get { return InstanceField; } }
}
下面是如果 S
没有静态构造方法或者使用 beforefieldinit
(在上面的字段初始化示例代码中会被 C# 自动使用)时的 Property
的机器代码:
; The struct is one word; move its value into EAX, and return it:
8B C2 mov eax,edx
C3 ret
而下面是如果你加了一个类构造方法会发生的:
; Big enough to get a frame:
56 push rsi
48 83 EC 20 sub rsp,20h
; Load the field into ESI:
8B F2 mov esi,edx
; Load up the cctor's initialization state:
48 8D 0D 02 D6 FF FF lea rcx,[1560h]
48 8B 09 mov rcx,qword ptr [rcx]
BA 03 00 00 00 mov edx,3
; Invoke the conditional initialization helper:
E8 DD E0 FF FF call 2048
; Move the field from ESI into EAX, and return it:
8B C6 mov eax,esi
48 83 C4 20 add rsp,20h
5E pop rsi
在每一个属性访问时!
当然,所有的静态成员仍然引致这样的检查,即使是采用 beforefieldinit
。
虽然 C++ 没有遭受同样的问题,它的确有令人头疼的初始化顺序语义。而且,像 C# 的 static
一样,C++11 引入了线程安全的初始化,通过“magic statics”特性。
在 Midori 中我们几乎清掉了这个烂摊子。
我之前提到过 Midori 没有可变的静态值。更准确地说,我们扩展了 const
的概念来覆盖任何种类的对象。这意味着静态值是在编译时评估的,写进生成二进制镜像的只读段,并且在所有的进程间共享。对代码质量更重要的是,所有的运行时初始化检查被去掉了,而且所有的静态访问只是简单地被替换成一个恒定的地址。
在系统的核心仍然有可变的静态值 —— 譬如,在内核中 —— 但这些并没有变成用户代码。并且因为它们很稀少,我们没有依赖于经典 C# 的惰性初始化检查。它们是在系统启动时手动初始化的。
正如我前面所说的,代码大小减少了 10%,而且速度提升了很多。很难确切知道这比标准的 C# 程序节省了多少,因为当我们做出改变时,开发人员很清楚这些问题,并在所有他们的类型上愉快地应用上我们的 [BeforeFieldInit]
特性,以避免一些这样的开销。所以 10% 这个数字是我们在整个旅程中实现的节省的下限。
异步模型
关于我们的异步模型我已经写了很多。我不会在这里重述所有这些。我将重申一点:编译器是让链接栈起效的关键。
在链接栈模型中,编译器需要在代码中插入检查可用栈空间的探针。如果没有足够的的空间去执行某些操作 —— 执行一个函数调用、在栈上动态分配等 —— 编译器需要安排一个新的链接来加进来,并切换到它。大多数情况下这意味着一些范围检查、对运行时函数的条件调用、以及对 RSP
进行修补。一个探针的样子如下:
; 检查栈空间的大小:
lea rax, [rsp-250h]
cmp rax, qword ptr gs:[0]
ja prolog
; 如果栈空间不足,链接到新段:
mov eax, 10029h
call ?g_LinkNewStackTrampoline
prolog:
; The real code goes here...
不消说,你希望探针尽可能的小。两个原因:第一,它们导致了运行时成本。第二,它们消耗代码大小。我们使用了一些技术来消除探针。
编译器当然知道如何计算函数对栈的使用。因此,它对于探针要检查的内存大小是智能的。我们将这知识融入到我们的全局分析器中。我们可以在做了代码移动和内联之后合并检查。我们提升检查到循环外部。在大多数情况下,我们针对消除检查作优化,有时候宁愿使用更多一点栈的代价。
我们消除探针的最有效的一个技术是在经典的栈上运行同步代码,并教我们的编译器对它们一起消除探针。这得益于我们对类型系统中的异步的理解。一次又一次地切换到经典栈再切换回来相当于玩弄 RSP:
; Switch to the classical stack:
move rsp, qword ptr gs:[10h]
sub rsp, 20h
; Do some work (like interop w/ native C/C++ code)...
; Now switch back:
lea rsp, [rbp-50h]
我知道 Go 由于这些切换放弃了链接栈。起先它们对我们来说相当糟,然而经过一个或两个人年的努力之后,切换时间消失到淹没于少于 0.5% 的噪音。
内存顺序模型
Midori 在安全并发上的平台真的有一个令人惊叹的好处:你可以毫无代价地获得一个顺序一致的内存顺序模型。你可能想再读一遍。毫无代价!
为什么能这样?首先,Midori 的进程模型确保默认是单线程运行的。其次,进程内部的任何细粒度的并行被一定数量的 API 组织起来的,它们全都是无竞争的。竞争的缺少因为这我们可以选择性地在 fork
和 join
点上插入栅栏(fence),无需开发人员需要关心或者知道。
显然,这对开发人员的生产力有着难以置信的好处。Midori 程序员从不会被内存重排序问题恶心过的这个事实,当然是我对这个项目最自豪的成果之一。
但这也意味着编译器可以自由地进行更加积极的代码移动优化,而无需牺牲这种高生产力的编程模型。换句话说,我们得到了两个世界中最好的部分。
少部分内核开发人员必须考虑底层机器的内存顺序模型,他们是实现异步模型本身的人。为此,我们去掉了 C# 中的 volatile
的概念 —— 无论如何它都被完全破坏了 —— 更倾向于类似 C++ 的 atomics 的东西。这个模型相当棒,有两个原因:首先,对于每个读和写,你需要的栅栏类型是显式的,这是真正重要的。(栅栏影响变量的使用,而不是声明)。其次,显式模型告知编译器关于什么优化能采用或不能的更多的信息,再加上特定的使用,这是最重要的。
错误模型
我们的错误模型旅程是一个相当漫长的旅程,会是将来一篇文章的主题。总之,我们用光谱的两端来做了试验 —— 异常和返回码 —— 以及中间的许多点。
以下是我们从代码质量角度找到的内容。
返回码很不错,因为类型系统告诉你可能会发生一个错误。开发人员因此不得不处理这个问题(前提是他们不忽略返回值)。返回码也简单,需要的“运行时魔法”比异常或相关的如 setjmp
/longjmp
的机制要少得多。所以,很多人喜欢它。
然而,从代码质量的角度来看,返回码就很差劲了。它们强迫你在热路径执行不需要执行的情形下的指令,包括当错误不会发生的情况下。你需要从你的函数中返回一个值 —— 占用了寄存器和/或栈空间 —— 而且调用者需要提供分支来检查结果。当然,我们喜欢这些是正确预测的,但现实是,你只是做了更多的活。
非类型化的异常也糟透了,当你试图建立一个可靠的系统时。操作系统需要的是可靠。当你调用一个函数是而不知道有隐藏的控制流路径时,那简直就是无法接受。它们也需要较重量级的运行时支持来展开栈,搜寻处理器等等。在编译器中对异常控制流建模也是一个真正的难题。(若你不相信我,只需通读一下这个邮件交换内容)。所以,很多人讨厌这个。
类型化的异常 —— 我习惯不说 checked
异常,怕刺痛 Java 的神经 —— 解决了这里面的一些短处,但也有它们自己的挑战。再说一次,我会在将来的文章中透露更细节的分析。
从代码质量的角度来看,异常会更好。首先,你可以组织你的代码段,使“冷”的处理器不会污染你在成功路径的 ICACHE。其次,你无需在正常的调用约定中做任何额外的工作。没有值的包装 —— 所以没有额外的寄存器和栈的压力 —— 也没有在调用者的分支。然而,异常也有一些缺点。在一个非类型化的模型中,你必须假定每个函数都可能会抛出异常,这显然会抑制了你移动代码的能力。
我们的模型最后变成了两个东西的混合:
- 对编程 bug 快速失败(Fail-fast)。
- 对可动态恢复的错误,使用类型化异常。
我得说 fail-fast 对类型化异常使用的比例最后为 10:1。异常通常对 IO 和处理用户数据的东西使用,像 shell 和分析器。约定(Contract
)是最大的 fail-fast 来源。
结果是得到了上述的代码质量属性的最佳配置:
- 无调用约定影响。
- 无包装返回值和调用者分支的一团糟的关联。
- 所有会抛出异常的函数在类型系统中都是已知的,允许更为弹性的代码移动。
- 所有会抛出异常的函数在类型系统中都是已知的,给我们带来了新的
EH
优化,像将try
/finally
块转变为直线代码,当try
的东西不会抛出异常时。
我们模型的一个好的意外是我们可以用返回码或异常来编译它。鉴于这,我们的确做了试验,来看对我们的系统的大小和速度有什么影响。基于异常的系统最终在某些关键的指标上大概更小 7% 和更快 4%。
最后,我们最终得到的是我所用过的最健壮的错误模型,当然也是性能最好的一个。
约定(Contract)
如上所述,Midori 的编程语言有头等公民的 contract
:
void Push(T element)
requires element != null
ensures this.Count == old.Count + 1
{
...
}
模型很简单:
- 默认,所有的
contract
是在运行时进行检查的。 - 编译器可以任意证明
contract
不满足,并抛出编译时错误。 - 编译器可以任意证明
contract
满足,并溢出这些运行时检查。
我们有条件编译模型,然而我现在会跳过它。后面我一个关于我们语言的文章会说这个。
在早期,我们用如 MSR 的 Clousot 的 contract
分析器做了尝试,以证明 contract
。然而,由于编译时的原因,我们不得不放弃了这个方法。事实证明,编译器已经非常擅长于处理简单的 contract
求解和传播。所以最终我们只是将约定建模成编译器知道的事实,并让它当需要的时候插入检查。
例如,使用上述范围信息完成的循环优化器已经可以利用像这样的检查:
void M(int[] array, int index) {
if (index >= 0 && index < array.Length) {
int v = array[index];
...
}
}
来消除在保护性的 if
语句后的冗余边界检查。所以为什么不在这里也这样做呢?
void M(int[] array, int index)
requires index >= 0 && index < array.Length {
int v = array[index];
...
}
然而,当设计到单独编译时,这些事实是特别的。一个约定是一个方法签名的一部分,我们的系统确保适当的子类型替代,让编译器在单独编译的边界上进行更为激进的优化。而且它可以更快地进行这些优化,因为它们不依赖于全局分析。
对象和分配
在未来的帖子中,我将详细描述我们与垃圾收集器的战争。然而,帮助我们胜利的一个技术是,积极减少一个行为良好的程序在堆上分配的对象的尺寸和数量。这有助于整个工作集,从而让程序更小更快。
头一个技术是压缩对象尺寸。
在 C# 和大部分 Java VM 中,对象有对象头。标准的尺寸是一个单字,也就是,在 32 位的架构上是 4 字节,在 64 位是 8 字节。这是除了 vtable
指针之外的。它通常用于 GC 来标记对象,而且在 .NET 中用于随机的玩意,如 COM 互操作、锁定、记住哈希值等等。(甚至源代码称它为“厨房水槽”。)
我们抛弃了这两个。
我们没有 COM 互操作。没有不安全的自由线程所以也没有锁(而且对随机对象上锁无论如何都是坏主意)。我们的 Object
没有定义 GetHashCode
等等。这为每个对象节省了一个字,而且在编程模型中没有明显的损失(事实上,相反,它被改进了),没有什么好犹豫的。
此时,每个对象的唯一多余开销是 vtable
指针。对于 struct
,当然没有这个(除非它被装箱)。我们尽了最大努力去消除它们。悲伤的是由于 RTTI
,很难做得很激进。我想这是我很想回去完全颠覆 C# 类型系统的这个方面,去遵循一个更加 C/C++,甚至更加像 Go 的模型。不过在最后,我认为我们已经跟平均的 C++ 程序相比获得了相当的竞争力。
也有填充的挑战。将 struct
的布局从 C# 现在默认的 sequential
换成我们首选的 auto
布局当然是有帮助的。跟众所周知的 C++ 的空基优化一样的优化方式。
为了更有效地分配对象,我们还做了积极的逃逸分析。如果一个对象被发现是限定在栈上的,它会被分配在栈上,而不是堆中。我们的最初对这个的实现将大概 10% 的静态分配从堆的某处移动到了栈上,这也让我们更积极地修剪对象的大小,消除 vtable
指针和整个未使用的字段。鉴于这种分析的保守性,我对这些结果非常满意。
如果开发人员想给编译器一个提示同时在语义上强制某种级别的限制时,我们提供了一种处于 C++ 引用和 Rust 的借用(borrowing
)之间的机制。例如,假设我想分配一个小数组来与被调用方共享,但要确保被调用方不会记住它的引用。这个可以简单地这样写:
void Caller() {
Callee(new[] { 0, 1, ..., 9 });
}
void Callee(int[]& a) {
... 保证 `a` 不会逃逸 ...
}
编译器使用 int[]&
信息来在栈上分配这个数组,而且经常整个地消除了它的 vtable
指针。加上对边界检查的复杂的消除,这给了我们非常接近 C 性能的东西。
Lambda/delegate 在我们的系统中也是 struct
,所以不需要在堆上分配。捕获的显示帧(display frame)接受上述的所有这些的支配,所以经常我们可以在栈上分配它们。因此,下面的代码是完全无堆上分配的;实际上,由于一些早期优化,如果被调用者被内联了,它会像实际的 lambda 体被展开为一个指令序列那样运行,也不会有调用的开销!
void Caller() {
Callee(() => ... do something ... );
}
void Callee(Action& callback) {
callback();
}
在我看来,这确实是借用(borrowing
)系统的杀手锏。开发人员在我们有这个特性之前的早期避免使用基于 lambda 的 API,因为害怕堆对象分配和低效率。在完成这特性之后,另一方面,一个充满活力的富有表现力的基于 lambda API 的生态系统蓬勃发展。
吞吐量(Throughput)
上面的那些全都是关于代码质量的,也就是生成的代码的大小和性能。另一个编译器性能的重要维度是吞吐量,也就是你能多快编译代码。在这点上,一个类似 C# 的语言也伴随着一些自己的挑战。
我们遇到的最大的挑战更少跟语言本身的安全特性有关,而是更多跟一个非常有力量的特性有关:参数多态。或者实在点说,泛型。
我之前已经提及,泛型只不过是一种方便的复制粘贴机制。而且我也提到了一些在代码大小方面的一些挑战。然而,它也给吞吐量带来了问题。如果一个 List<T>
实例化创建了 28 个类型,每个有它自己的少数方法,那就由更多的代码让编译器去处理。单独编译由帮助,然而之前也提及,泛型经常在模块边界流动。因此,很有可能会对编译时间有不可忽视的影响。实际上,就是有。
事实上,这与大多数 C++ 编译器花费大部分时间的地方并没有太多不同。在 C++ 中,它是模板。更多现代 C++ 代码库有类似的问题,因为它们重度使用模板抽象,如 STL、智能指针这样的东西。很多仍然只是“有类的 C”的 C++ 代码块就遭受这样的问题少一些。
正如我之前提到的那样,我希望我们已经抛弃掉 RTTI
。这将减少泛型造成的问题。但我猜,即使在考虑了所有情况之后,泛型仍然是我们最大的吞吐量挑战。
有意思的事情 —— 通过一种不那么有意思的方式 —— 是你可以试着去分析来修剪泛型的集,虽然这很有效,不过分析需要时间,而这正是你想要节省的东西。
我们习惯追踪的一个度量是,AOT 编译一个程序会比简单的 C# 编译它慢多少。这是一个完全不公平的比较,因为 C# 编译器只需要将它降低到 MSIL,而 AOT 编译器需要生成机器代码。将 AOT 编译跟 JIT 编译比较会显得更为公平点。不过无论如何,对 C# 用户来说,在吞吐量方面干得好尤为重要。他们对生产力的期望非常高。所以这是我们认为用户会对我们进行评判的关键指标,所以我们紧紧聚焦于这一点。
在开始的那段日子,数字差得荒谬。我记得它是慢了 40 多倍。经过一年半的关注努力之后,我们将它降低到 debug build 的 3 倍,optimized build 的 5 倍。我对这个非常高兴!
实现这个目标没有任何秘密。大多数时候必须要做的只是要让编译器变得更快,像你会对其他程序做的那样。然而,由于我们使用 Midori 的工具链来构建编译器 —— 并用它来编译自己 —— 通常这样做首先可以让 Midori 变得更好,而且可以让编译器变得更快。这是一个很好的良性循环。我们在字符串分配方面遇到了真正的问题,这告知我们在我们的编程模型中如何处理字符串。我们发现了失控的泛型实例化闭包,这迫使我们去消除它们,并构建工具来帮助主动找到它们。等等。
文化
总结之前让我多说几句。文化是我们所做的最重要的方面。没有这个文化,这样一个惊艳的团队不会有自我,也不会无尽地追求上述所有的这些成就。我会贡献一整篇文章来说说这个。然而,在这个编译器的上下文,两件事情起了帮助:
- 我们在实验室里度量每样东西。“如果它没有在实验室中,它对我们来说就是死的。”
- 我们尽早而且经常地 review 进度。即使在还没有取得进度的地方。我们习惯性地自我批评。
对于每一个 sprint,我们有一个称之为“CQ Review”的东西(CQ 代表“代码质量(code quality)”)。编译器团队准备有几天,review 每个基准测试 —— 从最底层的微基准到编译和启动 Windows 的所有东西 —— 并探讨所有的更改。所有预期的进步都被确认(我们称这个为“确认你的人头”),所有的退步都会被从根源上进行原因分析(和改 bug),还有所有突然出现的进步也会被分析和报告,以便我们可以从中学习。我们甚至盯着那些没有改变的数字,问自己,为什么它们没有改变。这是预期中的吗?我们是否感觉到不对劲?如果是这样,我们应该在下一个 sprint 做出什么改变?我们也 review 我们竞争对手最新的编译器,并监控了它们的改变速度。等等。
这个过程及其健康。每个人都被鼓励去自我批评。这不是“政治迫害”;这是一个作为团队去学习如何更好地达成我们目标的机会。
在 Midori 之后,我也一直保持这种过程。我很惊讶这对一些家伙造成了很多困扰。他们感到了威胁,并担心他们的缺乏进展让他们看起来很糟。他们用“数字没有改变是因为那还不是我们现在关注”作为摆脱节奏的接口。在我的经验中,只要代码在变化,数字就会变化。最好一直盯着它们,以免几个月之后它突然变得很重要时你被从马桶上被揪起来。纪律和持续的节奏是这些 review 最重要的部分,所以跳过哪怕只是其中一个可能都是有害的,因而是被禁止的。
这个过程跟其他东西一样都是我们的秘密武器。
总结
哇!这覆盖了很大的一片东西。我希望至少至少这也是有意思的,而且我希望有个难以置信的团队能够将这些构建出来,这样我多少也带来了些正义。(我知道我没有做到。)
这个旅程花了我们十几年,特别是如果你知道 Bartok 和 Phoenix 这两个甚至在 Midori 形成之前都已经存在了好多年这个事实。仅仅是 AOT 编译 C#,并且做好它,就能够帮我们从中获得许多好处。但要真正实现类似本机语言的性能,而且在某些领域超越它,就需要一些关键的“整系统”的架构赌注。我希望有朝一日我们可以在这个性能水平上为整个世界提供安全。鉴于业界安全状态的总体表现,人类极端需要它。
我已经足够触及我们的编程语言了,我需要更进一步深入它。下次见!