有了无边界的稀疏网格，再也不用担心二维数组要分配多大了。 坐标可以无限延伸，甚至可以是负数！比如 (-1,2) 等…… 他会自动在写入时分配 16x16 的子网格，称之为叶节点 (leaf node) ，而这里的 unordered_map 就是充当根节点 (root node) 。 图片解释稀疏的好处 传统稠密二维数组 无边界稀疏分块哈希表 此外，还是按需分配内存，即使被写入的部分奇形怪状也不会浪费内存。 浪费内存。 这些被写入的部分被称为激活元素 (active element) ，反之则是未激活 (inactive) 。 这就是稀疏的好处，按需分配，自动扩容。 分块则是利用了我们存储的数据常常有着空间局域性的特点，减轻哈希表的压 力，同时在每个块内部也可以快乐地 SIMD 矢量化， CPU 自动预取之类的。 第 2 章：位运算 稀疏的好处：坐标可以是负数 这样即使坐标为负数，或者可以是任意大的坐标，都不会产生越界错误。 结构。 • 下面这个例子中的稀疏数据结构，用这种语言可以表示为 hash().pointer(11).dense(8) 。 封装起来，方便多层解耦 封装起来，方便多层解耦 封装起来，方便多层解耦 封装起来，方便多层解耦 封装起来，方便多层解耦 • 这样就封装好了，通过模板的方式实现了 自定义的稀疏数据结构： • hash().pointer(11).dense(8) 开源的体素处理库：

全部执行完毕。 • 区别在于，一个任务不一定对应一个线程 ，如果任务数量超过 CPU 最大的线程数， 会由 TBB 在用户层负责调度任务运行在 多个预先分配好的线程，而不是由操作系 统负责调度线程运行在多个物理核心。 封装好了： parallel_invoke 更好的例子 第 1 章：并行循环 时间复杂度（ time-efficiency ）与工作量复杂度（ work-efficiency 是元素个数 并行映射 4 个线程，每人处理 2 个元素的映射，花了 2 秒 用电量： 4*2=8 度电 结论：并行映射的时间复杂度为 O(n/c) ，工作复杂度为 O(n) ，其中 c 是线程数量 封装好了： parallel_for 面向初学者： parallel_for 基于迭代器区间： parallel_for_each 二维区间上的 for 循环： blocked_range2d 三维区间上的 log2(n) 次并行 for 即可完成 缩并。 • 这种常用于核心数量很多，比如 GPU 上 的缩并。 结论：改进后的并行缩并的时间复杂度为 O(logn) ，工作复杂度为 O(n) 。 封装好了： parallel_reduce 保证每次运行结果一致： parallel_deterministic_reduce 并行缩并的额外好处：能避免浮点误差，例如求平均值 扫描（ scan ）

container ） C++ 标准库五大件：迭代器（ iterator ） C++ 标准库五大件：算法（ algorithm ） C++ 标准库五大件：仿函数（ functor ） C++ 标准库五大件：分配器（ allocator ） 侯捷 STL 侯捷 STL vector 容器 vector 容器：构造函数 • vector 的功能是长度可变的数组，他里面的数据 存储在堆上。 • vector 的目标长度大于原有的容量时， 就需要重新分配一段更大的连续内存，并 把原数组长度的部分移动过去，多出来的 部分则用 0 来填充。这就导致元素的地址 会有所改变，从而过去 data 返回的指针 以及所有的迭代器对象，都会失效。 vector 容器： resize 到更小尺寸不会导致 data 失效 • 当 resize 的目标长度小于原有的容量时， 不需要重新分配一段连续的内存也不会造 成元素的移动（这个设计是为了性能考 ，因此重新扩容到 5 是不需要重 新分配内存的，也就不会移动元素导致指 针失效。 vector 容器： capacity 函数查询实际的最大容量 • 可以用 capacity() 函数查询已经分配内存的大小，即最大容 量。 • 而 size() 返回的其实是已经存储了数据的数组长度。 • 可以发现当 resize 指定的新长度一个超过原来的最大容量时 时，就会重新分配一段更大容量的内存来存储数组，只有这时

