从稀疏数据结构到量化数据类型 by 彭于斌（ @archibate ） 往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 本课涵盖：稀疏矩阵、 unordered_map 、空间稀 疏网格、位运算、浮点的二进制格式、内存带宽优 化 面向人群：图形学、 >> 3 。 >> 2 = 位运算 >> 对负数的处理 signed 类型的 >> n 会把最高位复制 n 次。 因为补码的特性，这导致负数 >> 的结果仍是负 数。 这样就实现了和 Python 一样的始终向下取整除 法。 >> 2 = unsigned 类型的位运算 >> 不一样 而 unsigned 类型的 >> n 会不会复制最高位， 只是单纯的位移，这会导致负数的符号位单独被位 只是单纯的位移，这会导致负数的符号位单独被位 移，补码失效，造成结果不对。 unsigned 类型的 >> 会生成 shr 指令， signed 类型的 >> 会生成 sar 指令。 我们需要负方向无限延伸的稀疏数据结果，那就只 要 signed 那个就行。 >> 2 = 没有重合时可以用高效的加法：位运算 | • 如果可以保证 a 和 b 满足 a & b = 0 ， 如： • 1011000 和 0000110

• 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 位计算机得名就是因为他的字由 字的长度决定了计算机中寄存器的大小，从而决定计算机一次能处理多大的整数。 • 例如 32 位计算机的寄存器都是 32 位，因此只能做 32 位整数的加减乘除，超过 32 位 整数的加减乘除就要用特殊的指令来模拟了。 整数的表示范围受位数限制 • 8 位长的整数能表示的范围是 0 到 2^8-1 ，也就是 0 到 255 。 • 16 位长的整数能表示的范围是 0 到 2^16-1 ，也就是

org/wiki/ASCII 计算机如何表达字符 • 众所周知，计算机只能处理二进制 整数，字符要怎么办呢？ • 于是就有了 ASCII 码表，他规定， 每个英文字符（包括大小写字母、 数字、特殊符号）都对应着一个整 数。在计算机里只要存储这个的整 数，就能代表这个字符了。 • 例如 32 代表空格， 48 代表 ‘ 0’ ， 65 代表 ‘ A’ ， 97 代表 ‘ a’…… • 32~126 这些整数就用于是表示这些 可显示字符 (printable character) 的。 计算机如何表达字符 • 除了可显示字符 (printable character) 外， ASCII 还规定了一 类特殊的控制字符 (control character) ： • 0 表示空字符（‘ \0’ ） • 9 表示 Tab 制表符（‘ \t’ ） • 10 表示换行（‘ \n’ ） • 13 表示回车（‘ 后一次性显示出来的，并不是真的说 Ctrl 就是 ‘ ^’ 这 个字符。 C 语言字符串 第 2 章 C 语言中的字符类型 char • char c = ‘a’; • assert(c == 97); • c = c + 1; • assert(c == ‘b’); • C 语言中规定字符类型为 char 类型，是个 8 位整数。 • 这是因为 ASCII 码只有 0~127 这些整数，而 8 位整数的表示范围是

multiply(Numeric *) 的话 依然会违背你们的开 - 闭原则：比如 3.14f * 3 ，两 端是不同的类型，怎么处理所有可能类型的排列组合 ？ 不如放弃类和方法的概念，欣然接受全局函数和重载 。 模板函数：定义 • 使用 template • 其中 T 可以变成任意类型。 • 调用时 twice 即可将 T 替换为 int 。 • 注意有的教材上写做： 是完全等价的，只是个人喜好不同。 模板函数：自动推导参数类型 • 那这样需要手动写 ， 用起 来还不如重载方便了？ • 别担心， C++ 规定： • 当模板类型参数 T 作为函数参数时，则可 以省略该模板参数。自动根据调用者的参 数判断。 模板函数：特化的重载 • 有时候，一个统一的实现（比如 t * 2 ）满 足不了某些特殊情况。比如 std::string 就 不能用乘法来重复，这时候我们需要用 模板函数：默认参数类型 • 但是如果模板类型参数 T 没有出现在函数 的参数中，那么编译器就无法推断，就不 得不手动指定了。 • 但是，可以通过 • template • 表示调用者没有指定时， T 默认为 int 。 模板参数：整数也可以作为参数 • template • 可以声明类型 T 作为模板尖括号里的参数。除了 类型，任意整数也可以作为模板参数：

