优化

Video Game Optimization——CPU Bound:内存

Posted ResetOTER

计算机通过时间和空间运行，指令代表时间、内存代表内存。

检测内存问题

内存获取问题大部分情况下都不可见。除非你查看汇编代码。

你可能获取的是寄存器、堆、栈、或者内存空间映射到另外一个bus。

数据有可能缓存在L1、L2、或者L3，有可能对齐也可能没有。

二分查找一般来说比线性查找要快，但是因为随机获取内存，所以在小的搜索上效率还不如线性查找。所以数据量的大小也决定了你的trade-off。

使用工具查看内存阻塞和cache miss

如果没有工具的话可以通过时间测量来猜测和检查具体的瓶颈点。举个例子，在循环当中只对数组的第一个进行操作，来确定是否有cache missing的影响。

解决方案

由于物理限制，制造商只能通过cache和预测技术来隐藏延迟，例如pre-fetch。

用于优化内存使用来影响cache的技术：

  • 降低运行时和编译时内存的footprint
  • 使用memory移动、fetch较少的算法
  • 通过物理局部化、适当的布局和正确的对齐
  • 增加时间连贯性
  • 利用pre-fetch
  • 避免糟糕的获取模式来打破cache

其中降低内存footprint和增大cache是一样的，减少cache不够用的情况。

减少memory移动和fetch对于应用优化来说也非常重要。这里在算法选择上进行trade off，是否需要选择效率更高但是memory fetch更频繁的算法。

Pre-Fetching

CPU会识别内存获取的模式提前将memory获取，来隐藏延迟。

大部分情况下硬件pre-fetching优于软件pre-fetching

在使用软件prefetching的时候要特别注意测试是否性能有提升，否则pre-fetch反而会是一种浪费。

如果你遇到cpu没有支持硬件pre-fetch或者一些极少数的情况下软件prefetch确实有很大作用。

访问模式和缓存

4种访问模式

  • 向前线性访问 linear access forward
for(int i = 0; i < numData; i ++) {
	memArray[i];
}
  • 向后线性访问 linear access backward
for(int i = numData-1; i >= 0; i --) {
	memArray[i];
}
  • 周期性访问 periodic access

使用一般的布局来访问struct随机变量

struct vertex
{
	float m_Pos[3];
	float m_Norm[3];
	float m_TexCoords[2];
};

for(int i = -; i < numData; i ++)
}
	vertexArray[i].m_Pos;
}
  • 随机访问 rendom access
