《提高C++性能的编程技术》笔记：编码优化

笔记列表

缓存：在现代处理器中，缓存经常与处理器中的数据缓存和指令缓存联系在一起。缓存主要用来存储使用频繁而且代价高昂的计算结果，这样就可以避免对这些结果的重复计算。如，循环内对常量表达式求值是一种常见的低性能问题。

预先计算：预先计算和缓存联系紧密。当缓存某个计算的结果时，需要付出的代价是在对性能有重大影响的关键路径上完成一次计算。如果采用预先计算，那么甚至连这一次计算也可免了。将预先计算放置在影响性能的关键路径之外(例如初始化阶段)，就可以避免在性能关键路径上进行代价高昂的计算。

降低灵活性：使用堆存储空间(频繁的new/delete)存放IP地址可以改成使用固定大小的局部变量数组代替。

80-20法则：加快常用路径的速度：80-20法则适用于很多场合：80%的程序执行只遍历20%代码，80%的程序运行时间耗费在执行路径的所遇到的20%函数上。80-20法则有力地证明了过于草率的判断是一种错误这个观点。

延迟计算：为一个最终可能不需要的计算付出性能代价显然不是明智之举。然而在复杂的代码中这种情况比比皆是。我们不应该执行”只在某种情况下”才需要的昂贵计算，而应该只在必要的时候执行昂贵计算。这通常意味着把计算推迟到真正需要的时候才进行，因此称之为延迟计算(Lazy Evaluation)。在C++中，对象的定义会调用构造函数和析构函数，这可能是高成本的，因为它导致了立即计算----而这正是我们所要避免的。延迟计算原则建议我们推迟对象的定义，直到要使用该对象时再定义。为不一定用到的构造函数和析构函数付出代价是没有意义的。不仅应该将对象的创建推迟至合适的位置，而且应该直到具备了一个有效创建操作所必需的全部条件后，再创建对象。

无用计算：延迟计算是指那些不总是必须执行的计算，至于哪些计算是必须执行的与程序的执行流程有关，而无用计算是指那些根本无须执行的计算。无论执行流程如何，这些计算结果从不使用，因此它们是完全没有意义的。尽量使用初始化列表方式完成类成员的赋值。

系统体系结构：内存访问的代价差别很大。在某个特定的RISC体系结构中，若数据位于数据缓存中，那么访问它需要耗费一个CPU周期；若位于主存中(缓存失败)，则需要8个CPU周期；若位于硬盘上(页面错误)，则需要400000个CPU周期。虽然具体的数值会发生变化，但对于不同的处理器体系结构，周期数在总的关系上是一致的：缓存成功、缓存失败和页面错误之间的速度相差多个数量级。

当访问数据时，最先搜索的是数据缓存。若数据不在缓存中，硬件产生缓存失败信号，该信号会从RAM或硬盘加载数据至缓存中。缓存以缓存行为单位，通常加载比我们所寻找的特定数据项更大的一块数据。

内存管理：动态分配和释放堆内存的代价比较昂贵。从性能角度来讲，使用不需要显式管理的内存所产生的代价要低得多。被定义成局部变量的对象存放于堆栈上。该对象所占用的堆栈空间是为相应函数预留的堆栈空间的一部分，该对象被定义在这个函数范围内。

编译器优化：一个优秀的编译器可以代替开发者实施一些重要的优化，而无须开发者对源代码进行任何干预。第一个想到的优化是寄存器分配。当变量位于寄存器中时，载入和存储该变量是最快的。第二个需要特别注意的优化就会内联。

通常情况下，编译器默认根本不会进行任何优化。这意味着这些重要的性能优化将不会生效----即使在代码中使用了关键字register和inline也无济于事。编译器会自动忽略这些关键字，而且它经常这样做。为了更好地利用这些优化手段，必须通过向命令行添加开关或者在GUI界面上选择性能优化选项，手工打开编译器优化。

编码优化在范围上是局部的，并且不需要对程序的整体设计有深入的理解。当你加入到一个正在进行的开发项目中，并且你对其设计还没有完全理解时，这会是一个很好的起点。

最快的代码是从不执行的代码。试着按照以下步骤去剔除那些代价高昂的计算：

(1). 你打算使用该计算结果吗？听起来有点可笑，但这种可笑的事确实会发生----有时我们执行了计算但从未使用计算的结果。

(2). 你现在需要该结果吗？请在真正需要的时候再进行计算。在一些执行流程中有些结果永远不会被使用，因此不必过早地计算。

(3). 你是否已经知道结果？如果在程序执行流程的前期已经计算出了结果，那么应该使用该结果成为可重用的。

有的时候可能无法绕开该计算，此时就必须完成它。那么现在的挑战就是加快计算速度：

(1). 该计算是否过于通用？你的实现只需要跟该领域要求的一样灵活就行，而无须奢求。可以充分利用简化的假设以降低灵活性来增加速度。

