在本文中，我将讨论为在 Alpha 处理器上运行 Linux 的平台优化代码的技术。本文基于四年使用 Alpha 架构的经验。从这些经验中得出的主要教训是，对于许多应用程序来说，瓶颈主要是内存系统，而不是处理器本身。因此，大多数技术的目标是避免内存系统瓶颈。由于处理器和内存系统速度之间的差距很大，这些技术实现了高达 1700% 的性能提升。虽然重点是 Alpha 架构，但许多涵盖的技术很容易应用于其他 RISC 处理器，甚至现代 CISC CPU。

在讨论相同的技术如何在其他架构上工作时，棘手的部分是我们希望在不引发关于哪个 CPU 架构是“最好”或“最快”的争论的情况下做到这一点。这些术语在很大程度上是毫无意义的，因为它们只能相对于给定的问题才能有用。因此，性能结果的呈现方式如下：对于 Alpha，我们同时展示绝对结果和相对结果。绝对数字有助于具体感受代码的速度。相对结果（即，速度提升）告诉我们给定技术的效果如何。在有意义的地方，我们还列出了在基于奔腾 Pro 的系统上实现的速度提升（但不是绝对性能）。仅列出奔腾 Pro 情况下的速度提升，就可以在比较相对优势的同时，不可能判断哪个系统在给定问题上更快。（为了避免任何误解：选择这种安排不是因为 Alpha 性能不佳；作者已经使用 Alpha 一段时间了，并且通常对它们实现的性能水平感到满意。）

由于架构本身根本不执行任何操作，让我们更具体地了解用于测量的系统

Alpha 和 P6 系统都运行 Red Hat 4.0，内核版本为 2.0.18。使用的编译器是 gcc 版本 2.7.2。在 Alpha 上，使用了选项 -O2（对于此版本的 gcc，使用 -O3 或更高的选项设置通常会导致代码速度变慢）。在 P6 上，使用了选项 -O6 和 -m486。

将 gcc 与商业 Alpha 编译器（例如 Digital 的 GEM C 编译器）进行比较也具有启发意义。GEM C 编译器通常会生成稍微好一些的代码，但有时它创建的代码比 gcc 的代码快得多（这通常发生在浮点密集型代码上）。因此，一些测量结果还包括使用 GEM C 获得的结果。此编译器的调用方式如下

cc -migrate -O4 -tune ev5 -std1 -non_shared

不清楚编译器的哪个版本——它是 Digital UNIX 版本 3.2 附带的。

Alpha 架构不提供整数除法指令。其理由是

然而，有一些重要的例程依赖于整数除法。哈希表就是一个很好的例子，因为计算哈希表索引通常涉及除以整数素数常数。

基本上有两种方法可以避免整数除法。要么将整数除法替换为浮点除法，要么如果除数是常数，则可以将除法替换为乘以常数、移位和加一校正（并非总是必要）。浮点除法听起来可能不是一个好主意，但 Alpha 具有非常快的浮点单元，并且由于 32 位整数很容易放入双精度浮点数而不会损失精度，因此效果出奇地好。用乘以倒数来替换除以常数肯定更快，但这也很棘手，因为必须注意结果始终准确（差一错误尤其常见）。幸运的是，对于编译时常量，gcc 无需帮助即可处理此问题。

为了说明这可能产生的效果，我们测量了使用 ELF 哈希表查找算法（涉及一个整数除以素数常数）查找标准 C 库 (libc.so) 中所有符号所需的时间。使用整数除法，大约每秒可以执行 120 万次查找。使用双精度浮点数乘以除数的倒数，可以将此数字提高到每秒 195 万次查找（提高了 62%）。使用整数乘法代替可以获得最佳性能，即每秒 205 万次查找（提高了 70%）。由于双精度和整数乘以倒数版本之间的性能差异不是很大，因此通常最好使用浮点版本。只要操作数适合 52 位，这就可以完美地工作，并且避免了担心差一错误。

现代 CPU 中容易被遗忘的两个部分是数据和指令转换后备缓冲器 (TLB)。TLB 保存最近访问的页表条目。TLB 是必要的，因为在每次内存访问时都访问页表会太慢。由于每个 TLB 条目都映射整个页面（当前 Alpha 芯片为 8KB），因此 TLB 通常不是性能的限制因素。关键是，当程序确实遭受过多的 TLB 未命中时，性能会迅速下降。在这种情况下，减速幅度可能足以值得切换到完全不同的（通常较慢）算法，该算法具有更好的 TLB 行为。例如，在 Alpha 系统上，从 63 页数组（504KB）中的每个页面读取一个字大约需要每次访问 15ns。但是，在 64 页的数组中执行相同的操作需要每次访问 65ns——减速超过四倍。由于该系统中的二级缓存大小为 4MB，因此访问时间的这种跳跃纯粹是由于数据 TLB。

