常见操作所花费的时间 • 图中加法 (add) 和乘法 (mul) 都指的整数。 • 区别是浮点的乘法和加法基本是一样速度。 • L1/2/3 read 和 Main RAM read 的时间指的是 读一个缓存行（ 64 字节）所花费的时间。 • 根据计算： 125/64*4≈8 • 即从主内存读取一次 float 花费 8 个 cycle ， 符合小彭老师的经验公式。 • “right” 和“ wrong” 相差不多，符合我的预期 。 第 2 章：缓存与局域性 针对不同数据量大小的带宽测试 • 我们试试看 a 不同的大小，对带宽有什么影响。 针对不同数据量大小的带宽测试（续） • 可见数据量较小时，实际带宽甚至超过了 理论带宽极限 42672 MB/s ！ • 而数据量足够大时， 才回落到正常的带宽 。 • 这是为什么？ CPU 内部的高速缓存 • 原来 CPU 的厂商早就意识到了内存延迟高，读写效率低 器——虽然小，但是读写速度却特别快。这片小而快的 存储器称为缓存（ cache ）。 • 当 CPU 访问某个地址时，会先查找缓存中是否有对应的 数据。如果没有，则从内存中读取，并存储到缓存中； 如果有，则直接使用缓存中的数据。 • 这样一来，访问的数据量比较小时，就可以自动预先加 载到这个更高效的缓存里，然后再开始做运算，从而避 免从外部内存读写的超高延迟。 缓存的分级结构 查看高速缓存大小： lscpu • 可以看到我们

3 列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.4 内存与缓存 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.5 小结 . . . . . 如果感觉以下内容理解困难，可以在读完“栈”章节后再来复习。 那么，迭代和递归具有什么内在联系呢？以上述递归函数为例，求和操作在递归的“归”阶段进行。这意味 着最初被调用的函数实际上是最后完成其求和操作的，这种工作机制与栈的“先入后出”原则异曲同工。 事实上，“调用栈”和“栈帧空间”这类递归术语已经暗示了递归与栈之间的密切关系。 1. 递：当函数被调用时，系统会在“调用栈”上为该函数分配新的栈帧，用于存储函数的局部变量、参数、 编号，确保每个内存空间都有唯一的内存地址。有了这些地址，程序便可以访问内存中的数据。 图 3‑2 内存条、内存空间、内存地址 � 值得说明的是，将内存比作 Excel 表格是一个简化的类比，实际内存的工作机制比较复杂，涉 及地址空间、内存管理、缓存机制、虚拟内存和物理内存等概念。 内存是所有程序的共享资源，当某块内存被某个程序占用时，则无法被其他程序同时使用了。因此在数据结 构与算法的设计中，内存资源是一个重要的考虑因素

3 列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.4 内存与缓存 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.5 小结 . . . . . 如果感觉以下内容理解困难，可以在读完“栈”章节后再来复习。 那么，迭代和递归具有什么内在联系呢？以上述递归函数为例，求和操作在递归的“归”阶段进行。这意味 着最初被调用的函数实际上是最后完成其求和操作的，这种工作机制与栈的“先入后出”原则异曲同工。 事实上，“调用栈”和“栈帧空间”这类递归术语已经暗示了递归与栈之间的密切关系。 1. 递：当函数被调用时，系统会在“调用栈”上为该函数分配新的栈帧，用于存储函数的局部变量、参数、 。有了这些地址，程序便可以访问内存中的数据。 图 3‑2 内存条、内存空间、内存地址 Tip 值得说明的是，将内存比作 Excel 表格是一个简化的类比，实际内存的工作机制比较复杂，涉及地址 空间、内存管理、缓存机制、虚拟内存和物理内存等概念。 内存是所有程序的共享资源，当某块内存被某个程序占用时，则无法被其他程序同时使用了。因此在数据结 构与算法的设计中，内存资源是一个重要的考虑因素

