读书笔记(十七) 《C++性能优化指南》二

读书笔记(十七) 《C++性能优化指南》二

字符串问题

这里作者讲的有点啰嗦，没有围绕着重点去讲，所以这里我吸收下他的知识点并总结下自己的知识点和经验。

把字符串问题单独拎出来说是因为字符串问题比较大，也比较隐性，常常容易引起性能问题。字符串在概念上很简单，它就是一个字符数组，但是想要实现高效的字符串却非常不容易。

首先字符串内存是动态分配的，其次是字符串常常被用来当成一个值来使用，这导致字符串操作常常带来大量不必要的内存分配和内存复制。

字符串问题的重点在内存分配问题和字符串查找。字符串操作带来的内存频繁的分配和浪费导致程序性能效率大大降低，操作包括，字符串拼接、字符串拆分、字符串大小写切换等，每次操作字符串都会新分配一个字符串内存或者字符串内存集，而查找字符串，即使使用算法通常也会逐字比较，效率比价差，特别是在一个集合中查找某个字符串对应的值时，需要完整的比较两者字符串是否完全一致。

改善内存分配效率，我们可以使用预分配和内存池机制。字符串内存预分配可以有2种，一种预先分配很多个长度不同的字符串缓存起来，使用时给出去，例如分别预分配1-50长度的字符串各100个，当逻辑需要时再给出去，用完了再收回来。另一种是先分配多个长一点的字符串，例如分配100个100长度的字符串，让字符串能够在拼接时不用再分配内存，由于本身字符串长度足够长，所以可以直接在当前字符数组中改写内容。

除了预分配，我们也可以将已经分配的字符串加入到字符串缓冲池中去，来管理这些预先分配好的字符串，需要时给予，不用时回收，不够时再分配一批，这样就能重复利用已经分配的字符串内存，将分配内存的工作集中起来消耗在某个点上。

我们常会去比较和查找字符串，查找字符串中的字符串有很多算法，但比较两个字符串是否相同如果仍然使用查找算法去做就是一种浪费，那么我们应该怎样去做两个字符串的比较呢，最好用哈希的方式，把字符串计算出一个哈希值，用这个哈希值来比较是否相等就快很多了。例如我们常常在业务逻辑中判断两个字符串是否相等，每次比较都会浪费掉很多计算量，用哈希的方式就会快很多，因为比较的是两个整数，在每次更新字符串时只需要重新计算一次哈希值就可以，由于通常字符串更新的并不频繁，所以计算哈希的消耗远比每次遍历两个字符串所带来的消耗要小的多。但哈希计算不一定能够获得一个唯一值，所以它只能被用来判断是否不同，即当哈希值不同时，两个字符串一定不同，而两个哈希值相同时有可能不同，此时再比较两者是否真的相同。虽然无法直接比较相同的字符串，但仍然大大减少了不同的两个字符串的比较的计算。

算法是性能优化中的精髓，多数平庸的优化方法对性能改善都是线性的，但算法不同，如果说一个高效的算法替换了一个低效的算法性能可能呈现指数级的增长。

算法时间开销一般有O(1)，O(log2(N))，O(N)，O(Nlog2(N))，O(N^2)，O(N^3)，O(2^N)，从高效到低效的排列，大多数算法如果能到log2(N)已经是非常优秀了，再进一步到O(1)则通常要付出巨大的内存代价。

作者对二分查找、哈希、散列查找算法特别中意，于是讲了散列算法是怎样的和关键点是什么。我们在用在用查找算法时log2(N)的算法已经是非常不错的查找效率了，所以二分查找是效率比较高的，但它仍然是建立在有序队列的基础上，需要先排序再查找，排序比查找更能耗时，而且后续的元素加入需要插入到有序队列中。而散列算法则不同，排序和查找会更快，前提是数据特性能够散列，或者说散列的冲突不会那么高，于是他告诉我们哈希算法对于散列的重要性。

这里作者讲的查找和排序内容比较浅，我融入了一些自己的经验。