TLB 通常不是主要瓶颈，但一个小实验表明，一个 50% 已满且超出数据 TLB 大小的哈希表并不比需要每次查找两次内存访问的更紧凑的搜索树更快（哈希表只需要一次内存访问，但由于它超出了 TLB 大小，因此一次访问很慢）。总的来说，当以或多或少随机和稀疏的方式访问大型数据集时，TLB 可能是主要瓶颈。

在现代系统中，内存访问是不好的，而计算是好的。在理想情况下，我们希望完全用计算来代替内存访问。这显然并非总是可能的；但是，在可能的情况下，回报可能是巨大的。

例如，让我们考虑反转长整数中每个字节中的所有位的问题。字节反转方式如下：位 0 与位 7 交换，位 1 与位 6 交换，依此类推。由于我们要反转长整数中的所有字节，因此对于长整数中的每个字节，此算法应用一次。

为什么有人会想这样做？您可能知道，Alpha 和 x86 架构都是小端字节序，但是当 IBM 设计 VGA 图形适配器时，它选择对图形内存中的像素使用大端字节序位顺序。也就是说，字节中的位 7 对应于最左边的像素，位 0 对应于最右边的像素。这是向后的，因为最左边像素的坐标值较小。因此，字节反转对于 VGA X 服务器来说确实是一个相对重要的操作。

传统的字节反转实现方式如列表 1所示。为了节省空间，我们仅显示反转 4 字节整数的代码。8 字节长整数的情况是此代码的直接扩展。该代码假定数组 byte_reversed 已初始化，使得 byte_reversed[i] 是 i 的反转值。使用这种朴素的算法，每次字节反转都涉及表查找。

本文中的所有列表都可以通过匿名下载文件 ftp.linuxjournal.com/pub/lj/listings/issue43/2487.tgz获得。

由于 Alpha 是一个 64 位架构，这意味着每次长整数反转都涉及八次内存访问。我们如何避免这些昂贵的内存访问？好吧，一种简单且可以说更直观的字节反转实现方式是使用移位和掩码来交换位。列表 2显示了执行此操作的代码。

请注意，除了 mask 的初始化之外，此代码完全独立于长整数的宽度。因此，为了使其在 32 位机器上工作，我们需要做的就是将 mask 初始化为 0x01010101。

现在让我们看看这两种实现的比较情况。表 1 给出了 Alpha、奔腾 Pro (P6) 和 120MHz 奔腾笔记本电脑 (P5) 的结果。除了上面显示的两种实现之外，该表还包括一行，显示了在 x86 汇编代码中编码的朴素实现的性能（实现 byterev_x86）。此例程直接来自 XFree86 v3.2 发行版。

表 1. 字节反转例程的比较

如表所示，避免内存访问的字节反转例程在 Alpha 上快了 30% 以上。有趣的是，在 P6 上，此例程也是最快的。那里的好处较小（仅为 13%），但考虑到它更具可移植性且更直观，因此没有理由不使用它。令人震惊的是汇编版本在 P6 上的完全失败。该例程仅为避免内存访问的版本的一半速度。这可能是由于汇编例程大量使用字节访问 CPU 寄存器。对于奔腾笔记本电脑，如 P5 列所示，汇编代码例程是最快的版本。不要被相对性能数字所误导；就绝对性能而言，P5 仅为 P6 的一半速度。

总而言之，不仅 byterev_long() 是 Alpha 上最快的版本，而且它似乎也是 P6 上的正确解决方案。

gcc 有时生成的代码效率远低于 Digital 的 GEM 编译器的原因之一是它不执行过程间别名分析。这意味着 gcc 的别名分析有时会不必要地保守。为了说明这个问题，请考虑列表 3中显示的函数。它是一个简单的展开循环，用于反转数组 src 中的所有字节，并将结果存储在数组 dst 中。

此代码的问题在于 C 编译器无法知道 src 和 dst 指针之间如何关联。就它所知，dst 可能指向 src 指向的数组的第二个元素。当这种情况发生时，两个指针引用重叠的内存区域，并且据说它们彼此别名。对于编译器来说，重要的是要知道两个指针是否重叠，因为这决定了它在重新排序指令方面的自由度。例如，如果区域重叠，则将值存储到 dst[i+0] 可能会影响 src[i+1] 的值。因此，为了安全起见，编译器必须严格按照它们在源代码中出现的顺序生成上述函数中的加载和存储。