3 列表 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.4 内存与缓存 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.5 小结 . . . . . 如果感觉以下内容理解困难，可以在读完“栈”章节后再来复习。 那么，迭代和递归具有什么内在联系呢？以上述递归函数为例，求和操作在递归的“归”阶段进行。这意味 着最初被调用的函数实际上是最后完成其求和操作的，这种工作机制与栈的“先入后出”原则异曲同工。 事实上，“调用栈”和“栈帧空间”这类递归术语已经暗示了递归与栈之间的密切关系。 1. 递：当函数被调用时，系统会在“调用栈”上为该函数分配新的栈帧，用于存储函数的局部变量、参数、 。有了这些地址，程序便可以访问内存中的数据。 图 3‑2 内存条、内存空间、内存地址 Tip 值得说明的是，将内存比作 Excel 表格是一个简化的类比，实际内存的工作机制比较复杂，涉及地址 空间、内存管理、缓存机制、虚拟内存和物理内存等概念。 内存是所有程序的共享资源，当某块内存被某个程序占用时，则通常无法被其他程序同时使用了。因此在数 据结构与算法的设计中，内存资源是一个重要的考虑

里构建，即： make -C build -j4 // 调用本地的构建系统执行 install 这个目标，即安 装 -D 选项：指定配置变量（又称缓存变量） • 可见 CMake 项目的构建分为两步： • 第一步是 cmake -B build ，称为配置阶段（ configure ），这时只检测环境并生成构建规则 • 会在 build 目录下生成本地构建系统能识别的项目文件（ Makefile 或是 .sln ） • 第二步是 cmake --build build ，称为构建阶段（ build ），这时才实际调用编译器来编译代码 • 在配置阶段可以通过 -D 设置缓存变量。第二次配置时，之前的 -D 添加仍然会被保留。 • cmake -B build -DCMAKE_INSTALL_PREFIX=/opt/openvdb-8.0 • ↑ 设置安装路径为 /opt/openvdb-8 -DCMAKE_BUILD_TYPE=Release • ↑ 设置构建模式为发布模式（开启全部优化） • cmake -B build ← 第二次配置时没有 -D 参数，但是之前的 -D 设置的变量都会被保留 • （此时缓存里仍有你之前定义的 CMAKE_BUILD_TYPE 和 CMAKE_INSTALL_PREFIX ） -G 选项：指定要用的生成器 • 众所周知， CMake 是一个跨平台的构建系统，可以从 CMakeLists

