标来访 问，且提供了线性滤波的能力。 • 在核函数中可以通过 tex3D 来读取纹理中的值。 • 之所以纹理是因为 GPU 一开始是渲染图形的专用硬件 ，会用到一些贴图等，这就是二维的纹理。 • 当输入的浮点坐标不是整数时，由 GPU 硬件提供双线 性插值（ bilerp ），比手写的高效许多。 • 当然如果是三维数组，那就是三维纹理对象，访问时是 提供三线性插值（ trilerp 纹理对象：封装 • 其中 cudaTextureFilterMode 表示采样的坐标不是整数 时要如何在周围 8 个值之间插值，有以下几种选择： • cudaFilterModeLinear ：三线性插值更平滑（左图） • cudaFilterModePoint ：最接近的那个点作为值（右 图） 烟雾仿真系统：封装 • 我们统一通过 unique_ptr 来管理对象，这样尽管 CudaSurface 代码（二维定常流仿真），主要由 k-ye 编写 ，我学习 GAMES201 后贡献了支持 RK2 和 RK3 的版本。这里我们用高效的 CUDA 纹理对象 在 C++ 中重新实现了一遍，利用了硬件的三线性插值实现半拉格朗日（ semi-lagrangian ）对流。 对流部分：根据对流后位置重新采样 • 和 k-ye 思路不同的是我先在刚刚的 advect_kernel 算出对流后要采样的位置（

查找为什么低效 • vector 又称线性数组。在 vector 中查找元素可以用 头文件里的 std::find 。 • vector a = { 1, 4, 2, 8, 5, 7 }; • std::find(a.begin(), a.end(), 5); • 这个 std::find 就是标准库帮我们实现的线性数组中查找元素的算法，让我们用动画演示一 了，这就是我要找的节点，不用继续比较了。 • 成功找到 4 ，退出循环，返回指向 4 的迭代器。 2 1 4 5 8 7 4 4 < ? 要找的数 set 查找为什么高效 • 为什么二叉排序树 set 会比线性数组 vector 在查找这一点上更高效？ • 你看，我们刚才只判断了 3 次就找到了目标。这还是最坏的情况，最好只需要 1 次就够了。 • 最坏的情况需要判断多少次？最坏不会超过树的深度，而一棵有着 set map 第四章：哈希散列表 高效的查找离不开我 高效的查找离不开我 unordered_set 查找为什么高效 • 为什么哈希散列表 unorered_set 会比线性数组 vector 在查找这一点上更高效？ • 你看，我们刚才只判断了 3 次就找到了目标。这还是最坏的情况，最好只需要 1 次就够了。 • 最坏的情况需要判断多少次？最坏不会超过树的深度，而一棵有着

