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

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

此篇主要介绍热点代码、I/O、以及并行部分的优化，我们会从原理出发来，再根据原理讲优化，这样即学习了原理，又知道了优化的来龙去脉。

这里作者带我们聊一聊关于代码细节的优化，虽然语句的细节优化并不能带来非常明显的提升，但是也是非常有必要的优化步骤，尤其在那些追求极致高性能或精小的组件中，代码细节的优化决定了组件与组件之间的差异。

语句细节的优化，其实质是对CPU指令的优化，可以认为是从执行指令流中移除指令的过程。下面先来阐述一下细节优化的原理。

语句的细节优化，其实质是执行指令数量的优化，指令跳转次数的优化，向栈中保存临时寄存器次数的优化，以及内存分配次数的优化。

执行指令数量减少了可以减少CPU在执行程序时的耗时我们很好理解，指令跳转则是因为指令也是被放在内存中的数据，因此它也会被高速缓存cache，长距离跳转会让高速缓存失效，静态函数调用和非成员函数调用通常都是长距离指令跳转的典型案例。

函数调用开销不可忽视，即使一个空函数，在调用时也会有性能开销（编译器可能会帮我们优化掉空函数），有时为了极致的优化，我们应该最大限度的减少调用函数的频率，特别是频率最高的top3。

因为在函数被调用时会保存当前函数的数据，包括参数、局部变量、当前指令地址、临时寄存器和标记寄存器等，每次调用一个函数会做如下处理：

	1.当调用函数时，先保存当前函数的临时变量、参数、临时寄存器、标记寄存器。
	
	2.将这些每个要保存的数据都复制到栈中。
	
	3.当前执行的地址复制到栈中。

	4.将指令指针寄存器IP指向要执行的函数体的第一句

	5.执行函数体中的指令

	6.将函数调用结果保存到寄存器

	7.从栈中推出要返回的地址，并复制给指令寄存器IP

	8.推出栈中的临时寄存器、参数、局部变量、标记寄存器都重新还原回去

	9.继续执行剩下的指令直到遇到下一个函数。

如果遇到成员函数是虚函数的，还得先从虚表中偏移并取出函数地址再调用，这里又多了2次计算，即先取出虚表地址、再根据虚表地址偏移获得真正的函数地址、最后再才能跳转过去。如果是多重继承、或者是多重继承的继承类中的虚函数成员，则需要再加一次地址偏移计算。

inline内联是减少函数调用的最佳方式，内联函数并不像一般函数那样会保存数据并且跳转指令，因为编译器会就地展开内联函数中的指令，因此没有推栈入栈保存数据到栈和跳转指令到函数再返回的步骤，取而代之的是就地直接执行指令。

这样看来减少函数调用(或让函数内联)的同时也减少了入栈、出栈、复制数据的指令数量，也减少了指令跳转的丢失高速缓存的概率。

不必要的内存分配也是在代码细节中常犯的错误，尤其指向堆内存分配，当函数中需要某个容器或者类实例时，常会临时向堆内存申请一次以用来计算。

我们来看看以上这说的7个细节的具体例子：

for(int i = 0 ; i<strlen(str) ; i++)
	...

//改为

for(int i = 0, n = strlen(str) ; i<n ; i++)
	...

1.将重复计算提到前面，但这里不一定有优化，因为编译器可能会识别这类循环并将实时计算移出去，不过不能保证编译器一定会这么干，所以我们最好做人为的优化，保证不重复计算。

void function()
{
	list = new list();
	for(int i = 0 ; i<n ; i++)
	{
		list.Add(xx);
	}

	return;
}

//改为

public static list = new list(); //改为全局变量

void function()
{
	list.Clear();
	for(int i = 0 ; i<n ; i++)
	{
		list.Add(xx);
	}

	return;
}

2.函数中临时的堆内存分配，改为全局的共用内存，只要分配一次，每次使用前先清理就能节省开销。

