通常来说，并行只能加速计算的部分，不能加速内存读写的部分 。 • 因此，对 fill 这种没有任何计算量，纯粹只有访存的循环体，并 行没有加速效果。称为内存瓶颈（ memory-bound ）。 • 而 sine 这种内部需要泰勒展开来计算，每次迭代计算量很大的 循环体，并行才有较好的加速效果。称为计算瓶颈（ cpu- bound ）。 • 并行能减轻计算瓶颈，但不减轻内存瓶颈，故后者是优化的重点 1024 并非随意选取，而是要让每 个属性 SOA 数组的大小为一个页 （ 4KB ）才能最高效，原因稍后会说明。 AOSOA ：注意，内部 SOA 的尺寸不宜太小 如果内部 SOA 太小，内部循环只有 16 次连续的读 取， 16 次结束后就会跳跃一段，然后继续连续的 读取。这会导致 CPU 预取机制失效，无法预测下 一次要读哪里，等发现跳跃时已经来不及了，从而 计算的延迟无法隐藏。 如果每个属性都要访问到，那还是 解的伪代码，延迟和花费的时钟周期等。 第 4 章：循环合并法 两个循环体 • 原始的代码第一个循环体执行 a[i] = a[i] * 2 ，等乘法全 部结束了以后，再来一个循环体执行 a[i] = a[i] + 1 。 • 因为第一遍循环过了 1GB 的数据，执行到 a[n-1] 时 ，原本 a[0] 处的缓存早已失效，因此第二遍循环开始 读取 a[0] 时必须重新从主内存读取，然后再次写回主

movups 变成了 movaps 对齐的读写可能 带来微乎其微的 性能提升…… 数组求和： reduction 的优化 你看懂了吗？没关系！小彭老师也没看 懂！总之非常高效就对了！ 第 5 章：循环 循环中的矢量化：还在伺候指针别名 我们可怜的编译器啊！他还在担心 a 和 b 指向的数组是否有重合。 考虑 func(a, a + 1) 的情况，那样会产生数据依赖链，没法 SIMD 化 。 为了优化而不失正确性，他索性生成两份代码： SIMD 版本高效运行。 2. 如果重叠，则跳转到标量版本低效运行，但至少不会错。 SIMD 版 标量版 循环中的矢量化：解决指针别名 所以，让我们加上 __restrict 关键字，打消编译器的顾虑！ 这下只需要生成一个 SIMD 版本了，没有了运行时判断重叠的焦虑。 SIMD 版 循环中的矢量化： OpenMP 强制矢量化 除了可以用 __restrict 让编译器放心做 SIMD 优化外，还可以用 这个选项。 循环中的矢量化：编译器提示忽略指针别名 • 除了可以用 __restrict ， #pragma omp simd 外，对于 GCC 编译器还可以用： • #pragma GCC ivdep • 表示忽视下方 for 循环内可能的指针别名现象 。 • 不同的编译器这个 pragma 指令不同，这里只 是拿 GCC 举例，其他编译器请自行查找资料 。 循环中的 if 语句：挪到外面来

for 循环是串行的，我们可以把线 程数量调为 n ，然后用 threadIdx.x 作为 i 索引。这样就实现了，每个线程负责给数 组中一个元素的赋值。 小技巧：网格跨步循环（ grid-stride loop ） • 无论调用者指定了多少个线程 （ blockDim ），都能自动根据给定的 n 区间循环，不会越界，也不会漏掉几个元 素。 • 这样一个 for 循环非常符合 ，如果超过就要提前退出，防止越界 。 网格跨步循环：应用于线程和板块一起上的情况 • 网格跨步循环实际上本来是这样，利用扁平 化的线程数量和线程编号实现动态大小。 • 同样，无论调用者指定每个板块多少线程 （ blockDim ），总共多少板块（ gridDim ）。 都能自动根据给定的 n 区间循环，不会越界 ，也不会漏掉几个元素。 • 这样一个 for 循环非常符合 CPU 上常见的 parallel 看右边，这就是为什么我们用于 x_host 那 个 for_each 的 lambda 没有修饰，而用于 x_dev 的那个 lambda 需要修饰 __device__ 。 for_each 用于整数的循环： counting_iterator • 可以用 thrust::make_counting_iterator(num) 构建一个计数迭代器，他作为区间表示的就是 整数的区间。 合并多个迭代器为一个：