算法通常是根据数据特效来定制的，所以对数据独有的特性分析是重点。就我的理解，算法并一定要局限于当前的结构，可以重新创建一个全新的结构方式，这样在用算法去优化程序的时候思路会更开阔。例如我们在全地图寻找某个人的时候并不一定要在查找函数上优化算法，而可以重新制造一个方格结构体把世界分割成不同的方块，找人时只要收集四周方块内的人就可以更快的找到。

算法也可以是局部的，因为数据多少和数据的特性可以由不同算法处理，所以我们在处理一大堆数据时可以拆分成不同的数据集进行处理，这些数据集的大小和特性也有所不同，针对性的处理会得到更有效的算法效率，例如快速排序算法，可以由不同的算法组成，由于它的中间值决定了快排速度，所以中间值我们可以用三个值取中间数的算法来找到更加稳定的中间值，当数段被分割成多个区间并且单个区间小于等于8个数时，插入排序其实比快排会更加快一些，因此我们在快排中间当数据量小于8时选择用插入排序算法。

作者列举了一些常用的算法优化思路和套路。

套路有：预计算、延迟计算、批量处理、缓存、特化、提高处理量、提示、优化执行路径、散列法、双重检查。

提前计算好一些可以离线完成计算量存储在文件中，这样可以省去了实时计算的开销。

先让所有中间过程改变完成后再对最后的结果计算，这样就省去了每次都需要计算全路径的消耗，例如引擎中通常有节点相互的挂载，每次赋值节点position时都会去计算重新计算子节点的位置，这时就要思考如何让计算延后，每次子节点的真实位置只要在帧结束时计算一遍就可以了，不用每次改变position时都去全路径计算一遍所有子节点。

某些具有相同性质的数据不要一个个处理，因为一起同一类型的数据处理起来会有更优的方法，例如堆排序如果一个个插入的元素的话性能开销是O(Nlog2(N))，而一次性构建一个堆的话只需要O(N)。

不要每次都计算，然后拿着结果去比较，计算完后缓存起来，一直用缓存的值，直到需要更改时再计算一遍。

一堆数据处理时它们都会消耗一些计算量，如果某个数据是特别的，不需要计算或者计算量可以很小，则另外开辟一个通道给它，让它少消耗一些。

提高处理量

一次处理多个数据而不是一个个处理，例如写日志不要每次都写，每隔一段时间写一次，类似这样的操作，先把准备的数据集中起来，集中起来的数据可能会有更多相似的特性可以用来优化。

当处理数据的时候，给予一个提示，这样我们就能知道该如何更好更快的处理，例如在插入一个数据到队列里去时，告诉插入函数，这个数是个比较大的值或者是一个比较小的值，这样我们在做插入时就有了更多优化提示。

优化执行路径

程序语句里有很多个if…else，如果95%的语句都进某个if，那么最好把它提前到语句前，这样就不用执行其他的if里的计算了。

哈希值比较法，数据结构和字符串在比较时比较费时，用哈希值比较则比较方便，为它们计算一个哈希值，当两个哈希值不同时，它们一定不同，如果哈希值相同则再比较是否真的相同。

数据其实有很多个特征可供我们使用来优化我们的算法，比如长度，如果两个数组长度不一样，那么它们两个的内容肯定是不一样的。类似这样的特征还有数据结构的某个字段或者某几个字段可以决定算法的计算路径，我们只要判断这几个字段就能排除很多计算量。

套路只是方法论

很多时候技巧谁都知道，实际运用时却能难灵活自如，如果你不常用它们，它们就不回成为你思考的一部分。

作者对容器类数据结构性能做了一些介绍，从本质和测试标准两个方面做了讲解。

不管C++标准库和Boost中的容纳器，还是其他语言的标准容器，它们都是非常通用且性价比不错的容器。但是如果你想让容器的性能发挥到最佳状态，就得自己去改造它。为什么要改造呢？因为首先标准容器内存的分配方式对具体的业务逻辑并不友好，我们可以把跟业务强相关的内存分配方式和内存池的技巧用在容器上以提高内存分配效率，其次容器中数据结构的插入、删除、查找的算法跟业务匹配上并不是最佳的，所以我们要根据我们的实际情况来改造这些算法以提高性能效率。