现在，如果已知传递给函数的两个数组永远不会彼此别名，我们可以通过显式地向 gcc 提供此信息来帮助它。我们可以通过首先从内存中读取所有值，然后执行所有计算，最后将结果存储回内存来做到这一点。因此，上面的代码将转换为列表 4中显示的代码。

由于所有存储都发生在最后，因此 gcc 立即知道没有任何存储会影响任何先前的加载。这为它在为加载和计算生成最佳代码提供了完全的自由度（这里的假设是 byterev_long 是一个内联函数）。

在 Alpha 和大多数其他具有大量寄存器的架构（例如，大多数 RISC）上，这种代码永远（或至少很少）会损害性能，并且通常会提高 gcc 的性能。不幸的是，对于 x86 架构来说，情况并非如此。那里的问题是只有少量寄存器可用。因此，对于 RISC 来说更好的代码通常对于 x86 来说更糟，这是由于访问最终位于堆栈上的临时变量所需的额外存储和加载。表 2 给出了两个版本的性能数字。

表 2. 字节反转源代码的性能值

如表 2 所示，仅通过将加载与计算与存储分离，就可以在 Alpha 上的 gcc 中获得 13% 的收益。相比之下，相同的代码在 P6 上损失了 17%。这说明，虽然本文中的大多数技术都适用于这两种架构，但有时存在重要的差异，需要不同的编码才能获得最佳性能。

现在，让我们考虑一个简单的问题：矩阵乘法。虽然很简单，但它是被认为是浮点密集型问题的典型问题。实际上，大多数浮点密集型问题也是内存密集型问题。例如，它们处理大型向量或矩阵。因此，内存访问模式通常在实现最佳性能方面起着至关重要的作用。矩阵乘法的教科书式实现如列表 5所示。

在这里，由 a 指向的矩阵乘以由 b 指向的矩阵，结果存储在 c 中。矩阵维度在参数 dim 中传递。在 Alpha 上，使用此例程的 512x512 矩阵乘法以大约每秒 1300 万次浮点运算 (MFLOPS) 的速度执行。这还不错，但让我们看看是否可以从机器中挤出更多性能。在性能优化方面吸取了教训后，我们可能会尝试展开内部循环并避免由于索引而导致的所有乘法运算。这确实产生了更快的版本：现在，矩阵乘法以大约 15 MFLOPS 的速度执行。

gcc 的优化器无法消除归纳变量，因此也无法消除由于索引而导致的乘法运算。gcc 2.72.1 和更早版本在此区域中存在一个错误，该错误在为 Alpha 生成代码时出现。如果索引变量声明为 long 而不是 int，则 gcc 能够消除归纳变量，正如人们所期望的那样。

与其宣布问题已解决，不如让我们花一点时间思考内存访问模式。结果矩阵 c 中的每个元素都是 a 中的一行和 b 中的一列的点积。例如，元素 c[0][0] 计算为 a 中的第一行和 b 中的第一列的点积。如图 1 所示。在我们的朴素矩阵乘法例程中，这意味着对 a 的访问形成了一个良好的、密集的、线性内存访问模式。不幸的是，对于 b 来说，情况看起来并不那么好。那里的内存访问模式是稀疏的：首先，读取偏移量为 0 的元素，然后读取偏移量为 dim 的元素，依此类推。这种稀疏访问模式在很多方面都不利。可以说，为密集、线性访问优化机器是最容易的，因此这些访问很可能始终是最快的访问。幸运的是，有一个简单的技巧可以避免矩阵 b 的不良访问模式：在执行实际的矩阵乘法之前，我们可以简单地转置矩阵 b。然后，所有内存访问都是密集的。当然，转置 b 会导致额外的工作，但由于矩阵被访问 dim 次，因此这很可能值得。

图 1：矩阵乘法

因此，让我们通过在主循环前面添加矩阵转置，将 matmul0 更改为 matmul1。列表 6中的代码假定 tb 是一个大小合适的临时变量，用于保存 b 的转置。

如果您认为 15 MFLOPS 很快，请再想一想：matmul1 以惊人的 45 MFLOPS 的速度执行。接下来，我们将添加一些循环展开等。对于 matmul0，这为我们带来了 25% 的提升，这还不错。如果我们将循环展开八次并进行一些其他直接优化，我们将得到列表 7中显示的代码。为了紧凑起见，它假定 dim 是 8 的整数倍。这是否值得付出努力？当然值得：matmul2 的时钟频率为完整的 80 MFLOPS。您是否喜欢这种代码可能是一个品味问题，但它肯定很快。

