广州最好的网站设计,网站描述模板,祁阳网页设计,编程软件下载手机版一. 选择合适的数据结构
1.1 map与unordered_map的选择
如果仅仅只需要使用到快速查找的特性#xff0c;那么unordered_map更加合适#xff0c;他的复杂度是O(1)。如果还需要排序以及范围查找的能力#xff0c;那么就选择map。
1.2 vector与list的选择
通常情况下#…一. 选择合适的数据结构
1.1 map与unordered_map的选择
如果仅仅只需要使用到快速查找的特性那么unordered_map更加合适他的复杂度是O(1)。如果还需要排序以及范围查找的能力那么就选择map。
1.2 vector与list的选择
通常情况下顺寻存储一些数据然后通过下标进行查找就选择vector。那么什么时候选择list呢常见的一个用法就是在LRU 缓存的实现中我们会使用list来存放缓存结点而不是vector主要原因就在于list的插入和删除是高效的。
1.3 unordered_map与自定义查找表的选择
如果不需要复杂的哈希函数仅通过数组下标的形式就能完成哈希比如key是26个字母或者连续的数字。此时只需要定义一个数组就能实现哈希存储自定义查找表。
二. 选择合适的算法
算法对性能的影响是值得考虑的以排序算法举例
快速排序适合数据比较均匀的场景如果数据已经有序或者接近有序此时快速排序会退化到O(n*n)的复杂度。堆排序适合求topK问题。归并排序O(n)的空间复杂度但是排序性能不会因为数据本身已经有序而退化。冒泡排序一般情况下不推荐此排序。性能较差。
三. 避免不必要的拷贝
3.1 使用引用
引用可以直接与被引用对象共享同一份存储可以认为引用是给对象起一个别名。如下示例代码
// 形参使用引用
void show(const std::string str)
{// do something
}std::vectorstd::string strs;
/*
对strs进行填充
*/
// 使用引用接收返回值前提是函数返回对象的引用
const std::string str strs[1];3.2 使用移动语义
移动语义一般用在初始化对象或者给对象赋值时可以避免对象的拷贝。如下代码
std::string stra abc;
// 拷贝stra对象
std::string strb stra;
// 移动strb的资源到strc中
std::string strc std::move(strb);3.3 返回值优化RVO
通常编译器都有RVO优化的功能它允许直接在调用者的栈帧上构造对象从而避免了额外的拷贝和资源析构的开销。如下代码
class A {
public:A() {}~A() {}A(const A rhs) {}A(A rhs) {}
};int func()
{A a;return a;
}int main()
{A a func();return 0;
}上述代码中返回值优化之后类A的构造函数和析构函数只被调用一次不会产生临时变量的构造与析构以及拷贝构造的过程。
四. 合适的内存管理
4.1 智能指针
在管理动态内存时智能指针可以帮助我们实现更可靠的内存管理避免内存泄漏等严重问题。C11中提供了unique_ptr和shared_ptr两个智能指针那么该如何选择呢
shared_ptr共享智能指针。一个对象可能在多个地方被共享。unique_ptr独占智能指针。一个对象只能被一个智能指针对象所拥有。
通常情况下如果能明确是独占的场景那么就选择unique_ptr虽然shared_ptr也能保证正确性但是后者性能要比前者差30%。因为uniqe_ptr更接近裸指针而shared_ptr内部实现相对复杂引用计数、控制块等。
4.2 内存池
内存池是一个预先申请和分配好的内存区域。在需要申请内存资源时可以直接在内存池中获取在释放内存时将内存返还给内存池。从而避免了频繁的内存分配和释放的过程。google的tcmalloc就提供了这样的功能。
4.3 对象池
对象池同样也是一种预先申请和分配内存的技术区别于内存池的是其针对的是特定的类对象的内存管理。如果一个类型需要频繁的进行对象的创建和释放并且对象的创建比较耗时。那么我们可以选择使用池化技术预先创建好一定数量的对象放到对象池中。其实很多池化技术都属于这个范畴只是针对不同场景有其独特的叫法如MySQL的连接池、线程池等等。
4.4 栈内存的管理
通常我们只需要管理堆内存而栈内存交给操作系统来管理。但是栈内存的申请和初始化依旧是由程序员来控制的而操作系统只负责内存的分配和释放。考虑如下场景
void func()
{for (int i 0; i 999999; i) {char data[1000000];// do something}
}上述data在每一次循环都需要分配一次内存然后对其进行操作。如果data的创建可以放到循环体之外进行也不影响程序的正确性。那么data的内存分配只需要一次即可。 事实上我们还可以继续优化。因为这块内存很大函数也可能会被频繁调用每次调用都会重复申请一大块内存。所以考虑创建一个静态的data变量或者静态的全局变量。只要它能满足程序的正确性要求。何乐而不为呢当然静态变量在多线程环境下会存在数据竞争的问题。此时还可以考虑使用threadlocal变量。
五、减少函数调用
5.1 使用内联函数
一次函数调用涉及两次指令跳转。如果一个函数频繁调用可以使用内联机制来避免函数的调用。C11提供了inline关键字来告诉编译器被修饰的函数可以在调用处进行替换。一般这样的函数是一些功能简单代码行较少的函数。当然是否内联取决于编译器inline只是给编译器建议。是否内联可通过查看汇编代码来确认。
5.2 减少函数递归调用
函数递归通常写起来比较方便并且也更好理解。但是函数递归带来的开销是巨大的随着递归深度的加深性能也会受到影响。稍有不慎甚至会造成栈溢出。所以应该尽量避免使用递归函数考虑使用迭代或者只使用尾递归编译器优化只需要当前的栈帧空间无需开辟新空间的方式。
六、多线程处理
多线程可以利用多核特性同时处理多个任务从而提高程序性能。多线程常常涉及数据竞争的问题为了提高多线程的性能应减少数据竞争常见的方法有
使用原子变量。使用读写锁。降低锁的持有时间。使用线程池模型重复利用线程资源利用多队列减少工作线程间的数据竞争。使用无锁数据结构避免频繁的线程上下文切换。减少需要共享的状态。
七、编译器优化
在考虑性能问题之前首先得开启编译器优化很多时候代码虽然写的不是最优的但是在开启编译优化之后往往能达到很好的优化效果。常见的优化选项
O0不做任何优化。O1主要对代码的分支常量以及表达式等进行优化。O2会尝试更多的寄存器级的优化以及指令级的优化。O3在O2的基础上进行更多的函数内联优化因此目标代码会更大但执行速度会更快。
八、指令级优化
8.1 SIMD指令
SIMD单指令多数据指的是具有多个处理元件的计算机同时对多个数据执行相同操作的过程。以加法为例通常情况下我们需要先取操作数1再取操作数2然后求和。而SIMD指令则支持同时取多个操作数然后执行求和运算。也就是说取操作数的过程是并行的。在gcc中可以通过添加ftree-vectorize编译选项或者开启O2优化就可以让编译器使用SIMD优化代码。
九、提高缓存命中率
CPU有3级缓存L1、L2、L3其中L1离核心最近因此速度也最快。由于缓存有大小限制因此只有少量的数据和指令会被加载到缓存中所以经常会出现缓存无法命中的问题。因此提高cache命中率就可以提高程序性能。
9.1 选择合适的数据结构
数据结构多使用连续的存储如vector而少使用list、map这种非连续存储类型。因为连续的内存通常会被一起加载到缓存中。
9.2 内存对齐
内存不对齐的情况下cpu可能需要夸多个内存行去获取数据。从而增加了cpu的访存次数也增加了缓存不命中的可能性。
9.3 减少条件分支
程序中的条件判断如 if-else 语句可以通过逻辑重组或使用分支预测优化来提高缓存命中率。在某些情况下消除不必要的条件判断或将其重构为更高效的形式可以减少缓存行的加载和卸载从而提高性能。例如使用gcc的提供的关键字__builtin_expect来告诉编译器哪个分支命中的概率最高从而实现优化。
9.4 其他
避免频繁的内存分配与释放减少内存碎片。循环展开减少循环次数。循环中按行处理数据要比按列处理更高效。