程，真正的同时运行。目的：将一个任务分 派到多个核上，从而更快完成任务。 举个例子 • 并发：某互联网公司购置了一台单核处理 器的服务器，他正同时处理 4 个 HTTP 请求，如果是单线程的 listen-accept 循环 ，则在处理完 A 的请求之前， B 的请求 就无法处理，造成“无响应”现象。 C 的请 求进来，则还得继续排队…… • 每个请求开启一个线程来处理，这样处理 A 用户的同时还可以继续监听 会由 TBB 在用户层负责调度任务运行在 多个预先分配好的线程，而不是由操作系 统负责调度线程运行在多个物理核心。 封装好了： parallel_invoke 更好的例子 第 1 章：并行循环 时间复杂度（ time-efficiency ）与工作量复杂度（ work-efficiency ） • 在“小学二年级”算法课里，我们学过复杂度的概念，意思是算法执行所花费的时间取决于数据量 是线程数量 封装好了： parallel_for 面向初学者： parallel_for 基于迭代器区间： parallel_for_each 二维区间上的 for 循环： blocked_range2d 三维区间上的 for 循环： blocked_range3d 所有区间类型 第 2 章：缩并与扫描 缩并（ reduce ） 1 个线程，依次处理 8 个元素的缩并，花了 7 秒 用电量：

也是负数，会造成对 m_block 的越界访问。 • 因此 % 会返回负数对 CFD 用户来说是个很大的坑点，很多人想当然地用 % 做循环边界， 然而这对负方向会不起作用。 解决： (a % b + b) % b • 我看一些 CFD 用户喜欢写 (a + b) % b 做循环边界 ，从而避免负方向上出错。然而这还是避免不了 a < -b 时的出错。 • 正确的写法是： (a % b + b) 用户态的实现。区别： std::mutex 的陷入等待会让操作系统挂起 该线程，以切换到另一个；而 tbb::spin_mutex 的陷入等待是通过 不断地 while (locked); 这样一个死循环不断轮询。对于我们高性 能计算而言 tbb::spin_mutex 更高效。其实 sizeof(std::mutex) = 40 字节，而 sizeof(tbb::spin_mutex) = 1 字节…… ，从而支持用 lambda 捕获的访问者模式。 实现访问者模式 • 额，总之就是每一层都有一个缓存。 第 5 章：量化整型 使用 int ：每个占据 4 字节 • 记得我第七课说过，一个简单的循环体往 往会导致内存成为瓶颈（ memory- bound ）。 • 右边就是一个很好的例子。 使用 int64_t ：每个占据 8 字节 • 如果用更大的数据类型，用时会直接提升两倍！ •

效率低，需要额外的一块管理内存，访问实际对象 需要二级指针，而且 deleter 使用了类型擦除技术 。 2. 全部用 shared_ptr ，可能出现循环引用之类的问题 ，导致内存泄露，依然需要使用不影响计数的原始 指针或者 weak_ptr 来避免。比如右边这个例子： 循环引用：解决方案 1 • 如何解决？只需要把其中逻辑上“不具有所 属权”的那一个改成 weak_ptr 即可： • 因为父窗口“拥有”子窗口是天经地义的，而 引用计数的问题…… 循环引用：解决方案 2 • 还有一种更适应“父子窗口”这一场景的解决 方案。刚才提到原始指针的应用场景是“当 该对象不属于我，但他释放前我必然被释 放时”。这里我们可以发现父窗口的释放必 然导致子窗口的释放。因此我们完全可以 把 m_parent 变成原始指针。 • 这样也不需要 weak_ptr 判断是否 expired() 了。 循环引用：解决方案 2 （续）

