从稀疏数据结构到量化数据类型 by 彭于斌（ @archibate ） 往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 本课涵盖：稀疏矩阵、 unordered_map 、空间稀 疏网格、位运算、浮点的二进制格式、内存带宽优 化 面向人群：图形学、 16x16 分块存储 分块能减少 unordered_map 中存储的表项数量，从而减轻哈 希的压力。但意味着键值在空间上需要具有一定的局域性，否 则 会浪费分块中一 部分空间。 然而我们这里是 要用他记录粒子 经过的点，因此 具有一定空间局 域性，能够被分 块优化。 实际上空间局域 性正是稀疏网格 能够实现的一大 前提，稍后详细 讨论。 在 16x16 分块的基础上，只用一个 bit 存储 浪费内存。 这些被写入的部分被称为激活元素 (active element) ，反之则是未激活 (inactive) 。 这就是稀疏的好处，按需分配，自动扩容。 分块则是利用了我们存储的数据常常有着空间局域性的特点，减轻哈希表的压 力，同时在每个块内部也可以快乐地 SIMD 矢量化， CPU 自动预取之类的。 第 2 章：位运算 稀疏的好处：坐标可以是负数 这样即使坐标为负数，或者可以是任意大的坐标，都不会产生越界错误。

device ； device 可以调用 device 。 声明为内联函数 • 注意， inline 在现代 C++ 中的效果是声明一个函数为 weak 符号，和性能优化意义上的内联无关。 • 优化意义上的内联指把函数体直接放到调用者那里去。 • 因此 CUDA 编译器提供了一个“私货”关键字： __inline__ 来 声明一个函数为内联。不论是 CPU 函数还是 GPU 都可以使 用，只要你用的 CUDA 编译器。 GCC 编译器相应的私货则 是 __attribute__((“inline”)) 。 • 注意声明为 __inline__ 不一定就保证内联了，如果函数太大编 译器可能会放弃内联化。因此 CUDA 还提供 __forceinline__ 这个关键字来强制一个函数为内联。 GCC 也有相应的 __attribute__((“always_inline”)) 如需总的线程编号： blockDim * blockIdx + threadIdx 三维的板块和线程编号 • CUDA 也支持三维的板块和线程区间。 • 只要在三重尖括号内指定的参数改成 dim3 类型即可。 dim3 的构造函数就是接受三 个无符号整数（ unsigned int ）非常简单 。 • dim3(x, y, z) • 这样在核函数里就可以通过 threadIdx.y 获取

如果你没看出来（哪怕是其中一个），那就要好好上小彭老师的课哦！ 字节（ byte ） 和位（ bit ）有什么区别 • 众所周知，计算机是二进制的，存储的实际上是一个个 0 和 1 。 • 每个存储 0 或 1 的空间称为一个位（ bit ），一位可以存储 0 或 1 两个可能的值。 • 现在的计算机都会把 8 个位打包成一个字节（ byte ），也就是说： 1 字节 = 8 位。 • 一字节可以表示 0 到 • 11111100 表示 252 11111101 表示 253 11111110 表示 254 11111111 表示 255 • 字节实际上就是 C 语言中的 unsigned char 类型。 表示更大范围的整数：字（ word ） • 但是单单一个字节表示的范围还是太有限了，只能表示 0 到 255 的值。 • 如何扩大表示范围？简单，用两个字节合在一起即可，例如： • 00000000-00000000 11111111-11111110 表示 65534 11111111-11111111 表示 65535 • 这就是两个字节合成了一个字（ word ），实际上就是 C 语言里的 unsigned short 类型 。 不同位数的计算机，字（ word ）的大小也不一样 • 刚刚说把 2 个字节（ byte ）拼成一个字（ word ），实际上是 16 位计算机的做法。 • 16 位计算机得名就是因为他的字由