int k = 0;
for(int i = 0 ; i<100 ; i++)
{
	int j = sin(100) + cos(50);
	k = j*i;
}

//改为

int k = 0;
int j = sin(100) + cos(5);
for(int i = 0 ; i<100 ; i++)
{
	k = j*i;
}

3.移除循环中不变的计算，减少不必要的指令，可能会被编译器优化掉。

for(int i = 0 ; i<10 ; i++)
{
	int b = Add(3,5);
	...
}

//改为

int b = 0
for(int i = 0 ; i<10 ; i++)
{
	b = 3 + 5;
	...
}

//或者将Add函数内联

inline int Add(a,b)
{
	...
}

4.用内联或者手动内联的方式，减少循环中的函数调用开销。

string str = "a";

str = "<p>" + str + "</p>";

//改为

str = string.format("<p>{0}</p>",str);

//或者

str = StringCacheMgr.instance.Format("<p>{0}</p>",str);

5.减少字符串内存分配次数，将原来要分配两次的字符串，改为只要分配1次。或者使用自制的字符串内存管理方式管理分配和操作字符串(前面的内存优化那一节我们讲过这种方式)

for(int i = 0 ; i<1000 ; i++)
{
	test();
}

//改为

test();

void test()
{
	for(int i = 0 ; i<1000 ;i++)
	{
		...
	}
}

6.将1000次调用函数的开销改为1次，节省函数调用的开销。

if(x == a)
{
	...
}
else if(xx == a)
{
	...
}
else if(xxx == a)
{
	...
}
else ...

//改为

switch(a)
{
	case x:
		break;
	case xx:
		break;
	case xxx:
		break;
}

7.通常switch都会被编译器优化为索引的方式去跳转，因此用switch比if效率高的多，也不用我们自己对数据排序。

最后说下异常try catch的开销，在早期C++的try catch机制会在栈帧上包含一个异常上下文，这些上下文会随着异常抛出或者作用范围结束而销毁，增加性能开销。现在则不同了，上下文开销都没有了，只是会在开始try时多几个指令更改中断程序的指向，退出时再改回来，但是即使这样，我们也不能有太多try catch，因为try catch太多仍然会多出很多额外的指令消耗。

我们做个小结，我们说语句的细节优化，实质是减少执行指令数量，减少指令跳转次数，减少函数调用，以及减少内存分配次数。我们用代码细节来解释有哪些细节是可以遵从我们的原理来优化的，这些细节的优化，在性能要求比较高的组件上会比较有用，好的代码细节是业务逻辑优化的前提。业务逻辑上，当我们更多运用的是调整实现方式，调整数据结构的方式，调整业务逻辑策略的方式时，这些细节的优化则成了底层的支柱。

I/O 文件操作

I/O操作的优化空间相对比较小，是因为它主要的工作大部分由操作系统完成。因此我们先介绍下操作系统中I/O的读写原理，再从原理出发优化I/O操作效率，包括降低读写次数减少读取时间和优化体验俩个方面。

操作系统中为了分割操作内容让调用更安全，分为‘用户态’和‘内核态’，当用户态需要内核态工作时我们称为‘系统调用’，我们平常写的程序只要不涉及系统调用的都是用户态完成的，一旦涉及到需要操作系统工作的部分，就要先切到内核态完成工作，结束后再切回用户态继续执行后面的程序，这个切换的过程是比较费时费力的，I/O调用就是其中一种需要切换内核态的系统调用。

操作系统可以支持多种底层不同的文件系统（比如NTFS, FAT, ext3, ext4），为了给内核和用户进程提供统一的文件系统视图，Linux在用户进程和底层文件系统之间加入了一个抽象层，即虚拟文件系统(Virtual File System, VFS)，进程所有的文件操作都通过VFS，由VFS来适配各种底层不同的文件系统，完成实际的文件操作。