函数先预留那么多的容量，等待接下来的推入 。 • 这样之后 push_back 时，就不会一次次地扩容两倍慢 慢成长到 128 ，避免重新分配内存和移动元素，更高效 。 • 比如这里我们可以提前知道循环会执行 100 次，因此 reserve(100) 就可以了。 • 可以看到只有一次 malloc(400) ，之后那次 malloc(1024) 是 cout 造成的，不必在意。 vector 就是 begptr == endptr 的情况，非常容易判断。 • 更方便的是你可以通过指针的减法运算： endptr - begptr 来算出数组的长度！ • for 循环里也很容易写，判断是否继续循环 的条件为 ptr != endptr 就行了。 迭代器模式：首指针＋尾指针 • 还可以让首指针和尾指针声明为模板参数 ，这样不论指针是什么类型，都可以使用 print 这个模板函数来打印。 O(n²) 复杂度了？不 会哦， insert 的这个重载会一次性批量让 pos 之后的元素 移动 n 格，不存在反复移动 1 格的情况，最坏复杂度仍然 是 O(n) 。如果你自己写个 for 循环反复调 insert 那的确 是会 O(n²) 了，这就是为什么 insert 提供这个高效的重载 专门负责重复插入的操作。 • iterator insert(const_iterator pos

第二部分，也就是判断是否退出的条件： it != map.end() 判断是否抵达最右节点的下一个 。 • 第三部分，也就是每次循环后执行的更新语句： ++it 会让迭代器往下一个节点移动。 • 所以人话就是：从根节点出发，不断向下一个移动，直到没有节点可遍历了。 • 而 for 里面的循环体，会对每个不同的 it 执行一遍。 • 由于里面是 auto &[k, v] = *it; 而 it 的 operator* 所以 [k, v] 就会被 structural-binding 分别绑定到当前遍历到的元素的 K 和 V 上了。 • 然后从程序员的黑盒视角看来，就是对于所有 map 中的 K-V 对执行了一遍循环体。 迭代器 operator++ 的移动方向 • 迭代器的 ++ 是中根遍历，先左子节点，然后根节点，最后右子节点。 • 为什么是中根遍历？因为刚刚说了二叉排序树的规则是：左子节点＜父节点＜右子节点。 < ? 要找的数 set 查找为什么高效 • 刚刚移动到了节点 4 。 • 判断 4 < 4 ？额…他们相等！我找到 4 了，这就是我要找的节点，不用继续比较了。 • 成功找到 4 ，退出循环，返回指向 4 的迭代器。 2 1 4 5 8 7 4 4 < ? 要找的数 set 查找为什么高效 • 为什么二叉排序树 set 会比线性数组 vector 在查找这一点上更高效？

语言指针。 • 回想一下 C 语言咋遍历数组的： • int arr[n]; • for (int i = 0; i < n; i++) { • int value = arr[i]; • } • 循环的范围是 [0, n) 。 • 因为这里 arr[i] 等价于 *(arr + i) ，所以…… 复习 C 语言指针（ 2 ） • 上节课说了，迭代器就是在模仿 C 语言指针。 • 回想一下 C • for (int *p = arr; p < arr + n; p++) { • int value = *p; • } • 索性用 arr + i 作为迭代的变量，避免一次加法的开销。 • 循环的范围变成 [arr, arr + n) 。 复习 C 语言指针（ 3 ） • 上节课说了，迭代器就是在模仿 C 语言指针。 • 回想一下 C 语言咋遍历数组的： • int arr[n]; • (range-based for loop) 。 • for ( 类型 变量名 : 可迭代对象 ) • 这种写法，无非就是刚才 那一大堆代码的简写： set 的遍历 • 基于范围的 for 循环只是 一个简写，他会遍历整个 区间 [begin, end) 。 • 有时写完整版会有更大的 自由度，也就是说这里的 begin 和 end 可以替换 为其他位置的迭代器（如 find/lower_bound/upper_b

ng); reg.insert(“response_marshalling”.into(),response_marsh alling); } 自动化 HTTP 请求例子 自动化测试以循环方式执行 • Request 用了 http1x • foo_index! 里取 _i • 在 response_marshalling 里 foo_assert_eq!() fn request(_msg: get("data").unwrap_or(&mut NULL),&json!("hi"),"data is hi"); Ok(msg.to_vec()) } 自动化 HTTP 请求例子 自动化测试以循环方式执行 测验报告 HTML/ JSON 报告 Wasm Mock Server • 模拟数据规则 • 自动化测试 • 模拟数据规则 • 自动化测试 Some of its’ Host call