落花逐流水

落花逐流水

关注
发信
关注(28)粉丝(399)

C++程序加速方法

C++程序加速方法

1. 将反复使用的数据存放在全局变量里面

需要重复使用的数据，比如加载的图片，CSV文件等数据，存放在全局变量里面，每次加载DLL时，只加载一次，直到卸载DLL，这些数据一直保持在内存中，避免重复加载。
全局变量的使用参考文献：
https://blog.csdn.net/guoqianqian5812/article/details/52397930

2. 使用多线程

如果程序中有可以同时进行的代码，譬如五道算术题，大家每人算一道，最后只花费1/5的时间就解决了5道题，多线程就是这个思路，现代的CPU都是多核的，就相当于可以同时算五道题目，一旦你的代码使用了多线程，恐怕你再也回不到单线程的时代了。

有一段程序花费300ms，我们开了32个多线程之后花费16ms，加速了20倍，更别提GPU动辄百倍的加速效果。

多线程参考文献：
https://www.cnblogs.com/wangguchangqing/p/6134635.html

3. 用a++和++a，a–,–a

通常使用自加、自减指令和复合赋值表达式(如a-=1及a+=1等)都能够生成高质量的程序代码，编译器通常都能够生成inc和dec之类的指令，而使用a=a+1或a=a-1之类的指令，有很多C编译器都会生成二到三个字节的指令。

4. 减少除法运算

无论是整数还是浮点数的运算，除法都会比较耗时，所以最后将除法运算等效成乘法运算。例如：a/b>20可改为a>b*20，可以简化程序的运行时间。

5. 尽量减少值传递，多用引用来传递参数。

至于其中的原因，相信大家也很清楚，如果参数是int等语言自定义的类型可能能性能的影响还不是很大，但是如果参数是一个类的对象，那么其效率问题就不言而喻了。例如一个判断两个字符串是否相等的函数，其声明如下：

bool Compare（string s1, string s2)
bool Compare(string *s1, string *s2)
bool Compare(string &s1, string &s2)
bool Compare(const string &s1, const string &s2)

其中若使用第一个函数（值传递），则在参数传递和函数返回时，需要调用string的构造函数和析构函数两次（即共多调用了四个函数），而其他的三个函数（指针传递和引用传递）则不需要调用这四个函数。因为指针和引用都不会创建新的对象。如果一个构造一个对象和析构一个对象的开销是庞大的，这就是会效率造成一定的影响。

然而在很多人的眼中，指针是一个恶梦，使用指针就意味着错误，那么就使用引用吧！它与使用普通值传递一样方便直观，同时具有指针传递的高效和能力。因为引用是一个变量的别名，对其操作等同于对实际对象操作，所以当你确定在你的函数是不会或不需要变量参数的值时，就大胆地在声明的前面加上一个const吧，就如最后的一个函数声明一样。

同时加上一个const还有一个好处，就是可以对常量进行引用，若不加上const修饰符，引用是不能引用常量的。

举个例子，我们使用值传递和指针传递的方式传递一张10M的图片，使用值传递会多花费0.1s的时间。假如我们使用了10次值传递，将会增加1s的运行时间。

6. 循环引发的讨论1（循环内定义，还是循环外定义对象）

请看下面的两段代码：
代码1：

ClassTest CT；
for(inti = 0; i < 100; ++i)
{
  CT = a;
  //do something
}

代码2：

for(inti = 0; i < 100; ++i)
{
  ClassTest CT = a;
  //do something
}

你会觉得哪段代码的运行效率较高呢？代码1代码2？其实这种情况下，哪段代码的效率更高是不确定的，或者说是由这个类ClassTest本向决定的，分析如下：

对于代码1：需要调用ClassTest的构造函数1次，赋值操作函数（operator=）100次；对于代码2：需要调用（复制）构造函数100次，析构函数100次。

如果调用赋值操作函数的开销比调用构造函数和析构函数的总开销小，则第一种效率高，否则第二种的效率高。

大部分情况下我们建议循环外定义，也就是方法一

7. 循环引发的讨论2（避免过大的循环）

现在请看下面的两段代码，
代码1：

for(inti = 0; i < n; ++i)
{
  fun1();
  fun2();
}

代码2：

for(inti = 0; i < n; ++i)
{
  fun1();
}
for(inti = 0; i < n; ++i)
{
  fun2();
}

注：这里的fun1()和fun2()是没有关联的，即两段代码所产生的结果是一样的。

以代码的层面上来看，似乎是代码1的效率更高，因为毕竟代码1少了n次的自加运算和判断，毕竟自加运算和判断也是需要时间的。但是现实真的是这样吗？

