从稀疏数据结构到量化数据类型 by 彭于斌（ @archibate ） 往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 本课涵盖：稀疏矩阵、 unordered_map 、空间稀 疏网格、位运算、浮点的二进制格式、内存带宽优 化 面向人群：图形学、 ，反之则是未激活 (inactive) 。 这就是稀疏的好处，按需分配，自动扩容。 分块则是利用了我们存储的数据常常有着空间局域性的特点，减轻哈希表的压 力，同时在每个块内部也可以快乐地 SIMD 矢量化， CPU 自动预取之类的。 第 2 章：位运算 稀疏的好处：坐标可以是负数 这样即使坐标为负数，或者可以是任意大的坐标，都不会产生越界错误。 但是分块存储时负数却导致出错了 为什么 segf collapse(2) 遍历二维区间。 把 func 捕获为 firstprivate ，从而支持用 lambda 捕获的访问者模式。 实现访问者模式 • 额，总之就是每一层都有一个缓存。 第 5 章：量化整型 使用 int ：每个占据 4 字节 • 记得我第七课说过，一个简单的循环体往 往会导致内存成为瓶颈（ memory- bound ）。 • 右边就是一个很好的例子。 使用 int64_t

• addps ：四个 float 加法。 • addpd ：两个 double 加法。 省流助手： 如果你看到编译器生成的汇编里，有大量 ss 结尾 的指令则说明矢量化失败；如果看到大多数都是 ps 结尾则说明矢量化成功。 xmm0 xmm1 xmm0 addss %xmm1, %xmm0 addps %xmm1, %xmm0 xmm0 xmm1 xmm0 为什么需要 SIMD 语言。 编译器优化：合并写入 将两个 int32 的写入合 并为一个 int64 的写入 。 合并写入：不能跳跃 但如果访问的两个元素地 址间有跳跃，就不能合并 了。 第 4 章：矢量化 更宽的合并写入：矢量化指令（ SIMD ） 两个 int32 可以合并为一个 int64 四个 int32 可以合并为一个 __m128 xmm0 由 SSE 引入，是个 128 位寄存 器 他可以一次存储 看不懂？很简单，假设 n = 1023 ： 先对前 1020 个元素用 SIMD 指令填入，每次处理 4 个 剩下 3 个元素用传统的标量方式填入，每次处理 1 个 思想：对边界特殊处理，而对大部分数据能够矢量化 编译器做优化时会自动处理边界特 判。如果你是自己手写 SIMD 指令 的话就要考虑一下这个。 n 总是 4 的倍数？避免边界特判 如果你能保证 n 总是 4 的倍数，也可以这样写： 编译器会发现

。 • 计算太简单，数据量又大，并行只带来了多线程调度的额外开销 。 • 小彭老师经验公式： 1 次浮点读写 ≈ 8 次浮点加法 • 如果矢量化成功（ SSE ）： 1 次浮点读写 ≈ 32 次浮点加法 • 如果 CPU 有 4 核且矢量化成功： 1 次浮点读写 ≈ 128 次浮点加 法 常见操作所花费的时间 • 图中加法 (add) 和乘法 (mul) 都指的整数。 • 区别是浮点的乘法和加法基本是一样速度。 要 SIMD 矢量化的话可能还是要 SOA 或 AOSOA ，比如 hw04 那种的。而 “ pos 和 vel 应该用 SOA 分开存”是没问题的。 • 而且 SOA 在遇到存储不是 vector ，而是稀疏的哈希网格之类索引有一定 开销的数据结构，可能就不适合了。这就是为什么王鑫磊最喜欢 AOSOA ：在高层保持 AOS 的统一索引，底层又享受 SOA 带来的矢量化 和缓存行预取等好处……就是随机索引比较麻烦。 写回执行完成，然后重 新读取到缓存，反而更低效。 • 因此，仅当这些情况： 1. 该数组只有写入，之前完全没有读取过 。 2. 之后没有再读取该数组的地方。 • 才应该用 stream 指令。 4 倍矢量化的版本： _mm_stream_ps • _mm_stream_si32 可以一次性写入 4 字 节到挂起队列。而 _mm_stream_ps 可以 一次性写入 16 字节到挂起队列，更加高

