第三届中国Rust开发者大会 Rust Atomic Deep Dive Pu Wang @ DatenLord 2023/06/17 Rust原子操作高性能实践 What are atomic operations in Rust? What Why need atomic operations? Why How 01 02 03 Memory order in atomic operations

新一代分布式高性能图数据库的构建 北京海致星图科技有限公司 2023-06-18 沈游人 数据库与大数据专场 海致简介—企业级知识图谱开创者 专业顶尖技术团队支撑 超 700 人团队，其中 80% 为技术人员，创始团队在完成全球第一个中文知 识图谱网站研发后，探索知识图谱技术在企业领域的应用。 2021 年，海致院 士专家工作站成立，站内清华大学计算机博士生占比达 90% 以上。 专注于数据智能技术赋能中国数字经济发展 海致高性能图计算院士专家工作站 郑纬民 - 海致科技首席科学家 中国工程院院士、清华大学计算机科学与技术系教 授、中国计算机学会前理事长，中国计算机系统结构 的学科带头人，我国高性能计算和存储系统等方面的 泰斗和先行者。 2021 年 3 月 25 日，海致科技与清华大学计算机科学与技术系共同建设高性能图计算院士专家工作站 。 高性能图计算是高性能计算、图计算两项技术融合 杂数据的实时处理和存储需求，是计算机领域竞争新战略制高点。 产学结合、协同创新，打造全球领先的国产自研图数据库 AtlasGraph ，培育世界级的图计算软硬件 生态体系，保持对全球科技竞争的战略均衡。 海致高性能图计算院士专家工作站 海致获得“ 2021 年 CCF 科学技术奖科技进步卓越奖” CCF 科学技术奖被认为是计算机科学与技术领域最具影响力的专业奖项之一， 其中科技进步卓越奖是 CCF 科技

题时能够作出专业的反应和判断，从而提升工作的整体质量。举一个简单例子，每种编程语言都内置了排序 函数： ‧ 如果我们没有学过数据结构与算法，那么给定任何数据，我们可能都塞给这个排序函数去做了。运行顺 畅、性能不错，看上去并没有什么问题。 ‧ 但如果学过算法，我们就会知道内置排序函数的时间复杂度是 ?(? log ?) ；而如果给定的数据是固定 位数的整数（例如学号），那么我们就可以用效率更高的“基数排序”来做，将时间复杂度降为 的运行时间和内存占用情况。这种评估方式能够反映真 实情况，但也存在较大的局限性。 一方面，难以排除测试环境的干扰因素。硬件配置会影响算法的性能表现。比如一个算法的并行度较高，那 么它就更适合在多核 CPU 上运行，一个算法的内存操作密集，那么它在高性能内存上的表现就会更好。也 就是说，算法在不同的机器上的测试结果可能是不一致的。这意味着我们需要在各种机器上进行测试，统计 平均效率，而这是不现实的。 www.hello‑algo.com 19 ‧ 它无需实际运行代码，更加绿色节能。 ‧ 它独立于测试环境，分析结果适用于所有运行平台。 ‧ 它可以体现不同数据量下的算法效率，尤其是在大数据量下的算法性能。 Tip 如果你仍对复杂度的概念感到困惑，无须担心，我们会在后续章节中详细介绍。 复杂度分析为我们提供了一把评估算法效率的“标尺”，使我们可以衡量执行某个算法所需的时间和空间资 源，对比不同算法之间的效率。

的方法 是找一台计算机，运行这两个算法，并监控记录它们的运行时间和内存占用情况。这种评估方式能够反映真 实情况，但也存在较大的局限性。 一方面，难以排除测试环境的干扰因素。硬件配置会影响算法的性能。比如在某台计算机中，算法 A 的运行 时间比算法 B 短；但在另一台配置不同的计算机中，可能得到相反的测试结果。这意味着我们需要在各种机 器上进行测试，统计平均效率，而这是不现实的。 另一方 在以下两个方面。 ‧ 它独立于测试环境，分析结果适用于所有运行平台。 第 2 章 复杂度分析 hello‑algo.com 19 ‧ 它可以体现不同数据量下的算法效率，尤其是在大数据量下的算法性能。 Tip 如果你仍对复杂度的概念感到困惑，无须担心，我们会在后续章节中详细介绍。 复杂度分析为我们提供了一把评估算法效率的“标尺”，使我们可以衡量执行某个算法所需的时间和空间资 源，对比不同算法之间的效率。 维 方式。 ‧ 从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分 析。 2.2.3 两者对比 总结以上内容，如表 2‑1 所示，迭代和递归在实现、性能和适用性上有所不同。 表 2‑1 迭代与递归特点对比 第 2 章 复杂度分析 hello‑algo.com 27 迭代 递归 实现方 式 循环结构 函数调用自身 时间效 率 效率通常较高，无函数调用开销

的方法 是找一台计算机，运行这两个算法，并监控记录它们的运行时间和内存占用情况。这种评估方式能够反映真 实情况，但也存在较大的局限性。 一方面，难以排除测试环境的干扰因素。硬件配置会影响算法的性能。比如在某台计算机中，算法 A 的运行 时间比算法 B 短；但在另一台配置不同的计算机中，可能得到相反的测试结果。这意味着我们需要在各种机 器上进行测试，统计平均效率，而这是不现实的。 另一方 在以下两个方面。 ‧ 它独立于测试环境，分析结果适用于所有运行平台。 第 2 章 复杂度分析 hello‑algo.com 19 ‧ 它可以体现不同数据量下的算法效率，尤其是在大数据量下的算法性能。 � 如果你仍对复杂度的概念感到困惑，无须担心，我们会在后续章节中详细介绍。 复杂度分析为我们提供了一把评估算法效率的“标尺”，使我们可以衡量执行某个算法所需的时间和空间资 源，对比不同算法之间的效率。 维 方式。 ‧ 从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分 析。 2.2.3 两者对比 总结以上内容，如表 2‑1 所示，迭代和递归在实现、性能和适用性上有所不同。 表 2‑1 迭代与递归特点对比 第 2 章 复杂度分析 hello‑algo.com 27 迭代 递归 实现方 式 循环结构 函数调用自身 时间效 率 效率通常较高，无函数调用开销