表 3 总结了性能结果。为了进行比较，它还包括了使用 Digital 的 GEM C 编译器编译相同代码获得的结果，以及 P6 的相对结果。如表所示，使用 gcc，我们实现了超过七倍的性能提升。更重要的是，优化在所有三种情况下都得到了回报。事实上，使用 Digital 的编译器，改进超过了八倍。Digital C 和 gcc 之间的性能差距相当大。对于整数代码，差距通常较小，但看起来 gcc 在浮点领域需要做一些工作。最后，请注意，即使在 P6 上，性能也提高了近四倍。这是令人鼓舞的，因为将循环展开八次对于 x86 架构来说有点激进（因为可用的寄存器相对较少）。据推测，代码可以再加速一些，但这里的重点是所有三种情况都以相同的方式从内存访问优化中受益。

表 3. 矩阵乘法例程的性能结果

数据并行处理：MPEG 核心循环

多媒体应用程序是当今的潮流。所有主流 CPU 架构（PowerPC 的著名例外）都具有所谓的多媒体扩展。Alpha 非常适合此类应用程序，因为它从一开始就是 64 位架构。事实上，Alpha 多媒体扩展非常简单；它仅添加了四种新的指令类型（向量最小值/最大值、像素误差、打包和解包）。由于其中一些指令可以对不同的数据类型（字节或字，有符号或无符号）进行操作，因此添加的指令总数为 13，这远小于其他架构的相应数字。Alpha 能够用如此少的添加来解决问题，是因为其原始指令集已经包含多媒体应用程序所需的许多指令。例如，有一条指令允许并行比较八个字节——一条看似简单的指令，但在许多应用程序中可以证明其功能非常强大。

我们使用 Berkeley MPEG 解码器 mpeg_play 来说明这一点。（参见参考文献 2）。由于没有足够的空间来说明可以应用于此程序的所有优化，我们将重点关注 MPEG 解码器中最重要​​的操作之一。此操作涉及计算两个字节向量的平均值。这是一个频繁的操作，因为视频通常包含可以表示为早期图像和后期图像的平均值的图像。字节向量平均值的直接方法如列表 8所示。

当使用 gcc 编译时，此循环的每次字节平均（迭代）执行时间约为 94ns。将此循环展开两次并提前读取下一次迭代中需要的输入值会产生可能接近此面向字节的方法的最佳代码。实际上，使用 gcc，性能提高到每次字节平均约 60ns。（让我们将此函数的展开版本称为 byte_avg1。）

为了获得更高的性能，我们需要更加积极。考虑到 Alpha 是一个 64 位架构，我们希望并行计算八个字节的平均值。以这种数据并行格式重新制定面向字节的算法通常很简单。对于字节平均，它并没有那么简单。直接实现需要九位精度，因为 255 + 255 = 510。如果我们将八个字节打包成一个 64 位字，则没有额外的第九位。我们如何解决这个问题？显然，我们可以先将操作数除以 2，然后再将它们相加。这样，总和最多为 127 + 127 = 254，这可以方便地放入八位。关键是结果可能不正确；如果两个操作数都是奇数，则结果将小 1。幸运的是，很容易对此进行纠正：如果两个操作数中的位 0 都已设置，则需要加一校正。换句话说，我们可以通过使用额外的长寄存器来为额外的第九位腾出空间，该寄存器用于保存校正位。由于所有中间结果现在都适合八位，因此数据并行实现字节平均的障碍已消除。

结果代码如列表 9所示。为简单起见，它假定输入向量是长字对齐的，并且大小是长字大小的整数倍。请注意，宏 VEC() 采用一个 8 位值，并将其复制一次，用于长字中的每个字节——编写 VEC(0x01) 而不是 0x0101010101010101 要方便得多，并且更不容易出错。或许解释一下平均值的核心会很有帮助。变量 CC 保存校正位，因此它只是向量 A0 和 B0 的按位与，并使用 0x01 的向量进行掩码。我们通过将 A0 和 B0 向右移动一位并使用 0x7f 的向量掩码结果长字来将 A0 和 B0 除以 2。此掩码是必要的，因为否则字节“上方”的字节的位 0 会偷偷进入并成为该字节的位 7，从而导致严重错误。平均值是通过简单地将向量 A0、B0 和 CC 相加来计算的。此加法不会导致任何溢出，因为每个字节的最大可能值为 127 + 127 + 1 = 255。

尽管看起来如此，但此代码实际上非常可移植。对于 32 位架构，所有需要更改的是宏 VEC（甚至这只是为了消除编译器警告才是必要的）。字节顺序不是问题，因为即使数据一次访问一个长字，每个字节仍然是单独处理的。此数据并行版本的字节平均循环的每次字节平均运行时间为 5.3ns——比展开循环快一个数量级以上。