4 个字节时，实际会导致 0x0040~0x0080 的 64 字节数据整个被读取到缓存中。 • 这就是为什么我们喜欢把数据结构的起始地址和大小对齐到 64 字节，为的是不要浪费缓存行的存储空间。 缓存的工作机制：写 • 缓存中存储的数据结构： • struct CacheEntry { • bool valid, dirty; • uint64_t address; 量无关，和访问的每个字节所在的缓存行 数量有关。 • 可见，能否很好的利用缓存，和程序访问 内存的空间局域性有关。 缓存行决定数据的粒度（续） • 所以我们设计数据结构时，应该把数据存 储的尽可能紧凑，不要松散排列。最好每 个缓存行里要么有数据，要么没数据，避 免读取缓存行时浪费一部分空间没用。 重新认识结构体 重新认识 AOS * * 字节，之 后又没用到剩下的 60 字节，导致浪费了 94% 的带宽。 • 虽说连续、顺序访问是最理想的，然而在使用哈希表等数据结构中，不 可避免的会通过哈希函数得到随机的地址来访问，且 Value 类型可能小 于 64 字节，浪费部分带宽。怎么办？ 解决：按 64 字节分块地随机访问 • 解决方法就是，把数据按 64 字节大小分块。随 机访问时，只随机块的位置，而块的内部仍然按 顺序访问。

https://github.com/zenustech/zeno/tree/zeno2 • Zeno 1.0 所在的分支： https://github.com/zenustech/zeno/ Zeno 中的基本类型 • IObject 一切对象的公共基类。 • INode 一切节点的公共基类。 多态的经典案例 • IObject 具有一个 eatFood 纯虚函数，而 CatObject 和 DogObject IObject * 存储的指针在 delete 时只 会释放 IObject 里的成员，而不会释放 CatObject 里的成员 string m_catFood 。所以 这里的解构函数也是多态的，他根据类型的不同 调用不同派生类的解构函数。 多态用于设计模式之“模板模式” • 这样之后如果有一个任务是要基于 eatFood 做文章，比如要重复 eatFood 两遍。 • 就可以封装到一个函数 eatTwice 拷贝，然后对对象本身和他的拷贝都调用一次 eatFood 虚函数。 • 代码如下，这要怎么个封装法呢？你可能会想，是不是可以把拷贝构造函数也声明为虚函 数，这样就能实现了拷贝的多态？不行，因为 C++ 规定“构造函数不能是虚函数”。 模板函数？未免有些差强人意 • 索性把 eatTwice 声明为模板函数的确能解决问题，但模板函数不是面向对象的思路，并 且如果 cat 和 dog 是在一个 IObject 的指针里就会编译出错，例如右图的

单文件编译虽然方便，但也有如下缺点： 1. 所有的代码都堆在一起，不利于模块化和理解。 2. 工程变大时，编译时间变得很长，改动一个地方就得全部重新编译。 • 因此，我们提出多文件编译的概念，文件之间通过符号声明相互引用。 • > g++ -c hello.cpp -o hello.o • > g++ -c main.cpp -o main.o • 其中使用 -c 选项指定生成临时的对象文件 main PUBLIC 的含义稍后会说明（ CMake 中有很多这样的大写修饰符） 为什么 C++ 需要声明 • 在多文件编译章中，说到了需要在 main.cpp 声明 hello() 才能引用。为什么？ 1. 因为需要知道函数的参数和返回值类型：这样才能支持重载，隐式类型转换等特性。例 如 show(3) ，如果声明了 void show(float x) ，那么编译器知道把 3 转换成 3.0f 才能 调用。 hello 这个函数，而不是创建一个叫 hello 的类的对 象。 • 其实， C++ 是一种强烈依赖上下文信息的编程语言，举个例子： • vector < MyClass > a; // 声明一个由 MyClass 组成的数组 • 如果编译器不知道 vector 是个模板类，那他完全可以把 vector 看做一个变量名，把 < 解释为小于号，从而理解成判断‘ vector’ 这个变量的值是否小于‘

rdx, rbx, rsi, rdi, rsp, rbp, r8, r9, r10, r11, ..., r15 • 其中 r8 到 r15 是 64 位 x86 新增的寄存器，给了汇编程序员更大的空间，降低了编译 器处理寄存器翻车（ register spill ）的压力。 • 因此 64 位比 32 位机器相比，除了内存突破 4GB 限制外，也有一定性能优势。 8 位， 16 位， 32 的最低位进行运算；也可以是 p 表示矢量 (packed) ，一次对 xmm 中所有位进行运算。 3. 第二个 s 表示单精度浮点数 (single) ，即 float 类型；也可以是 d 表示双精度浮点数 (double) ，即 double 类型。 • addss ：一个 float 加法。 • addsd ：一个 double 加法。 • addps ：四个 float 加法。 • addpd ！否则编译器看不见函数体里的内容怎么 内联呢？ 为了效率我们可以尽量把常用函数定义在 头文件里，然后声明为 static 。这样调用 他们的时候编译器看得到他们的函数体， 从而有机会内联。 内联：当编译器看得到被调用函数（ other ）实现的时候 ，会直接把函数实现贴到调用他的函数（ func ）里。 局部可见函数： static 因为 static 声明表示不会暴露 other 给其 他文件，而且 func 也已经内联了

3000000 微秒，也就是 3 秒 • C 语言原始的 API ，没有类型区分，导致很容易弄错单位，混淆时间点和时间段。 • 比如 t0 * 3 ，乘法对时间点而言根本是个无意义的计算，然而 C 语言把他们看做一样的 long 类型，从而容易让程序员犯错。 C++11 引入的时间标准库： std::chrono • 利用 C++ 强类型的特点，明确区分时间点与时间段，明确区分不同的时间单位。 • • 时间点例子： 2022 年 1 月 8 日 13 点 07 分 10 秒 • 时间段例子： 1 分 30 秒 • 时间点类型： chrono::steady_clock::time_point 等 • 时间段类型： chrono::milliseconds ， chrono::seconds ， chrono::minutes 等 • 方便的运算符重载：时间点 + 时间段 = 时间点，时间点 案例：计算花费的时间 时间段：作为 double 类型 duration_cast 可以在任意的 duration 类型之间转换 duration 表示用 T 类型表示，且时间单位是 R R 省略不写就是秒， std::milli 就是毫秒， std::micro 就是微秒 seconds 是 duration 的类型别名 milliseconds 是 duration

0 码力 | 79 页 | 14.11 MB | 1 年前

3

且不说这样的性能问题，你忍得住寂寞去重复定义好 几个，然后每个运算符都要声明一个纯虚函数吗？ 而且， Float 的乘法应该是 multiply(float) ，你也去 定义好几个重载吗？定义为 multiply(Numeric *) 的话 依然会违背你们的开 - 闭原则：比如 3.14f * 3 ，两 端是不同的类型，怎么处理所有可能类型的排列组合 ？ 不如放弃类和方法的概念，欣然接受全局函数和重载 。 其中 T 可以变成任意类型。 • 调用时 twice 即可将 T 替换为 int 。 • 注意有的教材上写做： • template • 是完全等价的，只是个人喜好不同。 模板函数：自动推导参数类型 • 那这样需要手动写 ， 用起 来还不如重载方便了？ • 别担心， C++ 规定： • 当模板类型参数 T 作为函数参数时，则可 模板函数：默认参数类型 • 但是如果模板类型参数 T 没有出现在函数 的参数中，那么编译器就无法推断，就不 得不手动指定了。 • 但是，可以通过 • template • 表示调用者没有指定时， T 默认为 int 。 模板参数：整数也可以作为参数 • template • 可以声明类型 T 作为模板尖括号里的参数。除了 类型，任意整数也可以作为模板参数：

我知道可以用 accumulate 啦！但是为了引出 lambda 表达式…… 近现代： C++11 引入了 lambda 表达式 现代： C++14 的 lambda 允许用 auto 自动推断类型 当代： C++17 CTAD / compile-time argument deduction / 编 译期参数推断 当代： C++17 引入常用数值算法 未来： C++20 引入区间（ ranges getter/setter 封装。 • 各个成员之间相互正交，比如数学矢量类 Vec3 ，就没必要去搞封装，只会让程序员 变得痛苦，同时还有一定性能损失：特别 是如果 getter/setter 函数分离了声明和定 义，实现在另一个文件时！ C++ 思想： RAII （ Resource Acquisition Is Initialization ） 资源获取视为初始化，反之，资源释放视为销毁 C++ 其实谷歌在其 Code Style 中也明确提出别再通过 () 调用构造函数，需要类型转换时应该 用： 1. static_cast(3.14f) 而不是 int(3.14f) 2. reinterpret_cast(0xb8000) 而不是 (void *)0xb8000 • 更加明确用的哪一种类型转换（ cast ），从而避免一些像是 static_cast(ptr)