sizeof(uintptr_t) size_t ：表示大小的整数类型，其实等价于 uintptr_t • 除了指针需要随系统位数变化之外，数组的长度也是需要随系统位数变化的。 • 如果 64 位系统上 size_t 还是 uint32_t ，那就无法表示超过 4GB 大小的数组了。 • 今日乳 ja 笑话： java 的字符串常量不能超过 65535 个字符，因为他们是用 uint16_t 表示字符串长 表示空指针了，不安全 。 来看看 GLIBC 的源码 数组的本质究竟是什么？ 数组就是一堆在内存中紧密排列在一起的数 • 例如一个由 4 个字节组成的 char 数组，在内存中就是： 实验： char 类型数组 • 可以通过 char a[4] = {...} 来创建一个数组。 • 数组 a 可以通过 a[i] 访问第 i 个元素。 • a 数组有 4 个数组成，每个数称为元素。 • 这里的 i 俗称下标，表示第几个元素。 俗称下标，表示第几个元素。 • 要注意数组的下标是从 0 开始数起的！ • 虽然从 1 开始数数符合人类的习惯，但是从 0 开始数数符合计算机和程序员的习惯。 • 一个大小为 n 的数组，下标从 0 到 n-1 。 实验： char 类型数组 • 当后面有 {} 初始化时， [] 里的 4 可以省 略。 • 这时，编译器会自动推断出数组的大小。 实验： char 类型数组 • 如果没有初始化，而是稍后再赋值的话，