表 4 总结了三个平均例程。相对性能以吞吐量（每秒字节平均数）为单位，因为这既更直观又更令人印象深刻。Alpha 的结果同时针对 gcc 和 Digital 的 GEM C 编译器给出；与往常一样，对于 P6，使用了 gcc。

表 4. 平均例程的性能

请注意，GEM C 为愚蠢版本 (byte_avg0) 生成的代码更好得多，但为聪明版本 (byte_avg2) 生成的代码仅略好一些。这是一个常见的主题，至少对于整数代码而言：对于结构良好的代码，gcc 通常生成的代码与 GEM C 编译器相当。另一个有趣的结果是，提前读取和循环展开会损害 P6 的性能。这意味着 byte_avg2 可能可以针对 P6 进行更多优化（因为它也使用提前读取和循环展开），但即便如此，P6 使用数据并行版本的速度也快了两倍。这令人印象深刻，因为相对开销对于 32 位芯片来说要高得多（Alpha 可以将所有掩码和移位分摊到八个字节上，而 32 位架构只有四个字节）。

所有这些如何影响 mpeg_play 的性能？通过比较原始 Berkeley 版本与使用本节中描述的技术（特别是数据并行处理和避免整数除法）优化的版本，可以最好地说明这一点。（参见参考文献 3。）比较 MPEG 性能有点棘手，因为大部分时间都花在显示图像上。这可以通过使用选项 -dither<\!s>none 来排除，该选项的效果是不显示任何内容（同时 MPEG 流仍然像往常一样解码）。表 5 显示了此模式以及使用有序抖动时的结果。有序抖动本身也使用数据并行处理进行了优化，从而产生了一个名为 ordered4 的版本。用于 mpeg_play 的选项是 -controls<\!s>none<\!s>-framerate<\!s>0<\!s>-dither<\!s>D。D 的值是 none、ordered 或 ordered4，如表 5 中标记为“Dither”的列所示。这些测量中使用的电影是一个 320x240 像素大小的计算机动画，名为 RedsNightmare.mpg。（参见参考文献 4。）

表 5. MPEG 性能值

如表所示，即使在应用程序级别，优化技术也确实带来了巨大的性能提升。当然，很少有人会喜欢以每秒 98 帧的速度观看电影，但是使用优化的代码，您可以实时观看更大的视频，或者您可以在观看您最喜欢的电影时观看 CNN。当我们拥有真正的窗口系统时，谁还需要画中画功能呢？

Alpha 架构专为性能而设计，其实际应用确实使系统速度非常快。由于其芯片以非常高的时钟频率运行，因此 Alpha 通常从简单的技术中受益最多，这些技术可以改善给定程序或算法的内存系统行为。本文演示了其中的一些技术，并表明这些技术实现了 10% 到 1700% 范围内的性能提升。幸运的是，相同的技术似乎也有利于其他 CPU 架构。这是一个好消息，因为这意味着通常一个优化的实现将在各种 CPU 上表现良好。

在 Linux 下开发高性能应用程序的最大障碍是当前缺乏复杂的性能分析工具。相对缺乏此类工具并不奇怪；虽然大多数商业 Unix 供应商都为其自己的架构提供了工具，但很少有（如果有的话）是多平台的。在某种程度上，这是问题固有的，但毫无疑问，创建更好的便携式性能分析工具并非难事。

Linux 使低成本的基于 Alpha 的 Unix 工作站成为现实。虽然 Digital UNIX 目前配备了更好的编译器、运行时库和更多用于 Alpha 的工具，但价格差异如此之大，以至于人们可以通过花更多的钱购买更快的机器来轻松弥补性能差异。此外，gcc 和更好的库的开发并没有停滞不前。但是，由于大多数工作都是在自愿的基础上完成的，因此确实需要一些时间。即便如此，Linux 已经成为整数密集型应用程序极具竞争力的平台。对于浮点密集型应用程序，尤其是 FORTRAN 应用程序，事情尚未成熟。幸运的是，如果无法等待更好的编译器，始终可以选择购买可用于 Linux/Alpha 的商业 FORTRAN 编译器之一。

作者要感谢德克萨斯 A&M 大学的 Richard Henderson 和 Red Hat Software 的 Erik Troan 在短时间内审阅本文。他们的反馈极大地提高了本文的质量。错误和遗漏完全由作者负责。本文最初于 4 月 5 日在 Linux Expo 97 上作为演讲稿发表。

参考文献