旭穹の陋室

时空局部性 要精确评估算法在内存操作方面的性能，我们需要考虑缓存系统的多个特性：缓存层的数量，每层的缓存大小和块大小，每层用于缓存淘汰的具体策略，有时甚至需要考虑内存分页机制的细节。 在设计算法的初期阶段，应该尽可能地抽象这些细节，而不是计算理论的缓存命中率。这是因为更定性地去思考缓存性能，通常更有意义，也更有助于理解和改善算法性能。 在这个背景下，用来讨论缓存重用程度的方式主要有两种： 时间局部性（Temporal locality）是指在一小段时间内反复访问同一数据，使得在连续的请求之间，这份数据能够继续存储在缓存中； 空间局部性（Spatial locality）是指访问的数据如果在内存中地址相邻，那么它们可能在同一内存块中被一起获取，这样也能提高数据获取的效率。简单来说，就是"正在使用的数据附近的数据，接下来可能会被用到"。 换句话说，时间局部性是指这个相同的内存位置很可能很快就会再次被请求，而空间局部性是指一个附近的位置很可能在此之后马上被请求。 在本文种，我们将进行一些案例研究，以展示这些高级概念如何在实际优化中提供帮助。 深度优先与广度优先 考虑一 ...

缓存遗忘算法 在外部内存模型中，有两种类型的高效算法： 一种是缓存感知算法（Cache-aware algorithms），已知缓存块大小BBB和内存总大小MMM； 一种是缓存遗忘算法（Cache-oblivious algorithms），则不需要知道特定的缓存参数下，在任何BBB和MMM情况下都能高效运行； 例如，外部合并排序就是一种缓存感知算法，而非缓存遗忘算法：我们需要知道系统的内存特性，即可用内存与块大小的比例，以找到执行kkk路合并排序的正确kkk值。 缓存遗忘算法很有趣，因为无论在缓存层次结构中的哪一级，它们都会自动变得最优，而不仅仅是在为其特别调整的那一级。在这篇文章中，我们将探讨它在矩阵计算中的一些应用。 矩阵转置 假设我们有一个大小为N×NN×NN×N的方阵AAA，我们需要对它进行转置。根据定义实现的朴素方法大概会是这样： for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) swap(a[j * N + i], a[i * N + j]); 这里我们使用了一个指向内存起始 ...

淘汰策略 你可以手动控制程序的I/O操作，但大多数情况下都只是依赖自动的缓冲（bufferization）和缓存（caching），要么是因为懒惰，要么是因为计算环境的限制。 然而，自动缓存也有自己的挑战。当一个程序用完其用于存储中间数据的工作内存时，如果要为新数据创建空间，就需要去除一个现存的数据块。在冲突情况下决定在缓存中保留哪些数据的具体规则被称为淘汰策略（eviction policy）。 这个规则可以是任意的，但有几个流行的选择： 先入先出（first in first out，FIFO）：简单地淘汰最早添加的块，而不考虑之前访问的频率（与FIFO队列的方式相同）。 最近最少使用（least recently used，LRU）：淘汰最长时间未访问的块。 后入先出（last in first out，LIFO）和最近最常使用（most recently used，MRU）：与前两者相反。删除最热的块似乎有害，但是在某些情况下，这些策略是最优的，例如需要在有限的周期内循环遍历同一个文件（优先移除最新缓存的，这样等再次循环到文件开头时，内容还在缓存中）。 最少频率使用（leas ...

列表排名 在这一部分，我们将应用 外部排序 和 连接 来解决一个表面上看起来无用但实际上在大量外部存储和并行算法中被广泛使用的关键原语问题。 问题：给定一个单向链表，计算每个元素的排名（rank），等于其到最后一个元素的距离。下面是列表排名问题的输入和输出示例： 这个问题在 RAM 模型中可以轻易地解决：你只需要遍历整个列表并进行计数。但是，在外部存储器环境中直接使用指针跳跃的方式可能并不能很好地工作，因为列表节点是随机存储的，在最坏的情况下，读取每个新节点都可能需要读取一个新的块。 算法 考虑关于这个问题的一个更加通用的版本。现在，每个元素都有一个权重wiw_iwi​，对于每个元素，需要计算的不再是它之前的元素数量（即它的排名），而是需要计算它之前所有元素的权重之和。如果希望退化到最初的问题（即每个元素之前的元素数量），可以简单地将每个元素的权重都设为1，这样元素权重之和就等同于元素数量。 该算法的主要思想是删除一些元素（或者元素的一部分），用递归的方式来求解这个减小规模的问题。解决之后，算法会根据这些权重排名结果来重建初始问题的答案。 考虑三个连续的元素xxx，yyy和z ...

外部排序 现在，让我们试着为新的外部存储模型设计一些实际有用的算法。我们在这个部分的目标是慢慢构建更复杂的东西，最终达到外部排序及其有趣的应用。 这个算法将基于标准的归并排序算法，所以我们首先需要推导出它的主要原始形式。 归并 问题：给定两个有序数组aaa（长度为NNN）和bbb（长度为MMM），要生成一个包含两者所有元素的有序数组ccc（长度为N+MN+MN+M）。 用于合并排序数组的标准的双指针技巧如下所示： void merge(int *a, int *b, int *c, int n, int m) { int i = 0, j = 0; for (int k = 0; k < n + m; k++) { if (i < n && (j == m || a[i] < b[j])) c[k] = a[i++]; else c[k] = b[j++]; }} 在内存操作方面，我们只需线性地读取aaa和bbb的所有元素并 ...

