2018年4月30日
第16卷，第2期

C 不是一种低级语言

你的计算机不是一台快速的 PDP-11。

David Chisnall

在最近的 Meltdown 和 Spectre 漏洞之后，值得花一些时间来研究根本原因。这两个漏洞都涉及到处理器推测性地执行超出某种访问检查的指令，并允许攻击者通过侧信道观察结果。导致这些漏洞以及其他几个漏洞的功能被添加进来，是为了让 C 程序员继续相信他们正在使用一种低级语言进行编程，尽管这种情况已经几十年没有发生了。

处理器供应商并非孤军奋战。我们这些从事 C/C++ 编译器工作的人也参与其中。

什么是低级语言？

计算机科学先驱艾伦·佩里斯这样定义低级语言

“当一种编程语言的程序需要关注不相关的事物时，它就是低级的。”⁵

虽然，是的，这个定义适用于 C，但它并没有抓住人们对低级语言的期望。各种属性导致人们将一种语言视为低级语言。将编程语言视为属于一个连续统，一端是汇编语言，另一端是星舰企业号的计算机接口。低级语言“贴近硬件”，而高级语言更接近人类的思维方式。

对于一种“贴近硬件”的语言，它必须提供一个抽象机器，该机器可以轻松映射到目标平台公开的抽象。很容易论证 C 对于 PDP-11 来说是一种低级语言。它们都描述了一个模型，其中程序顺序执行，其中内存是一个平面空间，甚至前缀和后缀递增运算符都与 PDP-11 的寻址模式整齐地对齐。

快速的 PDP-11 模拟器

Spectre 和 Meltdown 漏洞的根本原因是处理器架构师试图构建的不仅仅是快速处理器，而是能够暴露与 PDP-11 相同抽象机器的快速处理器。这至关重要，因为它允许 C 程序员继续相信他们的语言贴近底层硬件。

C 代码提供了一个主要串行的抽象机器（在 C11 之前，如果排除非标准的供应商扩展，则完全是串行的机器）。创建新线程是一个众所周知的昂贵库操作，因此希望保持其执行单元忙于运行 C 代码的处理器依赖于 ILP（指令级并行性）。它们检查相邻的操作并并行发出独立的操作。这增加了大量的复杂性（和功耗），以允许程序员编写主要是顺序的代码。相比之下，GPU 在没有任何这种逻辑的情况下实现了非常高的性能，但代价是需要显式并行程序。

对高 ILP 的追求是 Spectre 和 Meltdown 的直接原因。现代英特尔处理器一次最多可以有 180 条指令在执行中（与顺序 C 抽象机器形成鲜明对比，后者期望每个操作在下一个操作开始之前完成）。 C 代码的典型启发式方法是，平均每七条指令就有一个分支。如果您希望从单个线程保持这样的流水线满负荷运行，那么您必须猜测接下来 25 个分支的目标。这再次增加了复杂性；这也意味着不正确的猜测会导致工作被完成然后被丢弃，这对于功耗来说并不理想。这种丢弃的工作具有可见的副作用，Spectre 和 Meltdown 攻击可以利用这些副作用。

在现代高端核心上，寄存器重命名引擎是芯片面积和功耗最大的消耗者之一。更糟糕的是，当任何指令正在运行时，它都无法关闭或断电，这在晶体管便宜但供电晶体管是昂贵资源的黑暗硅时代显得不方便。 GPU 上明显缺少此单元，GPU 上的并行性再次来自多个线程，而不是试图从本质上是标量代码中提取指令级并行性。如果指令没有需要重新排序的依赖关系，则不需要寄存器重命名。

考虑 C 抽象机器内存模型的另一个核心部分：平面内存。这在二十多年里已经不是真的了。现代处理器通常在寄存器和主内存之间有三级缓存，试图隐藏延迟。

顾名思义，缓存对程序员是隐藏的，因此 C 不可见。有效利用缓存是在现代处理器上快速运行代码的最重要方法之一，但这完全被抽象机器隐藏了，程序员必须依靠了解缓存的实现细节（例如，两个 64 字节对齐的值可能最终在同一个缓存行中）来编写高效的代码。

优化 C

低级语言的常见属性之一是它们速度快。特别是，它们应该很容易转换为快速代码，而无需特别复杂的编译器。当谈论其他语言时，C 倡导者经常驳斥足够聪明的编译器可以使一种语言快速的论点。