auto_partitioner 快 3.31 倍 原因 • tbb::simple_partitioner 能够按照给定的粒度 大小（ grain ）将矩阵进行分块。块内部小区 域按照常规的两层循环访问以便矢量化，块外 部大区域则以类似 Z 字型的曲线遍历，这样 能保证每次访问的数据在地址上比较靠近，并 且都是最近访问过的，从而已经在缓存里可以 直接读写，避免了从主内存读写的超高延迟。 • 下次课会进一步深入探讨访存优化，详细剖析

演算法猶如美妙的交響樂，每一行程式碼都像韻律般流淌。 願這本書在你的腦海中輕輕響起，留下獨特而深刻的旋律。 第 0 章 前言 www.hello‑algo.com 2 0.1 關於本書 本專案旨在建立一本開源、免費、對新手友好的資料結構與演算法入門教程。 ‧ 全書採用動畫圖解，內容清晰易懂、學習曲線平滑，引導初學者探索資料結構與演算法的知識地圖。 ‧ 源程式碼可一鍵執行，幫助讀者在練習 圖 0‑4 克隆倉庫與下載程式碼 第三步：執行源程式碼。如圖 0‑5 所示，對於頂部標有檔案名稱的程式碼塊，我們可以在倉庫的 codes 檔案 夾內找到對應的源程式碼檔案。源程式碼檔案可一鍵執行，將幫助你節省不必要的除錯時間，讓你能夠專注 於學習內容。 圖 0‑5 程式碼塊與對應的源程式碼檔案 除了本地執行程式碼，網頁版還支持 Python 程式碼的視覺化執行（基於 pythontutor 第 1 章 初識演算法 www.hello‑algo.com 13 圖 1‑3 貨幣找零過程 在以上步驟中，我們每一步都採取當前看來最好的選擇（儘可能用大面額的貨幣），最終得到了可行的找零方 案。從資料結構與演算法的角度看，這種方法本質上是“貪婪”演算法。 小到烹飪一道菜，大到星際航行，幾乎所有問題的解決都離不開演算法。計算機的出現使得我們能夠透過程 式設計將資料結構儲存在記憶體中，同時編寫程式碼呼叫

Menu 編輯器 / 301 Accelerator 編輯器 / 303 Dialog 編輯器 / 304 * Console 程式的專案管理 / 305 第㆔篇 淺出 MFC 程式設計 / 309 第５章 總觀 Application Framework / 311 什麼是 Application Framework ClassWizard 的輔佐 / 496 WizardBar 的輔佐 / 498 Serialize：物件的檔案讀寫 / 498 目 錄 21 Serialization 以外的檔案讀寫動作 / 499 檯面㆖的 Serialize 動作 / 501 檯面㆘的 Serialize Document 類別 / 736 新的 Document Template / 739 新的 UI 系統 / 740 新文件的檔案讀寫動作 / 742 * 第 14 章 MFC 多緒程式設計（Multi-threaded Programming in MFC） / 745 從作業系統層面看執行緒 / 745

ghost cell 处理方式 ，这里用了 std::min 和 std::max 来防止 访问越界。主要是 GPU 的 SIMT 处理这 个比较擅长，不像 CPU 如果这样来钳制 可能导致矢量化失败。 减轻 membound ：一次代替四次迭代 • 和第七课提到的循环合并法局部迭代一样的方式 。 • 不过这里改用了 GPU 的板块共享内存，线程之 间自动并行，没有像 CPU 那样用循环。

