. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 元组基本操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 运行期索引 . . . . . . . . . . . . . . . . . . . . . . 66 7.5 原子操作与内存模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 原子操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 9.2 noexcept 的修饰和操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 9.3 字面量 . . . . .

同理，还有 cudaMemcpyHostToDevice 和 cudaMemcpyDeviceToDevice 。 cudaMemcpy 会自动同步！ • 注意： cudaMemcpy 会自动进行同步操作 ，即和 cudaDeviceSynchronize() 等价！ 因此前面的 cudaDeviceSynchronize() 实 际上可以删掉了。 统一内存地址技术（ Unified Memory allocate/deallocate 成员函数的类，这样就可以“骗过” vector ， 让他不是在 CPU 内存中分配，而是在 CUDA 的统一内存 (managed) 上分配。 • 实际上这种“骗”来魔改类内部行为的操作，正是现代 C++ 的 concept 思想所在。因此替换 allocator 实际上是标准库允许的 ，因为他提升了标准库的泛用性。 进一步：避免初始化为 0 • vector 在初始化的时候（或是之后 C++03 ， B 站 / 油管偶尔翻出几个介绍 C++11 新特性的视频已经算很先进很前卫了，然而现在 C++23 的标准都已经开始往官网上挂了…… 第 7 章：原子操作 经典案例：数组求和 • 如何并行地对数组进行求和操作？ • 首先让我们试着用串行的思路来解题。 • 因为 __global__ 函数不能返回值，只能 通过指针。因此我们先分配一个大小为 1 的 sum 数组，其中

std::milli> 的别名 跨平台的 sleep ： std::this_thread::sleep_for • 可以用 std::this_thread::sleep_for 替代 Unix 类操作系统专有的的 usleep 。他可 以让当前线程休眠一段时间，然后继续。 • 而且单位也可以自己指定，比如这里是 milliseconds 表示毫秒，也可以换成 microseconds • 除了接受一个时间段的 sleep_for ，还有 接受一个时间点的 sleep_until ，表示让当 前线程休眠直到某个时间点。 第 1 章：线程 进程与线程 • 进程是一个应用程序被操作系统拉起来加载到内存之后从开始执行到执行结束的这样一个 过程。简单来说，进程是程序（应用程序，可执行文件）的一次执行。比如双击打开一个 桌面应用软件就是开启了一个进程。 • 线程是进程中的一个实 我们的程序常常需要同时处理多个任务。 • 例如：后台在执行一个很耗时的任务，比 如下载一个文件，同时还要和用户交互。 • 这在 GUI 应用程序中很常见，比如浏览 器在后台下载文件的同时，用户仍然可以 用鼠标操作其 UI 界面。 没有多线程：程序未响应 • 没有多线程的话，就必须等文件下载完了 才能继续和用户交互。 • 下载完成前，整个界面都会处于“未响应”状 态，用户想做别的事情就做不了。 现代

以有的指针被重复分配了两遍，写入了那个地址却没有实际被存到 m_data 这个指针数组里。因此结果不对，还造成了内存泄露。 解决：使用互斥量和原子变量 暴力解决方案就是用 std::mutex 避免多个线程同时访问。 然而这样会严重影响性能，锁和原子多了，就根本并行不起来。 教科书式的解决：二次判断法 这样如果 block 已经非空，则可以不用上锁，减少上锁次数。 如果 block 为空，则上锁；再次检测是否为空，空则分配内存， ）不一定就是完美解决方案，要根据实际情况判断。 真正的解决： tbb::spin_mutex 其实主要的瓶颈在于 std::mutex 会切换到操作系统内核中去调度 ，非常低效。而 tbb::spin_mutex 则是基于硬件原子指令的，完全 用户态的实现。区别： std::mutex 的陷入等待会让操作系统挂起 该线程，以切换到另一个；而 tbb::spin_mutex 的陷入等待是通过 不断地 while (locked); uantaichi.pdf ← ？？？ 第 7 章： SPGrid 操作系统管理内存的最小单位：页（ 4KB ） • 当调用 malloc 时，操作系统并不会实际分配那一块内存，而是将这一段内存标记为“不可 用”。当用户试图访问（写入）这一片内存时，硬件就会触发所谓的缺页中断（ page fault ），进入操作系统内核，内核会查找当前进程的 malloc 历史记录。如果发现用户写 入的地址是他曾经

发现了吗？其实不管是 size/resize 这样的 get/set 模式也好；自定义的拷贝构造函数 也好； RAII 保证异常安全也好；都是在为 面向对象思想的“封装：不变性”服务。 • 即：保证任何单个操作前后，对象都是处于 正确的状态，从而避免程序读到错误数据 （如空悬指针）的情况。 三五法则：拷贝赋值函数 • 区分两种拷贝可以提高性能。 • int x = 1; // 拷贝构造函数 里，常常听到这样的说法： • “ 释放一个指针后，必须把这个指针设为 NULL ， 防止空悬指针！” • delete p; • p = nullptr; • unique_ptr 则把他们封装成一个操作：只需要 • p = nullptr; // 等价于： p.reset() • 即可。也不会保留着一个空悬指针，体现了面向 对象“封装：不变性”的思想。 unique_ptr ：禁止拷贝 用了原始指针（假定他释放前我必然被释 放）。因为因此我们完全可以把 m_child 变成一个标志这“完全所有权”的 unique_ptr 。 • 这样也不需要 shared_ptr 维护一个原子 计数器的开销了。 休息一下……再想想？ • 接下来你会发现，在智能指针的管理下，某些类型的对象并不是总是需要用到拷贝和移动 。 三五法则：什么时候需要担心 • 一般来说，可以认为符合三五法则的类型是安全的。