不幸的是，提供快速代码的简单转换对于 C 来说并非如此。尽管处理器架构师投入了巨大的努力来设计可以快速运行 C 代码的芯片，但 C 程序员期望的性能水平只有通过极其复杂的编译器转换才能实现。 Clang 编译器，包括 LLVM 的相关部分，大约有 200 万行代码。即使只计算使 C 快速运行所需的分析和转换过程，也几乎达到了 20 万行（不包括注释和空行）。

例如，在 C 中，处理大量数据意味着编写一个顺序处理每个元素的循环。为了在现代 CPU 上以最佳方式运行此代码，编译器必须首先确定循环迭代是独立的。 C restrict 关键字可以在这里提供帮助。它保证通过一个指针的写入不会干扰通过另一个指针的读取（或者如果它们干扰，程序员也乐于接受程序给出意外结果）。此信息远比 Fortran 等语言中的信息有限，这在很大程度上是 C 未能在高性能计算中取代 Fortran 的原因。

一旦编译器确定循环迭代是独立的，那么下一步就是尝试将结果向量化，因为现代处理器在向量代码中获得的吞吐量是标量代码的四到八倍。这种处理器的低级语言将具有任意长度的本机向量类型。 LLVM IR（中间表示）正是如此，因为将大型向量操作拆分为较小的操作总是比构造更大的向量操作更容易。

此时优化器必须与 C 内存布局保证作斗争。 C 保证具有相同前缀的结构可以互换使用，并且它将结构字段的偏移量暴露给语言。这意味着编译器不能自由地重新排列字段或插入填充以改进向量化（例如，将结构数组转换为结构数组或反之亦然）。对于低级语言来说，这不一定是问题，在低级语言中，对数据结构布局的细粒度控制是一项功能，但这确实使 C 更难变得快速。

C 还要求在结构末尾进行填充，因为它保证数组中没有填充。填充是 C 规范中特别复杂的部分，并且与其他语言部分交互不良。例如，您必须能够使用类型无关的比较（例如，memcmp）来比较两个 struct，因此 struct 的副本必须保留其填充。在一些实验中，发现某些工作负载上的总运行时有相当一部分时间花在了复制填充上（填充通常尺寸和对齐方式都很笨拙）。

考虑 C 编译器执行的两个核心优化：SROA（聚合的标量替换）和循环解开关。 SROA 尝试用单个变量替换 struct（和固定长度的数组）。这允许编译器将访问视为独立的，并且如果它可以证明结果永远不可见，则完全省略操作。这具有在某些情况下删除填充但在其他情况下不删除填充的副作用。

第二个优化，循环解开关，将包含条件的循环转换为两个路径中都带有循环的条件。这改变了流程控制，与程序员知道低级语言代码运行时将执行什么代码的想法相矛盾。它还会导致 C 的未指定值和未定义行为的概念出现重大问题。

在 C 中，从未初始化的变量读取是一个未指定的值，并且每次读取时都允许是任何值。这很重要，因为它允许诸如页面延迟回收之类的行为：例如，在 FreeBSD 上，malloc 实现通知操作系统页面当前未使用，并且操作系统使用对页面的第一次写入作为不再如此的提示。对新 malloc 内存的读取最初可能会读取旧值；然后操作系统可以重用底层的物理页面；然后在下次写入页面中的不同位置时，将其替换为新清零的页面。然后从同一位置的第二次读取将给出零值。

如果将流程控制的未指定值使用（例如，在 if 语句中将其用作条件），则结果是未定义行为：允许发生任何事情。考虑循环解开关优化，这次是在循环最终执行零次的情况下。在原始版本中，循环的整个主体都是死代码。在解开关版本中，现在有一个对变量的分支，该变量可能未初始化。一些死代码现在已转换为未定义行为。这只是对 C 语义的仔细调查表明是不健全的众多优化之一。

总而言之，有可能使 C 代码快速运行，但这只能通过花费数千人年的时间构建足够智能的编译器来实现——即使这样，也只有在您违反某些语言规则的情况下才能实现。编译器编写者让 C 程序员假装他们正在编写“贴近硬件”的代码，但如果他们希望 C 程序员继续相信他们正在使用一种快速语言，则必须生成行为非常不同的机器代码。

理解 C

低级语言的关键属性之一是程序员可以轻松理解语言的抽象机器如何映射到底层物理机器。这在 PDP-11 上肯定是正确的，其中每个 C 表达式都简单地映射到一两条指令。类似地，编译器对局部变量执行了直接的降级到堆栈槽的操作，并将原始类型映射到 PDP-11 可以本机操作的事物。