这里我们来了解下虚拟文件系统构成和主要模块：

超级块（super_block）

用于保存一个文件系统的所有元数据，相当于这个文件系统的信息库，为其他的模块提供信息。

因此一个超级块可代表一个文件系统，文件系统的任意元数据修改都要通过超级块修改，超级块对象是常驻内存并被缓存起来的。

目录项模块

是管理路径的目录项，比如一个路径 /home/foo/hello.txt，那么目录项有home, foo, hello.txt三个。

每个目录项的块，存储的是这个目录下的所有的文件的inode号和文件名等信息。其内部是树形结构，操作系统检索一个文件是从根目录开始，按层次解析路径中的所有目录，直到定位到具体文件。

inode模块

管理的是一个具体的文件，是文件的唯一标识，一个文件对应一个inode。

通过inode可以方便的找到文件在磁盘扇区的位置，同时inode模块可链接到address_space模块，方便查找自身文件数据是否已经被缓存在内存中。

打开文件列表模块

包含所有内核已经打开的文件，已经打开的文件对象由open系统调用在内核中创建，也叫文件句柄。

打开文件列表模块中包含一个列表，列表表项是一个结构体struct file，结构体中的信息存储了打开的一个文件的各种状态参数。

file_operations模块

模块中维护一个数据结构，是一系列函数指针的集合，其中包含所有可以使用的系统调用函数，例如open、read、write、mmap等。

每个打开文件（打开文件列表模块的一个表项）都可以连接到file_operations模块，从而对任何已打开的文件，通过系统调用函数，实现各种操作。

address_space模块

记录了文件在页缓存中已经缓存了的物理页信息，是页缓存和外部设备中文件系统的桥梁。如果将文件系统可以理解成数据源，内存中的页缓存是已经读取的内容，那么address_space可以说是内存系统和文件系统的中间层。

所有文件信息保存在超级块中，通过目录项模块找到文件所在位置，所有被打开的文件放在文件列表模块中，file_operations模块负责操作文件，每个文件都有唯一标识inode，磁盘数据与内存缓存通过address_space联接与映射。

下面我们来看看读写入文件时的基本流程：

1、进程调用库函数向内核发起读文件请求；

2、内核通过检查进程的文件描述符定位到虚拟文件系统的已打开文件列表表项；

3、调用该文件可用的系统调用函数read()

read()函数通过文件表项链接到目录项模块，根据传入的文件路径，在目录项模块中检索，找到该文件的inode；

4、在inode中，通过文件内容偏移量计算出要读取的页；

5、通过inode找到文件对应的address_space；

6、在address_space中访问该文件的页缓存树，查找对应的页缓存结点：

（1）如果页缓存命中，那么直接返回文件内容；

（2）如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode找到文件该页的磁盘地址，读取相应的页填充该缓存页；重新进行第6步查找页缓存；

7、文件内容读取成功。

前5步和读文件一致，在address_space中查询对应页的页缓存是否存在：

6、如果页缓存命中，直接把文件内容修改更新在页缓存的页中。写文件就结束了。这时候文件修改位于页缓存，并没有写回到磁盘文件中去。

7、如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode找到文件该页的磁盘地址，读取相应的页填充该缓存页。此时缓存页命中，进行第6步。

8、一个页缓存中的页如果被修改，那么会被标记成脏页。脏页需要写回到磁盘中的文件块。有两种方式可以把脏页写回磁盘：

（1）手动调用sync()或者fsync()系统调用把脏页写回

（2）pdflush进程会定时把脏页写回到磁盘

同时注意，脏页不能被置换出内存，如果脏页正在被写回，那么会被设置写回标记，这时候该页就被上锁，其他写请求被阻塞直到锁释放。

页缓存实际上就是一个基数树结构，它将一个文件的内容组织起来存放在struct page结构中，文件越大树形结构越庞大，每一页都记录着文件内容的页信息和缓存信息。