这就要看fun1和fun2这两个函数的规模（或复杂性）了，如果这多个函数的代码语句很少，则代码1的运行效率高一些，但是若fun1和fun2的语句有很多，规模较大，则代码2的运行效率会比代码1显著高得多。可能你不明白这是为什么，要说是为什么这要由计算机的硬件说起。

由于CPU只能从内存在读取数据，而CPU的运算速度远远大于内存，所以为了提高程序的运行速度有效地利用CPU的能力，在内存与CPU之间有一个叫Cache的存储器，它的速度接近CPU。而Cache中的数据是从内存中加载而来的，这个过程需要访问内存，速度较慢。

这里先说说Cache的设计原理，就是时间局部性和空间局部性。时间局部性是指如果一个存储单元被访问，则可能该单元会很快被再次访问，这是因为程序存在着循环。空间局部性是指如果一个储存单元被访问，则该单元邻近的单元也可能很快被访问，这是因为程序中大部分指令是顺序存储、顺序执行的，数据也一般也是以向量、数组、树、表等形式簇聚在一起的。

看到这里你可能已经明白其中的原因了。没错，就是这样！如果fun1和fun2的代码量很大，例如都大于Cache的容量，则在代码1中，就不能充分利用Cache了（由时间局部性和空间局部性可知），因为每循环一次，都要把Cache中的内容踢出，重新从内存中加载另一个函数的代码指令和数据，而代码2则更很好地利用了Cache，利用两个循环语句，每个循环所用到的数据几乎都已加载到Cache中，每次循环都可从Cache中读写数据，访问内存较少，速度较快，理论上来说只需要完全踢出fun1的数据1次即可。

8. 局部变量VS静态变量

很多人认为局部变量在使用到时才会在内存中分配，也就是储存单元，而静态变量在程序的一开始便存在于内存中，所以使用静态变量的效率应该比局部变量高，其实这是一个误区，使用局部变量的效率比使用静态变量要高。

这是因为局部变量是存在于堆栈中的，对其空间的分配仅仅是修改一次esp寄存器的内容即可（即使定义一组局部变量也是修改一次）。而局部变量存在于堆栈中最大的好处是，函数能重复使用内存，当一个函数调用完毕时，退出程序堆栈，内存空间被回收，当新的函数被调用时，局部变量又可以重新使用相同的地址。当一块数据被反复读写，其数据会留在CPU的一级缓存（Cache）中，访问速度非常快。而静态变量却不存在于堆栈中。

可以说静态变量是低效的

9. 避免使用多重继承

在C++中，支持多继承，即一个子类可以有多个父类。书上都会跟我们说，多重继承的复杂性和使用的困难，并告诫我们不要轻易使用多重继承。其实多重继承并不仅仅使程序和代码变得更加复杂，还会影响程序的运行效率。

这是因为在C++中每个对象都有一个this指针指向对象本身，而C++中类对成员变量的使用是通过this的地址加偏移量来计算的，而在多重继承的情况下，这个计算会变量更加复杂，从而降低程序的运行效率。而为了解决二义性，而使用虚基类的多重继承对效率的影响更为严重，因为其继承关系更加复杂和成员变量所属的父类关系更加复杂。

10. 将小粒度函数声明为内联函数（inline）

正如我们所知，调用函数是需要保护现场，为局部变量分配内存，函数结束后还要恢复现场等开销，而内联函数则是把它的代码直接写到调用函数处，所以不需要这些开销，但会使程序的源代码长度变大。
所以若是小粒度的函数，如下面的Max函数，由于不需要调用普通函数的开销，所以可以提高程序的效率。

inline Max(inta, intb)
{
  returna>b?a:b;
}

什么是内联函数
https://blog.csdn.net/zengxiaosen/article/details/73784922

11. 多用直接初始化

与直接初始化对应的是复制初始化，什么是直接初始化？什么又是复制初始化？举个简单的例子，

ClassTest ct1;
ClassTest ct2(ct1);  //直接初始化
ClassTest ct3 = ct1;  //复制初始化

那么直接初始化与复制初始化又有什么不同呢？直接初始化是直接以一个对象来构造另一个对象，如用ct1来构造ct2，复制初始化是先构造一个对象，再把另一个对象值复制给这个对象，如先构造一个对象ct3，再把ct1中的成员变量的值复制给ct3，从这里，可以看出直接初始化的效率更高一点，而且使用直接初始化还是一个好处，就是对于不能进行复制操作的对象，如流对象，是不能使用赋值初始化的，只能进行直接初始化。可能我说得不太清楚，那么下面就引用一下经典吧！
以下是Primer是的原话：

“当用于类类型对象时，初始化的复制形式和直接形式有所不同：直接初始化直接调用与实参匹配的构造函数，复制初始化总是调用复制构造函数。复制初始化首先使用指定构造函数创建一个临时对象，然后用复制构造函数将那个临时对象复制到正在创建的对象”，还有一段这样说，“通常直接初始化和复制初始化仅在低级别优化上存在差异，然而，对于不支持复制的类型，或者使用非explicit构造函数的时候，它们有本质区别：