从那时起，C 的实现必须变得越来越复杂，以维持 C 易于映射到底层硬件并提供快速代码的错觉。 2015 年对 C 程序员、编译器编写者和标准委员会成员进行的一项调查提出了关于 C 的可理解性的几个问题。³ 例如，C 允许实现将填充插入结构（但不插入数组）中，以确保所有字段都具有目标有用的对齐方式。如果您将结构清零然后设置某些字段，填充位是否都为零？根据调查结果，36% 的人确信它们会为零，而 29% 的人不知道。根据编译器（和优化级别），它可能会也可能不会。

这是一个相当简单的例子，但很大一部分程序员要么相信了错误的事情，要么不确定。当您引入指针时，C 的语义变得更加令人困惑。 BCPL 模型相当简单：值是字。每个字要么是一些数据，要么是一些数据的地址。内存是由地址索引的存储单元的平面数组。

相比之下，C 模型旨在允许在各种目标上实现，包括分段架构（其中指针可能是段 ID 和偏移量）甚至垃圾回收虚拟机。 C 规范小心地限制了对指针的有效操作，以避免此类系统出现问题。对缺陷报告 260¹ 的回复在指针的定义中包含了指针来源的概念

“允许实现跟踪位模式的来源，并将表示不确定值的位模式与表示确定值的位模式区分对待。即使指针在位上相同，它们也可以将基于不同来源的指针视为不同的。”

不幸的是，来源一词根本没有出现在 C11 规范中，因此由编译器编写者来决定它的含义。例如，GCC（GNU 编译器集合）和 Clang 在转换为整数然后再转换回来的指针是否通过强制转换保留其来源方面存在差异。编译器可以自由地确定指向不同 malloc 结果或堆栈分配的两个指针始终比较为不相等，即使指针的按位比较可能显示它们描述了相同的地址。

这些误解并非纯粹是学术性质的。例如，已经观察到来自有符号整数溢出（C 中的未定义行为）和来自在空检查之前取消引用指针的代码的安全漏洞，向编译器表明指针不可能是空指针，因为取消引用空指针是 C 中的未定义行为，因此可以假定不会发生（https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2009-1897）。

鉴于这些问题，很难论证可以期望程序员准确理解 C 程序将如何映射到底层架构。

想象一个非 C 处理器

针对 Spectre 和 Meltdown 提出的修复程序带来了显着的性能损失，在很大程度上抵消了过去十年微架构的进步。也许是时候停止尝试使 C 代码快速运行，而是考虑在设计为快速的处理器上编程模型会是什么样子。

我们有很多没有专注于传统 C 代码的设计示例可以提供一些灵感。例如，高度多线程芯片，例如 Sun/Oracle 的 UltraSPARC Tx 系列，不需要太多缓存来保持其执行单元满负荷运行。研究处理器² 已将此概念扩展到非常大量的硬件调度线程。这些设计背后的关键思想是，通过足够的高级并行性，您可以挂起正在等待来自内存的数据的线程，并用来自其他线程的指令填充您的执行单元。这种设计的问题在于 C 程序往往只有很少的繁忙线程。

ARM 的 SVE（可伸缩向量扩展）——以及伯克利⁴ 的类似工作——提供了程序和硬件之间更好接口的另一种瞥见。传统的向量单元公开了固定大小的向量操作，并期望编译器尝试将算法映射到可用的单元大小。相比之下，SVE 接口期望程序员描述可用的并行度，并依赖硬件将其映射到可用执行单元的数量。从 C 中使用它很复杂，因为自动向量化器必须从循环结构中推断出可用的并行性。从函数式风格的 map 操作生成代码是微不足道的：映射数组的长度是可用并行度的程度。

缓存很大，但它们的大小并不是它们复杂性的唯一原因。 缓存一致性协议是现代 CPU 中最难做到既快速又正确的部分之一。涉及的大部分复杂性来自支持一种语言，在这种语言中，数据被期望是共享的和可变的，这是理所当然的。相比之下，考虑 Erlang 风格的抽象机器，其中每个对象要么是线程本地的，要么是不可变的（Erlang 甚至对此进行了简化，其中每个线程只有一个可变对象）。这种系统的缓存一致性协议将有两种情况：可变的或共享的。迁移到不同处理器的软件线程需要显式地使其缓存无效，但这是一种相对不常见的操作。

不可变对象可以进一步简化缓存，并使几个操作更便宜。 Sun Labs 的 Project Maxwell 指出，缓存中的对象和将在年轻代中分配的对象几乎是同一组。如果对象在需要从缓存中逐出之前就已死亡，那么永远不将它们写回主内存可以节省大量电力。 Project Maxwell 提出了一个年轻代垃圾收集器（和分配器），它将在缓存中运行并允许快速回收内存。借助堆上的不可变对象和可变堆栈，垃圾收集器变成了一个非常简单的状态机，它很容易在硬件中实现，并且可以更有效地利用相对较小的缓存。

