优化：Tips for Optimizing C/C++ Code

前言

读到一篇不长但是很有指导性，也很实用的优化相关的文章，虽然标题带C/C++，内容基本是以游戏客户端举例，不过里面很多内容都是大部分语言通用的语法，可以通用在任何语言

为了更好的记录，自己翻译一下 (: 还好文章不长，还好有翻译app

原文

chrome-extension://ikhdkkncnoglghljlkmcimlnlhkeamad/pdf-viewer/web/viewer.html?file=https%3A%2F%2Fpeople.cs.clemson.edu%2F~dhouse%2Fcourses%2F405%2Fpapers%2Foptimize.pdf

翻译/记录

记住阿姆达尔（Ahmdal）定律:

$$Speedup = \frac {time_{old}}{time_{new}} = \frac{1}{(1 - func_{cost}) + func_{cost} / func_{speedup}} $$

其中 $func_{cost}$ 是指函数 $func$ 运行时间的百分比，$func_{speedup}$ 是加速函数的因子
因此，如果优化占运行时间40%的函数 TriangleIntersect()，使其运行速度提高两倍，那么你的程序运行速度将提高 25%($\frac{1}{(1 - 0.4) + 0.4 / 2} = \frac{1}{0.8} = 1.25$)
这意味着不经常使用的代码（例如，场景加载器）可能应该很少被优化（如果有的话）
这通常被表述为：让常见的情况快速，让罕见的情况正确

先编写代码以获得正确性，然后再优化！

这并不意味着编写功能齐全的光线追踪器 8 周，然后再优化 8 周！
分多个步骤对光线追踪器执行优化
编写正确性，然后如果您知道函数将被频繁调用，执行明显的优化
然后分析以发现瓶颈，并消除瓶颈（通过优化或改进算法）
通常改进算法会极大地改变瓶颈——也许是你意想不到的功能。这是对您知道会经常使用的所有函数进行明显优化的一个很好的理由

我认识的那些编写非常高效的代码的人说，他们优化代码的时间至少是编写代码的两倍

Jumps(跳转)/branches(分支) 很贵. 尽可能减少它们的使用

函数调用需要两次跳转，除了堆栈内存操作
优先使用迭代而不是递归
对短函数使用内联函数以消除函数开销

在函数调用中移动循环
例如:

1 2	for(i = 0; i < 100; ++i) DoSomething();

修改为

1
2
3

DoSomething() {
    for(i = 0; i < 100; ++i) {...} 
}

很长的 if...else if...else if... else if... 对于链结尾附近的情况，需要跳转很多次（除非需要测试每个条件）。如果可能，请转换为 switch 语句，编译器有时会将其优化为单次跳转的表查找。如果不可能有 switch 语句，请将最常用的子句放在 if 链的开头

关注数组索引的顺序

二维和更高维的数组仍然存储在一维内存中。这意味着（对于 C/C++ 数组）array[i][j] 和 array[i][j+1] 彼此相邻，而array[i][j]和array[i+1][j] 可能距离任意远
以或多或少的顺序方式访问存储在物理内存中的数据，可以显着加速您的代码（有时是一个数量级或更多）！
当现代 CPU 将数据从主内存加载到处理器时缓存，它们获取的不仅仅是单个值。相反，它们获取包含请求数据和相邻数据（acacheline）的内存块。这意味着array[i][j]在CPU缓存中之后，array[i][j+1]很有可能已经在缓存中，而array[i+1][j]很可能还在主存中

关注指令级并行运算

尽管许多应用程序仍然依赖单线程执行，但现代 CPU 已经在单核内具有大量并行性。这意味着单个 CPU 可能同时执行 4 次浮点乘法，等待 4 次内存请求，并为即将到来的分支执行比较
为了充分利用这种并行性，代码块（即跳转之间）需要有足够的并行指令以允许充分利用 CPU
考虑展开循环以改善这一点
这也是使用内联函数的一个很好的理由

避免/减少局部变量的数量

局部变量通常存储在堆栈中。但是如果数量足够少，它们也可以被存放在寄存器中。在这种情况下，函数不仅可以获得存储在寄存器中的数据的快速内存访问的好处，而且函数还避免了设置堆栈框架的开销
（但是，不要完全切换到全局变量！）

减少函数参数的数量

与减少局部变量的原因相同–它们也被存储在堆栈中

通过引用传递struct(结构)，而不是通过值

据我所知，在光线追踪器中，没有任何情况下结构应该通过值来传递（即使是像矢量、点和颜色这样的简单结构）

如果你不需要一个函数的返回值，就不要定义一个

尽量避免casting（强制类型转换）

整数和浮点指令通常在不同的寄存器上运行，因此强制转换需要复制
较短的整数类型（char 和 short）仍然需要使用全尺寸寄存器，并且需要将它们填充到 32/64 位然后在存储回内存之前转换回较小的大小（但是，此成本必须与较大数据类型的额外内存成本进行权衡）

声明 C++ 对象变量时要非常小心

使用初始化而不是赋值
1
Color c(black);
比下面这种形式快的多
1
Color c; c = black;

让默认的类构造函数尽可能轻巧

特别是对于简单的、经常使用的类（例如，颜色、向量、点等）
这些默认的构造函数经常在你意想不到的地方被调用

使用构造函数初始化器列表
使用：

1
2
3

Color::Color() 
    : r(0), g(0), b(0)
{}

而不是

1 2	Color::Color() { r = g = b = 0; }

尽可能使用位操作`>>, <<`代替整数乘法和除法

谨慎使用表格查询功能

许多人鼓励对复杂的函数（例如三角函数）使用预先计算的数值表。对于光线追踪来说，这通常是不必要的。内存查找的成本非常高（而且越来越高），重新计算一个三角函数的速度往往和从内存中检索数值的速度一样快（特别是当你考虑到三角函数的查找会污染CPU的缓存）
在其他情况下，查找表可能非常有用。对于 GPU 编程，对于复杂函数，通常首选表查找

对于大多数对象类型，使用运算符`+=`、`-=`、`=`和`/=`，而不是运算符`+`、`-`、``和`/`

简单的操作需要创建一个未命名的、临时的中间对象
例如：
1
Vector v = Vector(1,0,0) + Vector(0,1,0) + Vector(0,0,1);
创建五个未命名的临时Vector对象：
Vector(1,0,0)
Vector(0,1,0)
Vector(0,0,1)
Vector(1,0,0) + Vector(0,1,0)
Vector(1,0,0) + Vector(0,0,0)
稍微啰嗦的代码：
1
2
3
Vector v(1,0,0);
v+= Vector(0,1,0);
v+= Vector(0,0,1);
只创建两个临时Vector：
Vector(0,1,0)
Vector(0,0,1)
这节省了6个函数调用（3个构造函数和3个析构函数）

对于基本数据类型，使用运算符`+`、`-`、``和`/`而不是运算符`+=`、`-=`、`=`和`/=`

延迟声明局部变量

声明对象变量总是涉及一个函数调用（构造函数）
如果一个变量只是有时需要（例如在 if 语句中）只在必要时才声明，那么只有在使用这个变量的时侯才调用构造函数

对于对象，使用前缀运算符（`++obj`）而不是后缀运算符（`obj++`）

这在你的光线追踪器中可能不会成为一个问题
使用后缀操作符必然会对对象进行拷贝（额外调用constructor和destructor），而前缀操作符不需要临时拷贝

谨慎使用模板

有时候对各种实例可能需要不同方式的优化
标准模板库优化得相当好，但如果你打算实现交互式光线追踪器，我会避免使用它
为什么？通过自己实现它，你会知道它使用的算法，所以你会知道使用代码的最有效方式
更重要的是，我的经验是：STL库的调试编译很慢。通常情况下，这不是一个问题，除非你需要使用调试版本进行性能剖析。你会发现STL构造、迭代等使用了15％以上的运行时间，这可能会使性能剖析报告输出很混乱

在计算过程中避免动态内存分配

动态内存非常适用于存储场景和其他在计算过程中不改变的数据
然而，在许多（大多数）系统上，动态内存分配需要使用锁来控制对分配器的访问。对于使用动态内存的多线程应用程序，由于需要等待分配和释放内存，增加额外的处理器实际上可能会导致速度减慢
即使是单线程的应用程序，在堆上分配内存也比在堆上添加内存要昂贵。操作系统需要进行一些计算来找到一个大小合适的内存块

查找并且利用系统内存缓存相关的信息

如果一个数据结构适合在一个缓存行中，那么只需要从主内存中提取一次就可以处理整个类
确保所有数据结构都和cache line边界对齐。（假设你的数据结构和缓存行都是 128 字节，如果你的结构的 1 个字节在第一个缓存行中，而其他 127 个字节在第二个缓存行中，性能仍然会很差）

避免不必要的数据初始化

如果你必须初始化一大块内存，考虑使用memset()

尽量提前结束循环和提前返回函数

考虑将一条射线和一个三角形相交。常见的情况是，射线会错过三角形。因此，这应该被优化
如果你决定让射线与三角形平面相交，如果射线平面相交的t值为负数，你可以立即返回。这样你就可以跳过大约一半的射线与三角形相交处的重心坐标计算。这是个大胜利。一旦你知道没有相交发生，相交函数就应该退出
同样，有些循环可以提前终止。例如，在拍摄阴影射线时，最近的交叉点的位置是不必要的。一旦发现任何结论性的相交点，相交程序就可以返回

在纸上简化你的公式

在许多方程中，等式两边的项会被抵消……要么总是如此，要么在某些特殊情况下如此
编译器无法找到这些简化，但你可以。只是消除内循环中一些耗时的操作，比其他需要优化好几天的地方更事半功倍

integers、fixed-points、32-bit floats、64-bit double 在数学运算之间的差别并不像你想象的那么大

在现代 CPU 上，浮点运算与整数运算的吞吐量基本相同。在光线追踪等计算密集型程序中，这导致整数和浮点成本之间的差异可以忽略不计。这意味着，您不应该特意把浮点数转成整数再运算
双精度浮点运算可能并不比单精度浮点运算慢，特别是在64位机器上。我见过在同一台机器上，射线追踪器使用所有的双精度运算比所有的浮点运算更快。我也看到过相反的情况

考虑重新表述你的数学的方法，以消除耗时的操作

sqrt()通常是可以避免的，特别是在比较值的平方时可以得到相同的结果
如果你反复除以x，可以考虑计算$\frac{1}{x}$并乘以结果。这曾经是向量归一化的一个大赢家（3次除法），但我最近发现它现在是一个折腾的过程。然而，如果你做的除法超过3次，它应该还是有好处的
如果你执行一个循环，确保在迭代之间没有变化的计算被拉出循环
考虑是否可以在一个循环中增量计算数值（而不是每次迭代都从头计算）

待续

https://www.eventhelix.com/embedded/optimizing-c-and-cpp-code/

前言

原文