C++性能优化，简直太硬核了！

前言

性能优化不管是从方法论&＃xff0c;还是从实践上都有很多东西。本文从 C&＃43;&＃43; 语本身入手&＃xff0c;介绍了一些性能优化的方法&＃xff0c;希望能做到简洁实用。

实例1

在开始本文的内容之前&＃xff0c;让我们看段小程序&＃xff1a;

// 获取一个整数对应10近制的位数
uint32_t digits10_v1(uint64_t v) {uint32_t result &＃61; 0;do {&＃43;&＃43;result;v /&＃61; 10;} while (v);return result;
}

如果要对这段代码进行优化&＃xff0c;你认为瓶颈会是什么呢&＃xff1f;代码 -g -O2 后看一眼汇编&＃xff1a;

Dump of assembler code for function digits10_v1(uint64_t):
0x00000000004008f0 : mov %rdi,%rdx
0x00000000004008f3 : xor %esi,%esi
0x00000000004008f5 : mov $0xcccccccccccccccd,%rcx
0x00000000004008ff : nop
0x0000000000400900 : mov %rdx,%rax
0x0000000000400903 : add $0x1,%esi
0x0000000000400906 : mul %rcx
0x0000000000400909 : shr $0x3,%rdx
0x000000000040090d : test %rdx,%rdx
0x0000000000400910 : jne 0x400900
0x0000000000400912 : mov %esi,%eax
0x0000000000400914 : retq/*
注&＃xff1a;对于常数的除法操作&＃xff0c;编译器一般会转换成乘法&＃43;移位的方式&＃xff0c;即
a / b &＃61; a * (1/b) &＃61; a * (2^n / b) * (1 / 2^n) &＃61; a * (2^n / b) >> n.
这里的n&＃61;3, b&＃61;10, 2^n/b&＃61;4/5&＃xff0c;0xcccccccccccccccd是编译器对4/5的定点算法表示
*/

指令已经很少了&＃xff0c;有多少优化空间呢&＃xff1f;先不着急&＃xff0c;看看下面这段代码