专为速度而非在速度和 C 支持之间妥协而设计的处理器可能会支持大量线程、具有宽向量单元，并具有更简单的内存模型。在这样的系统上运行 C 代码将是有问题的，因此，鉴于世界上大量的遗留 C 代码，它不太可能在商业上取得成功。

软件开发中有一个常见的误解，即并行编程很难。艾伦·凯对此会感到惊讶，他能够向年幼的孩子教授一种actor模型语言，他们用这种语言编写了包含 200 多个线程的工作程序。 Erlang 程序员对此感到惊讶，他们通常编写包含数千个并行组件的程序。更准确的说法是，在使用类似 C 抽象机器的语言进行并行编程很困难，并且鉴于并行硬件的普及，从多核 CPU 到多核 GPU，这只是另一种说法，即 C 不能很好地映射到现代硬件。

参考文献

1. C 缺陷报告 260。 2004 年； http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm。

2. Chadwick, G. A. 2013。面向通信、多核、细粒度处理器架构。技术报告 832。剑桥大学计算机实验室； http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-832.pdf。

3. Memarian, K., Matthiesen, J., Lingard, J., Nienhuis, K., Chisnall, D. Watson, R. N. M., Sewell, P. 2016。深入 C：详细阐述事实上的标准。 第 37 ^届 SIGPLAN 编程语言设计与实现会议论文集：1-15； http://dl.acm.org/authorize?N04455。

4. Ou, A., Nguyen, Q., Lee, Y., Asanović, K. 2014。MVP 案例：混合精度向量处理器。第二届移动平台并行性国际研讨会，第 41 届国际计算机体系结构研讨会。

5. Perlis, A. 1982。关于编程的警句。 SIGPLAN 通知 17(9)。

跨语言互操作性的挑战
David Chisnall
语言之间的接口变得越来越重要。
https://queue.org.cn/detail.cfm?id=2543971

在苹果中发现不止一只虫子
Mike Bland
如果你看到什么，就说出来。
https://queue.org.cn/detail.cfm?id=2620662

为代码而编码
Friedrich Steimann, Thomas Kühne
模型可以为软件开发提供 DNA 吗？
https://queue.org.cn/detail.cfm?id=1113336

David Chisnall 是剑桥大学的研究员，他在那里从事编程语言设计和实现工作。在完成博士学位并来到剑桥大学之间，他花了几年时间担任顾问，在此期间他还撰写了关于 Xen 以及 Objective-C 和 Go 编程语言的书籍，以及大量文章。他还为 LLVM、Clang、FreeBSD、GNUstep 和 Étoilé 开源项目做出了贡献，并且他跳阿根廷探戈舞。

最初发表于 Queue vol. 16, no. 2—
在数字图书馆中评论本文

更多相关文章

Matt Godbolt - C++ 编译器中的优化
在为编译器提供更多信息方面需要权衡：这会使编译速度变慢。诸如链接时优化之类的技术可以为您提供两全其美的优势。编译器中的优化不断改进，并且即将到来的间接调用和虚函数分派的改进可能很快就会带来更快的多态性。

Ulan Degenbaev, Michael Lippautz, Hannes Payer - 垃圾回收作为合资企业
跨组件跟踪是一种解决组件边界之间引用循环问题的方法。只要组件可以形成具有跨 API 边界的非平凡所有权的任意对象图，就会出现此问题。 CCT 的增量版本在 V8 和 Blink 中实现，从而能够以安全的方式有效且高效地回收内存。

Tobias Lauinger, Abdelberi Chaabane, Christo Wilson - 你不应该依赖我
大多数网站都使用 JavaScript 库，其中许多库已知存在漏洞。了解问题的范围以及包含库的许多意外方式只是改善情况的第一步。这里的目标是，本文中包含的信息将有助于为社区提供更好的工具、开发实践和教育工作。

Robert C. Seacord - 未初始化的读取
大多数开发人员都理解，在 C 中读取未初始化的变量是一个缺陷，但有些人仍然这样做。在当前版本的 C 标准 (C11).3 中，读取未初始化对象时会发生什么尚不确定。已提出各种提案来解决计划中的 C2X 标准修订版中的这些问题。因此，现在是了解现有行为以及标准拟议修订以影响 C 语言演变的好时机。鉴于 C11 中未初始化读取的行为尚不确定，谨慎的做法是从代码中消除未初始化的读取。