ifstream file1("filename")://ok:direct initialization
ifstream file2 = "filename";//error:copy constructor is private

注：如还对直接初始化和复制初始化有疑问，可以参考一下前面的一篇文章：
C++直接初始化与复制初始化的区别深入解析，里面有有关直接初始化和复制初始化的详细解释。

12. 尽量少使用dynamic_cast

dynamic_cast的作用是进行指针或引用的类型转换，dynamic_cast的转换需要目标类型和源对象有一定的关系：继承关系。 实现从子类到基类的指针转换，实际上这种转换是非常低效的，对程序的性能影响也比较大，不可大量使用，而且继承关系越复杂，层次越深，其转换时间开销越大。在程序中应该尽量减少使用。

参考：C++程序加速的12个方法

13. TBB或 OpenMP的使用

13.1. TBB、OpenMP对比

1、TBB需要相当可观的重新设计程序，而OpenMP足够简单；

2、TBB不太适合并行化已有的实现（软件），它为新设计的并行程序培养一种好的编程风格和更高的抽象层；

3、在论文的实验中，OpenMP稍稍超过TBB；

4、TBB只能针对C++, 如果程序基于C或者Fortran就用不上了；

5、TBB提供了并行容器，使得结构上的并行更加简单方便；

6、如果您的并行模式主要用于内建类型的有界循环（bounded loop），最好采用 OpenMP；

7、OpenMP需要编译器支持，TBB需要下载运行库；

参考：TBB、OpenMP对比

13.2. C++并行编程探讨分析（OpenMP & TBB & Thread Pool）

一、前言

在日常并行编程开发时，我们通常想到的方式有OpenMP，TBB和原生的多线程等。这里先简要各种比较结论如下，然后会在各部分详细论述：

  1. TBB需要相当可观的重新设计程序，而OpenMP足够简单；
  2. TBB不太适合并行化已有的实现，它为新设计的并行程序培养一种好的编程风格和更高的抽象层；
  3. 在论文的实验中，OpenMP稍稍超过TBB；
  4. TBB只能针对C++, 如果程序基于C或者Fortran就用不上了；
  5. TBB提供了并行容器，使得结构上的并行更加简单方便；
  6. 如果您的并行模式主要用于内建类型的有界循环（bounded loop），最好采用 OpenMP；
  7. OpenMP需要编译器支持，TBB需要下载运行库；

PS：以下多线程库比较图示仅供参考（From https://www.xcelerit.com/computing-benchmarks/software/multi-threading/）：
C++程序加速方法-LMLPHP

C++程序加速方法-LMLPHP

二、OpenMP

2.1 OpenMP简介

OpenMP是一种用于共享内存并行系统的多线程程序设计方案，支持的编程语言包括C、C++和Fortran。OpenMP提供了对并行算法的高层抽象描述，特别适合在多核CPU机器上的并行程序设计。编译器根据程序中添加的pragma指令，自动将程序并行处理，使用OpenMP降低了并行编程的难度和复杂度。当编译器不支持OpenMP时，程序会退化成普通（串行）程序。程序中已有的OpenMP指令不会影响程序的正常编译运行。

2.2 OpenMP执行模式

OpenMP采用fork-join的执行模式。开始的时候只存在一个主线程，当需要进行并行计算的时候，派生出若干个分支线程来执行并行任务。当并行代码执行完成之后，分支线程会合，并把控制流程交给单独的主线程。

一个典型的fork-join执行模型的示意图如下：
C++程序加速方法-LMLPHP

2.3 OpenMP编程模型
2.3.1 共享内存模型

OpenMP是为多处理器或多核共享内存机器设计的。底层架构可以是共享内存UMA或NUMA。
C++程序加速方法-LMLPHP

2.4 OpenMP API概述

OpenMP编程模型以线程为基础，通过编译制导指令制导并行化，有三种编程要素可以实现并行化控制，他们分别是编译器指令、API函数集和环境变量。

2.4.1 编译器指令

OpenMP的编译器指令的目标主要有：1）产生一个并行区域；2）划分线程中的代码块；3）在线程之间分配循环迭代；4）序列化代码段；5）同步线程间的工作。编译制导指令以#pragma omp 开始，后边跟具体的功能指令，格式如：

#pragma omp 指令[子句],[子句] …]　　