C++20 作为扩展阅读。 C++ 有哪些面向对象思想？ C++ 思想：封装 比如要表达一个数组，需要：起始地址指针 v ，数组大小 nv 将多个逻辑上相关的变量包装成一个类 因此 C++ 的 vector 将他俩打包起来，避免程序员犯错 封装：不变性 比如当我要设置数组大小为 4 时，不能只 nv = 4 还要重新分配数组内存，从而修改数组起始地址 v 常遇到：当需要修改一个成员时，其他也成员需要被修改，否则出错 常遇到：当需要修改一个成员时，其他也成员需要被修改，否则出错 这种情况出现时，就意味着你需要把成员变量的读写封装为成员函数 不变性：请勿滥用封装 • 仅当出现“修改一个成员时，其他也成员要 被修改，否则出错”的现象时，才需要 getter/setter 封装。 • 各个成员之间相互正交，比如数学矢量类 Vec3 ，就没必要去搞封装，只会让程序员 变得痛苦，同时还有一定性能损失：特别 是如果 getter/setter ，我们还是需要实现一下的。 • 发现了吗？其实不管是 size/resize 这样的 get/set 模式也好；自定义的拷贝构造函数 也好； RAII 保证异常安全也好；都是在为 面向对象思想的“封装：不变性”服务。 • 即：保证任何单个操作前后，对象都是处于 正确的状态，从而避免程序读到错误数据 （如空悬指针）的情况。 三五法则：拷贝赋值函数 • 区分两种拷贝可以提高性能。 • int

就像你和同学随手“拉钩”定下的约定，这是 printf 约定俗成的。 • \ 就像正式合同，有法律效力的，这是 C 语言编译器规定好的。 C++ 字符串类 第 3 章 C 语言字符串操作繁琐 封装的 std::string 应运而生 封装的 std::string 应运而生 • string 可以从 const char * 隐式构造： • string s = “hello”; • string 具有 + 、 类型的，他们没有 + 运算 符。 • C++ 为了向前兼容，没办法改变 C 语言的这项规定，只能退而求其次，他另 外定义了一个 string 类，重载了 + 运算符，并告诉同学们：以后尽量用我这 个封装好的类，不要直接用 C 语言的 const char * 。 • 因此如果需要把两个字符串加在一起，就必须至少有一方是 string 才行。 • 可以用 string(“hello”) 这种形式包裹住每个字符串常量，这样就方便用 正确： C++14 新特性：自定义字面量后缀 • 不少同学就觉得这样好麻烦，其他语言都是直接 “ hello” 就是字符串类 型， C++ 还得套一层壳 string(“hello”) 才能变成安全封装的类型，才能用他 的成员函数。 • 因此， C++14 引入了一项缓解“键盘压力”的新特性： • 写 “ hello”_s 就相当于写 operator“”_s(“hello”, 5) ，就相当于

2667*16*2=42672 MB/s • 那么，频率相同的情况下，可以考虑插两块 8GB 的内存， 比插一块 16GB 的内存更快，不过价格可能还是翻倍的。 • 系统会自动在两者之间均匀分配内存，保证读写均匀分配 到两个内存上，实现内存的并行读写，这和磁盘 RAID 有 一定相似之处。 验证一下刚刚的 parallel_add 是不是用足了全部带宽 • 刚刚 a 数组的大小是 1024 MB 等待数据抵达前空转浪费时间。 页对齐的重要性 • 为什么要 4KB ？原来现在操作系统管理内存是用分页 （ page ），程序的内存是一页一页贴在地址空间中的， 有些地方可能不可访问，或者还没有分配，则把这个页设 为不可用状态，访问他就会出错，进入内核模式。 • 因此硬件出于安全，预取不能跨越页边界，否则可能会触 发不必要的 page fault 。所以我们选用页的大小，因为本 来就不 同学们可以课后研究一下。 第 5 章：内存分配与分页 vector ：写入两次，时间都是一样的（理所当然） malloc ：写入两次，第一次明显比第二次慢？ new int[n] ：和 malloc 一样，写入两次，第一次明显比第二次慢？ new int[n]{} ：后面加个花括号，就和 vector 一样，两次一样快了 结论 • 原理，当调用 malloc 时，操作系统并不会实际分配那一块内存，而是将这一段内存标记

小端序的电脑会得到 0x04030201 。 动态数组的分配与释放 如果不是固定长度为 4 的数组呢？ • 刚才的 char a[4] ，数组的长度是一个编译期常 量。如果不是常量呢？ • 比如 char a[n] ，在 gcc 上居然是可以编译通 过的，这是因为他调用了 gcc 特有的 alloca(n) 函数，会在当前函数的栈上分配内存，函数退出 时也会自动释放。 如果不是固定长度为 DIDU_KNOW_THAT_MICROPIG_BUYS_GITHUB 使用 malloc 函数：在堆上分配内存，实现动态数组 • 栈上不能动态分配内存，堆上就可以！ • char a[4] 可以在编译期确定一片栈上的连 续内存，大小为 4 字节， 4 必须是常量 。 • 而调用 stdlib.h 的 malloc(n) 就可以从堆 上分配一段 n 字节的连续内存，这里的 n 就可以不是常量了。 • 栈上的内存会在函数退出时自动释放，而 。 动态数组作为函数参数？不仅要传首地址，还要传数组长度！ • 刚才说定长数组（长度是编译期常量，在栈上分 配的）只需一个起始地址就能确定。 • 而动态长度的数组（通过 malloc 在堆上分配 的）就需要起始地址和数组长度两个，才能确定 下来，也就是 char * 和 int 两个。 • 所以要把动态数组的引用传给函数，需要有两个 参数，一个指针加一个长度。 使用 const 修饰指针指向的值