容器包括，序列容器和关联容器，序列容器有string，vector，deque，list，forward_list，大都是以数组或链表形式存在的容器，而关联容器则以map和set为代表，用来建立key和value之间联系的容器，包括map、multimap、set、multiset等。

我们在构造完自己的容器后，需要跟标准容器进行比较，只有这样才能知道我们改造的与业务强相关的容器是否比标准容器更加高效。

容器性能测试标准就是为了判断容器的在各方面的性能是否更优秀，测试内容需要包含向一个没有内容的容器中以及向一个有数万条记录的容器中插入，删除，查找十万个不同的元素所需要消耗的纳秒数，比较拥有相同功能的容器在执行同一功能的操作时所消耗的时间。我们在测试时用到的数据也会遇到问题，十万个元素也并不能代表数据的典型性，所以很多时候我们需要离线Random随机1000组不同的数据以覆盖所有测试范围。

由于我们自己不可能对所有容器进行重构，所以第三方容器库也是我们需要关注的地方，包括Boost、EASTL等都是我们需要参考的对象。

提升内存分配效率是提升程序性能非常有效的手段，其实质就是减少内存分配次数，减少内存分配次数就意味着减少内存分配带来的消耗，因此关键的关键还是如何减少内存分配次数，注意，是次数，不是大小，也不是释放。

讲内存分配之前，我们先来了解下内存分配接口以及内存分配的底层原理。

C++中内存管理函数有new，delete，malloc，free，其中new，delete运算符可以被类重载为 new()，new，delete()，delete，他们与class强相关，而malloc()和free()则是经典的C函数库中的内存管理函数，它们分配和释放的是无类型内存块，当无类型内存块被创建出来后，可以被强制指定为是某个变量、数据结构或者类实例。

从概念上来说，分配内存的函数会从内存中寻找一块可以使用的内存来满足请求，但事实上并没有这么简单。作者没有详细介绍内存分配和释放的底层原理，但我觉得这部分的底层原理是值得挖掘和说明的，作为一个频繁与内存打交道的程序员来说，知道内存是如何分配和释放的是非常有必要的。

我们的程序被加载到内存后分为几个内存段，包括指令段，数据段，bss段，栈段，堆段，指令段放具体指令，数据段放常量数据，bss段放静态和全局变量，栈段放调用栈、临时寄存器和临时变量，以上几个段都是固定的，不会有扩容一说，只有堆段是可扩容的。new和malloc分配的内存就在这个堆段中。

堆段会事先分配一段内存，当malloc请求分配的内存时，如果剩余空的内存足够，则分配返回一段足够大小的内存，如果不足则再申请内存。

堆段在向系统申请内存时类似于提高内存块大小，分配新内存这个操作需要系统将用户态切换到内核态再切回来，因此性能损耗是比较大的。其实malloc分配了内存，也并不代表实际物理内存中申请了某块内存，因为进程所面对的虚拟内存地址空间，只有按页映射到物理内存地址，才能真正使用。而且分配了新的内存，物理内存上实际没有此内存空间，只有当我们memset实际使用它时系统发现了物理内存缺页情况时才真正分配实际物理内存空间。

从这个角度看，内存分配在操作系统底层上会稍显复杂。那么申请内存在系统底层到底是如何操作的呢？我们来深究一下。

在Linux中进程由进程控制块(PCB)描述，用一个task_struct 数据结构表示，这个数据结构记录了所有进程信息，包括进程状态、进程调度信息、标示符、进程通信相关信息、进程连接信息、时间和定时器、文件系统信息、虚拟内存信息等. 和malloc密切相关的就是虚拟内存信息，定义为struct mm_struct描述了进程的地址空间。

mm_struct结构对整个用户空间（进程空间）的描述如下:

///include/linux/sched.h 

