性能优化 之 无分支编程 Branchless Programming by 彭于斌（ @archibate ） 两种代码写法：分支 vs 三目运算符 两种使用方式：排序 vs 不排序 测试结果（均为 gcc -O3 ） 测试结果可视化 图表比较：分支 vs 无分支 分支 无分支 0 0.01 0.02 0.03 耗时（越低越好） 乱序 有序 • 传统的分支方法实现的 uppercase ，对于 排序过的数据明显比乱序时高效。 • 无分支的方法对于乱序和有序的数据一样 高效，性能吊打了传统的分支方法。 • 对于传统分支的做法，为什么排序了的更 高效？既然无分支更高效，我要怎样优化 才能让我的程序变成无分支的呢？那就来 看本期性能优化专题课吧！ 分支预测成败对性能的影响 排序为什么对有分支的版本影响那么大 为什么需要流水线 • 为了高效， CPU 的内部其实是一个流水 、 90% 、 99% 直到有一次， 突然出现了一次分支 B 成功的案例， CPU 瞬间被打脸！不得不浪费 99% 已经填满 A 数 据的流水线清空，重启整个流水线，这就是分支预测失败，他是导致分支性能低下的罪魁祸 首。不过被打了一次脸的 CPU 还不敢相信，觉得这可能只是碰巧，下一次还是会执行分 支 A 的吧，所以他只是把分支 A 的比例下调到 80% ，直到第二次又被打脸，下调到最初 的起点 50%……

• 等价于： • const K &k = tmp.first; • V &v = tmp.second; • 其实，就算遍历时不修改，还是建议加引用，在 K 和 V 类型尺寸很大时，可以节省性能 。 • 因为引用最多只有 8 字节（指针的大小），而他指向的 V 可能是非常大的（比如 string 类型在栈上的空间就要消耗 32 字节，更不用说可能堆上还有），深拷贝一下要花费不少 时间。 map 中的 堆空间 执行你这段代码 的栈空间 & ( 深拷贝，浪费时间 ) v （假如非常大的话） • 其实，就算遍历时不修改，还是建议加引用，在 K 和 V 类型尺寸很大时，可以节省性能 。 • 因为引用最多只有 8 字节（指针的大小），而他指向的 V 可能是非常大的（比如 string 类型在栈上的空间就要消耗 32 字节，更不用说可能堆上还有），深拷贝一下要花费不少 时间。

生成器； MacOS 系统默认是 Xcode 生成器。 • 可以用 -G 参数改用别的生成器，例如 cmake -GNinja 会生成 Ninja 这个构建系统的构 建规则。 Ninja 是一个高性能，跨平台的构建系统， Linux 、 Windows 、 MacOS 上都可 以用。 • Ninja 可以从包管理器里安装，没有包管理器的 Windows 可以用 Python 的包管理器安 装： • 事实上， MSBuild 是单核心的构建系统， Makefile 虽然多核心但因历史兼容原因效率一 般。 • 而 Ninja 则是专为性能优化的构建系统，他和 CMake 结合都是行业标准了。 Ninja 和 Makefile 简单的对比 性能上： Ninja > Makefile > MSBuild Makefile 启动时会把每个文件都检测一遍， 浪费很多时间。特别是有很多文件，但是实 CMAKE_BUILD_TYPE 是 CMake 中一个特殊的变量，用于控制构建类型，他的值可以 是： • Debug 调试模式，完全不优化，生成调试信息，方便调试程序 • Release 发布模式，优化程度最高，性能最佳，但是编译比 Debug 慢 • MinSizeRel 最小体积发布，生成的文件比 Release 更小，不完全优化，减少二进制体积 • RelWithDebInfo 带调试信息发布，生成的文件比

global 可以调 用 device ； device 可以调用 device 。 声明为内联函数 • 注意， inline 在现代 C++ 中的效果是声明一个函数为 weak 符号，和性能优化意义上的内联无关。 • 优化意义上的内联指把函数体直接放到调用者那里去。 • 因此 CUDA 编译器提供了一个“私货”关键字： __inline__ 来 声明一个函数为内联。不论是 CPU 获取 y 方向的线程编号，以此类推。 那二维呢？ • 需要二维的话，只需要把 dim3 最后一位 （ z 方向）的值设为 1 即可。这样就只有 xy 方向有大小，就相当于二维了，不会有 性能损失。实际上一维的 <<>> 不 过是 <<>> 的简写而已。 图片解释三维的板块和线程 • 之所以会把 blockDim 先传回到 CPU 再进行调用，这是 CUDA 特有的能力。 常用于这种情况：需要从 GPU 端动态计算出 blockDim 和 gridDim ，而又不希望导回数据到 CPU 导致强制同步影响性能。 这种模式被称为动态并行（ dynamic parallelism ）， OpenGL 有一 个 glDispatchComputeIndirect 的 API 和这个很像，但毕竟没有 CUDA

