字符串的优化
糟糕的字符串连接函数
在C++中字符串是按照值的形式实现的，又因为C++中字符串底层是使用动态内存实现的，因此、在项目中对字符串的优化必不可少，也是性能优化的重点。
假如代码中有如下remove_ctrl函数的实现：
std::string remove_ctrl(std::string s) {
std::string result;
for (int i=0; i<s.length(); ++i) {
if(s[i] >= 0x20)
result = result + s[i];
}
return result;
}
remove_ctrl() 在循环中对通过参数接收到的字符串 s 的每个字符进行处理。循环中的代码就是导致这个函数成为热点的原因。 if 条件语句从字符串中得到一个字符，然后与一个字面常量进行比较。这里没有什么问题。但是第 5 行的语句就不一样了。
正如之前所指出的，字符串连接运算符的开销是很大的。它会调用内存管理器去构建一个新的临时字符串对象来保存连接后的字符串。如果传递给 remove_ctrl() 的参数是一个由大于0x2(可打印)的字符组成的字符串，那么 remove_ctrl() 几乎会为 s 中的每个字符都构建一个临时字符串对象。对于一个由 100 个字符组成的字符串而言，这会调用 100 次内存管理器来为临时字符串分配内存，调用 100 次内存管理器来释放内存
对上述代码进行基准测试，结果如下：
-------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------
bench_remove_ctrl_operator 12433 ns 12432 ns 54195
如果你的代码编辑器带自动检查，就会发现这样的代码连代码编辑器都受不了，给你显示一大堆波浪号。
使用复合赋值操作避免临时字符串
注意观察上面实现的第5行代码result = result + s[i];，因为字符串是按照值处理的，等号右边的值想加后会在挨个赋值到等号左边，这样如果参数字符串有n个字符，那么remove_ctrl会复制O(n[^2])个自负，所有这些内存分配和复制都会导致性能变差。
为了减少字符串的复制，可以使用复合操作符+=，使用复合操作符之后的代码如下:
std::string remove_ctrl(std::string s) {
std::string result;
for (int i=0; i<s.length(); ++i) {
if(s[i] >= 0x20)
result += s[i];
}
return result;
}
改进之后测试结果：
-------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------
bench_remove_ctrl_operator 12433 ns 12432 ns 54195
bench_remove_ctrl_operator_opt 12400 ns 12400 ns 56281
可以看出测试结果中改进之后的代码明显比没有改进之前快很多，而且这个时间会随着传入的字符串的长度增长而增加，传入的字符串越长，没有改进的代码需要复制的就越多。
通过预留存储空间来减少内存的重新分配
经过上述优化之后，result仍然存在在执行的过程中，由于缓存区不够需要重新分配的情况，导致频繁分配内存，可以通过提前分配内存优化该问题，结果如下：
std::string remove_ctrl_reserve(std::string s) {
std::string result;
result.reserve(s.length());
for (int i=0; i< (int)s.length(); ++i) {
if(s[i] >= 0x20)
result += s[i];
}
return result;
}
运行结果：
-------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------
bench_remove_ctrl_operator 12170 ns 12168 ns 56990
bench_remove_ctrl_operator_opt 12390 ns 12388 ns 57518
bench_remove_ctrl_reserve 767 ns 767 ns 908214
消除对参数字符串的复制
上述方法中还是会对参数字符串进行一次复制，由于内存分配是非常昂贵的，因此哪怕是一次内存分配也值得从程序中去除，优化之后参数按照引用传递，结果如下：
std::string remove_ctrl_ref_args(std::string &s) {
std::string result;
result.reserve(s.length());
for (int i=0; i< (int)s.length(); ++i) {
if(s[i] >= 0x20)
result += s[i];
}
return result;
}
更改之后运行结果：
-------------------------------------------------------------------------
Benchmark Time CPU Iterations
-------------------------------------------------------------------------
bench_remove_ctrl_operator 12158 ns 12159 ns 56439
bench_remove_ctrl_operator_opt 12044 ns 12046 ns 57409
bench_remove_ctrl_reserve 762 ns 762 ns 921342
bench_remove_ctrl_ref_args 737 ns 738 ns 938882
移除对返回值的复制
经过上述的优化之后，性能已经有了很大的改善。但是仔细观察代码还是能发现存在不必要的内存申请的地方，那就是返回值，每次在处理好字符串之后，返回时还需要复制一次，这时也会申请内存。我们完全可以将字符串通过引用传出去，改进之后的代码如下：
void remove_ctrl_ref_result_it(std::string &result, std::string const &s) {
result.clear();
result.reserve(s.length());
for (auto &it:s) {
if (it >= 0x20)
result += it;
}
}
改进之后的运行结果如下：
--------------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------------
bench_remove_ctrl_operator 11948 ns 11949 ns 55770
bench_remove_ctrl_operator_opt 12088 ns 12089 ns 58264
bench_remove_ctrl_reserve 767 ns 767 ns 899659
bench_remove_ctrl_ref_args 742 ns 742 ns 948853
bench_remove_ctrl_ref_args_it 758 ns 758 ns 922450
bench_remove_ctrl_ref_result_it 493 ns 493 ns 1382138
可以看到，当返回值也通过引用返回时，函数调用的耗时一下子降低到了493纳秒。
用字符串代替数组
当程序有严格的性能要求的时候，不是使用C++风格的字符串，而应该使用C风格的字符数组，使用字符数组需要程序员自己控制内存的申请和释放，能够最大程度提升性能，但是带来的后果就是维护的成本增加
void remove_ctrl_cstrings(char* destp, char const* srcp, size_t size) {
for (size_t i=0; i<size; ++i) {
if (srcp[i] >= 0x20)
*destp++ = srcp[i];
}
*destp = 0;
}
使用C风格的字符数组测试结果：
--------------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------------
bench_remove_ctrl_operator 12103 ns 12103 ns 55630
bench_remove_ctrl_operator_opt 12175 ns 12175 ns 57324
bench_remove_ctrl_reserve 765 ns 765 ns 918301
bench_remove_ctrl_ref_args 746 ns 746 ns 938322
bench_remove_ctrl_ref_args_it 751 ns 751 ns 912842
bench_remove_ctrl_ref_result_it 497 ns 497 ns 1394954
bench_remove_ctrl_cstrings 270 ns 270 ns 2575663
使用更好的算法
有没有即好维护又有高性能的的方法，答案是有的，那就是使用更好的算法。
经过对以上的改进的思考，我们发现只要想办法能够减少内存的申请和释放，字符串也能有很高的性能，这就是新算法需要下手的地方。
因为、老的实现方式，是每个值都要对比之后，挨个添加到result中，这就导致频繁的操作内存，新算法中使用append一段一段的取符合条件的字符串添加到result中，实际测试结果141纳秒左右，已经优于C风格的字符串，这就要感谢算法带来的buff加成。
void remove_ctrl_block_append(std::string &result, const std::string &s) {
result.clear();
result.reserve(s.length());
for (size_t b=0,i=b; b < s.length(); b = i+1) {
for (i=b; i<s.length(); ++i) {
if (s[i] < 0x20) break;
}
result.append(s, b, i-b);
}
}
运行结果：
--------------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------------
bench_remove_ctrl_operator 12258 ns 12257 ns 54639
bench_remove_ctrl_operator_opt 12347 ns 12347 ns 56488
bench_remove_ctrl_reserve 765 ns 765 ns 896059
bench_remove_ctrl_ref_args 736 ns 736 ns 947049
bench_remove_ctrl_ref_args_it 746 ns 746 ns 926601
bench_remove_ctrl_ref_result_it 494 ns 494 ns 1394869
bench_remove_ctrl_cstrings 270 ns 270 ns 2562077
bench_remove_block_append 141 ns 141 ns 4941262
当然，还可以使用剔除不符合要求字符的方式实现：
void remove_ctrl_erase(std::string &s) {
for (size_t i = 0; i < s.length();)
if (s[i] < 0x20)
s.erase(i,1);
else ++i;
}
测试结果：
--------------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------------
bench_remove_ctrl_operator 12146 ns 12146 ns 56901
bench_remove_ctrl_operator_opt 12254 ns 12254 ns 56758
bench_remove_ctrl_reserve 756 ns 756 ns 909901
bench_remove_ctrl_ref_args 735 ns 735 ns 938884
bench_remove_ctrl_ref_args_it 748 ns 748 ns 922788
bench_remove_ctrl_ref_result_it 494 ns 494 ns 1422658
bench_remove_ctrl_cstrings 275 ns 275 ns 2534856
bench_remove_block_append 143 ns 143 ns 4871896
bench_remove_erase 169 ns 169 ns 4104307
当然、还可以使用更优秀的库，使用优化性能更好的编译器，或者为自己的业务专门定制一个字符串的类，来达到最优。