std::vector

对于push_back的优化思路在于：明白当前的工程环境，减小不必要的拷贝。
优化的方法

  • 根据当前的需要，采 reserve 预留出足够的空间，防止vector在阔充空间时的自我拷贝。

    1. void reserve( size_type new_cap );
    2. (until C++20)
    3. constexpr void reserve( size_type new_cap );

  • 采用 emplace_back 替代push_back,防止从暂时栈中的拷贝操作。

  1. vector<int>myvec;
  2. myvec.reserve(3);
  3. myvec.push_back(vector<int>{3});
  4. myvec.emplace_back(3);

emplace_back的具体用法和优势

  1. template< class... Args >
  2. void emplace_back( Args&&... args );
  3. (since C++11)
  4. (until C++17)
  5. template< class... Args >
  6. reference emplace_back( Args&&... args );
  7. (since C++17)
  8. (until C++20)
  9. template< class... Args >
  10. constexpr reference emplace_back( Args&&... args );
  1. #include <vector>
  2. #include <string>
  3. #include <cassert>
  4. #include <iostream>
  6. struct President
  7. {
  8.     std::string name;
  9.     std::string country;
  10.     int year;
  12.     President(std::string p_name, std::string p_country, int p_year)
  13.         : name(std::move(p_name)), country(std::move(p_country)), year(p_year)
  14.     {
  15.         std::cout << "I am being constructed.\n";
  16.     }
  17.     President(President&& other)
  18.         : name(std::move(other.name)), country(std::move(other.country)), year(other.year)
  19.     {
  20.         std::cout << "I am being moved.\n";
  21.     }
  22.     President& operator=(const President& other) = default;
  23. };
  25. int main()
  26. {
  27.     std::vector<President> elections;
  28.     std::cout << "emplace_back:\n";
  29.     auto& ref = elections.emplace_back("Nelson Mandela", "South Africa", 1994);
  30.     assert(ref.year != 1984 && "uses a reference to the created object (C++17)");
  32.     std::vector<President> reElections;
  33.     std::cout << "\npush_back:\n";
  34.     reElections.push_back(President("Franklin Delano Roosevelt", "the USA", 1936));
  36.     std::cout << "\nContents:\n";
  37.     for (President const& president: elections) {
  38.         std::cout << president.name << " was elected president of "
  39.                   << president.country << " in " << president.year << ".\n";
  40.     }
  41.     for (President const& president: reElections) {
  42.         std::cout << president.name << " was re-elected president of "
  43.                   << president.country << " in " << president.year << ".\n";
  44.     }
  45. }

对于内存的建议

  1. 一起使用的函数存储在一起。函数的存储通常按照源码中的顺序来的，如果函数A,B,C是一起调用的，那尽量让ABC的声明也是这个顺序
  2. 一起使用的变量存储在一起。使用结构体、对象来定义变量，并通过局部变量方式来声明，都是一些较好的选择。例子见后文：
  3. 合理使用对齐(attribute((aligned(64)))、预取(prefecting data)，让一个cacheline能获取到更多有效的数据
  4. 动态内存分配、STL容器、string都是一些常容易cache不友好的场景，核心代码处尽量不用
  1. int Func(int);
  2. const int size = 1024;
  3. int a[size], b[size], i;
  4. ...
  5. for (i = 0; i < size; i++) {
  6. b[i] = Func(a[i]);
  7. }
  8. // pack a,b to Sab 
  9. int Func(int);
  10. const int size = 1024;
  11. struct Sab {int a; int b;};
  12. Sab ab[size];
  13. int i;
  14. ...
  15. for (i = 0; i < size; i++) {
  16. ab[i].b = Func(ab[i].a);
  17. }

cache miss

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

  • 当某个集合内的cache line都有数据时，且该集合内有新的数据就会导致老数据的换出，进而访问老数据就会出现cache miss。
  • 以先后读取0x2710, 0x2F00, 0x3700, 0x3F00, 0x4700为例, 这几个地址都在28这个编号的集合内，当去读0x4700时，假定CPU都是以先进先出策略，那么0x2710就会被换出，这时候如果再访问0x2700~0x273F的数据就cache miss，需要重新访问内存了。
  • 可以看出变量是否有cache 竞争，得看变量地址间的距离，distance = (number of sets ) (line size) = ( total cache size) / ( number of ways) , 即距离为3264 = 8K/4= 2K的内存访问都可能产生竞争。

上面这些不光对变量、对象有用，对代码cache也是如此。

静态变量

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

  • 变量大小是要限制的，不超出cache的大小(最好是L1 cache)
  • 变量的初始化在栈上完成，故最好不要在循环内部定义，以避免不必要的初始化。

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

函数

本身开销

  • 函数调用使得处理器跳到另外一个代码地址并回来，一般需要4 clock cycles，大多数情况处理器会把函数调用、返回和其他指令一起执行以节约时间。
  • 函数参数存储在栈上需要额外的时间( 包括栈帧的建立、saving and restoring registers、可能还有异常信息)。在64bit linux上，前6个整型参数(包括指针、引用)、前8个浮点参数会放到寄存器中；64bit windows上不管整型、浮点，会放置4个参数。
  • 在内存中过于分散的代码可能会导致较差的code cache

    优化方式

  1. 避免不必要的函数，特别在最底层的循环，应该尽量让代码在一个函数内。看起来与良好的编码习惯冲突(一个函数最好不要超过80行)，其实不然，跟这个系列其他优化一样，我们应该知道何时去使用这些优化，而不是一上来就让代码不可读。
  2. 尝试使用inline函数，让函数调用的地方直接用函数体替换。inline对编译器来说是个建议，而且不是inline了性能就好，一般当函数比较小或者只有一个地方调用的时候，inline效果会比较好
  3. 在函数内部使用循环(e.g., change for(i=0;i<100;i++) DoSomething(); into DoSomething()
    { for(i=0;i<100;i++) { … } } )
  4. 减少函数的间接调用，如偏向静态链接而不是动态链接，尽量少用或者不用多继承、虚拟继承
  5. 优先使用迭代而不是递归
  6. 使用函数来替换define，从而避免多次求值。宏的其他缺点：不能overload和限制作用域（undef除外）

分支预测

Tips

  • 比较、整型的加减、位操作速度快于除法和取余运算
  • 除法、取余运算unsigned ints 快于 signed ints
  • 除以常量比除以变量效率高，因为可以在编译期做优化，尤其是常量可以表示成2^n时
  • ++i和i++本身性能一样，但不同的语境效果不一样，如array[i++]比arry[++i]性能好；当依赖自增结果时，++i性能更好，如a=++b,a和b可复用同一个寄存器
  • 单精度、双精度的计算性能是一样的

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

    1. // 混用
    2. float a, b;
    3. a = b * 1.2; // bad. 先将b转换成double，返回结果转回成float
    4. // Example 14.18b
    5. float a, b;
    6. a = b * 1.2f; // ok. everything is float
    7. // Example 14.18c
    8. double a, b;
    9. a = b * 1.2; // ok. everything is double

  • 浮点除法比乘法慢很多，故可以利用乘法来加快速度，如

    double y, a1, a2, b1, b2;
y = a1/b1 + a2/b2;  // slow
double y, a1, a2, b1, b2;
y = (a1*b2 + a2*b1) / (b1*b2); // faster

  • 减小内存的写操作。比方将数据提前写到表中。需要数据之时，然后进行查表操作获得所需的诗句

  • 对于内存的读操作，尽可能顺序访问内存

    参考资料

    https://www.zhihu.com/zvideo/1337128432204300288
    https://zhuanlan.zhihu.com/p/33638344