另外内核使用task_struct来表示单个进程的描述符，其中包含维护一个进程的所有信息。task_struct结构体中维护了一个 files的指针（和“已打开文件列表”上的表项是不同的指针）来指向结构体files_struct，files_struct中包含文件描述符表和打开的文件对象信息，这使得系统能够：

1、多个进程可以同时指向一个打开文件对象（文件列表表项）。

2、一个进程可以多次打开一个文件，生成不同的文件描述符，每个文件描述符指向不同的文件列表表项。但是由于是同一个文件，inode唯一，所以这些文件列表表项都指向同一个inode。

我们知道了文件的读写原理再来看看我们在平时编写文件操作时的优化思路。

1.减少读写次数，减少读写时间。

由于每次读取文件内容都会从用户态转到内核态，完成后再切回来，这种切换的消耗是比较重的，因此我们应该尽量减少读写次数。

在读取一个文件时，尽量将需要的内容一次性读取完毕，甚至可以预先读取未来的内容，以避免多次读取。在写文件时也是同样，尽量一次性写入硬盘，避免多次写入。例如下面代码：

while(getline(file,line))
{
	doSomeThing(line);
}

//改为

lines = getlines(file);

for(int i = 0 ,n = len(lines) ; i< n ; ++i)
{
	doSomeThing(lines[i]);
}

一次性读取所有行，再对每行做处理。

void write_lines(std::ostream& file std::string const& lines[])
{
	for(int i = 0,n = len(lines) ; i<n ; ++i)
	{
		file << lines[i]
		file->flush();
	}
}

//改为

void write_lines(std::ostream& file std::string const& lines[])
{
	for(int i = 0,n = len(lines) ; i<n ; ++i)
	{
		file << lines[i];
	}
	file->flush();
}

//或用内存池的方式改为

void write_lines(std::ostream& file std::string const& lines[])
{
	int str_size = 0;
	for(int i = 0,n = len(lines) ; i<n ; ++i)
	{
		str_size += len(lines[i] + 1)*sizeof(char);
	}
	
	byte[] data = MemoryPool.instance.AllocMemory(str_size);

	CombineStringData(lines, data); //将lines中的数据都拷贝到data中

	file->write(data);
	file->flush();

	MemoryPool.instance.Free(data);
}

每次写入文件时系统并不会立即写入文件，而是存放在页缓存，如果我们每次刷新，则会每次都同步到硬盘，写入硬盘速度比较内存慢很多，会消耗比较长时间，所以要减少刷新调用次数。

只是减少刷新次数，但依然减少不了内核态切换的次数。于是我们用内存池的方式减少内存分配的时间，将内存分配的耗时降低，将原本要调用很多次系统调用的次数降低为了一次，从而减少了内核态切换的次数。

2.优化体验

用阻塞读取的方式，由于线程要等待磁盘设备的工作，对于整个程序的效率来说是比较低的，因为硬盘设备读写的速度比较慢，主线程要等待硬盘设备工作完毕后才进行后面的工作。因此为了能让程序的整体效率提升，我们可以用异步读取的方式来优化整体的程序时间，即在读取或写入文件的同时，其他程序工作同步进行。

最常见的是游戏的开机画面，加载画面，切换场景画面，甚至有些游戏中边加载边进行的部分，都是可以通过并行来优化体验的。

文件读写并发通常都是开启线程后的读写操作，与阻塞内容一样，只是更多的利用可利用的CPU时间而不让线程空闲等待硬盘，原理是我们尽力能让计算机中的所有设备资源都满负荷运转并很好的协作，而不是相互牵制。

下面我们就来讲讲并发的优化内容。

并发的方案有很多特别是在业务层上有很多技巧，这里只是选取与语言相关部分。我们将从原理出发讲一讲，线程同步中的技巧、原子性、以及无锁容器的原理。