float gSum = 0;
void Test()
{
	for(int i = 0; i < numData; i ++)
{
	gSum += vertexArray[RandI()];
}

他们的性能对比下来是这样的：

  1. 随机访问效率是最糟糕的
  2. 周期性访问在线性访问和随机访问之间，具体取决于布局的大小。情况最糟糕的时候周期性访问可能慢于随机访问。
  3. 线性访问则是最快的

申请大内存块对于线性移动来说很快，但是是有意义的，图形API对这个非常擅长。但是很难对所有的解决方案都使用大数组。申请和释放大数组是很消耗的，而且很多时候你需要对数组进行顺序转换。必须在实现中进行权衡。

以一种方法在固定申请和动态申请之间。其实就是使用Block，然后在数组变化的时候追加新的Block。

对于大块数据处理因为线性获取的好处性能有提升，但是也是需要权衡的。一些情况下线性访问并不是最好的。

随机访问可以显著降低你的性能。一个树状结构可以很容易地让你的性能下降。

在每个item上进行大量操作的时候你可以通过pre-fetch来隐藏乱序访问的消耗。当然你还是要自行考虑你的访问模式。

CPU做了大量的memory的工作，内存系统可以按照预期地fetch内存。当你线性向前或向后访问的时候硬件的prefetch可以最大程度高效地使用缓存工作。

随机性

随机性是否总是会导致更慢，这个主要取决于问题的尺寸。

如果你处理小尺寸的struct然后获取成员，你可能察觉不到区别。如果struct可以装进cacheline而且是对齐耳朵，那顺序不会有任何的性能影响。

如果是大的struct则影响会变大。

Randomness in fine granularity (from 0 to 512 bytes granularity) yields the best performance when randomness strides are very small.

流

目前只讨论了单个内存流。大部分CPU可以支持多条内存流。

高效的流数量很难概括，和处理器、芯片、操作系统等都有关系。

The number of arrays we are reading concurrently changes our performance. On this Intel Xeon, there is a significant penalty reading above eight streams. We traversed slightly less than 4MB, because parsing exactly 4MB causes a different cache penalty. The source for this chart is available in the perf Test Harness test ‘‘memory/stream/memorystream.’’

最好的方法是测量，从8到16条流之间。你内存获取的大小在稍微小于4M的地方、也就是稍微小于系统的内存页。

4核 3Ghs的Intel Xeon的CPU测试的时候8条流是性能最高的，之后性能会变得更糟糕。

在不同设备上需要自行测试。

AOS 和 SOA

内存布局是很关键的，一般有两种主要的方式：

array of structures (AOS).

接近线性访问

struct aos
{
	float m_Float1;
	float m_Float2;
	float m_Float3;
	float m_Float4;
};
aos myArray[256];

structure of arrays (SOA):

更接近于周期访问

struct soa
{
float m_Float1[256];
float m_Float2[256];
float m_Float3[256];
float m_Float4[256];
};
soa myArray;

了解AOS和SOA的方式帮助你提高多线程的性能。

The position of members for an array of structures as opposed to a structure of arrays.

解决方案：Strip Mining

通过Strip Mining你可以在遍历的时候采用分块的方式，每一块都去适应cache的大小。

保持时间连续性以及空间局部性

例如：

原本写的方式是这样的：

for( int i=0;i<numStructs:i++ )
{
	m_Vertex[i].pos = processPos(&m_Vertex[i].pos);
}
for( int i=0;i<numStructs:i++ )
{
	m_Vertex[i].normal = processNormal(&m_Vertex[i].normal);
}

修改之后需要按照BlockSize去进行遍历.

BlockSize需要根据不同的处理器来区分。

for( int j=0;j<numStructs;j+=blocksize)
{
	for( int i=j;i< blocksize;i++ )
	{
		m_Vertex[i].pos = processPos(&m_Vertex[i].pos);
	}
	for( int i=j;i<blocksize;i++ )
	{
		m_Vertex[i].normal = processNormal(&m_Vertex[i].normal);
	}
}

栈、全局、堆

通过new申请、添加function本地变量、添加static变量。

对于应用开发者可能没区别，但是底层实现的细微差别可以帮助优化。

栈

函数中的本地变量，因为存在栈上，空间局部性和时间连续性都很优秀。

栈空间有限，特别是递归代码，缩小栈使用可以提供更好的性能。

全局

全局内存作为你程序image的一部分被申请。是去除内存碎片的好办法。

全局内存基于连接器获取object的顺序来申请。因此，如果是申请非常频繁的对象可以选择放在同一个链接单元。

一个重要的警告：全局变量在多线程获取的时候性能会由于同步导致下降，一般称作伪共享。

堆

堆上分配，一般就是new和delete。时间久了之后会出现大量内存碎片，我们需要尽可能避免。

申请和释放内存非常消耗性能。内存管理可能会非常复杂，一般用内存池或者记录操作。有时候也会很耗。

动态内存的消耗不可避免，但是有很多策略可以避免消耗。

解决方案：不要申请

移除new操作符并且 只静态申请

解决方案：线性申请

以粒子系统为粒子，粒子系统当中有很多小的数据结构，动态申请导致两个严重后果：

  • 内存碎片化
  • 导致随机访问

如果你使用线性数组来保存那么会有两个好处

  • 申请活动次数降低。活动和非活动的数组分开，形成一个类似于池的结构。
  • 线性的访问让你的性能变得更好

数组大小变化很快的时候可能工作没这么好，比如爆炸的时候产生大量粒子，这个时候需要申请大量空间。爆炸结束之后粒子数量减少，多余的内存实际上是浪费的。

解决方案：内存池

内存池让你的内存哦更加连续，并且最大化性能。防止内存碎片的发生，减少内存申请导致的性能问题。

解决方案：不要构造和析构

POS 是没有构造和析构的数据结构。

当数组申请的时候构造会在每一个实例上进行。例如Mesh数据你必须等待上百万个数据初始化。

如果你避免了构造和析构你可以省很大一块时间。

解决方案：Time-Scoped Pools

定义好内存所需的范围可以在这上面下一些文章。

很多游戏实现了Level相关的池，生命周期只在当前关卡里面。这样离开关卡的时候可以直接抛弃整个池子。

另一个是基于帧的申请器。不断从栈上面申请帧。比如在函数开始的时候记录stack的位置。等函数结束的时候位置网上的内存可以直接抛弃，重置成0。不过这种申请方案可能有数据对齐的问题。

运行时性能

下面是一些实现上的经验：

别名

指针别名别名发生在两个指向同一个地址的指针。

有别名：

void foo(int *array,int *size,int *value) {
    for(int i=0;i<*size;++i) {
        array[i] = 2 * *value;
    }
}

无别名：

void foo(int *array,int size,int value) {
    for(int i=0;i<size;++i) {
        array[i] = 2 * value;
    }
}

stackoverflow上有这么一个回答：

https://stackoverflow.com/questions/9709261/what-is-aliasing-and-how-does-it-affect-performance

无别名的情况可以比有别名的情况要快30%左右。

运行时内存对齐

对齐的数据和未对齐数据中有细微的差别。

修复重点Stride问题

减少大的二次幂数组。大结构导致先前的缓存失效。

SSE加载和Pre-fetch

通过SSE可以实现SIMD等并行处理方法，工作得更快。

通过SSE还可以实现软件pre-fetching。

在使用软件pre-fetching的时候要特别进行测量。可以通过将获取模式改为线性来作为替代方案，来保证获取最大的硬件pre-fetch收益。

Write-Combined内存

通过Bus获取CPU内存是很大的问题。即使设备的带宽足够也是这样。例如更新vertex buffer，把数据回读会有明显的延迟。

所以Write-Combining实现了。

Write Combining

TODO..

总结

内存访问模式是应用程序性能中的一大块。学习trick可能会消耗大量时间，但是基础都是一样的：

  • 测量很重要
  • 你无法避免cache miss但是你可以降低它们
  • 不同处理器的内存系统都不一样，你需要确保你用户的硬件性能
  • 多做一些内存保存和线性访问的优化

最快的内存是从不申请内存。寻找缓存友好的算法。如果工作集足够小，实际上你不需要用到任何的这章提到的知识。

微海报分享

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注