侯捷 STL 侯捷 STL vector 容器 vector 容器：构造函数 • vector 的功能是长度可变的数组，他里面的数据 存储在堆上。 • vector 是一个模板类，第一个模板参数是数组里 元素的类型。 • 例如，声明一个元素是 int 类型的动态数组 a ： • vector a; vector 容器：构造函数和 size • vector 可以在构造时指定初始长度。 可以在构造时指定初始长度。 • explicit vector(size_t n); • 例如，要创建一个长度为 4 的 int 型数组 ： • vector a(4); • 之后可以通过 a.size() 获得数组的长度。 • 比如右边这段代码会得到 4 。 • size_t size() const noexcept; vector 容器： operator[] • 要访问 vector noexcept; • int const &operator[](size_t i) const noexcept; vector 容器： operator[] • 值得注意的是， [] 运算符在索引超出数组大 小时并不会直接报错，这是为了性能的考虑。 • 如果你不小心用 [] 访问了越界的索引，可能 会覆盖掉别的变量导致程序行为异常，或是访 问到操作系统未映射的区域导致奔溃。 • int &operator[](size_t

https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 为什么往 int 数组里赋值 1 比赋值 0 慢一倍？ 第 1 章：内存带宽 cpu-bound 与 memory-bound • 通常来说，并行只能加速计算的部分，不能加速内存读写的部分 。 • 因此，对 fill 循环体，并行才有较好的加速效果。称为计算瓶颈（ cpu- bound ）。 • 并行能减轻计算瓶颈，但不减轻内存瓶颈，故后者是优化的重点 。 浮点加法的计算量 • 冷知识：并行地给浮点数组每个元素做一次加法反而更慢。 • 因为一次浮点加法的计算量和访存的超高延迟相比实在太少了。 • 计算太简单，数据量又大，并行只带来了多线程调度的额外开销 。 • 小彭老师经验公式： 1 次浮点读写 系统会自动在两者之间均匀分配内存，保证读写均匀分配 到两个内存上，实现内存的并行读写，这和磁盘 RAID 有 一定相似之处。 验证一下刚刚的 parallel_add 是不是用足了全部带宽 • 刚刚 a 数组的大小是 1024 MB 。 • 因为不光读取了 a ，计算完还写回了 a ，实际搬运 了 2048 MB 的数据。 • 花费了 0.0656 秒。 • 因此带宽是 31198 MB/s 。

GTX9 开头及以上 。 • 虽然方便，但并非完全没有开销，有条件的话还是尽量用分离的设备内存和主机内存吧。 第 3 章：数组 分配数组 • 如 malloc 一样，可以用 cudaMalloc 配 合 n * sizeof(int) ，分配一个大小为 n 的 整型数组。这样就会有 n 个连续的 int 数 据排列在内存中，而 arr 则是指向其起始 地址。然后把 arr 指针传入 kernel kernel ，即 可在里面用 arr[i] 访问他的第 i 个元素。 • 然后因为我们用的统一内存 (managed) ， 所以同步以后 CPU 也可以直接读取。 多个线程，并行地给数组赋值 • 刚刚的 for 循环是串行的，我们可以把线 程数量调为 n ，然后用 threadIdx.x 作为 i 索引。这样就实现了，每个线程负责给数 组中一个元素的赋值。 小技巧：网格跨步循环（ *allocate(size_t n) // 分配长度为 n ，类型为 T 的数组，返回其起始地址 • void deallocate(T *p, size_t n) // 释放长度为 n ，起始地址为 p ，类型为 T 的数组 抽象的 std::allocator 接口 • vector 会调用 std::allocator 的 allocate/deallocate

就是由字符 (character) 组成的数组。 • C 语言中，字符串用双引号 “” 包裹，字符用单引号 ‘’ 包裹 。 • char c = ‘h’; • char s[] = “hello”; C 语言中的字符串 • 正如 ‘ h’ 是个语法糖，等价于 h 的 ASCII 码——整数 104 。 • “hello” 也是个语法糖，他等价于数组 {‘h’, ‘e’, ‘l’, ‘l’ • “hello” 也是个语法糖，他等价于数组 {‘h’, ‘e’, ‘l’, ‘l’, ‘o’, 0} 。 • hello 每个字符都连续地排列在这个数组中，那么末尾的 0 是怎么回事？原来 C 语言的字符串因为只保留数组的 首地址指针（指向第一个字符的指针），在以 char * 类型 传递给其他函数时，其数组的长度无法知晓。为了确切知 道数组在什么地方结束，规定用 ASCII 码中的“空字符”也 码中的“空字符”也 就是 0 来表示数组的结尾。这样只需要一个首地址指针就 能表示一个动态长度的数组，高，实在是高。 “0 结尾字符串”知识点应用举例 • 利用 C 语言字符串“以 0 结尾”这个特点，我们可以在一个 本来非 0 的字符处写入 0 ，来提前结束字符串。例如在第 n 个字符写入 0 ，就会只保留前 n 个字符作为一个子字 符串，删除后半部分。 “0 结尾字符串”知识点应用举例 •

mory CUDA 多维数组：封装 • cudaMalloc3DArray 用于分配一个三维数组。 各维度上的大小通过 cudaExtent 指定，方 便起见我们的 C++ 封装类用了 uint3 表示 大小。 • GPU 的多维数组有特殊的数据排布来保障 访存的高效，和我们 CPU 那样简单地行主 序或列主序（如 a[x + nx * y] ）的多维数组 不一样。 • 随后可用 随后可用 cudaMemcpy3D 在 GPU 的三 维数组和 CPU 的三维数组之间拷贝数据。 CUDA 表面对象：封装 • 要访问一个多维数组，必须先创建一个表面对象 （ cudaSurfaceObject_t ）。 • 考虑到多维数组始终是需要通过表面对象来访问的，这 里我们让表面对象继承自多维数组。 • 在核函数中可以用 surf3Dread 和 surf3Dwrite 来读写 表面对象中的元素， clamp ）到原本的数组大小范围内，比如把 - 100 钳制到 0 ， n+100 钳制到 n-1 。 • cudaBoundaryModeZero ：对于读来说越界会读取到 0 ；对于写来说越界会放弃写入，不修改数组中的任 何值。 • 表面对象保障了高效的访存，并且自动判断越界，体 现了 GPU 作为图形学专业硬件的能力。 CUDA 纹理对象：封装 • 表面对象访问数组是可读可写的。纹理对象也可以访问

本课涵盖：稀疏矩阵、 unordered_map 、空间稀 疏网格、位运算、浮点的二进制格式、内存带宽优 化 面向人群：图形学、 CFD 仿真、深度学习编程人 员 第 0 章：稀疏矩阵 稠密数组存储矩阵 用 foreach 包装一下枚举的过程 改用 map 来存储 分离 read/write/create 三种访问模式 foreach 直接给出当前坐标指向的值 改用 unordered_map 图片解释稀疏的好处 传统稠密二维数组 无边界稀疏分块哈希表 有了无边界的稀疏网格，再也不用担心二维数组要分配多大了。 坐标可以无限延伸，甚至可以是负数！比如 (-1,2) 等…… 他会自动在写入时分配 16x16 的子网格，称之为叶节点 (leaf node) ，而这里的 unordered_map 就是充当根节点 (root node) 。 图片解释稀疏的好处 传统稠密二维数组 无边界稀疏分块哈希表 改成 & 和 ~ 自动推算 B 和 Bmask ，顺便扁平化 Block 第 3 章：多层稀疏 用一个指针的数组来表示 图片解释：指针数组的原理 1 nul nul 2 3 nul nul nul nul 表示 nullptr （空指针） 图片解释：指针数组的稀疏 这样指针表中为 null 的部分，稠密叶节点的内存就省掉 了 垃圾回收 (garbage-collect)

位系统上相当于 uint64_t size_t 在 32 位系统上相当于 uint32_t 从而不需要用 movslq 从 32 位符号扩展 到 64 位，更高效。而且也能处理数组大 小超过 INT_MAX 的情况，推荐始终用 size_t 表示数组大小和索引。 浮点作为参数和返回： xmm 系列寄存器 xmm0 = xmm0 + xmm1 参数分别通过 xmm0 ， xmm1 传入。 返回值通过 xmm0 让编译器自动检测当前硬件支持的指令集 -march=native 让编译器自动判断当前硬件支 持的指令。老师的电脑支持 AVX 指令集，所 以他用了。不过注意这样编译出的程序，可能 放到别人不支持 AVX 的电脑上没法运行。 数组清零：自动调用标准库的 memset memcpy 同理，不必为了高效，手动改 写成对 memcpy/memset 的调用，影响 可读性。编译器会自动分析你是在做拷贝 或是清零，并优化成对标准库这俩的调用 1024 填充： SIMD 加速（续） 看不懂？小彭老师解析一下。右边是方便大家理解的伪代码： 一次写入 4 个 int ，一次计算 4 个 int 的加法，从而更加高 效但这样有个缺点，那就是数组的大小必须为 4 的整数倍 否则就会写入越界的地址！ 如果不是 4 的倍数？边界特判法 看不懂？很简单，假设 n = 1023 ： 先对前 1020 个元素用 SIMD 指令填入，每次处理 4

作为扩展阅读。 C++ 有哪些面向对象思想？ C++ 思想：封装 比如要表达一个数组，需要：起始地址指针 v ，数组大小 nv 将多个逻辑上相关的变量包装成一个类 因此 C++ 的 vector 将他俩打包起来，避免程序员犯错 封装：不变性 比如当我要设置数组大小为 4 时，不能只 nv = 4 还要重新分配数组内存，从而修改数组起始地址 v 常遇到：当需要修改一个成员时，其他也成员需要被修改，否则出错 三五法则：拷贝构造函数 • 在 = 时，默认是会拷贝的。比如右边这样： • 但是这样对我们当前 Vector 的实现造成一个很大 的问题。其 m_data 指针是按地址值浅拷贝的， 而不深拷贝其指向的数组！ • 这就是说，在退出 main 函数作用域的时 候， v1.m_data 会被释放两次！更危险的则是 v1 被解构而 v2 仍在被使用的情况。 • 这就是为什么“如果一个类定义了解构函数，那么

查找为什么低效 • vector 又称线性数组。在 vector 中查找元素可以用 头文件里的 std::find 。 • vector a = { 1, 4, 2, 8, 5, 7 }; • std::find(a.begin(), a.end(), 5); • 这个 std::find 就是标准库帮我们实现的线性数组中查找元素的算法，让我们用动画演示一 下他的工作原理吧。 1 4 2 8 5 7 内存 地址 a a+1 a+2 a+3 a+4 a+5 vector 查找为什么低效 • 我们要找的数是 5 ，首先从数组第一个元素开始，判断第一个元素是否等于 5 ？ 1 == 5 × • 发现不相等，只能继续判断第二个元素是否等于 5 ？ 4 == 5 × • 发现不相等，只能继续判断第三个元素是否等于 5 ？ 2 == 5 × • 就会返回指向第五个元素的迭代器 。 1 4 2 8 5 7 要找的数 内存 5 ==? 地址 a a+1 a+2 a+3 a+4 a+5 vector 查找为什么低效 • 在由 n 个数组成的 vector 中查找一个数，最好需要 1 次比较运算就能找到（例如查找 1 ）。 • 最坏需要 n 次比较运算才能找到或者发现找不到（例如查找 7 ，或者找一个不存在的 数）。 • 所以我们说