元，剩余 1 − 1 = 0 元。 5. 完成找零，方案为 20 + 10 + 1 = 31 元。 在以上步骤中，我们每一步都采取当前看来最好的选择（尽可能用大面额的货币），最终得到了可行的找零方 案。从数据结构与算法的角度看，这种方法本质上是「贪心算法」。 1. 初识算法 hello‑algo.com 9 Figure 1‑3. 货币找零过程 小到烹饪一道菜，大到星际航行，几乎所有问题的解 上。换句话说，我们只能从第 ? − 1 阶或第 ? − 2 阶前往第 ? 阶。 由此便可得出一个重要推论：爬到第 ? − 1 阶的方案数加上爬到第 ? − 2 阶的方案数就等于爬到第 ? 阶的方 案数。公式如下： ??[?] = ??[? − 1] + ??[? − 2] 这意味着在爬楼梯问题中，各个子问题之间不是相互独立的，原问题的解可以从子问题的解构建得来。 14. 动态规划 hello‑algo − 1] ，状态转移至 [? − 1, ? − ???[? − 1]] 。 上述的状态转移向我们揭示了本题的最优子结构：最大价值 ??[?, ?] 等于不放入物品 ? 和放入物品 ? 两种方 案中的价值更大的那一个。由此可推出状态转移方程： ??[?, ?] = max(??[? − 1, ?], ??[? − 1, ? − ???[? − 1]] + ???[? − 1]) 需要注意的是，若当前物品重量

31 元。 第 1 章 初识算法 hello‑algo.com 13 图 1‑3 货币找零过程 在以上步骤中，我们每一步都采取当前看来最好的选择（尽可能用大面额的货币），最终得到了可行的找零方 案。从数据结构与算法的角度看，这种方法本质上是“贪心”算法。 小到烹饪一道菜，大到星际航行，几乎所有问题的解决都离不开算法。计算机的出现使得我们能够通过编程 将数据结构存储在内存中，同时编写代码调用 上。换句话说，我们只能从第 ? − 1 阶或第 ? − 2 阶迈向第 ? 阶。 由此便可得出一个重要推论：爬到第 ? − 1 阶的方案数加上爬到第 ? − 2 阶的方案数就等于爬到第 ? 阶的方 案数。公式如下： ??[?] = ??[? − 1] + ??[? − 2] 这意味着在爬楼梯问题中，各个子问题之间存在递推关系，原问题的解可以由子问题的解构建得来。图 14‑2 展示了该递推关系。 例如零钱兑换问题，我们虽然能够容易地举出反例，对贪心选择性质进行证伪，但证实的难度较大。如果问： 满足什么条件的硬币组合可以使用贪心算法求解？我们往往只能凭借直觉或举例子来给出一个模棱两可的答 案，而难以给出严谨的数学证明。 Quote 有一篇论文给出了一个 ?(?3) 时间复杂度的算法，用于判断一个硬币组合能否使用贪心算法找出任 意金额的最优解。 Pearson, D. A polynomial‑time

第 1 章 初识算法 www.hello‑algo.com 13 图 1‑3 货币找零过程 在以上步骤中，我们每一步都采取当前看来最好的选择（尽可能用大面额的货币），最终得到了可行的找零方 案。从数据结构与算法的角度看，这种方法本质上是“贪心”算法。 小到烹饪一道菜，大到星际航行，几乎所有问题的解决都离不开算法。计算机的出现使得我们能够通过编程 将数据结构存储在内存中，同时编写代码调用 上。换句话说，我们只能从第 ? − 1 阶或第 ? − 2 阶迈向第 ? 阶。 由此便可得出一个重要推论：爬到第 ? − 1 阶的方案数加上爬到第 ? − 2 阶的方案数就等于爬到第 ? 阶的方 案数。公式如下： ??[?] = ??[? − 1] + ??[? − 2] 这意味着在爬楼梯问题中，各个子问题之间存在递推关系，原问题的解可以由子问题的解构建得来。图 14‑2 展示了该递推关系。 例如零钱兑换问题，我们虽然能够容易地举出反例，对贪心选择性质进行证伪，但证实的难度较大。如果问： 满足什么条件的硬币组合可以使用贪心算法求解？我们往往只能凭借直觉或举例子来给出一个模棱两可的答 案，而难以给出严谨的数学证明。 Quote 有一篇论文给出了一个 ?(?3) 时间复杂度的算法，用于判断一个硬币组合能否使用贪心算法找出任 意金额的最优解。 Pearson, D. A polynomial‑time