由于设备资源并不总是运行，因为我们的程序并没有使用到这些资源，或者说有时没有同一时间同时让它们一起运转，这使得资源的闲置造成了浪费，如果能在当某个程序在执行指令时，另一个设备在满负荷运作，这样就相当于提高了运行效率。

并发的挑战是找到足够多的独立任务来充分地使用所有可用的计算机资源，让资源都能满负荷的执行，提高整体运行效率。其中CPU资源是最稀缺，也是使用最频繁的资源，如果能让多核中所有CPU都满负荷工作(不考虑降频问题)程序的效率就能提高很多，即使不满负荷，也能提其他CPU分担不少工作，让降频的概率减少到最低。

首先我们来梳理下操作系统中的进程、线程、时间片的概念。

线程是实际工作的单元，进程只是一个容器用来管理线程。严格来说Linux内核其实不区分进程和线程，内核把执行单元叫做任务(Task)。操作系统实际上调度的是进程，进程通过fork()来创建同样的另一个进程。每个进程有一个PID，同一组进程中最先启动的那个还有一个TGID，严格来说前者应该叫线程ID，后者应该叫进程ID，其实它们都是Linux的Task。

多线程能同时做好几件事情以提高效率，但实际问题是，CPU的数量（核心数）是有限的，而且并不多。如果你的CPU有8个核，并且整个操作系统中有8个线程的话，不考虑中断等因素，每个线程理论上能一直执行下去。然而多于8个线程以后，操作系统就必须进行调度，也就是分配时间片。具体的分配方案，或者说调度算法有很多种。如果一个进程创建了很多线程的话，最多也只有8个能够处于执行的状态(这里说的是物理线程，有别于逻辑线程)，其余的线程必须等待调度。线程被调度的时候需要进行上下文切换，这个操作是一种额外的开销。当线程数量过多的时候，上下文切换产生的额外开销会对系统的效率造成负面影响。

线程的调度算法和进程一样通常有优先级之分，优先级高的线程可以比优先级低的线程多抢占些CPU时间片。甚至不同的线程可以通过系统调用将线程绑定在某个CPU核上。因此我们也可以通过将线程绑某个cpu核的方式来强制执行线程调度，从而优化并行开销。

通常我们在多个线程交叉执行时最关心的是同步问题。解决这个问题我们可以用，减少锁的占用时间、减少锁的颗粒度、无锁容器三个方式。前两者更好理解些，也用的比较多，最后一个需要阐明下原理。

通常我们使用锁和互斥量来解决线程间的同步问题，但这会带来潜在问题，就是由于锁的原因导致线程间的等待时间变长，实际执行的效率可能并没有因此而增加。

因此锁的范围必须被压缩到最小，例如：

void doFunction(item)
{
	lock(obj)
	{
		doSomeThing1();

		list.push(item); //must lock

		doSomeThing2();
	}
}

//改为

void doFunction(item)
{
	doSomeThing1();

	lock(obj)
	{
		list.push(item); //must lock
	}

	doSomeThing2();
}

尽可能的缩小锁的范围，减少锁等待时间。

void doFunction1()
{
	lock(obj)
	{
		...
	}
}

void doFunction2()
{
	lock(obj)
	{
		...
	}
}

//改为

void doFunction1()
{
	lock(obj1)
	{
		...
	}
}

void doFunction2()
{
	lock(obj2)
	{
		...
	}
}

减少锁的颗粒度，让各自的锁只负责自己一小部分的内容。这里也涉及到细粒度锁(算法)，它通常基于轻量级原子性原语，由于并不是基于系统提供的同步原语所以性能开销很小，但在高并发的情况下，细粒度锁(算法)就会成为程序的瓶颈。

由于指定锁某些局部的计算范围或者函数，锁的时间太长并不划算，所以我们通常在两个线程间的协作上使用消息队列(或者其他容器)让线程更大程度的并行，但这依然需要对容器加锁，以使得操作不冲突。

