提高c++性能的编程技术 pdf_《提高C++性能的编程技术》笔记
0. 导读1. 软件低效的根源：(1). 设计效率，再好的编码效率都无法弥补糟糕的设计。(2). 编码效率，其中包括数据和算法结构，程序分解（任务的分解）。对编码效率再分解有四个小项：系统体系结构（系统性能）、语言结构、库、编译器优化。2. 在提到性能时要考虑以下几点：(1). 内存大小有限制。(2). 内存访问的开销不是均衡的，对缓存、主内存和磁盘的访问开销不是同等数量级的。(3). 程序没有专
0. 导读
1. 软件低效的根源：
(1). 设计效率，再好的编码效率都无法弥补糟糕的设计。
(2). 编码效率，其中包括数据和算法结构，程序分解（任务的分解）。
对编码效率再分解有四个小项：系统体系结构（系统性能）、语言结构、库、编译器优化。
2. 在提到性能时要考虑以下几点：
(1). 内存大小有限制。
(2). 内存访问的开销不是均衡的，对缓存、主内存和磁盘的访问开销不是同等数量级的。
(3). 程序没有专用的CPU，只是获取一个时间片。
(4). 在单处理器上，并行只是轮询而已。
1.跟踪实例
1. 熟悉一条指令的内部执行过程，包含的计算有哪些。例如：t.debug("x= " + itoa(x));
执行步骤如下：
(1). 为"x= "创造临时string对象。
(2). 调用itoa(x)函数。
(3). 从itoa()返回的字符串指针创建一个临时的string对象。
(4). 连接"x= "进而创建第三个string临时对象。
(5). 在debug()调用后销毁全部string临时对象。
2. C++性能的基本原则有：
(1). I/O的开销是高昂的。
(2). 函数的调用开销是一个因素。应该将短小、频繁调用的函数内联。
(3). 复制对象的开销是高昂的。最好选择传递引用，而不是传递值。（什么时候传递值，什么时候传递引用呢？难道传递值的方式再也不推荐使用了吗？）
#include <iostream>
#include <windows.h>
static LARGE_INTEGER cpuFreq;
static LARGE_INTEGER startTime;
static LARGE_INTEGER endTime;
static double run_time = 0.0;
using namespace std;
class Trace{
public:
//Trace(const string &name); //string类型的传值和引用的性能差异有多大？
Trace(const char *name); //string类型换成char*,时间是2862.73ms
~Trace();
void debug(const string &msg);
static bool traceIsActive;
private:
string *theFunctionName;
};
//inline Trace::Trace(const char *name) : theFunctionName(name) //增加了对theFunctionName成员变量赋值的开销
inline Trace::Trace(const char *name) : theFunctionName()
{
if (this->traceIsActive){
cout << "Enter function" << name << endl;
theFunctionName = new string(name); //修改完这个，时间是547.31ms
}
}
inline void Trace::debug(const string &msg)
{
if (this->traceIsActive){
cout << msg << endl;
}
}
inline Trace::~Trace()
{
if (this->traceIsActive){
cout << "Exit function" << *theFunctionName << endl;
delete theFunctionName;
}
}
bool Trace::traceIsActive = false;
int addone_0(int x) //统计运行次数10e7次，时间190ms左右
{
return x+1; //原始版本
}
int addone_1(int x) //统计运行次数10e7次，时间4095.77ms左右。相差21倍左右！！
{
Trace t("addone"); //增加Trace类，看吃掉多少性能！！！
return x+1;
}
int main()
{
QueryPerformanceFrequency(&cpuFreq); //获取系统时钟的频率
QueryPerformanceCounter(&startTime);
for (int i = 0; i < 10e7; i++) {
addone_1(1);
}
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "run_time: "<< run_time <<"ms" << endl;
while(1);
}
3. 要点：
(1). 对象定义会触发隐性执行构造函数和析构函数。但是对象构造和析构并不总是意味着开销。如果这两者的执行是必要的。那么考虑使用高效的代码（内联会减少函数调用的开销）。
(2). 通过引用不能保证良好的性能，所以更要避免使用对象复制所带来的开销。减少对象的创建和销毁有利于提高性能。（单例模式算其中一种吗？）
(3). 内联函数减少了常调用小函数的开销。内联的构造函数和析构函数使得消除对象变得更容易。
2.构造函数和析构函数
1. 在多行代码多线程接口中添加了返回语句，容易导致两个问题：
(1). 很容易忽略之前曾获得锁这个事实。
(2). 如果抛出异常有持有锁，那么只有在捕获异常时手工释放锁。感觉特别变扭。
解决方式是：可以利用自动调用的析构函数解决锁的维护问题。把锁封装在对象内部并构造函数获得，析构函数自动释放锁。编译器会在每条返回语句之前会对带锁的析构函数进行释放。（但是这种类型只能作为局部变量）
实现如下：
class Lock{
public:
Lock(pthread_mutex_t& key):theKey(key)
{
pthread_mutex_lock(&theKey);
}
~Lock()
{
pthread_mutex_unlock(&theKey);
}
private:
pthread_mutex_t &theKey;
};
2. 对象的创建和销毁会造成性能的损失。其次，对象的相关开销与对象本身的派生链长度和复杂性有关。所创造对象的数量与派生的复杂性成正比。
3. 遵守最重要的原则：尽全力使用最简单的解决方案。
4. string对象的创建和销毁都是自动完成的，你无法阻止。为了对子对象的创建和销毁进行更好的控制，你可以使用指针来代替它。
5. 向一个指针赋值0比构造一个新对象要廉价得多。
6. 性能最佳与代码优化往往是相违背的。性能优化经常需要牺牲一些其他的软件目标，例如灵活性、可维护性、重用之类的重要目标经常必须为性能让步。生成高质量的代码，而不影响其他的软件目标是很少见的。
7. C++比C更好的一个原因就是它能够延迟变量的创建。
8. 要点：
(1). 构造函数和析构函数在实践中经常包含冗余计算。
(2). 当心复杂层次中的对象的复合使用。它们使得创建和销毁的开销更为高昂。
(3). 对象的生命周期不是无偿的。不要随意创建一个对象，要等到需要使用对象的地方再创建它。
(4). 编译器必须初始化被包含的成员对象之后再执行构造函数体。你必须在初始化阶段完成成员对象的创建。这样可以降低随后在构造函数部分调用赋值操作符的开销。
3.虚函数
1. 虚函数可能会造成的性能损失：
(1). 构造函数必须初始化vptr（虚函数列表）。
(2). 虚函数是通过指针间接调用的，必须先得到指向虚函数表的指针，然后再获取到正确的函数偏移量。
(3). 内联是在编译时决定的。编译器不可能把运行时才解析的虚函数设置为内联。
2. 函数调用的动态绑定是继承的结果，消除动态绑定的一种方式是用基于模板的设计来代替继承。模板把解析步骤放在编译期间，而不是运行期间。并且模板有两方面的优点重用和效率。
4.返回值优化
1. 返回值优化指的是通过转换源代码和消除对象的创建来加快代码的执行速度。
案例：
#include <iostream>
#include <windows.h>
static LARGE_INTEGER cpuFreq;
static LARGE_INTEGER startTime;
static LARGE_INTEGER endTime;
static double run_time = 0.0;
using namespace std;
class Complex
{
friend Complex operator+ (const Complex&, const Complex&);
friend void Complex_Add (Complex&, const Complex&, const Complex&);
friend Complex Complex_Add_1 (const Complex&, const Complex&);
public:
//默认构造函数
Complex(double r = 0.0, double i = 0.0) : real(r),imag(i) {}
//拷贝构造函数
Complex(const Complex& c) : real(c.real), imag(c.imag){}
//赋值运算符
Complex&operator= (const Complex &c){
this->real = c.real;
this->imag = c.imag;
return *this;
}
~Complex(){}
private:
double real;
double imag;
};
//Complex operator+ (const Complex& a, const Complex& b) //没有执行返回值优化
//{
// Complex retVal;
// retVal.real = a.real + b.real;
// retVal.imag = a.imag + b.imag;
// return retVal;
//}
void Complex_Add (Complex& result, const Complex& a, const Complex& b) //执行返回值优化
{
result.real = a.real + b.real;
result.imag = a.imag + b.imag;
}
Complex Complex_Add_1 (const Complex& a, const Complex& b) //没有执行返回值优化
{
Complex retVal(a.real + b.real, a.imag + b.imag);
return retVal;
}
Complex operator+ (const Complex& a, const Complex& b) //没有执行返回值优化，和文章描述的不符合。可能是编译器原因
{
return Complex(a.real + b.real, a.imag + b.imag);
}
int main()
{
Complex a(1.0);
Complex b(2.0);
Complex c;
QueryPerformanceFrequency(&cpuFreq); //获取系统时钟的频率
QueryPerformanceCounter(&startTime);
for (int i = 0; i < 10e6; i++) {
//c = a + b; //108ms 第一版
//Complex_Add(c,a,b); //35.69ms
//Complex_Add_1(a,b); //70.69ms
c = a + b; //100ms 第二版
}
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "run_time: "<< run_time <<"ms" << endl;
while(1);
}
2. 要点
(1). 如果必须返回对象，通过RVO（返回值优化）可以节省创建和销毁局部对象的步骤，从而改善性能。
(2). RVO的应用要遵守编译器的实现而定。需要参考编译器文档和通过实验证明是否达到优化的效果。
(3). 通过编写计算性构造函数可以更好的使用RVO。
5.临时变量
1. 临时对象的产生对性能绝不是微弱影响，如果不理解临时变量的起源、开销，以及如何在适当的时候消除它，很难写出高效的代码。（那么如何找出临时变量的产生很关键！！）。实际上，编译器有时候也会去优化省去临时变量，所以在实践的时候，可以试验一下性能有没有提升。不能一概而论。
案例：
string s1 = "hello";
string s2 = "world";
string s3 = s1 + s2; //没有产生临时对象
s3 = s1 + s2; //产生临时对象
2. 使用op =()消除临时对象
案例：
s3 = s1 + s2; //产生临时对象
s3 = s1; s3 += s2; //没有临时对象，但是代码不雅观。
3. 要点
(1).临时变量会以构造函数和析构函数的形式降低一半的性能。
(2).如果可以，尽可能使用按引用传递和返回对象来代替对象拷贝。
(3).在<op>可能是“+、-、*、/”的地方，使用<op>=运算可以消除临时对象。
6.单线程内存池
1. 频繁地分配和回收内存会严重影响性能，通过开发专用的内存管理器可以解决这个问题。
2. 对专用内存管理器的设计至少要从两个方面考虑：大小和并发。
从大小的角度分为以下两种：
(1)、固定大小：分配固定大小内存块的内存管理器。
(2)、可变大小：分配任意大小内存块的内存管理器。所请求分配的大小事先是未知的。
从并发的角度也分为以下两种：
(1)、单线程：内存管理器局限在一个线程内。内存被一个线程使用，并且不越出该线程的界限。这种内存管理器不涉及相互访问的多线程。
(2)、多线程：内存管理器被多个线程并发地使用。这种实现需要包含互斥执行的代码段。无论什么时候，只能有一个线程在执行一个代码段。
案例：
- 版本0：全局函数new()和delete()
#include <iostream>
#include <windows.h>
static LARGE_INTEGER cpuFreq;
static LARGE_INTEGER startTime;
static LARGE_INTEGER endTime;
static double run_time = 0.0;
using namespace std;
class Rational0 //一百万次运行:73.3ms
{
public:
Rational0(int a = 0, int b = 1) : n(a),d(b) {}
private:
int n; // 分子
int d; // 分母
};
int main()
{
Rational0 *array0[1000];
QueryPerformanceFrequency(&cpuFreq); //获取系统时钟的频率
QueryPerformanceCounter(&startTime);
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
array0[j] = new Rational0(j);
}
for (int k = 0; k < 1000; k++) {
delete array0[k];
}
}
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "run_time: "<< run_time <<"ms" << endl;
Rational2::deleteMemPool();
while(1);
}
- 版本1：专用内存管理器
#include <iostream>
#include <windows.h>
static LARGE_INTEGER cpuFreq;
static LARGE_INTEGER startTime;
static LARGE_INTEGER endTime;
static double run_time = 0.0;
using namespace std;
class NextOnFreeList { //声明一个辅助结构来连接空闲列表的相邻元素
public:
NextOnFreeList* next;
};
/*需求:避免频繁使用默认内存管理器，原理是先分配指定大小的内存空间，当空间使用完时再分配*/
class Rational1 { //一百万次运行:9.03ms
public:
Rational1(int a = 0, int b = 1) : n(a),d(b) {}
//Rational2的操作符new()和delete()用来管理静态列表。重载全局的new()和delete()。
inline void* operator new(size_t size);
inline void operator delete(void* doomed);
static void newMemPool() { expandTheFreeList(); }
static void deleteMemPool();
private:
static NextOnFreeList* freeList; //空闲静态列表
static void expandTheFreeList(); //静态成员函数，避免从新生成一个类变量，可以节省内存，方便调用，但不能访问类中的非静态成员
enum { EXPANSION_SIZE = 32};
int n; // 分子
int d; // 分母
};
NextOnFreeList* Rational1::freeList = nullptr;
inline void* Rational1::operator new(size_t size)
{
if(nullptr == freeList){
expandTheFreeList(); //列表为空时，扩展
}
NextOnFreeList *head = freeList;
freeList = head->next;
return head;
}
inline void Rational1::operator delete(void* doomed)
{
NextOnFreeList *head = static_cast<NextOnFreeList *>(doomed);
head->next = freeList;
freeList = head;
}
void Rational1::expandTheFreeList() //
{
//必须分配足够大的对象以包含下一个指针
size_t size = (sizeof (Rational1) > sizeof (NextOnFreeList *)) ? sizeof (Rational1) : sizeof (NextOnFreeList *);
NextOnFreeList* runner = static_cast<NextOnFreeList*>((void*)new char[size]);
freeList = runner;
for (int i = 0; i < EXPANSION_SIZE; ++i) {
//修改runner的地址同时也修改了freeList，因为是指针类型，并将runner->next强制转换成NextOnFreeList*类型
runner->next = static_cast<NextOnFreeList*>((void*)new char[size]);
runner = runner->next;
}
runner->next = nullptr;
}
void Rational1::deleteMemPool()
{
NextOnFreeList* nextPtr;
for (nextPtr = freeList; nextPtr != nullptr; nextPtr = freeList) {
freeList = freeList->next;
delete [] nextPtr;
}
}
int main()
{
Rational1 *array1[1000];
Rational1::newMemPool();
QueryPerformanceFrequency(&cpuFreq); //获取系统时钟的频率
QueryPerformanceCounter(&startTime);
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
array1[j] = new Rational1(j);
}
for (int k = 0; k < 1000; k++) {
delete array1[k];
}
}
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "run_time: "<< run_time <<"ms" << endl;
Rational1::deleteMemPool();
while(1);
}
- 版本2：固定大小对象的内存池
#include <iostream>
#include <windows.h>
static LARGE_INTEGER cpuFreq;
static LARGE_INTEGER startTime;
static LARGE_INTEGER endTime;
static double run_time = 0.0;
using namespace std;
/*需求：希望内存管理器适用于其他不同的大小类型*/
//MemoryPool类的作用是维护空闲列表
template <class T> //声明一个模板，虚拟类型名为T
class MemoryPool //类模板名为MemoryPool
{
public:
MemoryPool(size_t size = EXPANSION_SIZE);
~MemoryPool();
//从空闲列表中分配T元素
inline void* alloc(size_t size);
//返回T元素到空闲列表中
inline void free(void *doomed);
private:
//空闲列表的下一个元素
MemoryPool<T> *next;
//空闲列表为空时，按照指定大小扩展
enum {EXPANSION_SIZE = 32};
//添加空闲元素至空闲列表
void expandTheFreeList(int list_size = EXPANSION_SIZE);
};
template <class T>
MemoryPool<T>::MemoryPool(size_t size)
{
expandTheFreeList(size);
}
template <class T>
MemoryPool<T>::~MemoryPool()
{
MemoryPool<T> *nextPtr = next;
for (nextPtr = next; nextPtr != nullptr; nextPtr = next) {
next = next->next;
delete [] nextPtr;
}
}
template <class T>
void* MemoryPool<T>::alloc(size_t size)
{
if(nullptr == next){
expandTheFreeList(); //列表为空时，扩展
}
MemoryPool<T> *head = next;
next = head->next;
return head;
}
template <class T>
void MemoryPool<T>::free(void* doomed)
{
MemoryPool<T> *head = static_cast<MemoryPool<T> *>(doomed);
head->next = next;
next = head;
}
/*用途：向空闲列表添加新元素。在空闲列表用尽时被调用*/
template <class T>
void MemoryPool<T>::expandTheFreeList(int list_size)
{
size_t size = (sizeof (T) > sizeof (MemoryPool<T>*)) ? sizeof (T) : sizeof (MemoryPool<T>*);
//从堆上分配新元素
MemoryPool<T>* runner = static_cast<MemoryPool<T>*>((void*)new char[size]);
//将新元素连接到列表中
next = runner;
//分配固定大小的内存
for (int i = 0; i < list_size; ++i) {
//修改runner的地址同时也修改了freeList，因为是指针类型，并将runner->next强制转换成NextOnFreeList*类型
runner->next = static_cast<MemoryPool*>((void*)new char[size]);
runner = runner->next;
}
runner->next = nullptr;
}
class Rational2 { //运行时间：12.07ms
public:
Rational2(int a = 0, int b = 1) : n(a),d(b) {}
inline void* operator new(size_t size){ return memPool->alloc(size); }
inline void operator delete(void* doomed){ return memPool->free(doomed); }
static void newMemPool() { memPool = new MemoryPool<Rational2>; }
static void deleteMemPool(){ delete memPool; }
private:
static MemoryPool<Rational2>* memPool;
static void expandTheFreeList();
enum { EXPANSION_SIZE = 32};
int n; // 分子
int d; // 分母
};
MemoryPool<Rational2>* Rational2::memPool = nullptr;
int main()
{
Rational2 *array3[1000];
Rational2::newMemPool();
QueryPerformanceFrequency(&cpuFreq); //获取系统时钟的频率
QueryPerformanceCounter(&startTime);
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
array3[j] = new Rational2(j);
}
for (int k = 0; k < 1000; k++) {
delete array3[k];
}
}
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "run_time: "<< run_time <<"ms" << endl;
Rational2::deleteMemPool();
while(1);
}
版本3：单线程可变大小内存管理器
#include <iostream>
#include <windows.h>
static LARGE_INTEGER cpuFreq;
static LARGE_INTEGER startTime;
static LARGE_INTEGER endTime;
static double run_time = 0.0;
using namespace std;
/*需求：当我们一开始无法判断数据所需内存的大小时，需要设计可变大小的内存管理器*/
//MemoryChunk代替前面的NextOnFreeList类，作用：把不同大小的内存块连接成块序列
class MemoryChunk
{
public:
MemoryChunk(MemoryChunk *nextChunk, size_t reqSize);
~MemoryChunk(){delete [] mem;}
inline void *alloc(size_t size);
inline void free(void* someElement){}
//指向列表下一个内存块
MemoryChunk *nextMemoryChunk() {return next;}
//检查当前剩余的内存空间
size_t spaceAvailable() {return chunkSize - byteAlreadyAllocated;}
//默认分配的内存空间
enum {DEFAULT_CHUNK_SIZE = 4096};
private:
MemoryChunk *next;
//要分配的对象
void *mem;
//一个内存块的默认大小
size_t chunkSize;
//当前已经分配的字节数
size_t byteAlreadyAllocated;
};
MemoryChunk::MemoryChunk(MemoryChunk *nextChunk, size_t reqSize)
{
//确认内存块的适当大小
chunkSize = (reqSize > DEFAULT_CHUNK_SIZE)? reqSize :DEFAULT_CHUNK_SIZE;
next = nextChunk;
//这是全新的构造函数，当前已经分配的字节数为0
byteAlreadyAllocated = 0;
//根据内存块的适当大小，分配内存空间
mem = new char[chunkSize];
}
//内存分配请求，返回一个指向mem所指向的MemoryChunk中的可用空间
void* MemoryChunk::alloc(size_t size)
{
void *addr = static_cast<void *>(static_cast<char*>(mem) + byteAlreadyAllocated);
//记录已经分配的内存大小
byteAlreadyAllocated += size;
return addr;
}
class ByteMemoryPool
{
public:
ByteMemoryPool(size_t initSize = MemoryChunk::DEFAULT_CHUNK_SIZE);
~ByteMemoryPool();
inline void *alloc(size_t size);
inline void free(void* someElement) {listOfMemoryChunk->free(someElement);}
private:
//内存块列表
MemoryChunk *listOfMemoryChunk;
//添加内存块
void expandStorage(size_t reqSize);
};
//创建对象，生成私有存储空间
ByteMemoryPool::ByteMemoryPool(size_t initSize)
{
expandStorage(initSize);
}
//释放内存空间
ByteMemoryPool::~ByteMemoryPool()
{
MemoryChunk *memChunk = listOfMemoryChunk;
while (memChunk) {
listOfMemoryChunk = memChunk->nextMemoryChunk();
delete memChunk;
memChunk = listOfMemoryChunk;
}
}
void* ByteMemoryPool::alloc(size_t size)
{
size_t space = listOfMemoryChunk->spaceAvailable();
//所需要的空间大于实践剩余空间，就申请内存
if(space < size){
expandStorage(size);
}
return listOfMemoryChunk->alloc(size);
}
void ByteMemoryPool::expandStorage(size_t reqSize)
{
listOfMemoryChunk = new MemoryChunk(listOfMemoryChunk,reqSize);
}
class Rational3 { //运行时间:20.1893ms
public:
Rational3(int a = 0, int b = 1) : n(a),d(b) {}
inline void* operator new(size_t size){ return memPool->alloc(size); }
inline void operator delete(void* doomed){ return memPool->free(doomed); }
static void newMemPool() { memPool = new ByteMemoryPool; }
static void deleteMemPool(){ delete memPool; }
private:
static ByteMemoryPool* memPool;
static void expandTheFreeList();
enum { EXPANSION_SIZE = 32};
int n; // 分子
int d; // 分母
};
ByteMemoryPool* Rational3::memPool = nullptr;
int main()
{
Rational3 *array3[1000];
Rational3::newMemPool();
QueryPerformanceFrequency(&cpuFreq); //获取系统时钟的频率
QueryPerformanceCounter(&startTime);
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
array3[j] = new Rational3(j);
}
for (int k = 0; k < 1000; k++) {
delete array3[k];
}
}
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "run_time: "<< run_time <<"ms" << endl;
Rational3::deleteMemPool();
while(1);
}
增加了分配逻辑的复杂程度，版本3比版本1,2稍慢，但是易用性更高。
3. 要点：
(1). 内存管理器的功能和灵活性增加会降低执行速度。
(2).全局内存管理器的new()和delete()是通用的，代价高。
(3). 专用内存管理器比全局内存管理器快一个数量级以上。
(4). 单线程专用内存管理器省去了全局函数new()和delete()必须要处理并发问题，性能有所提高。
7.多线程内存池
有些不是很懂，待续。。。。。。
8.内联基础
1. 为了满足性能需求，设计者不得不牺牲一些设计特性，如代码量、可移植性、可扩展性以及通用性。
2. 内联会显著提升性能，但也增加了编译时间。并且在大多数情况下会要求整体程序重新编译。所以内联的过程搁置到代码开发后期是比较明智的。
3. 编译器将方法内联化的步骤：
(1). 将待内联方法的连续代码块复制到调用方法中的调用点处。
(2). 为所有的内联方法的局部变量分配内存。
(3). 将内联方法的输入参数和返回值映射到调用方法的局部变量空间内
(4). 如果内联方法的返回点有多个，将其转换成内联代码块末端的分支。
4. 避免方法的调用和调用间优化是内联可提升性能空间的两种方式。
5. 内联终究还是一种由编译器/配置器/优化器执行的、基于编译和配置的优化操作。
6. 要点：
(1). 内联就是用方法的代码来替换方法的调用。
(2). 内联通过消除调用开销来提高性能，并允许进行调用间优化。
(3). 内联的主要作用是对运行时间进行优化，当然它也可以是可执行映像变得更小。
9. 内联——站在性能的角度
1. 调用间优化的一般形式为：在编译期间进行一部分预处理，从而避免在运行时重复类似的过程。
2. 不能内联的全部方法的原因之一是内联所带来的代码膨胀有时无法接受。
3. 内联产生的方法调用和返回方面的性能提升，可能会因为内联导致的缓存性能锐减所抵消。（内联的滥用导致的缓存错误会使性能锐减）。
4. 内联的规则：
(1). 能够缩小代码大小的内联函数都是可取的，而任何显著增大代码大小的内联都是不可取的。
(2). 如果方法的实现是易变的，则不应该将其内联。
(3). 有些函数本身就应该避免内联，例如递归函数。
5. 开发阶段和编译期的内联考虑：
(1). 内联的方法应该定义在类的头文件中，可内联的方法一旦有所改变，就会导致相关模块重新编译。对于大工程来说，会带来额外的时间消耗。
(2). 针对内联方法的调试比较复杂。因为单个断点无法跟踪到内联函数的出入口。
6. 配置是一种依赖配置工具的性能测试技术，通过为程序生成工具代码。在程序样本执行期间使性能具备某种特征。一般配置文件至少包括：哪些方法被执行以及调用该方法的相关信息。
7. 配置文件要同时兼顾指令数的计算和时间的度量。但是通过指令数进行性能度量存在以下问题：
(1). 存在某些指令的执行长于其他指令。例如加载和存储指令比逻辑与运算指令更耗时。
(2). 指令数的误导性尤为突出。某些指令执行只需要消耗一个时钟周期，有些要消耗几十个时钟周期。
(3). 针对指令数的度量标准完全忽略了底层体系结构对性能的影响。这些影响包括缓存效率、流水线中的跳转机制、寄存器与内存使用的相关问题以及内存的访问延迟等。
8. 要点：
(1). 直接量参数与内联结合使用。为编译器性能的提升开辟了空间。
(2). 对于那些调用频率高的方法，如何是静态尺寸较大，而动态尺寸较小，可以考虑重写，从而抽取其核心的动态特性，并将动态组件内联。
(3). 精简化与唯一化方法总是可以被内联的。
10.内联技巧
忽略……
11.标准模板库
1. 标准模板库（STL）是容器和通用算法的强效结合。但是从性能的角度出发，我们要考虑以下问题：
(1). 在渐近复杂度方面，STL与各种容器和算法的性能密切相关。这是什么意思？
(2). STL是由很多容器组成的，对于一个具体的计算任务（例如排序、插入、删除、遍历、查找等），应该使用哪种容器比较好，为什么？另外，在特定的条件下还有更好的选择吗？
(3). STL的性能如何？如果更好的使用自定义的容器和算法？
2. 插入测试
案例：
#include <iostream>
#include <stdlib.h>
#include <windows.h>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
static LARGE_INTEGER cpuFreq;
static LARGE_INTEGER startTime;
static LARGE_INTEGER endTime;
static double run_time = 0.0;
using namespace std;
/*目的：测试不同容器，插入数据的性能*/
/*测试要求：将100万个随机元素插入到数组、向量、列表和多重集中。每个插入测试带有三个参数
1.指向被测目标容器的指针。
2.指向data数组的指针，该数组保存了要插入到目标容器的元素。
3.data数组的大小。
*/
//数组形式插入
template <class T>
void arrayInsert(T *a, const T *collection, int size)
{
for(int k = 0; k < size; k++){
a[k] = collection[k];
}
}
//向量形式插入
template <class T>
void vectorInsert(vector<T> *v, const T *collection, int size)
{
for(int k = 0; k < size; k++){
v->push_back(collection[k]);
}
}
//向量形式插入容器前端
template <class T>
void vectorInsertFront(vector<T> *v, const T *collection, int size)
{
for(int k = 0; k < size; k++){
v->insert(v->begin(), collection[k]);
}
}
//列表形式插入
template <class T>
void listInsert(list<T> *l, const T *collection, int size)
{
for(int k = 0; k < size; k++){
l->push_back(collection[k]);
}
}
//列表形式插入容器前端
template <class T>
void listInsertFront(list<T> *l, const T *collection, int size)
{
for(int k = 0; k < size; k++){
l->push_front(collection[k]);
}
}
//多重集中形式插入
template <class T>
void multisetInsert(multiset<T> *s,const T *collection, int size)
{
for(int k = 0; k < size; k++){
s->insert(collection[k]);
}
}
//产生随机元素函数
int *genInitData(int size)
{
int *data = new int[size];
generate(&data[0], &data[size],rand);
return data;
}
//各个容器插入性能对比
void Insert_Perfor()
{
QueryPerformanceFrequency(&cpuFreq); //获取系统时钟的频率
const int size = 1000000;
//int array_data[1000000] = {0}; //直接分配的int类型数组在栈空间上的大小有限。有问题
int *data = genInitData(size);
int *array_data = new int[size];
QueryPerformanceCounter(&startTime);
arrayInsert(array_data,data,size);
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "arrayInsert run_time: "<< run_time <<"ms" << endl;
vector<int> vec_data;
QueryPerformanceCounter(&startTime);
vectorInsert(&vec_data,data,size);
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "vectorInsert run_time: "<< run_time <<"ms" << endl;
list<int> list_data;
QueryPerformanceCounter(&startTime);
listInsert(&list_data,data,size);
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "listInsert run_time: "<< run_time <<"ms" << endl;
multiset<int> multiset_data;
QueryPerformanceCounter(&startTime);
multisetInsert(&multiset_data,data,size);
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "multisetInsert run_time: "<< run_time <<"ms" << endl;
}
//向量和列表插入容器前端性能对比
void Insert_Front_Perfor()
{
QueryPerformanceFrequency(&cpuFreq); //获取系统时钟的频率
const int size_front = 100000;
int *data_front = genInitData(size_front);
vector<int> vec_front_data;
QueryPerformanceCounter(&startTime);
vectorInsertFront(&vec_front_data,data_front,size_front);
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "vectorInsertFront run_time: "<< run_time <<"ms" << endl;
list<int> list_front_data;
QueryPerformanceCounter(&startTime);
listInsertFront(&list_front_data,data_front,size_front);
QueryPerformanceCounter(&endTime);
run_time = (((endTime.QuadPart - startTime.QuadPart) * 1000.0) / cpuFreq.QuadPart);
cout << "listInsertFront run_time: "<< run_time <<"ms" << endl;
}
int main()
{
Insert_Perfor();
Insert_Front_Perfor();
while(1);
}
运行结果及分析：
数组性能远远优于其它容器原因是数组是直接分配内存包含100万个数据元素。但是向量、列表和多重集不会提前知道集合的大小，都是动态分配内存的。而且对于每一个数据，列表除了要为其设置前项指针和后向指针外，还要分配一个列表元素来存储数据。多重集一直保持其集合为有序的状态。
总结插入测试的测试结果：在知道集合大小的情况下，数组的性能最佳，在集合大下未知的情况下，插入整数，向量优于列表。将元素插入容器前端时，列表优于向量。
3.删除测试
案例：
//向量形式删除
template <class T>
void vectorDelete(vector<T> *v)
{
while(!v->empty()){
v->pop_back();
}
}
//向量形式前端删除
template <class T>
void vectorDeleteFront(vector<T> *v)
{
while(!v->empty()){
v->erase(v->begin());
}
}
//列表形式删除
template <class T>
void listDelete(list<T> *l)
{
while(!l->empty()){
l->pop_back();
}
}
//列表形式前端删除
template <class T>
void listDeleteFront(list<T> *l)
{
while(!l->empty()){
l->pop_front();
}
}
总结删除测试结果：（很多关于插入效率的结论同样适用于删除）
(1). 向量擅长于尾部对元素进行插入（或删除）操作。此操作与集合大小无关，是固定时间的操作。
(2). 除对集合尾部进行操作外，采用向量进行其他任何位置的插入（或删除）都是糟糕的选择。性能的损失与插入（或删除）点到向量尾部元素的距离成正比。（为什么？）
(3). 双向队列在集合的前端和尾部插入（或删除）元素效率都很高。在其他任何位置插入（或删除）元素效率都很低。
(4). 列表在集合的任何位置插入（或删除）元素效率都很高。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
1
0- 0
已为社区贡献2条内容
所有评论(0)