外部存储模型 当我们要理解和预测一个内存受限的算法性能时，我们需要创建一个新的成本模型。这个模型需要对昂贵的块I/O（Input/Output，输入输出）操作更敏感，但又不能过于严格以至于失去其实用性。 缓存感知模型（Cache-Aware Model） 标准的 RAM 模型忽略了一点：完成不同基本操作所需的时间是不相同的。更为关键的是，这个模型并未区别对待对不同类型内存的操作。例如，直接从 RAM 中读取数据，现实中大约需要 50 纳秒的时间；而从硬盘读取数据则大约需要 5 毫秒的时间，这比从 RAM 读取数据的时间要长大约 100,000 倍。 在外部存储模型中，我们只关注与输入输出（I/O）操作相关的部分，而忽视了所有其他非输入输出操作的部分。另外，我们假设系统只有一级缓存层次，并且有如下关于硬件和其他问题的假设： 数据集的总大小为NNN，所有的数据都保存在外部的存储设备中，可以在单位时间内进行读取或者写入BBB个元素的数据块（读取整个块和只读取一个元素所需的时间相同）。 我们可以在内存中存储MMM个元素，意味着我们可以存储至多⌊MB⌋⌊\frac{M}{B}⌋⌊BM​⌋ ...

虚拟内存 早期的操作系统允许每个进程自由地读取和修改它们想要的任何内存区域，包括为其他进程分配的那些区域。虽然这让事情变简单，但也带来了一些问题： 如果某个进程存在bug，或者完全存粹是恶意的（病毒），我们应该如何防止它修改分配给其他进程的内存，同时仍然保持通过内存进行进程间通信的可能性？ 我们如何应对内存碎片化问题？假设我们有4MB的内存，进程A分配了开头的1MB给自己，然后进程B声明了下一个2MB，然后A结束并释放了它的内存，这时进程C启动并请求一个连续的2MB空间——但是无法得到，因为我们只有两个分离的1MB空间。重新启动进程B或者以某种方式暂停它并将其所有数据和指针向前移动1MB似乎并不是一个好的解决方案。 我们如何访问非RAM类型的存储？我们该如何插入闪存并从中读取特定文件呢？ 对于某些特定类型的计算机系统，例如图形处理器（GPU），这些问题并不是那么关键，因为你通常一次只解决一个任务，并完全掌控计算过程。但是对于现代的多任务操作系统，这些问题绝对是不可避免的，而这些系统通过使用一种名为虚拟内存（virtual memory）的技术来解决所有这些问题。 内存分页 虚拟内存 ...

存储层次结构 现代计算机存储具有高度层次化的结构。它由不同速度和大小的多个缓存层（cache layer）组成，其中高层通常存储低层中最常访问的数据以减少延迟：每高一层通常都要快一个数量级，但也会更小和/或更贵。 抽象来说，各类存储设备可以被描述为这样的模块：具有一定存储容量MMM，并且可以一次读写尺寸为B的数据块（而非单个字节！），每次读写在固定的时间内来完成。 从这个角度看，各种类型的内存都有一些重要的特性： 总大小（total size）MMM； 数据块大小（block size）BBB； 延迟（latency），即获取一个字节需要多少时间； 带宽（bandwidth），可能高于单纯用数据块大小乘以延迟时间，这意味着I/O操作可能有重叠； 摊销成本，包括芯片的价格、功耗、维护等。 下面是2021年的消费级硬件的大致对比表： Type M B Latency Bandwidth $/GB/mo1^11 L1 10K 64B 2ns 80G/s - L2 100K 64B 5ns 40G/s - L3 1M/core 64B 20ns 20G/s - ...

外部存储器 将两个数字相加需要多长时间？作为最常用的指令之一，add本身的执行只需要一个周期。因此，如果数据已经加载到寄存器中，它只需要一个周期。 但在一般情况下（*c = *a + *b），我们需要先从内存中获取其操作数： mov eax, DWORD PTR [rsi]add eax, DWORD PTR [rdi]mov DWORD PTR [rdx], eax 当你从内存中获取任何东西时，数据到达之前总是有一些延迟。此外，访存请求并不直接去到其最终的存储位置，而是首先要通过一个复杂的系统，包括地址转换单元和缓存层，这个系统旨在帮助内存管理并减少延迟。 因此，这个问题唯一正确的答案是“看情况”——主要取决于操作数存储的位置： 如果数据存储在主内存（RAM）中，这就需要大约~100ns，或者大约200个周期，来获取它，然后需要另外200个周期来写回。 如果它最近被访问过，它可能已经被缓存（cached）了，获取它的时间会变少，这取决于它多久之前被访问 —— 若数据在最慢的缓存层中，这可能需要大约50个周期，若数据在最快的缓存层中，则可能只需要4-5个周期。 但是，它也可能存储在某 ...

蒙哥马利乘法 不出所料，模运算中的大部分计算通常用于取模运算，其速度与一般的整数除法一样慢，通常需要15-20个周期，具体取决于操作数的大小。 解决这个问题的最好方法是完全避免使用取模运算，通过使用分支预测来推迟或代替它，例如在计算模之和时就可以这样做： const int M = 1e9 + 7;// input: array of n integers in the [0, M) range// output: sum modulo Mint slow_sum(int *a, int n) { int s = 0; for (int i = 0; i < n; i++) s = (s + a[i]) % M; return s;}int fast_sum(int *a, int n) { int s = 0; for (int i = 0; i < n; i++) { s += a[i]; // s < 2 * M s = (s >= M ? s ...