首页 / C++ / C++ 内存角度的效率和性能优化

C++ 内存角度的效率和性能优化

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++ 内存角度的效率和性能优化，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1981字，纯文字阅读大概需要3分钟。

内容图文

算法保证效率，减少对数据结构的访问
数据结构优化性能

文章目录

一、减少内存访问次数

1. reserve减少分配内存次数

// 优化前:多次分配内存
std::vector<X> f(int n) {
	std::vector<X> result;
	for (int i = 0; i < n; ++i)
		result.push_back(X(...));
	return result;
}
// 优化后
std::vector<X> fun(int n){
	std::vector<X> result;
	result.reserve(n);              // 1.预先分配好内存，减少malloc
	for (int i = 0; i < n; ++i)
		result.push_back(X(...));   // 已经匹配 push_back(X&&)
	return result;
}

2. Hash Lookup与内存访问

// 优化前:内存访问频繁(Hash Lookup),极端情况每次访问遍历全部元素
X* getX(std::string key, std::unordered_map<std::string, 
									std::unique_ptr<x>> &cache){
	if (cache[key])
		return cache[key].get();
	cache[key] = std::make_unique<x>(...);
	return cache[key].get();
}
// 优化后:利用地址，访问一次
X* getX(std::string key, std::unordered_map<std::string, 
									std::unique_ptr<x>> &cache){
	std::unique_ptr<x> &entry = cache[key];
	if (entry)
		return entry .get();
	entry  = std::make_unique<x>(...);
	return entry .get();
}

二、使用连续存储数据类型

1.不要使用List (不连续的内存访问)

STD::List的特点

  • 正反遍历的链表
  • List 的每个节点单独分配内存
  • 每次指针访问跳转到新的内存地址，最坏情况每次都是cache miss
  • 仅在很少遍历List，但频繁更新的情况下使用

2. 使用Vector足够大部分情况

  • Vector就是很好的Stack
  • 始终增大Vector
  • Vector加index代替Queue

3. STD::MAP性能差

  • 二叉树链表存储的RBT，相比AVL，牺牲平衡减少重平衡次数。访存依然捉急。
  • 插入和删除会遍历二叉树。
  • 修改可能会导致re-balance
  • 有std::unordered_map

4.Hash表

STD::UNORDERED_MAP的尴尬:

  • 由多个buckets桶组成，每个桶可以放多个Key-Value.
  • 每个buckets之间的连接依然是链表，充满指针访问

好的Hash设计:

  • 无buckets，开放的连续地址
  • hash表连续存储
  • 使用local probe在cacheline中找到slot
  • Key和Value都不占地方 (比如用unique_ptr)

三、反直觉的算法

  • 冒泡排序很好(cache)在小数据集上几乎是最好的
  • cuckoo hash 保证O(1)的查询

内容总结

以上是互联网集市为您收集整理的C++ 内存角度的效率和性能优化全部内容，希望文章能够帮你解决C++ 内存角度的效率和性能优化所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/925091.html

来源：【匿名】