struct mm_struct {
  struct vm_area_struct * mmap;  /* 指向虚拟区间（VMA）链表 */
  rb_root_t mm_rb;         /*指向red_black树*/
  struct vm_area_struct * mmap_cache;     /* 指向最近找到的虚拟区间*/
  pgd_t * pgd;             /*指向进程的页目录*/
  atomic_t mm_users;                   /* 用户空间中的有多少用户*/                                     
  atomic_t mm_count;               /* 对"struct mm_struct"有多少引用*/                                     
  int map_count;                        /* 虚拟区间的个数*/
  struct rw_semaphore mmap_sem;
  spinlock_t page_table_lock;        /* 保护任务页表和 mm->rss */       
  struct list_head mmlist;            /*所有活动（active）mm的链表 */
  unsigned long start_code, end_code, start_data, end_data; /* 代码段、数据段 起始地址和结束地址 */
  unsigned long start_brk, brk, start_stack; /* 栈区 的起始地址，堆区 起始地址和结束地址 */
  unsigned long arg_start, arg_end, env_start, env_end; /*命令行参数 和 环境变量的 起始地址和结束地址*/
  unsigned long rss, total_vm, locked_vm;
  unsigned long def_flags;
  unsigned long cpu_vm_mask;
  unsigned long swap_address;

  unsigned dumpable:1;
  /* Architecture-specific MM context */
  mm_context_t context;
};

其中start_brk和brk分别是堆的起始和终止地址，我们使用malloc动态分配的内存就在这之间。系统分配堆空间时，进程通过malloc()库函数在堆上进行空间动态分配，堆空间如果不够用，malloc就进行系统调用增大brk的值。malloc只知道start_brk 和brk之间连续可用的内存空间它可用任意分配，如果不够用了就向系统申请增大brk。

我们看到实际堆内存在虚拟空间中是可以不断向上扩张的，虽然实际物理内存中不是这样，但至少在虚拟空间中我们可以认为堆内存是一段连续的内存空间地址。

由于我们分配的内存空间都在虚拟空间当中，我们看到的都是虚拟的地址，实际物理内存分配并不是我们想象的那样连续，也有可能在分配时由于物理内存不足我们拿到的空间是从硬盘空间上的一段数据交换到内存上来的。所以很多时候即使我们分配了连续的空间，在物理内存上也并不是连续的，只能说连续的概率比较大而已。

其实还有很多分配内存在操作系统层面的原理，这里暂时不深究下去。

作者指出提高内存分配效率的方法有两种，一种是减少不必要的内存复制的情况，另一种是用固定大小内存分配器解决减少内存分配次数。

其中内存复制现象常会存在于对象初始化、赋值运算、函数参数、函数返回、插入一个元素到标准容器中，这几种情况是我们需要特别注意的，常常会由于失误编码而导致内存复制的情况，特别是针对一些常用的结构体和非指针类型的实例传递。

固定大小内存管理器，意思是分配的内存块大小是固定的，这块内存可以是某个类或数据结构相匹配的一个固定大小，也可以是按某固定大小的内存块，这块内存能容纳某个范围内的一个类或数据结构的实例，这个内存管理器专门管理这个类或数据结构的所有内存的，或者专门管理某个固定大小内存块的管理类，这样在分配某一类大小实例时可以专门使用这样的内存管理器(有冗余不可避免)。

在固定大小内存管理器中，会预加载一段内存以便给足够数量的类和数据结构使用，并且在回收时存储在管理器中以便重复利用，这样既减少了内存分配次数，也减少了内存碎片。

这样一来，内存块的管理，可以分为，专门为某个类设计的内存管理类，和专门为某个大小范围内设计的内存管理类，我们可以称它们为通用的内存块管理类。

在实际编程中，我们在写一个固定大小的内存分配管理器时，如果某个类使用数量比较固定和分配释放率比较频繁的话，可以专门为这个类做一个分配器是性价比比较高的。我们通常也会写一个比较通用的内存管理器，用大小不同的内存块来进行区分，例如我们可以为64byte，128byte，256byte，512byte，1k，2k，这几档大小分别预分配几十个内存块存储在通用内存分配管理器中，当程序请求内存时，将请求大小四舍五入后变为2的下一个幂，这样就能获得一个最快适配的内存管理器，当然在使用完毕释放时也同样只是回到这个内存管理器中存储起来以便重复利用，就像内存池和对象池那样。

这周依然没有写完，下周继续最后一部分的总结。

参考资料：

《malloc和free的实现原理解析》https://jacktang816.github.io/post/mallocandfree/