做文章，比如要重复 eatFood 两遍。 • 就可以封装到一个函数 eatTwice 里，这个函数只需接受他们共同的基类 IObject 作为参数，然后调 用 eatFood 这个虚函数来做事（而不是直接操作具体的猫和狗本身）。 • 这样只需要写一遍 eatTwice ，就可以对猫和狗都适用，实现代码的复用（ dont-repeat-yourself ）， 也让函数的作者不必去关注点从猫和狗的其他具 类型擦除：还是以猫和狗为例 • 就这样，小彭老师根本不用修改 Cat 和 Dog 的定义 ，就能随意地把 speak 封装为多态的虚函数。只要语 义上一样，也就是函数名字一样，就可以用这个办法 随意转换任意依赖于操作为虚函数。 • 实际上 std::any 也是一个类型擦除的容器…… • 这里我们的 Animal 擦除了 speak 这个成员函数， 而 std::any 实际上是擦除了拷贝构造函数和解构函数 。 • （把 sort 封装成虚函数，留作回家作业） Zeno 中对 OpenVDB 的类型擦除 • 结合类型擦除技术，自动虚克隆技术。 • VDBGrid 作为所有网格类的基类提供各个 操作做为虚函数， VDBGridWrapper 则是 那个实现了擦除的包装类。 Zeno 节点系统 • 节点在 Zeno 中所扮演的角色，实际上相当于函数式编程中的函数。 • 节点输入若干个对象，并输出若干个对象。

今天，双核或者四核机器在多线程应用方面，其性能不见得的是单核机器的两倍或者四倍。 这一问题一直伴随 CPU 发展至今。 并发和并行的区别 • 运用多线程的方式和动机，一般分为两种。 • 并发：单核处理器，操作系统通过时间片调 度算法，轮换着执行着不同的线程，看起来 就好像是同时运行一样，其实每一时刻只有 一个线程在运行。目的：异步地处理多个不 同的任务，避免同步造成的阻塞。 • 并行：多核处理器，每个处理器执行一个线 互。并在主线程中等待该任务组里的任务 全部执行完毕。 • 区别在于，一个任务不一定对应一个线程 ，如果任务数量超过 CPU 最大的线程数， 会由 TBB 在用户层负责调度任务运行在 多个预先分配好的线程，而不是由操作系 统负责调度线程运行在多个物理核心。 封装好了： parallel_invoke 更好的例子 第 1 章：并行循环 时间复杂度（ time-efficiency ）与工作量复杂度（ work-efficiency 核心数量，让系统调度保证各个核心始终饱和 • 因此，最好不是按照图像大小均匀等分，而是按照工 作量大小均匀等分。然而工作量大小我们没办法提前 知道……怎么办？ • 最简单的办法：只需要让线程数量超过 CPU 核心数量 ，这时操作系统会自动启用时间片轮换调度，轮流执 行每个线程。 • 比如这里分配了 16 个线程，但是只有 4 个处理器核心。 那么就会先执行 1,2,3,4 号线程，一段时间后自动切换 到 5,6,7

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 8.2. 建堆操作 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.3. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 9.2. 图基础操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.3. 图的遍历 . . 包括推算 方法、常见类型、示例等。 ‧ 数据结构：常用的基本数据类型，数据在内存中的存储方式、数据结构分类方法。数组、链表、栈、队列、 散列表、树、堆、图等数据结构，内容包括定义、优劣势、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：查找算法、排序算法、搜索与回溯、动态规划、分治算法，内容包括定义、使用场景、优劣势、时 空效率、实现方法、示例题目等。 0. 写在前面 hello‑algo

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 8.2. 建堆操作 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 8.3. 小结 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 9.2. 图基础操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.3. 图的遍历 . . 包括推算 方法、常见类型、示例等。 ‧ 数据结构：常用的基本数据类型，数据在内存中的存储方式、数据结构分类方法。数组、链表、栈、队列、 散列表、树、堆、图等数据结构，内容包括定义、优劣势、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：查找算法、排序算法、搜索与回溯、动态规划、分治算法，内容包括定义、使用场景、优劣势、时 空效率、实现方法、示例题目等。 0. 写在前面 hello‑algo

堆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 8.2 建堆操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 8.3 Top‑k 问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 9.2 图的基础操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 9.3 图的遍历 . . . . . 复杂度分析：数据结构和算法的评价维度与方法。时间复杂度和空间复杂度的推算方法、常见类型、示 例等。 ‧ 数据结构：基本数据类型和数据结构的分类方法。数组、链表、栈、队列、哈希表、树、堆、图等数据 结构的定义、优缺点、常用操作、常见类型、典型应用、实现方法等。 ‧ 算法：搜索、排序、分治、回溯、动态规划、贪心等算法的定义、优缺点、效率、应用场景、解题步骤 和示例问题等。 第 0 章 前言 hello‑algo.com