10 作为初始容量。 ‧ 数量记录：需要声明一个变量 size ，用来记录列表当前有多少个元素，并随着元素插入与删除实时更 新。根据此变量，可以定位列表的尾部，以及判断是否需要扩容。 ‧ 扩容机制：插入元素有可能导致超出列表容量，此时需要扩容列表，方法是建立一个更大的数组来替换 当前数组。需要给定一个扩容倍数 extendRatio ，在本示例中，我们规定每次将数组扩容至之前的 2 倍。 out_of_range(" 索引越界"); nums[index] = num; } /* 尾部添加元素 */ void add(int num) { // 元素数量超出容量时，触发扩容机制 if (size() == capacity()) extendCapacity(); nums[size()] = num; // 更新元素数量 numsSize++; } /* 中间插入元素 index, int num) { if (index < 0 || index >= size()) throw out_of_range(" 索引越界"); // 元素数量超出容量时，触发扩容机制 if (size() == capacity()) extendCapacity(); // 索引 i 以及之后的元素都向后移动一位 for (int j = size() - 1; j >=

编译器如何自动优化：从汇编角度看 C++ 5.C++11 起的多线程编程：从 mutex 到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 显然不是。甚至在两个处理器上同时运行两个线程也不见得可以获得两倍的性能。相似的 ，大多数多线程的应用不会比双核处理器的两倍快。他们应该比单核处理器运行的快，但 是性能毕竟不是线性增长。 • 为什么无法做到呢？首先，为了保证缓存一致性以及其他握手协议需要运行时间开销。在 今天，双核或者四核机器在多线程应用方面，其性能不见得的是单核机器的两倍或者四倍。 这一问题一直伴随 CPU 发展至今。 并发和并行的区别 • 运用多线程的方式和动机，一般分为两种。 ：每个线程一个任务队列，做完本职工作后可以认领其他线程的任务 工作窃取法（ work-stealing ） 原始的单一任务队列 解决 4 ：随机分配法（通过哈希函数或线性函数） • 然而队列的实现较复杂且需要同步机制，还是有一 定的 overhead ，因此另一种神奇的解法是： • 我们仍是分配 4 个线程，但还是把图像切分为 16 份。然后规定每一份按照 xy 轴坐标位置编号，比 如 (1,3) 等。

10 作为初始容量。 ‧ 数量记录：需要声明一个变量 size ，用来记录列表当前有多少个元素，并随着元素插入与删除实时更 新。根据此变量，可以定位列表的尾部，以及判断是否需要扩容。 ‧ 扩容机制：插入元素有可能导致超出列表容量，此时需要扩容列表，方法是建立一个更大的数组来替换 当前数组。需要给定一个扩容倍数 extendRatio ，在本示例中，我们规定每次将数组扩容至之前的 2 倍。 out_of_range(" 索引越界"); nums[index] = num; } /* 尾部添加元素 */ void add(int num) { // 元素数量超出容量时，触发扩容机制 if (size() == capacity()) extendCapacity(); nums[size()] = num; // 更新元素数量 numsSize++; } /* 中间插入元素 index, int num) { if (index < 0 || index >= size()) throw out_of_range(" 索引越界"); // 元素数量超出容量时，触发扩容机制 if (size() == capacity()) extendCapacity(); // 索引 i 以及之后的元素都向后移动一位 for (int j = size() - 1; j >=

hello‑algo.com 60 ‧ 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和 后一个网页。双向链表的特性使得这种操作变得简单。 ‧ LRU 算法：在缓存淘汰算法（LRU）中，我们需要快速找到最近最少使用的数据，以及支持快速地添 加和删除节点。这时候使用双向链表就非常合适。 循环链表常被用于需要周期性操作的场景，比如操作系统的资源调度。 ‧ 时 实时更新。根据此 变量，我们可以定位列表尾部，以及判断是否需要扩容。 ‧ 扩容机制：插入元素时可能超出列表容量，此时需要扩容列表。扩容方法是根据扩容倍数创建一个更大 的数组，并将当前数组的所有元素依次移动至新数组。在本示例中，我们规定每次将数组扩容至之前的 2 倍。 本示例旨在帮助读者直观理解列表的工作机制。实际编程语言中，列表实现更加标准和复杂，各个参数的设 定也非常有考究，例如初始 out_of_range(" 索引越界"); nums[index] = num; } /* 尾部添加元素 */ void add(int num) { // 元素数量超出容量时，触发扩容机制 if (size() == capacity()) extendCapacity(); nums[size()] = num; // 更新元素数量 numsSize++; } /* 中间插入元素

优化数据结构的操作效率。 ‧ 空间效率高: 数组为数据分配了连续的内存块，无须额外的结构开销。 ‧ 支持随机访问: 数组允许在 ?(1) 时间内访问任何元素。 ‧ 缓存局部性: 当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓 存来提升后续操作的执行速度。 连续空间存储是一把双刃剑，其存在以下缺点。 ‧ 插入与删除效率低: 当数组中元素较多时，插入与删除操作需要移动大量的元素。 此各种性质和 操作效率也呈现对立的特点。 第 4 章 数组与链表 hello‑algo.com 74 表 4‑1 数组与链表的效率对比 数组 链表 存储方式 连续内存空间 离散内存空间 缓存局部性 友好 不友好 容量扩展 长度不可变 可灵活扩展 内存效率 占用内存少、浪费部分空间 占用内存多 访问元素 ?(1) ?(?) 添加元素 ?(?) ?(1) 删除元素 ?(?) ?(1) 向父节点的引用来实现，类似于双向链表。 ‧ 浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和 后一个网页。双向链表的特性使得这种操作变得简单。 ‧ LRU 算法：在缓存淘汰算法（LRU）中，我们需要快速找到最近最少使用的数据，以及支持快速地添 加和删除节点。这时候使用双向链表就非常合适。 循环链表常被用于需要周期性操作的场景，比如操作系统的资源调度。 ‧ 时