字。这里显示错误号为 77 ，具体名字是 cudaErrorIllegalAddress 。意思是我们访问了非法的地 址，和 CPU 上的 Segmentation Fault 差不多。 封装好了： helper_cuda.h • 其实 CUDA toolkit 安装时，会默认附带一系列案例代码， 这些案例中提供了一些非常有用的头文件和工具类，比如这 个文件： • /opt/cu ize()) • 即可自动帮你检查错误代码并打印在终端，然后退出。还会 报告出错所在的行号，函数名等，很方便。 堆上分配试试？ • 那你可能会想，难道是因为我的 ret 创建 在栈上，所以 GPU 不能访问，才出错的 ？ • 于是你试图用 malloc 在堆上分配一个 int 来给 GPU 访问，结果还是失败了。 原因： GPU 使用独立的显存，不能访问 CPU 内存 • 原来， (host) 。 GPU 使 用的内存称为设备内存 (device) ，他是显卡上板载 的，速度更快，又称显存。 • 而不论栈还是 malloc 分配的都是 CPU 上的内存 ，所以自然是无法被 GPU 访问到。 • 因此可以用用 cudaMalloc 分配 GPU 上的显存， 这样就不出错了，结束时 cudaFree 释放。 • 注意到 cudaMalloc 的返回值已经用来表示错误代 码，所以返回指针只能通过

mming-guide/index.html#texture-and-surface-memory CUDA 多维数组：封装 • cudaMalloc3DArray 用于分配一个三维数组。 各维度上的大小通过 cudaExtent 指定，方 便起见我们的 C++ 封装类用了 uint3 表示 大小。 • GPU 的多维数组有特殊的数据排布来保障 访存的高效，和我们 CPU 那样简单地行主 序或列主序（如 a[x + nx * y] ）的多维数组 不一样。 • 随后可用 cudaMemcpy3D 在 GPU 的三 维数组和 CPU 的三维数组之间拷贝数据。 CUDA 表面对象：封装 • 要访问一个多维数组，必须先创建一个表面对象 （ cudaSurfaceObject_t ）。 • 考虑到多维数组始终是需要通过表面对象来访问的，这 里我们让表面对象继承自多维数组。 • 弄一个访问者类 CudaSurfaceAccessor ，不管理资源 ，仅仅是指向资源的一个弱引用，可以随意拷贝。并把 读写访问的方法（ surf3Dread ）定义在访问者类。 CUDA 表面对象：封装 • 此外，表面对象还支持自动判断 x,y,z 坐标是否越界 ， surf3Dread/write 的最后一个参数，用于指定出现 越界时要采取的行动： • cudaBoundaryModeTrap

内存之后从开始执行到执行结束的这样一个 过程。简单来说，进程是程序（应用程序，可执行文件）的一次执行。比如双击打开一个 桌面应用软件就是开启了一个进程。 • 线程是进程中的一个实体，是被系统独立分配和调度的基本单位。也有说，线程是 CPU 可 执行调度的最小单位。也就是说，进程本身并不能获取 CPU 时间，只有它的线程才可以。 • 从属关系：进程 > 线程。一个进程可以拥有多个线程。 • std::vector • 刚才说了， vector 不是多线程安全的容器 。 • 多个线程同时访问同一个 vector 会出现 数据竞争（ data-race ）现象。 封装一个线程安全的 vector • 因此，可以用一个类封装一下对 vector 的访问，使其访问都受到一个 mutex 的 保护。 • 然而却出错了：因为 size() 是 const 函 数，而 mutex::lock() • 生产者：厨师，往 foods 队列里推送食品 ，推送后会通知消费者来用餐。 • 消费者：等待 foods 队列里有食品，没有 食品则陷入等待，直到被通知。 条件变量：将 foods 队列封装成类 std::condition_variable 小贴士 1. std::condition_variable 仅仅支持 std::unique_lock 作为 wait