就没问题，因为他们是静态大小，编译器可 以检测到并自动扁平化，转换成乘法和加法来计算地址。 今日乳 Ja (1/1) 有一种病 ~ 叫 JavaBean~ 为什么二级指针是低效的存储和索引方式 随机访问性能测试 内存分配性能测试 二维数组：行主序与列主序 • 实际上二维数组的扁平化分为两种方法，行主序与列主序。 • （以下符号约定： i 行号， j 列号； n 行数， m 列数） • C/C++ 编译器把静态数组 我们已经仁至义尽地尽量 消除了。 • 如果单单采用手动预取，或者单单采用循环分块，那反而还会变慢。这就是性能调优中的一 大难点：某个改动可能对性能没有效果，甚至反而产生负面效果。然而有经验的优化人员会 知道，这不一定意味着这项改动是错的：有可能要配合多个改动一起上，才能有正面效果。 • 性能优化我们需要尝试所有的排列组合，而不能使用控制变量法，否则无法发现这种组合拳 。 用 stream 直写，进一步优化写入带宽 blockSize*nx*nblur 改进：只对 X 循环做分块 BM_y_blur_tiled BM_y_blur_tiled_only_x 因此，可以只对 X 循环分块，并且把外 层改成 XY 序，形成 XYx 序。 需要缓存： blockSize*nx*nblur 需要缓存： blockSize*nblur 改进：只对 X 循环做分块 • 反而变慢了，是怎么回事？ • 记得小彭老师说过，性能优化讲究组合拳，光看一

学 C++ 从 CMake 学起 by 彭于斌（ @archibate ） 高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ 入门：常用 STL 容器， RAII 内存管理 3.现代 C++ 进阶：模板元编程与函数式编程 4.编译器如何自动优化：从汇编角度看 bombela/backward-cpp - 实现了 C++ 的堆栈回溯便于调试 7. google/googletest - 谷歌单元测试框架 8. google/benchmark - 谷歌性能评估框架 9. glfw/glfw - OpenGL 窗口和上下文管理 10.libigl/libigl - 各种图形学算法大合集 fmt - 使用这个神奇的格式化库 • fmt::format

往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ • 可为何直到今天也生产不出 10GHz 的芯片？ • 结论：狭义的摩尔定律没有失效。但晶体管数 量的增加，不再用于继续提升单核频率，转而 用于增加核心数量。单核性能不再指数增长！ 你醒啦？免费午餐结束了！ 指望靠单核性能的增长带来程序性 能提升的时代一去不复返了，现在 要我们动动手为多核优化一下老的 程序，才能搭上摩尔定律的顺风车 。 神话与现实： 2 * 3GHz < 6GHz • • 显然不是。甚至在两个处理器上同时运行两个线程也不见得可以获得两倍的性能。相似的 ，大多数多线程的应用不会比双核处理器的两倍快。他们应该比单核处理器运行的快，但 是性能毕竟不是线性增长。 • 为什么无法做到呢？首先，为了保证缓存一致性以及其他握手协议需要运行时间开销。在 今天，双核或者四核机器在多线程应用方面，其性能不见得的是单核机器的两倍或者四倍。 这一问题一直伴随 CPU 发展至今。

往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ Numeric 接口类并实现 ，其中 multiply(int) 作为虚函数。然后定义： Numeric *twice(Numeric *t) { return t->multiply(2); } 且不说这样的性能问题，你忍得住寂寞去重复定义好 几个，然后每个运算符都要声明一个纯虚函数吗？ 而且， Float 的乘法应该是 multiply(float) ，你也去 定义好几个重载吗？定义为 multiply(Numeric func(int N) ，则变成运行期常量，编译器无法自动优化，只 能运行时根据被调用参数 N 的不同。 • 比如 show_times<0>() 编译器就可以自动优化为一个空函数。 因此模板元编程对高性能编程很重要。 • 通常来说，模板的内部实现需要被暴露出来，除非使用特殊的手 段，否则，定义和实现都必须放在头文件里。 • 但也正因如此，如果过度使用模板，会导致生成的二进制文件大 小剧增，编译变得很慢等。

github@archibate ） 往期录播： https://space.bilibili.com/263032155 PPT 和代码： https://github.com/parallel101/course 高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ 仅当出现“修改一个成员时，其他也成员要 被修改，否则出错”的现象时，才需要 getter/setter 封装。 • 各个成员之间相互正交，比如数学矢量类 Vec3 ，就没必要去搞封装，只会让程序员 变得痛苦，同时还有一定性能损失：特别 是如果 getter/setter 函数分离了声明和定 义，实现在另一个文件时！ C++ 思想： RAII （ Resource Acquisition Is Initialization 糊（有好处也有坏处，对高性能计算而言利大于 弊） 如果没有解构函数，则每个带有返回的分 支都要手动释放所有之前的资源 : RAII ：异常安全（ exception-safe ） C++ 标准保证当异常发生时，会调用已创建对象的解构函数 。 因此 C++ 中没有（也不需要） finally 语句。 如果此处不关闭，则可等 待稍后垃圾回收时关闭。 虽然最后还是关了，但如 果对时序有要求或对性能 有要求就不能依靠