CMAKE_BUILD_TYPE 和 CMAKE_INSTALL_PREFIX ） -G 选项：指定要用的生成器 • 众所周知， CMake 是一个跨平台的构建系统，可以从 CMakeLists.txt 生成不同类型的构建系 统（比如 Linux 的 make ， Windows 的 MSBuild ），从而让构建规则可以只写一份，跨平 台使用。 • 过去的软件（例如 TBB ）要跨平台，只好 Makefile 放到和源码同一个目录里，我个人的建议是把源码放到 src 目录下 。 第 2 章：项目配置变量 CMAKE_BUILD_TYPE 构建的类型，调试模式还是发布模式 • CMAKE_BUILD_TYPE 是 CMake 中一个特殊的变量，用于控制构建类型，他的值可以 是： • Debug 调试模式，完全不优化，生成调试信息，方便调试程序 • Release 发布模式，优化程度最高，性能最佳，但是编译比 ：根项目源码路径（存放 main.cpp 的地方） • CMAKE_BINARY_DIR ：根项目输出路径（存放 main.exe 的地方） • PROJECT_IS_TOP_LEVEL ： BOOL 类型，表示当前项目是否是（最顶层的）根项目 • PROJECT_NAME ：当前项目名 • CMAKE_PROJECT_NAME ：根项目的项目名 • 详见： https://cmake.org/

我知道可以用 accumulate 啦！但是为了引出 lambda 表达式…… 近现代： C++11 引入了 lambda 表达式 现代： C++14 的 lambda 允许用 auto 自动推断类型 当代： C++17 CTAD / compile-time argument deduction / 编 译期参数推断 当代： C++17 引入常用数值算法 未来： C++20 引入区间（ ranges 其实谷歌在其 Code Style 中也明确提出别再通过 () 调用构造函数，需要类型转换时应该 用： 1. static_cast(3.14f) 而不是 int(3.14f) 2. reinterpret_cast(0xb8000) 而不是 (void *)0xb8000 • 更加明确用的哪一种类型转换（ cast ），从而避免一些像是 static_cast(ptr) 译器会自动生成一 个无参构造函数 Pig() ，他会调用每个成员的无参构造函数。 • 但是请注意，这些类型不会被初始化为 0 ： 1. int, float, double 等基础类型 2. void *, Object * 等指针类型 3. 完全由这些类型组成的类 • 这些类型被称为 POD （ plain-old-data ）。 • POD 的存在是出于兼容性和性能的考虑。 <<