23.5 資料結構中的生命週期 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 23.6 練習：Protobuf 剖析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 23.6.1 解決方案 . . . . . . . . . Slices: &[T] 10 minutes 迷途參照 10 minutes 函式呼叫中的生命週期 10 minutes 生命週期 5 minutes 生命週期 5 minutes 練習：Protobuf 剖析 30 minutes 23.1 切片 切片能讓您查看更大的集合： fn main() { let mut a: [i32; 6] = [10, 20, 30, 40, 50, 60]; println 述參照之間的生命週期關係，就可能有必要擁有多個生命週期註解。那些是相當進階的用途。 23.6 練習：Protobuf 剖析 在本練習中，您將建構 protobuf 二進位編碼的剖析器。請放心，這比看起來容易！這個練習也會舉例說 明常見的剖析模式，也就是傳遞資料切片。基礎資料本身一律不會複製。 如要完整剖析 protobuf 訊息，您必須瞭解欄位型別，這會依欄位編號建立索引，通常位於 proto 檔案 內。在

23.5 資料結構中的生命週期 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 23.6 練習：Protobuf 剖析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 23.6.1 解決方案 . . . . . . . . . Slices: &[T] 10 minutes 迷途參照 10 minutes 函式呼叫中的生命週期 10 minutes 生命週期 5 minutes 生命週期 5 minutes 練習：Protobuf 剖析 30 minutes 23.1 切片 切片能讓您查看更大的集合： fn main() { let mut a: [i32; 6] = [10, 20, 30, 40, 50, 60]; println 述參照之間的生命週期關係，就可能有必要擁有多個生命週期註解。那些是相當進階的用途。 23.6 練習：Protobuf 剖析 在本練習中，您將建構 protobuf 二進位編碼的剖析器。請放心，這比看起來容易！這個練習也會舉例說 明常見的剖析模式，也就是傳遞資料切片。基礎資料本身一律不會複製。 如要完整剖析 protobuf 訊息，您必須瞭解欄位型別，這會依欄位編號建立索引，通常位於 proto 檔案 內。在

........................................................................................ 335 13.4. 性能比较：循环对迭代器 ......................................................................................... 这个表现形式看起来 并不像 图 4-3 中的那样，如果 Rust 也拷贝了堆上的数据，那么内存看起 来就是这样的。如果 Rust 这么做了，那么操作 s2 = s1 在堆上数据比较大的时候会对运行时 性能造成非常大的影响。 77/600 Rust 程序设计语言 简体中文版 图 4-3：另一个 s2 = s1 时可能的内存表现，如果 Rust 同时也拷贝了堆上的数据的话 之前我们提到过当变量离开作用域后，Rust 这样就解决了我们的问题！因为只有 s2 是有效的，当其离开作用域，它就释放自己的内存， 完毕。 另外，这里还隐含了一个设计选择：Rust 永远也不会自动创建数据的 “深拷贝”。因此，任何 自动 的复制都可以被认为是对运行时性能影响较小的。 变量与数据交互的方式（二）：克隆 如果我们 确实 需要深度复制 String 中堆上的数据，而不仅仅是栈上的数据，可以使用一个 叫做 clone 的通用函数。第五章会讨论方法语法，不过因为方法在很多语言中是一个常见功

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 13.4. 性能比较：循环对迭代器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 这个表现形式看起来并不像图 4-3 中的那样，如果 Rust 也拷贝了堆上的数据，那么内存看起 来就是这样的。如果 Rust 这么做了，那么操作 s2 = s1 在堆上数据比较大的时候会对运行时 性能造成非常大的影响。 73/562Rust 程序设计语言 简体中文版 s2 name value ptr len 5 capacity 5 indexvalue 0 h 1 e 2 l 这样就解决了我们的问题！因为只有 s2 是有效的，当其离开作用域，它就释放自己的内存， 完毕。 另外，这里还隐含了一个设计选择：Rust 永远也不会自动创建数据的 “深拷贝”。因此，任何 自动的复制都可以被认为是对运行时性能影响较小的。 作用域与赋值 作用域、所有权和通过 drop 函数释放内存之间的关系反过来也同样成立。当你给一个已有的 变量赋一个全新的值时，Rust 将会立即调用 drop 并释放原始值的内存。例如，考虑如下代

位執行“計數排序”。完成後，資料會根據第 ? 位從小到大排序。 3. 將 ? 增加 1 ，然後返回步驟 2. 繼續迭代，直到所有位都排序完成後結束。 圖 11‑18 基數排序演算法流程 下面剖析程式碼實現。對於一個 ? 進位制的數字 ? ，要獲取其第 ? 位 ?? ，可以使用以下計算公式： ?? = ⌊ ? ??−1⌋ mod ? 其中 ⌊?⌋ 表示對浮點數 ? 向下取整，而 mod 我們不希望看到的。 Q：哨兵劃分中“從右往左查詢”與“從左往右查詢”的順序可以交換嗎？ 不行，當我們以最左端元素為基準數時，必須先“從右往左查詢”再“從左往右查詢”。這個結論有些反直覺， 我們來剖析一下原因。 哨兵劃分 partition() 的最後一步是交換 nums[left] 和 nums[i] 。完成交換後，基準數左邊的元素都 <= 基 準數，這就要求最後一步交換前 nums[left]