Optimized C++:Proven Techniques for Heightened Performance

C++性能优化指南

这是一篇关于C++性能优化指南的学习笔记,主要是通过阅读学习Kurt Guntheroth著的Optimized C++:Proven Techniques for Heightened Performance。 这是一本知识量和信息量很大的一本书书,书里详细介绍了影响C++程序性能的原因,也给出了很多提高性能的优化策略。
书中不仅讲解了软件和系统方面的相关内容,还涉及了计算机的硬件组成的基础知识,使读者可以全面的了解计算机和程序设计。书中介绍的方法是具有通用性的,可以延伸至其他的编程语言,个人认为这是一本可以提升程序设计能力、感受到优化之美的一本值得一读的好书。

book

以下是我关于本书的学习笔记

Catagory

  1. C++代码优化策略总结
  2. 影响优化的计算机行为
  3. 性能测量
  4. 优化字符串的使用
  5. 优化动态分配内存的变量
  6. 优化热点语句
  7. 使用更好的库
  8. 优化算法
  9. 优化查找和排序
  10. 优化并发

C++代码优化策略总结

1、用好的编译器并用好编译器(支持C++11的编译器,IntelC++(速度最快)、GNU的C++编译器GCC/G++(非常符合标准),Visual C++(性能折中),clang(最年轻Mac OS x))。

2、使用更好的算法。(绝大多数高效的程序都有高效的算法)。

3、使用更好的数据结构(不同的数据结构在使用内存管理器的方式也有所不同)。

4、使用更好的库(熟悉和掌握标准C++模板库对于进行性能优化的开发员是必须的技能,Boost Project 和 Google Code 公开了很多有用的库)。

5、减少内存分配和复制(减少对内存管理器的调用是一种非常有效的优化手段)。

6、优化内存管理(内存管理器的调度,丰富的API)。

7、提高并发性(多个处理核心执行指令)。

影响优化的计算机行为

1、计算机的主内存是比较慢的(通往主内存的接口是限制执行速度的瓶颈(冯*诺伊曼瓶颈),(摩尔定理)每年处理器的核心的数量都会增加,但是计算机的性能未必会提高,因为这些核心只是等待访问内存的机会(内存墙memory wall))。

2、计算机内存的访问方式(并非以字节为单位),某些内存访问会比其他的更慢(分为一级高速缓存(cache memory)、二级高速缓存、三级高速缓存、主内存、磁盘上的虚拟内存页)。

3、内存的容量是有限的,每个程序都会与其他程序竞争计算机资源,计算比做决定快。

4、在处理器中,访问内存的性能开销远比其他操作的性能开销大,非对齐访问所需要的时间是所有字节都在同一字节中的两倍。

5、访问频繁使用的内存地址的速度比访问非频繁使用的地址快,访问相邻地址的内存的速度比访问相互远隔的地址的内存快。

6、访问线程间共享的数据比访问非共享的数据资源慢很多。当并发线程共享数据时,同步代码降低了并发量。

7、有些语句隐藏了大量的计算,从语句的外表上看不出语句的性能开销会有多大。

性能测量

1、90/10规则:一个程序会花费90%的运行时去执行10%的代码。
2、只有正确且精确的测量才是准确的测量。
3、分辨率不是准确性
4、在Windows上,clock()函数提供了可靠的毫秒级的时钟计时功能。在Windows8和之后的版本中,GetSystemTimePreciseAsfileTime()提供了亚微秒的计时功能。
5、计算一条C++语句对内存的读写次数,可以估算出一句C++ 语句的性能开销。

优化字符串的使用

1、由于字符串是动态分配内存的,因此他们的性能开销非常大。它们在表达式中的行为与值类似,它们的实现方式中需要大量的复制。

2、将字符串作为对象而非值可以降低内存分配和复制的频率。

3、为字符串预留内存空间可以减少内存分配的开销。

4、将指向字符串的常量引用传递给函数与传递值的结果几乎一样,但是更加高效。

5、将函数的结果通过输出参数作为引用返回给调用方会复用实参的存储空间,这可能比分配新的存储空间更加高效。

6、即使只是有时候会减少内存分配的开销,仍然是一种优化。

优化动态分配内存的变量

1、在C++程序中,乱用动态分配内存的变量是最大的“性能杀手”。

2、C++变量(每个普通数据类型的变量;每个数组,结构体或类实例)在内存中的布局都是固定的,它们的大小在编译时就已经确定了。

3、每个变量都有它的存储期(生命周期),只有在这段时间内变量所占用的存储空间或者内存字节中的值才是有意义的。为变量分配内存的开销取决于存储期(静态存储期、线性局部存储期、自动存储期、动态存储期)。

4、C++变量的所有者决定了变量什么时候会被创建,什么时候会被析构(变量所有权是一个单独的概念,与存储期不同)。动态变量的所有权必须有程序员执行并编写在程序逻辑中,它不受编译器控制,也不由C++定义。具有强定义所有权的程序会比所有权分散的程序更高效。