uint32_t digits10_v2(uint64_t v) {uint32_t result &＃61; 1;for (;;) {if (v <10) return result;if (v <100) return result &＃43; 1;if (v <1000) return result &＃43; 2;if (v <10000) return result &＃43; 3;// Skip ahead by 4 orders of magnitudev /&＃61; 10000U;result &＃43;&＃61; 4;}
}uint32_t digits10_v3(uint64_t v) {if (v <10) return 1;if (v <100) return 2;if (v <1000) return 3;if (v <1000000000000) { // 10^12if (v <100000000) { // 10^7if (v <1000000) { // 10^6if (v <10000) return 4;return 5 &＃43; (v >&＃61; 100000); // 10^5}return 7 &＃43; (v >&＃61; 10000000); // 10^7}if (v <10000000000) { // 10^10return 9 &＃43; (v >&＃61; 1000000000); // 10^9}return 11 &＃43; (v >&＃61; 100000000000); // 10^11}return 12 &＃43; digits10_v3(v / 1000000000000); // 10^12
}

写了一个小程序&＃xff0c;digits10_v2 比 digits10_v1 快了 45%, digits10_v3 比digits10_v1 快了60%&＃43;。不难看出测试结论跟数据的取值范围相关&＃xff0c;就本例来说数值越大&＃xff0c;提升越明显。是什么原因呢&＃xff1f;附测试程序&＃xff1a;

int main() {srand(100);uint64_t digit10_array[ITEM_COUNT];for( int i &＃61; 0; i // digits10_v1uint64_t sum1 &＃61; 0;uint64_t time1 &＃61; 0;gettimeofday(&start,NULL);for( int i &＃61; 0; i }
/*

执行结果&＃xff1a;

g&＃43;&＃43; -g -O2 cplusplus_optimize.cpp && ./a.out
sum1:9944152 sum2:9944152 sum3:9944152
cost1:27560us cost2:14998us cost3:10525us cost2/cost1:0.544194 cost3/cost1:0.381894
*/

Strength reduction

优化原因不是因为做了循环展开&＃xff0c;而是由于不同指令本身的速度就是不一样的&＃xff0c;比较、整型的加减、位操作速度都是最快的&＃xff0c;而除法/取余却很慢。下面有一个更详细的列表&＃xff0c;为了更直观一些&＃xff0c;用了clock cycle 来衡量&＃xff0c;不过这里的 clock cycle 是个平均值&＃xff0c;不同的 CPU 还是稍有差异&＃xff1a;

* comparisons (1 clock cycle)
* (u)int add, subtract, bitops, shift (1 clock cycle)
* floating point add, sub (3~6 clock cycle)
* indexed array access (cache effects)
* (u)int32 mul (3~4 clock cycle)
* Floating point mul (4~8 clock cycle)
* Float Point division, remainder (14~45 clock cycle)
* (u)int division, remainder (40~80 clock cycle)

虽然大多数场景下&＃xff0c;数学运算都不会有太多性能问题&＃xff0c;但相对来说&＃xff0c;整型的除法运算还是比较昂贵的。编译器就会利用这一特点进行优化&＃xff0c;一般称作 Strength reduction.

对于前面的例子&＃xff0c;核心原因是 digits10_v2 用比较和加法来减少除法 (/&＃61;) 操作&＃xff0c;digits10_v3 通过搜索的方式进一步减少了除法操作。由于 cpu 并行处理技术&＃xff0c;我们不能简单的用后面的 clock cycle 来衡量性能&＃xff0c;但不难看出处理器对类型的还是非常敏感的&＃xff0c;以整型和浮点的处理为例&＃xff1a;

整型

类型转换

• int--> short/char (0~1 clock cycle)

• int --> float/double (4~16个clock cycle), signed int 快于 unsigned int&＃xff0c;唯一一个场景 signed 比 unsigned 快的

• short/char 的计算通常使用 32bit 存储&＃xff0c;只是返回的时候做了截取&＃xff0c;故只在要考虑内存大小的时候才使用 short/char&＃xff0c;如 array

• 注&＃xff1a;隐式类型转换可能会溢出&＃xff0c;有符号的溢出变成负数&＃xff0c;无符号的溢出变成小的整数

运算

• 除法、取余运算unsigned int 快于 signed int

• 除以常量比除以变量效率高&＃xff0c;因为可以在编译期做优化&＃xff0c;尤其是常量可以表示成2^n时

• &＃43;&＃43;i和i&＃43;&＃43;本身性能一样&＃xff0c;但不同的语境效果不一样&＃xff0c;如array[i&＃43;&＃43;]比arry[&＃43;&＃43;i]性能好&＃xff1b;当依赖自增结果时&＃xff0c;&＃43;&＃43;i性能更好&＃xff0c;如a&＃61;&＃43;&＃43;b,a和b可复用同一个寄存器

代码示例

// div和mod效率
int a, b, c;
a &＃61; b / c; // This is slow
a &＃61; b / 10; // Division by a constant is faster
a &＃61; (unsigned int)b / 10; // Still faster if unsigned
a &＃61; b / 16; // Faster if divisor is a power of 2
a &＃61; (unsigned int)b / 16; // Still faster if unsigned

浮点

• 单精度、双精度的计算性能是一样的

• 常量的默认精度是双精度

• 不要混淆单精度、双精度&＃xff0c;混合精度计算会带来额外的精度转换开销&＃xff0c;如

// 混用
float a, b;
a &＃61; b * 1.2; // bad. 先将b转换成double&＃xff0c;返回结果转回成float
// Example 14.18b
float a, b;
a &＃61; b * 1.2f; // ok. everything is float
// Example 14.18c
double a, b;
a &＃61; b * 1.2; // ok. everything is double

浮点除法比乘法慢很多&＃xff0c;故可以利用乘法来加快速度&＃xff0c;如:

double y, a1, a2, b1, b2;
y &＃61; a1/b1 &＃43; a2/b2; // slow
double y, a1, a2, b1, b2;
y &＃61; (a1*b2 &＃43; a2*b1) / (b1*b2); // faster

这里介绍的大多是编译器的擅长但又不能直接优化的场景&＃xff0c;也是平常优化中比较容易忽视的点&＃xff0c;其实往往我们往前多走一步&＃xff0c;编译器就可以工作得更好。

实例2

先看一个数字转字符串的例子&＃xff0c;stringstream 和 sprintf 自然不会是我们考虑的对象&＃xff0c;虽然 protobuf 库中的 FastInt32ToBuffer 很不错&＃xff0c;其实还能优化&＃xff0c;下面的版本就比例子中 stringstream 快 6 倍&＃xff0c;代码如下&＃xff1a;

// integer to string
uint32_t u64ToAscii_v1(uint64_t value, char* dst) {// Write backwards.char* start &＃61; dst;do {*dst&＃43;&＃43; &＃61; &＃39;0&＃39; &＃43; (value % 10);value /&＃61; 10;} while (value !&＃61; 0);const uint32_t result &＃61; dst - start;// Reverse in place.for (dst--; dst > start; start&＃43;&＃43;, dst--) {std::iter_swap(dst, start);}return result;
}

不用细读 stringstream/sprintf 的源码&＃xff0c;反汇编看下就能知道个大概&＃xff0c;对于转字符串这个场景&＃xff0c;stringstream/sprintf 就太重了&＃xff0c;通常来说越少的指令性能也越好,本文讨论的重点是内存访问&＃xff0c;就上面这段代码&＃xff0c;有什么内存使用上的问题&＃xff1f;如何进一步优化&＃xff1f;

分析

优化前还是得找一下性能热点&＃xff0c;下面是 vtune 结果的截图(虽然 cpu time 和汇编指令的消耗对应得不是特别好):

vtune_1

vtune_2

数组 reverse 的开销跟上面生成数组元素相近&＃xff0c;reverse有这么耗时么&＃xff1f;

从图中的汇编可以看出&＃xff0c;一次 swap 对应着两次内存读 (movzxb)、两次内存写 (movb)&＃xff0c;因为一次写就意味着一个读和一个写&＃xff0c;描述的是内存-->cache-->内存的过程。

优化

减少内存写操作 一个很自然的优化想法&＃xff0c;应该尽量避免内存写操作&＃xff0c;于是代码可以进一步优化&＃xff0c;结合 Strength reduction&＃xff0c;代码如下&＃xff1a;

uint32_t u64ToAscii_v2(uint64_t value, char *dst) {const uint32_t result &＃61; digits10_v3(value);uint32_t pos &＃61; result - 1;while (value >&＃61; 10) {const uint64_t q &＃61; value / 10;const uint32_t r &＃61; static_cast(value % 10);dst[pos--] &＃61; &＃39;0&＃39; &＃43; r;value &＃61; q;}*dst &＃61; static_cast(value) &＃43; &＃39;0&＃39;;return result;
}

实测发现新版本比之前版本性能提升了 10%&＃xff0c;还有优化空间么&＃xff1f;答案是&＃xff0c;有。方案是&＃xff1a;通过查表&＃xff0c;一次处理2个数字&＃xff0c;减少数据依赖&＃xff0c;如&＃xff1a;

uint32_t u64ToAscii_v3(uint64_t value, char* dst) {static const char digits[] &＃61;"0001020304050607080910111213141516171819""2021222324252627282930313233343536373839""4041424344454647484950515253545556575859""6061626364656667686970717273747576777879""8081828384858687888990919293949596979899";const size_t length &＃61; digits10_v3(value);uint32_t next &＃61; length - 1;while (value >&＃61; 100) {const uint32_t i &＃61; (value % 100) * 2;value /&＃61; 100;dst[next - 1] &＃61; digits[i];dst[next] &＃61; digits[i &＃43; 1];next -&＃61; 2;}// Handle last 1-2 digitsif (value <10) {dst[next] &＃61; &＃39;0&＃39; &＃43; uint32_t(value);} else {uint32_t i &＃61; uint32_t(value) * 2;dst[next - 1] &＃61; digits[i];dst[next] &＃61; digits[i &＃43; 1];}return length;
}

结论&＃xff1a;

• u64ToAscii_v3性能比基准版本提升了30%&＃xff1b;

• 如果用到悟时的那个测试场景&＃xff0c;性能可以提升6.5倍。

下面是完整的测试代码和结果&＃xff1a;

#include
#include #define ITEM_COUNT 1024*1024
#define RUN_TIMES 1024*1024
#define BUFFERSIZE 32using namespace std;uint32_t digits10_v1(uint64_t v) {uint32_t result &＃61; 0;do {&＃43;&＃43;result;v /&＃61; 10;} while (v);return result;
}uint32_t digits10_v2(uint64_t v) {uint32_t result &＃61; 1;for(;;) {if (v <10) return result;if (v <100) return result &＃43; 1;if (v <1000) return result &＃43; 2;if (v <10000) return result &＃43; 3;v /&＃61; 10000U;result &＃43;&＃61; 4;}return result;
}uint32_t digits10_v3(uint64_t v) {if (v <10) return 1;if (v <100) return 2;if (v <1000) return 3;if (v <1000000000000) { // 10^12if (v <100000000) { // 10^7if (v <1000000) { // 10^6if (v <10000) return 4;return 5 &＃43; (v >&＃61; 100000); // 10^5}return 7 &＃43; (v >&＃61; 10000000); // 10^7}if (v <10000000000) { // 10^10return 9 &＃43; (v >&＃61; 1000000000); // 10^9}return 11 &＃43; (v >&＃61; 100000000000); // 10^11}return 12 &＃43; digits10_v3(v / 1000000000000); // 10^12
}
uint32_t u64ToAscii_v1(uint64_t value, char* dst) {// Write backwards.char* start &＃61; dst;do {*dst&＃43;&＃43; &＃61; &＃39;0&＃39; &＃43; (value % 10);value /&＃61; 10;} while (value !&＃61; 0);const uint32_t result &＃61; dst - start;// Reverse in place.for (dst--; dst > start; start&＃43;&＃43;, dst--) {std::iter_swap(dst, start);}return result;
}uint32_t u64ToAscii_v2(uint64_t value, char *dst) {const uint32_t result &＃61; digits10_v3(value);uint32_t pos &＃61; result - 1;while (value >&＃61; 10) {const uint64_t q &＃61; value / 10;const uint32_t r &＃61; static_cast(value % 10);dst[pos--] &＃61; &＃39;0&＃39; &＃43; r;value &＃61; q;}*dst &＃61; static_cast(value) &＃43; &＃39;0&＃39;;return result;
}uint32_t u64ToAscii_v3(uint64_t value, char* dst) {static const char digits[] &＃61;"0001020304050607080910111213141516171819""2021222324252627282930313233343536373839""4041424344454647484950515253545556575859""6061626364656667686970717273747576777879""8081828384858687888990919293949596979899";const size_t length &＃61; digits10_v3(value);uint32_t next &＃61; length - 1;while (value >&＃61; 100) {const uint32_t i &＃61; (value % 100) * 2;value /&＃61; 100;dst[next - 1] &＃61; digits[i];dst[next] &＃61; digits[i &＃43; 1];next -&＃61; 2;}// Handle last 1-2 digitsif (value <10) {dst[next] &＃61; &＃39;0&＃39; &＃43; uint32_t(value);} else {uint32_t i &＃61; uint32_t(value) * 2;dst[next - 1] &＃61; digits[i];dst[next] &＃61; digits[i &＃43; 1];}return length;
}int main() {srand(100);uint64_t digit10_array[ITEM_COUNT];for( int i &＃61; 0; i // digits10_v1uint64_t sum1 &＃61; 0;uint64_t time1 &＃61; 0;gettimeofday(&start,NULL);for( int i &＃61; 0; i }/* 测试结果g&＃43;&＃43; -g -O2 cplusplus_optimize.cpp -o cplusplus_optimize && ./cplusplus_optimize
sum1:9944152 sum2:9944152 sum3:9944152
cost1:47305us cost2:42448us cost3:31657us cost2/cost1:0.897326 cost3/cost1:0.66921
*/

看到优化写内存操作的威力了吧&＃xff0c;让我们再看一个减少写操作的例子&＃xff1a;

struct Bitfield {
int a:4;
int b:2;
int c:2;
};
Bitfield x;
int A, B, C;
x.a &＃61; A;
x.b &＃61; B;
x.c &＃61; C;

假定 A、B、C 都很小&＃xff0c;且不会溢出&＃xff0c;可以写成

union Bitfield {
struct {
int a:4;
int b:2;
int c:2;
};
char abc;
};
Bitfield x;
int A, B, C;
x.abc &＃61; A | (B <<4) | (C <<6);

如果需要考虑溢出&＃xff0c;也可以改为

x.abc &＃61; (A & 0x0F) | ((B & 3) <<4) | ((C & 3) <<6 );

读取效率

对于内存的写&＃xff0c;最好的办法就是减少写的次数&＃xff0c;那么内存的读取呢&＃xff1f;教科书的答案是&＃xff1a;尽可能顺序访问内存。理解这句话还是得从 cache line 开始&＃xff0c;因为实际的 cpu 比较复杂&＃xff0c;下面的表述尝试做些简化&＃xff0c;如有问题&＃xff0c;欢迎指正&＃xff1a;

cache line

• 假设 L1cache 大小为 8K&＃xff0c;cache line 64 字节、4way&＃xff0c;那么整个 cache 会分成32 个集合&＃xff0c; 81024/64&＃61;128&＃61;324&＃xff0c;一个内存地址进入哪个 cache line 不是任意的&＃xff0c;而是确定在某个集合中&＃xff0c;可以通过公式 (set ) &＃61; (memory address) / ( line size) % (number of sets )来计算&＃xff0c;如地址是 10000&＃xff0c;则(set)&＃61;10000/64%32 &＃61; 28, 即编号为28的集合内的4个 cache line 之一。

• 用 16 进制来描述&＃xff0c;10000&＃61;0x2710 ,一次内存读取是 64bytes&＃xff0c;那么访问内存地址 10000 即意味着地址 0x2700~0x273F 都进集合编号为 28(0x1C) 的 cache line 中了。

cache miss

可以看出&＃xff0c;顺序的访问内存是能够比较高效而且不会因为 cache 冲突&＃xff0c;导致药频繁读取内存。那什么的情况会导致 cache miss 呢&＃xff1f;

• 当某个集合内的 cache line 都有数据时&＃xff0c;且该集合内有新的数据就会导致老数据的换出&＃xff0c;进而访问老数据就会出现 cache miss。

• 以先后读取 0x2710, 0x2F00, 0x3700, 0x3F00, 0x4700 为例, 这几个地址都在 28 这个编号的集合内&＃xff0c;当去读 0x4700 时&＃xff0c;假定 CPU 都是以先进先出策略&＃xff0c;那么 0x2710 就会被换出&＃xff0c;这时候如果再访问 0x2700~0x273F 的数据就 cache miss&＃xff0c;需要重新访问内存了。

• 可以看出变量是否有 cache 竞争&＃xff0c;得看变量地址间的距离&＃xff0c;distance &＃61; (number of sets ) (line size) &＃61; ( total cache size) / ( number of ways) , 即距离为3264 &＃61; 8K/4&＃61; 2K的内存访问都可能产生竞争。

• 上面这些不光对变量、对象有用&＃xff0c;对代码 cache 也是如此。

建议

对于内存的访问&＃xff0c;可以考虑以下一些建议&＃xff1a;

• 一起使用的函数存储在一起。函数的存储通常按照源码中的顺序来的&＃xff0c;如果函数A,B,C是一起调用的&＃xff0c;那尽量让ABC的声明也是这个顺序

• 一起使用的变量存储在一起。使用结构体、对象来定义变量&＃xff0c;并通过局部变量方式来声明&＃xff0c;都是一些较好的选择。例子见后文&＃xff1a;

• 合理使用对齐(attribute((aligned(64)))、预取(prefecting data)&＃xff0c;让一个cacheline能获取到更多有效的数据

• 动态内存分配、STL容器、string都是一些常容易cache不友好的场景&＃xff0c;核心代码处尽量不用

int Func(int);
const int size &＃61; 1024;
int a[size], b[size], i;
...
for (i &＃61; 0; i b[i] &＃61; Func(a[i]);
}
// pack a,b to Sab
int Func(int);
const int size &＃61; 1024;
struct Sab {int a; int b;};
Sab ab[size];
int i;
...
for (i &＃61; 0; i ab[i].b &＃61; Func(ab[i].a);
}

静态变量

让我们再回到最前面的优化&＃xff0c;u64ToAscii_v3 引入了局部静态变量 (digits)&＃xff0c;是否合适&＃xff1f;通常来说&＃xff0c;要具体问题具体分析&＃xff0c;没有标准答案。

静态变量和栈地址是分开的&＃xff0c;可能会带来 cache miss 的问题&＃xff0c;通过去掉 static 修饰符&＃xff0c;直接在栈上声明变的方式可以避免&＃xff0c;但这种做法可行有几个前提条件&＃xff1a;

• 变量大小是要限制的&＃xff0c;不超出cache的大小(最好是L1 cache)

• 变量的初始化在栈上完成&＃xff0c;故最好不要在循环内部定义&＃xff0c;以避免不必要的初始化。

其实内存访问和 CPU 运算是没有一定的赢家&＃xff0c;真正做优化时&＃xff0c;需要结合具体的场景&＃xff0c;仔细测量才能得到答案。

回顾

前面两个实例分别从编译器和内存使用的角度介绍了一些性能优化的方法&＃xff0c;后面内容则会回到cpu&＃xff0c;从指令并行的角度看看我们常见的逻辑控制有哪些可以优化的点。

从原理上来说&＃xff0c;这个系列的优化不是特别区分语言&＃xff0c;只是这里我们用C&＃43;&＃43;来描述。

流水线

通常一个 CPU 可以并行执行多条指令&＃xff0c;如&＃xff1a;4 条浮点乘法&＃xff0c;等待 4 个内存访问、一个还为到来的分支比较&＃xff0c;不同的运算单元也是可以并行计算&＃xff0c;如 for(int i &＃61; 0; i  这里的 i

从流水线的角度看&＃xff0c;指令 pipeline 的几个阶段&＃xff1a;fetch、decode、execute、memory-access、write-back&＃xff0c;除了存储器的访问效率会影响并行度外&＃xff0c;下一条指令的 fetch/decode 也很关键&＃xff0c;而跳转和分支则是又一个拦路虎&＃xff0c;这也是本文接下去要主要分析的地方。