容器 vector 容器：构造函数 • vector 的功能是长度可变的数组，他里面的数据 存储在堆上。 • vector 是一个模板类，第一个模板参数是数组里 元素的类型。 • 例如，声明一个元素是 int 类型的动态数组 a ： • vector a; vector 容器：构造函数和 size • vector 可以在构造时指定初始长度。 • explicit vector(size_t vector 的这个显式构造函数，默认会把所有元 素都初始化为 0 （不必手动去 memset ）。 • 如果是其他自定义类，则会调用元素的默认构造 函数（例如：数字类型会初始化为 0 ， string 会初始化为空字符串，指针类型会初始化为 nullptr ） • explicit vector(size_t n); vector 容器：构造函数 • 这个显式构造函数还可以指定第二个参数，这样 等价于： • vector a = {1, 2}; • void pop_back() noexcept; vector 容器： back • 要注意的是 pop_back 函数的返回类型是 void ，也就是没有返回值，如果需要获取删除的 值，可以在 pop_back() 之前先通过 back() 获 取末尾元素的值，实现 pop 效果。 • a.back(); • 等价于：

key” 元素 • val = m.at(“key”); // 读取键值为 “ key” 的元素，如果不存在，抛出异常 • 所以 [] 和 at() 唯一的区别，在于键值不存在这一特殊情况的处理方式。 • [] 默默创建。 • at() 抛出异常。 读取 map 元素 • map m; • val = m[“key”]; • 读取键值为 “ key” 写入要创建元素，而读取则要在元素不存在时出错，确实应该是两个不同的函数。 • 为什么 Python 不用区分读取和写入两个函数？只有统一的 [] ？因为 Python 作为老牌胶水语言，为了 用户体验做了些特殊处理。他的 ast 模块能自动识别 [] 位于等号左侧还是右侧，分成两个独立的函数 。 • 如果等号在左侧，则被他的 ast 模块视为写入上下文（ store context ），翻译成 __setitem__ defl; • } • } • 封装成函数方便使用： • auto val = map_get(m, “key”, “default”); • ss map 常用函数不同情况下的行为分析 类型 C++ 代码 key 已存在 key 不存在 读取 val = m.at(key) 读取这个值 抛出 out_of_range 异常 val = m[key] 读取这个值 创建并零初始化（默认构造函数）

是为并行而生的，可以开启很大数量的 线程，用于处理大吞吐量的数据。 获取线程编号 • 可以通过 threadIdx.x 获取当前线程的编 号，我们打印一下试试看。 • 这是 CUDA 中的特殊变量之一，只有在 核函数里才可以访问。 • 可以看到线程编号从 0 开始计数，打印出 了 0 ， 1 ， 2 。这也是我们指定了线程数 量为 3 的缘故。 • 等等，为什么后面有个 .x ？稍后再说明。 如需总的线程编号： blockDim * blockIdx + threadIdx 三维的板块和线程编号 • CUDA 也支持三维的板块和线程区间。 • 只要在三重尖括号内指定的参数改成 dim3 类型即可。 dim3 的构造函数就是接受三 个无符号整数（ unsigned int ）非常简单 。 • dim3(x, y, z) • 这样在核函数里就可以通过 threadIdx.y 获取 可以直接在核函数里调用核函数并指定参数这么方便…… 不过，这个功能同样需要开启 CUDA_SEPARABLE_COMPILATION 。 第 2 章：内存管理 如何从核函数里返回数据？ • 我们试着把 kernel 的返回类型声明为 int ，试 图从 GPU 返回数据到 CPU 。 • 但发现这样做会在编译期出错，为什么？ • 刚刚说了 kernel 的调用是异步的，返回的时候 ，并不会实际让 GPU 把核函数执行完毕，必须

是骨感的，对于程序来说，指令不只是一个 个简单的任务，有时候我们需要做判断，来 决定要执行的具体任务，这就是分支，在汇 编语言中体现为条件跳转指令。 • 例如我们这里给任务清单加一个，如果烧开 水时被烫伤，则直接去医院的特殊任务。 • 特点：一旦触发去医院这个支线，则后面的 任务都不用做了，直接跳过。 任务 时间 占用资源 洗脸 5 分钟 眼睛，嘴巴，手 烧开水 10 分钟 煤气灶 如果烧开水时被烫伤，则跳转到去医院 这里 x > 0 返回的是一个 bool 类型（通过指令 setg al 求出） • bool 类型和 char 一样只占据 1 字节（ al 寄存器就 1 字节） • 而 C 语言可以自动把 bool 转换成 int 类型（ movzx 把 1 字节的 al 转换成 4 字节的 eax ，零扩展：高 3 字节 填充零） • 返回类型 int 占据 4 字节（ eax 寄存器就是 寄存器就是 4 字节的） • 返回值都放 eax 寄存器（刚刚算得的就在 eax ，直接返 回） 无分支优化：从语法角度分析 • 刚刚其实是利用了 C 语言把 bool 类型的 true 当做 1 ， false 当做 0 的特性。 • (int)true == 1 (int)false == 0 • 例如： • if (x > 0) return 1; else return 0; 优化成