(2). 一些灵活性隐藏在函数调用中。通过实现库调用的自定义版本可以提升速度。不过，这些库调用必须是被频繁调用的，否则你的努力将得不到明显效果。熟悉你所使用的库和系统调用中隐藏的代价。

(3). 尽量减少内存管理调用的数量。在绝大多数编译器中，这些调用的代价都是非常高的。

(4). 如果考虑所有可能的输入数据，则可以发现20%的数据在80%时间里出现。因此，应当以牺牲其它不经常出现的场景为代价来提高典型输入的处理速度。

(5). 缓存、RAM和磁盘访问的速度差异很明显。应该多编写缓存友好的代码。

以下是测试代码:

#include <ctype.h>
#include <string.h>
#include <iostream>
#include <chrono>
#include <string>
 
 
namespace coding_optimizations_ {
 
// reference: 《提高C++性能的编程技术》：第十三章：编码优化
 
namespace {
static char uppercaseTable[256];
 
void initLookupTable()
{
	for (int i = 0; i < 256; ++i) {
		uppercaseTable[i] = toupper(i);
	}
}
 
class Student1 {
public:
	// C++保证在Student1的构造函数体执行之前，所有的成员对象已经创建完成，此处即string型的name对象。
	// 既然我们没有显示告诉编译器如何构造它，编译器就插入了对string默认构造函数的调用。该调用在Student1的构造函数体执行之前进行。
	Student1(char* nm) { name = nm; }
private:
	std::string name;
};
 
class Student2 {
public:
	// 通过在Student2的构造函数初始化列表中显示指明string构造函数，可以避免Student1中的无效计算
	// 由于我们明确告诉编译器使用哪个string构造函数，编译器将不再隐式地调用string默认构造函数。因此我们实现了一步完成string成员对象的构造
	Student2(char* nm) : name(nm) {}
private:
	std::string name;
};
 
} // namespace

} // namespace coding_optimizations_
using namespace coding_optimizations_;

int main()
{
	initLookupTable();
 
	std::chrono::high_resolution_clock::time_point time_start, time_end;
	const int count{1000000000}, count2{100000};
	const char* header{"afaIELQEadsfjl943082jdfaadfajqwppreijfadfadfaoueheufiekasdLdamsaldfadfawweevKKA"};
	int length = strlen(header);
	char ch;
 
{ // test lowercase letter to uppercase letter: normal
	time_start = std::chrono::high_resolution_clock::now();
	for (int t = 0; t < count; ++t) {
		for (int i = 0; i < count; ++i) {
			char* p = const_cast<char*>(header);
			for (int j = 0; j < length; ++j) {
				ch = toupper(*p++);
				//fprintf(stdout, "%c", ch);	
			}
			//fprintf(stdout, "\n");
		}
	}
	time_end = std::chrono::high_resolution_clock::now();	
	fprintf(stdout, "lowercase letter to uppercase letter normal time spend: %f seconds\n",
		(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}
 
{ // test lowercase letter to uppercase letter: pre-calculated
	time_start = std::chrono::high_resolution_clock::now();
	for (int t = 0; t < count; ++t) {
		for (int i = 0; i < count; ++i) {
			char* p = const_cast<char*>(header);
			for (int j = 0; j < length; ++j) {
				ch = uppercaseTable[*p++];
				//fprintf(stdout, "%c", ch);	
			}
			//fprintf(stdout, "\n");
		}
	}
	time_end = std::chrono::high_resolution_clock::now();	
	fprintf(stdout, "lowercase letter to uppercase letter pre-calculated time spend: %f seconds\n",
		(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}
 
{ // test unuseful calculate: normal
	time_start = std::chrono::high_resolution_clock::now();
	for (int t = 0; t < count2; ++t) {
		Student1 st((char*)"beijing");
	}
	time_end = std::chrono::high_resolution_clock::now();	
	fprintf(stdout, "unuseful calculate normal time spend: %f seconds\n",
		(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}
 
{ // test unuseful calculate: list init
	time_start = std::chrono::high_resolution_clock::now();
	for (int t = 0; t < count2; ++t) {
		Student2 st((char*)"beijing");
	}
	time_end = std::chrono::high_resolution_clock::now();	
	fprintf(stdout, "unuseful calculate list init time spend: %f seconds\n",
		(std::chrono::duration_cast<std::chrono::duration<double>>(time_end-time_start)).count());
}
 
	return 0;
}

利用 godbolt 执行，相应代码见点击这里测试结果如下：

lowercase letter to uppercase letter normal time spend: 0.000000 seconds
lowercase letter to uppercase letter pre-calculated time spend: 0.000000 seconds
unuseful calculate normal time spend: 0.000914 seconds
unuseful calculate list init time spend: 0.000000 seconds