5、在C++中,动态变量是由 new 表达式创建,由 delete 表达式释放的。它们会调用C++标准库的内存管理函数。

6、智能指针会通过耦合动态变量的生命周期与拥有该变量的智能指针的生命周期,来实现动态变量所有权的自动化。C++允许多个指针和引用指向同一个动态变量,共享了所有权的动态变量开销更大。

7、静态的创建类成员并且在有必要时采用“两段初始化”,这样可以节省为这些成员变量分配内存的开销。

8、让主指针来拥有动态变量,使用无主指针替代共享所有权。

9、从性能优化的角度上看,使用指针或是引用进行赋值和参数传递,或是返回指针或引用更加高效,因为指针和引用时存储在寄存器中的。

10、当一个数据结构中的元素被存储在连续的存储空间中时,我们称这个数据结构为扁平的,相比于通用指针链接在一起的数据结构,扁平数据结构具有显著的性能优势。

优化热点语句

1、除非有一些因素放大了语句的性能开销,否则不值得进行语句级别的性能优化,因为所能带来的性能提升不大。

2、循环中的语句的性能开销被放大的倍数是循环的次数。函数中的语句的性能开销被放大的倍数是函数被调用的次数。被频繁地调用的编程惯用法的性能开销被放大的倍数是其被调用的次数。

3、从循环中移除不变性代码(当代码不依赖于循环的归纳变量时,它就具有循环不变性),不过现代编译器非常善于找出循环中被重复计算的具有循环不变性的代码。

4、从循环中移除无谓的函数调用,一次函数调用可能会执行大量指令,这是影响程序性能的一个重要因素,如果一个函数具有循环不变性,那么将它移除到循环外有助于改善性能。有一种函数永远都可以被移动到循环外部,那就是返回值只依赖于函数参数而且没有副作用的纯函数。

5、从循环中移除隐含的函数调用;如果将函数签名从通过值传递实参修改为传递指向类的引用和指针,有时候可以在进行隐式函数调用时移除形参构建。

6、调用函数的开销是非常小的,只是执行函数体的开销可能非常大,如果一个函数被重复调用多次则累积的开销会变得很大。函数调用的开销主要包括函数调用的基本开销、虚函数的开销、继承中的成员函数调用、函数指针的开销等。函数的调用开销虽然很大,但正因为函数调用才实现了程序的一些复杂的功能。

6、调用操作系统的函数的开销是高成本的。

7、内联函数是一种有效的移除函数调用开销的方法。

使用更好的库

1、C++为常用功能提供了一个简洁的标准库。

  • 确定哪些依赖于实现的行为,如每种数据类型的最大值和最小值。
  • 易于使用但是编写和验证都很繁琐的可移植的超越函数(超越函数指的是变量之间的关系不能用有限次加、减、乘、除、乘方、开方运算表示的函数),如正弦函数和余弦函数、对数函数和幂函数、随机数函数等等。
  • 除了内存分配外,不依赖于操作系统的可移植的通用数据结构、如字符串、链表和表。
  • 可移植的通用数据查找算法、数据排序算法和数据转换算法。
  • 以一种独立于操作系统的方式与操作系统的基础服务相联系的执行内存分配、操作线程、管理和维护时间以及流I/O等任务的函数。

2、使用C++标准库的注意事项

  • 标准库的实现中有bug,(标准库和编译器是单独维护的,编译器中也可能存在bug,标准需求的改变、责任的分散、计划问题以及标准库的复杂度都会不可避免地影响它们的质量)。
  • 标准库的实现可能不符合C++标准,(库的发布计划和编译器是不同的,而编译器的发布计划与与C++标准不同,一个标准库的实现可能会领先或是落后于编译器)。
  • 对于标准库开发人员来说,性能并非是最终要的事情,(因为库会被长期使用,所以库的简单性和可维护性更加重要)。
  • 库的实现可能会让一些优化手段失效,C++标准库中的有些部分并非是有用的。
  • 标准库不如最好的原生函数,(标准库没有为某些操作系统提供异步文件I/O等特性,性能优化人员只能通过调用原生函数,牺牲可移植性来换取运行速度)。

3、C++标准库之所以提供这些函数和类,是因为要么无法以其他方式提供这些函数和类,要么这些函数和类被广泛地用于多种操作系统上。在对库进行性能优化时,测试用例非常关键;接口的稳定性是可交付的库的核心。

4、扁平继承层次关系(多数抽象都不会有超高三层类继承层次,一旦超高三次可能表明类的层次结构不够清晰,其引入的复杂性会导致性能的下降)。
扁平调用链(绝大多数抽象的实现都不会超高三层嵌套函数的调用,在已经充分解耦的库中是不会包含冗长的嵌套抽象调用链的)。

优化算法