常用的功能指令如下：

  • parallel ：用在一个结构块之前，表示这段代码将被多个线程并行执行；
  • for：用于for循环语句之前，表示将循环计算任务分配到多个线程中并行执行，以实现任务分担，必须由编程人员自己保证每次循环之间无数据相关性；
  • parallel for ：parallel和for指令的结合，也是用在for循环语句之前，表示for循环体的代码将被多个线程并行执行，它同时具有并行域的产生和任务分担两个功能；
  • sections ：用在可被并行执行的代码段之前，用于实现多个结构块语句的任务分担，可并行执行的代码段各自用section指令标出（注意区分sections和section）；
  • parallel sections：parallel和sections两个语句的结合，类似于parallel for；
  • single：用在并行域内，表示一段只被单个线程执行的代码；
  • critical：用在一段代码临界区之前，保证每次只有一个OpenMP线程进入；
  • flush：保证各个OpenMP线程的数据影像的一致性；
  • barrier：用于并行域内代码的线程同步，线程执行到barrier时要停下等待，直到所有线程都执行到barrier时才继续往下执行；
  • atomic：用于指定一个数据操作需要原子性地完成；
  • master：用于指定一段代码由主线程执行；
  • threadprivate：用于指定一个或多个变量是线程专用，后面会解释线程专有和私有的区别。

相应的OpenMP子句为：

  • private：指定一个或多个变量在每个线程中都有它自己的私有副本；
  • firstprivate：指定一个或多个变量在每个线程都有它自己的私有副本，并且私有变量要在进入并行域或任务分担域时，继承主线程中的同名变量的值作为初值；
  • lastprivate：是用来指定将线程中的一个或多个私有变量的值在并行处理结束后复制到主线程中的同名变量中，负责拷贝的线程是for或sections任务分担中的最后一个线程；
  • reduction：用来指定一个或多个变量是私有的，并且在并行处理结束后这些变量要执行指定的归约运算，并将结果返回给主线程同名变量；
  • nowait：指出并发线程可以忽略其他制导指令暗含的路障同步；
  • num_threads：指定并行域内的线程的数目；
  • schedule：指定for任务分担中的任务分配调度类型；
  • shared：指定一个或多个变量为多个线程间的共享变量；
  • ordered：用来指定for任务分担域内指定代码段需要按照串行循环次序执行；
  • copyprivate：配合single指令，将指定线程的专有变量广播到并行域内其他线程的同名变量中；
  • copyin n：用来指定一个threadprivate类型的变量需要用主线程同名变量进行初始化；
  • default：用来指定并行域内的变量的使用方式，缺省是shared。
2.4.2 API函数集

OpenMP API 包括越来越多的运行时库函数。

2.4.3 环境变量

OpenMP提供了一些环境变量，用来在运行时对并行代码的执行进行控制。这些环境变量可以控制：1）设置线程数；2）指定循环如何划分；3）将线程绑定到处理器；4）启用/禁用嵌套并行，设置最大的嵌套并行级别；5）启用/禁用动态线程；6）设置线程堆栈大小；7）设置线程等待策略。

常用的环境变量：

  • OMP_SCHEDULE：用于for循环并行化后的调度，它的值就是循环调度的类型；
  • OMP_NUM_THREADS：用于设置并行域中的线程数；
  • OMP_DYNAMIC：通过设定变量值，来确定是否允许动态设定并行域内的线程数；
  • OMP_NESTED：指出是否可以并行嵌套。

三、TBB

3.1 TBB简介

TBB(Thread Building Blocks)是英特尔发布的一个库，全称为 Threading Building Blocks。TBB 获得过 17 届 Jolt Productivity Awards，是一套 C++ 模板库，和直接利用 OS API 写程序的 raw thread 比，在并行编程方面提供了适当的抽象，当然还包括更多其他内容，比如 task 概念，常用算法的成熟实现，自动负载均衡特 性还有不绑定 CPU 数量的灵活的可扩展性等等。在多核的平台上开发并行化的程序，必须合理地利用系统的资源 - 如与内核数目相匹配的线程，内存的合理访问次序，最大化重用缓存。有时候用户使用(系统)低级的应用接口创建、管理线程，很难保证是否程序处于最佳状态。 而 TBB 很好地解决了上述问题：

1）TBB提供C++模版库，用户不必关注线程，而专注任务本身。
2）抽象层仅需很少的接口代码，性能上毫不逊色。
3）灵活地适合不同的多核平台。
4）线程库的接口适合于跨平台的移植(Linux, Windows, Mac)

OneTBB源码： https://github.com/oneapi-src/oneTBB

OneTBB开发手册： https://oneapi-src.github.io/oneTBB/

3.2 TBB主要模块介绍

TBB包含了 Algorithms、Containers、Memory Allocation、Synchronization、Timing、Task Scheduling这六个模块。TBB的结构：

C++程序加速方法-LMLPHP

参考：C++并行编程探讨分析（OpenMP & TBB & Thread Pool）

10-14 20:27
Powered by LMLPHP ©2024 落花逐流水 0.002826