说明
本文是个人学习用的非官方中英对照译文,原文:https://diveintosystems.org/book/C11-MemHierarchy/index.html。
原书采用 CC BY-NC-ND 4.0 许可(禁止演绎),请勿公开传播本译文。
标为「译注」「现代更新」的内容是译者补充,不代表原书作者观点;代码与原文逐字一致,未作改动。
11. Storage and the Memory Hierarchy
尽管设计和实现高效的算法通常是编写高性能程序最关键的一环,但还有另一个常被忽视、却可能对性能产生重大影响的因素:内存。也许出人意料的是,两个渐近性能相同(最坏情况下的步数相同)的算法,在相同的输入上运行时,由于执行它们的硬件的组织方式不同,实际表现可能大相径庭。这种差异通常源于算法的内存访问,尤其是它们把数据存放在哪里,以及访问数据时呈现出什么样的模式。这些模式称为内存局部性(memory locality);要获得最佳性能,程序的访问模式需要与硬件的内存安排相契合。
Although designing and implementing efficient algorithms is typically the most critical aspect of writing programs that perform well, there’s another, often overlooked factor that can have a major impact on performance: memory. Perhaps surprisingly, two algorithms with the same asymptotic performance (number of steps in the worst case) run on the same inputs might perform very differently in practice due to the organization of the hardware on which they execute. Such differences generally stem from the algorithms’ memory accesses, particularly where they store data and the kinds of patterns they exhibit when accessing it. These patterns are referred to as memory locality, and to achieve the best performance, a program’s access patterns need to align well with the hardware’s memory arrangement.
例如,考虑表 1 所示的、求 N×N 矩阵中各值平均数的函数的两个变体。尽管两个版本访问的内存位置相同、次数也相同(N2 次),但在真实系统上,左边代码的执行速度大约是右边代码的五倍。差异来自它们访问这些内存位置的模式。在本章的末尾,我们会用内存剖析工具 Cachegrind 来分析这个例子。
For example, consider the following two variations of a function for averaging the values in an N×N matrix, as shown in Table 1. Despite both versions accessing the same memory locations an equal number of times (N2), the code on the left executes about five times faster on real systems than the code on the right. The difference arises from the patterns in which they access those memory locations. Toward the end of this chapter we analyze this example using the memory profiling tool Cachegrind.
译注 · 在 Apple M1 Pro 上实测
译者把这两个函数原样放进一个测试程序,用 malloc 逐行分配一个 8192×8192 的 int 矩阵(数组的数组),在 Apple M1 Pro 上计时:-O0 编译时 v1 约 0.09 秒、v2 约 0.66 秒;-O2 编译时 v1 约 0.035 秒、v2 约 0.26 秒,两种情况下 v2 都慢约 7 倍。具体倍数随机器和矩阵大小变化,但「按行访问远快于按列访问」的结论很稳定。
表 1. 访问 NxN 矩阵每个元素的函数的两个版本。它们的唯一区别是对矩阵的下标顺序。
Table 1. Two versions of a function that accesses every element of an NxN* matrix. They only differ in their memory indexing into the matrix.*
1 | float averageMat_v1(int **mat, int n) { |
1 | float averageMat_v2(int **mat, int n) { |
寄存器、CPU 缓存、主存和磁盘上的文件等存储位置,在访问时间、传输速率和存储容量上都有显著差别。编写高性能应用程序时,重要的是要考虑数据存放在哪里,以及程序访问每种设备上数据的频率。例如,程序启动时访问一次慢速磁盘,很少会成为大问题。另一方面,频繁访问磁盘则会大大拖慢程序。
Storage locations like registers, CPU caches, main memory, and files on disk all feature remarkably different access times, transfer rates, and storage capacities. When programming a high-performance application, it’s important to consider where data is stored and how frequently the program accesses each device’s data. For example, accessing a slow disk once as the program starts is rarely a major concern. On the other hand, accessing the disk frequently will slow down the program considerably.
本章描述多种多样的存储设备,并介绍它们在现代 PC 中是如何组织的。有了这些背景,我们就能看到如何把各种不同的存储设备组合起来,利用典型程序的内存访问模式中所具有的局部性。
This chapter characterizes a diverse set of memory devices and describes how they’re organized in a modern PC. With that context, we’ll see how a collection of varied memory devices can be combined to exploit the locality found in a typical program’s memory access patterns.