为了能让容器冲突时间更小，当只有两个线程操作容器时，我们通常会采用些技巧。

• 例如双队列，设置两个队列，其中一个用于处理消息，另一个用于接收消息，当处理消息时，两个队列的头指针交换一下再处理，这样就能让接收的队列继续接收，处理的队列独自处理，这种方式的缩短了锁的占用时间，锁的时间缩短到了变量交换时间。

• 以及循环队列的方式，用头尾循环的方式做队列，一个线程只对尾部操作，另一个线程只对头部操作，发送数据的线程向尾部推入数据，接收数据的线程从头部取出数据，循环操作队列，只有当队列满时才需要停一停等待数据 处理，其他时候，两者永远都不需要相互等待。

无锁容器的复杂度有点高，它适用于高并发场景，这里不便深入，其原理是原子操作。虽然我们不深入无锁容器的具体写法，但我们用问答的方式来解释下原子操作。

什么是原子性？

如果一个更新操作不会计算到一半的时候被另外一个线程看到，就叫原子性。

原子操作可认为是一个不可分的操作；要么发生，要么没发生，我们看不到任何执行的中间过程，不存在部分结果(partial effects)。可以想象的到，原子操作要保证要么全部发生，要么全部没发生，这样原子操作绝对不是一个廉价的消耗低的指令，相反，原子操作是一个较为昂贵的指令。

非原子操作，为什么会更新到一半被另一个线程看到？

即使一个简单的整型变量的赋值操作，也有可能更新到一半被另一个线程看到，这是为什么呢？原因就是高速缓存中的旧数据。

由于每个cpu除了共享一个内存设备外还有各自的高速缓存，一个cpu更新了内存中的内容后，其实并没有通知其他cpu中的缓存去掉该内容，这导致其他cpu中的高速缓存存储的仍然是旧的数据。当这些CPU读取这个变量时会从缓存中取得旧数据，直到缓存中的这个数据被丢弃或更新。

原子操作，做了什么使得更新不被其他线程看到？

CPU的高速缓存间有一个MESI协议(cache一致性协议，4个关键词 Modifed Exclusive Shared Invalid 拼凑起来的缩写)，通过这个消息协议，CPU可以查看其他CPU高速缓存中的数据状态，就像不同设备间通信那样。

当执行原子操作 store 即写入数据时，先查看当前cpu高速缓存中有没有数据，如果没有，则通知其他cpu中的高速缓存该数据切为无效状态，等待所有cpu都将该数据切为无效状态后，此cpu才开始发起写入内存和高速缓存的操作，并标记该值为修改状态。如果有，则更新高速缓存中的值，并通知其他cpu中的高速缓存该值已经不合法，最后此cpu并没有将该值写入内存，而是在高速缓存中标记该值被修改，以便下次再利用，或者等到丢弃时再写入内存。

当执行原子操作 load 即读取数据时，先查看当前cpu高速缓存中有没有该数据，如果没有(或者是无效的)，则从先从查看其他cpu中查看该数据，如果有则获取，没有则从内存中获取。如果当前cpu高速缓存中有该数据，则直接使用该数据(必须不是无效的)。

其他并行优化

1.分割资源，减少线程间的争夺。

分割或者复制一块内存出来，让某个线程专门使用，这样就不会与其他线程冲突，计算结束时再考虑合并的事。

此方法在Unity引擎的 Job System中有使用到，即给Job System一块独立的内存来处理自己的事物，与其他线程不冲突。

2.散列容器，减少锁的范围，和前面介绍的细粒度锁(算法）稍微有点不一样，这种容器是散列的，冲突更少但使用范围很小。

3.SIMD指令虽然不是并行，但由于它可以同时处理4个数据的运算，也算是勉强算并行处理了。

参考资料：

《从内核文件系统看文件读写过程》

《Linux系统中 进程 、线程 、时间片的关系》

《说说无锁(Lock-Free)编程那些事》