1、高效的算法是计算机科学一直研究的主题,计算机科学家十分重视算法和数据结构的研究,因为它是展示优化代码的典型事例。当一个程序需要数秒内执行完毕,实际上却要花费数小时时,唯一可以用成功的优化方法可能就是选择一种高效的算法了。算法是一个非常重要且不能简而概之的主题,可以参考《算法导论》,进行更深入的学习。
book

2、优化模式
开发人员研究算法和数据结构的原因之一是其中蕴含着用于改善性能的“思维库”,这些改善性能的通用技巧是非常的使用的,其中的一些模式也是数据结构、C++语言特性和硬件创新的核心。

  • 预计算;可以在程序早期,通过在热点代码前执行执行计算来将计算从热点部分中移除。
  • 延迟计算;通过在正真需要执行计算时才执行计算,可将计算从某些代码路径上移除。
  • 批量处理;每次对多个元素一起进行计算,而不是一次只对一个元素进行计算。
  • 缓存;通过保存和复用高代价计算的结果来减少计算量,而不是重复进行计算。
  • 特化;通过移除未使用的共性来减少计算量。
  • 提高处理量;通过一次处理一大组数据来减少循环处理的开销。
  • 提示;通过在代码中加入可能会改善性能的提示来减少计算量。
  • 优化期待路径;以期待频率从高到低的顺序对输入数据或是运行时发生的事件进行测试。
  • 散列法;计算可变成字符串等大型数据结构的压缩数值映射(散列值)。在进行比较时,用散列代替数据结构可以提高性能。
  • 双重检查;通过先进行一项开销不大的检查,然后只在必要时才进行另外一项开销昂贵的检查来减少计算量。

优化查找和排序

1、改善查找性能的工具箱,测量当前的实现方式的性能来得到比较基准,识别出待优化的抽象活动,将待优化的活动分解为组件算法和数据结构,修改或是替换那些可能并非最优的算法和数据结构,然后进行性能测试以确定修改是否有效果。

2、标准库查找算法接受两个迭代器参数:一个指向待查找序列的开始位置,另一个则指向待查找序列的末尾位置(最后一个元素的下一个位置)。所有的算法还都接受一个要查找的键作为参数以及一个可选的比较函数参数。

3、使用C++标准库优化排序,在能够使用分而治之算法高效地进行查找之前,我们必须先对序列容器排序,C++标准库提供了两种能够高效地对序列容器进行排序的标准算法——std::sort()std::stable_sort()

优化并发

1、并发是多线程控制的同步执行,并发的目标不是减少指令执行的次数或是每秒访问数据的次数,而是通过提高计算资源的使用率来减少程序运行的时间的。

2、有很多机制能够为程序提供并发,其中有些基于操作系统或是硬件。C++标准库直接支持线程共享内存的并发模型。

3、计算机硬件、操作系统、函数库以及C++自身的特性都能够为程序提供并发支持。

  • 时间分隔;这是操作系统的一个调度函数,为每个程序都分配时间块。操作系统是依赖于处理器和硬件的。它会使用计时器和周期性的中断来调整处理器的调度。
  • 虚拟化;虚拟化技术是让操作系统将处理器的时间块分配给客户虚拟机,计算资源能够根据每台客户虚拟机上正在运行的程序的需求进行分配。
  • 容器化;容器中包含了程序在检查点的文件系统镜像和内存镜像,其主机是一个操作系统,能够直接提供I/O和系统资源。
  • 对称式多处理;是一种包含若干执行相同机器代码并访问相同物理内存的执行单元的计算机,现代多核处理器都是对称式多处理器。使用正真的硬件并发执行多线程控制。
  • 同步多线程;有些处理器的硬件核心有两个或多个寄存器集,可以相应地执行两条或多条指令流。最高效第使用软件线程的方法是让软件线程数量与硬件线程数量匹配。
  • 多进程;进程是并发的执行流,这些执行流有它们自己的受保护的虚拟内存空间,进程之间通过管道、队列、网路I/O或是其他不共享的机制进行通信,进程的主要优点是操作系统会隔离各个进程,使其不会互相干扰影响。
  • 分布式处理;是指程序活动分布在一组处理器上,这些处理器可以不同。分布式处理系统通常会被分解为子系统,形成模块化的,易于理解的和能够重新配置的体系结构。
  • 线程;线程是进程中的并发执行流,它们之间共享内存;与进程相比,线程的优点在于消耗的资源更少、创建和切换也更快。由于进程中的所有线程都共享相同的内存空间,所以一个线程写入无效的内存地址可能会覆盖掉其他线程的数据结构,导致线程奔溃或是出现不可预测的情况。
  • 任务;任务是一个独立线程的上下文中能够被异步调用的执行单元,任务运行的基础是线性池。基于任务的并发构建于线程之上,因此任务也具有线程的优点和缺点。

4、如果没有竞争,那么一个多线程C++程序具有顺序一致性,理想的竞争一块短临界区的核心数量是两个。在临界区中执行I/O操作无法优化性能,可运行线程的数量应当少于或等于处理器核心数量。