妙用本用于指针的指令，尽管此时 rdi 和 rsi 并不是指针 整数加常数乘整数：都可以被优化成 leal 因为这种线性变换在地址索引 中很常见，所以被 x86 做成 了单独一个指令。这里尽管不 是地址，但同样可以利用 lea 指令简化生成的代码大小。 eax = rdi + rsi * 8 指针访问对象：线性访问地址 rsi = (int64_t)esi eax = *(int *)(rdi + rsi * Struct of Array ）属性分离存储在多个数组 • xxxxyyyyzzzz • AOS 必须对齐到 2 的幂才高效， SOA 就不需要。 • AOS 符合直觉，不一定要存储在数组这种线性结构， 而 SOA 可能无法保证多个数组大小一致。 • SOA 不符合直觉，但通常是更高效的！ AOS ：紧凑存储多个属性 SIMD 矢量化失败！ 符合一般面向对象编程 (OOP) 的习惯，但常常不利于性能

时间复杂度更被看重 • 时间和空间复杂度不是对立的，可以协同 时间和空间复杂度 复杂度计算 • 大Ｏ标记法（数量级近似） • 用 AI 来估计 算步骤、算存储 Rust 基本数据结构复杂度 线性数据结构 非线性数据结构 总体来看，时间复杂度没有超过 O(n) 的！ Rust 实现数据结构 • 栈 • 链表 • Vec Rust 实现数据结 构 栈 借助 Vec 容器 泛型支持 Option

图平台 Atlas Studio Atlas Client 基础 设施 Docker/K8S/VM X86/ARM - 基于 RUST 语言保证性能优势 - 分布式架构性能可线性扩展 - 针对大规模图优化的存算引擎 - 配合 Atlas 图平台，实现无代码图分析 - Query 性能分析模块，启发式提示优化 - 内置多种分析函数，面向分析师友好 -MVOCC 保证事务一致性 体展现 可视化图探索分析 AtlasGraph 架构及实现 图技术简介 Takeway AtlasGraph 图数据库关键特性 - 基于 RUST 语言保证性能优势 - 分布式架构性能可线性扩展 - 针对大规模图的优化的存算引擎 - 配合 Atlas 图平台，实现无代码图分析 - Query 性能分析模块，启发式提示优化 - 内置多种分析函数，面向分析师友好 -MVOCC 保证事务一致性

的处理能力，是吗？ • 显然不是。甚至在两个处理器上同时运行两个线程也不见得可以获得两倍的性能。相似的 ，大多数多线程的应用不会比双核处理器的两倍快。他们应该比单核处理器运行的快，但 是性能毕竟不是线性增长。 • 为什么无法做到呢？首先，为了保证缓存一致性以及其他握手协议需要运行时间开销。在 今天，双核或者四核机器在多线程应用方面，其性能不见得的是单核机器的两倍或者四倍。 这一问题一直伴随 CPU 2 3 4 解决 3 ：每个线程一个任务队列，做完本职工作后可以认领其他线程的任务 工作窃取法（ work-stealing ） 原始的单一任务队列 解决 4 ：随机分配法（通过哈希函数或线性函数） • 然而队列的实现较复杂且需要同步机制，还是有一 定的 overhead ，因此另一种神奇的解法是： • 我们仍是分配 4 个线程，但还是把图像切分为 16 份。然后规定每一份按照 xy

Struct of Array ）属性分离存储在多个数组 • xxxxyyyyzzzz • AOS 必须对齐到 2 的幂才高效， SOA 就不需要。 • AOS 符合直觉，不一定要存储在数组这种线性结构， 而 SOA 可能无法保证多个数组大小一致。 • SOA 不符合直觉，但通常是更高效的！ AOS 和 SOA 的对比 • 因为缓存行大小是 64 字节，他是从内存读写的最小单位。 • 不用等待，就可以直接开始处理 a[2] ，避免等待数据的 时候 CPU 空转浪费时间。 • 这种策略称之为预取（ prefetch ），由硬件自动识别你程序的访存规律 ，决定要预取的地址。一般来说只有线性的地址访问规律（包括顺序、 逆序；连续、跨步）能被识别出来，而如果你的访存是随机的，那就没 办法预测。遇到这种突如其来的访存时， CPU 不得不空转等待数据的抵 达才能继续工作，浪费了时间。

如果实在不能改的话，可以用 std::recursive_mutex 。他会自动判断是不 是同一个线程 lock() 了多次同一个锁，如 果是则让计数器加 1 ，之后 unlock() 会让 计数器减 1 ，减到 0 时才真正解锁。但是 相比普通的 std::mutex 有一定性能损失。 • 同理还有 std::recursive_timed_mutex ， 如果你同时需要 try_lock_for()

拷贝，他解决重复释放的方式是通过引用计数： 1. 当一个 shared_ptr 初始化时，将计数器设为 1 。 2. 当一个 shared_ptr 被拷贝时，计数器加 1 。 3. 当一个 shared_ptr 被解构时，计数器减 1 。减到 0 时 ，则自动销毁他指向的对象。 • 从而可以保证，只要还有存在哪怕一个指针指向该对象 ，就不会被解构。 更智能的指针： shared_ptr （续） • 我们可以使用 p.use_count()

改用首地址指针和尾地址指针以后，要特 别注意一点：尾地址指针实际上是指向末 尾元素再往后后一个元素的指针！ • 也就是说尾地址指针所指向的地方是无效 的内存 a + a.size() ，尾地址指针减 1 才 是真正的末尾元素指针 a + a.size() - 1 。 • 为什么要这样设计？因为如果用 a + a.size() - 1 也就是 &a.back() 作为尾地址 指针，将无法表示数组长度为