内存对程序效率的影响很大。即使是好的算法,用了不正确的内存分配,仍然会有效率问题。

内存对效能的影响有两方面:

  1. 动态内存分配(dynamic memory allocation)非常慢。它慢主要有两个原因。首先,堆分配器必须处理任何大小的分配请求;其次,在多数操作系统上,malloc()/free()必然会从用户模式(user mode)切换至(kernel mode),处理请求,再切换回来,这种上下文切换(context-switch)会非常耗时。
  2. 软件访问效能受其内存访问模式(memory access patter)主宰。数据置于连续内存块,比起置于广阔内存地址要更高效(cache等原因)。

  因此,游戏开发中一个常见的经验法则是:维持最低限度的堆分配,并且永不在紧凑循环中使用堆分配。

  我们可以不使用操作系统提供的分配器,而根据具体情况,使用自定义的分配器。多数游戏引擎会实现一个或多个定制分配器(custom allocator)。他比操作系统分配器更优的原因有二:

  1. 定制分配器从预分配的内存中完成分配请求。这样就不需要进行上下文切换。
  2. 通过对定制分配器的使用模式做出多个假设,定制分配器便可以比通用的堆分配器高效。

几种常见的定制分配器:

池分配器(pool allocator)

  主要用于分配内存大小固定的情况。
  池分配器的工作方式如下。首先,池分配器会预分配一大块内存,其大小刚好是分配元素的倍数。池内每个元素会加到一个存放自由元素的链表。池分配器收到分配请求时,就会把自由链表的下一个元素取出,并传回该元素。释放元素之时,只需简单地把元素插回自由链表中。

  注意!储存自由元素的链表可以实现为单链。但是这样就要花费额外空间来存储链表的指针。意识到,自由列表内的内存块,按定义来说就是可用的内存。那为什么不用这些内存本身来储存自由列表的“next”指针呢?只要元素尺寸≧sizeof(void*),就可以使用这个小诀窍了。

  若元素尺寸小余指针,则可以使用池元素的索引代替指针去实现链表。例如元素大小为16位,那么池里元素个数不超过2^16即可。(因为自由列表的内存是连续的,用索引可以算出其地址)。

具体实现

先看头文件的申明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// freelist.h
class Freelist
{
public:
Freelist* m_next;
};
class FreelistHead: private Freelist {
public:
FreelistHead(int num, size_t elementSize);
~FreelistHead();
inline void* Obtain(void);
inline void Return(void* ptr);
private:
void * m_start;
};

  Freelist类是链表的每个结点。FreelistHead类是链表的头结点,也代表了内存分配器。

测试代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//main.cpp
int main() {
FreelistHead freelist(2, 64); // elementsize >= sizeof(void*)
void* object0 = freelist.Obtain();
cout<<object0<<endl;
void* object1 = freelist.Obtain();
cout<<object1<<endl;
// obtained slots can be returned in any order
freelist.Return(object1);
freelist.Return(object0);
return 0;
}

类成员函数的具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//freelist.cpp
FreelistHead::FreelistHead(int num, size_t elementSize) {
union element {
void* as_void;
char* as_char;
Freelist* as_self;
}start, end, now, nxt;
unsigned long step = elementSize/8;
start.as_void = malloc(num*elementSize);
end.as_char = start.as_char + (num*step);
m_start = start.as_void;
// initialize the free list - make every m_next of each element point to the next element in the list
m_next = start.as_self;
for (now=start, nxt.as_char = start.as_char + step;
nxt.as_char < end.as_char;
now=nxt, nxt.as_char = nxt.as_char + step) {
now.as_self->m_next = nxt.as_self;
}
now.as_self->m_next = nullptr;
}
FreelistHead::~FreelistHead() {
free(m_start);
}
inline void* FreelistHead::Obtain(void)
{
// is there an entry left?
if (m_next == nullptr)
{
// we are out of entries
return nullptr;
}
// obtain one element from the head of the free list
Freelist* head = m_next;
m_next = head->m_next;
return head;
}
inline void FreelistHead::Return(void* ptr)
{
// put the returned element at the head of the free list
Freelist* head = static_cast<Freelist*>(ptr);
head->m_next = m_next;
m_next = head;
}

含对齐(alignment)功能的分配器

  所有内存分配器都必须能传回对齐的内存块。要实现这个功能十分容易。只要在分配内存时,分配比请求所需多一点的内存,再向上调整其内存地址至适当的对齐,最后传回调整后的地址。由于我们分配了多一点的内存,即使把地址往上调整,传回的内存块仍够大。在多数情况下,额外分配的字节等于对齐字节。
  
  计算调整偏移量的方法如下。首先用掩码(mask)把原本内存块地址的最低有效位取出,再把期望的对齐减去此值,结果就是调整偏移量。对齐应该总是2的幂,因此要算掩码,只要把对齐减1就行了。例如,若请求16字节对齐的内存块,掩码就是$(16-1) = 15 = \rm 0x0000000F$。把未对齐的地址与掩码进行位并(bitwise AND)操作,就可得到错位(misalignment)的字节数目。例如,如果原来分配到的内存块地址为$\rm 0x50341233$,位并掩码$\rm 0x0000000F$后,得出$\rm 0x00000003$。要把这个地址对齐,只要加上$(对齐字节-错位字节)=(16-3)=13=\rm 0xD$。因此,最终对齐地址为$\rm 0x50341233+\rm 0xD = \rm 0x50341240$。
  
  但还有一个问题,关于内存的回收。申请内存时,分配函数传回了一个对齐的地址,但是实际上,这一次分配还占用了更低地址的内存(由于没对齐的缘故,被浪费了)。回收的时候怎么知道应该从哪个地址开始回收呢?注意到,用上面的方法,偏移量是大于1的,也就是说对齐地址的前一个地址一定是可用的,我们可以把偏移量记录在对齐地址的前一个字节。这样在回收的时候,就能找到正确的地址。
  
代码如下(参考自《游戏引擎架构》):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdint>
typedef unsigned int U32;
typedef std::uint8_t U8;
void * allocateAligned(U32 size_bytes, U32 alignment) {
// 计算总共要分配的内存量
U32 expandedSize_bytes = size_bytes + alignment;
// 分配未对齐的内存块,并转换为int类型
U32 rawAddress = (U32)allocateUnaligned(expandedSize_bytes);
// 使用掩码去除地址低位部分,计算“错位”量,从而计算整量
U32 mask = (alignment - 1);
U32 misalignment = (rawAddress & mask);
U32 adjustment = alignment - misalignment;
// 计算调整后的地址,并把它以指针类型返回
U32 alignedAddress = rawAddress + adjustment;
// 把alignment储存在调整后地址的前4字节
U32* pAdjustment = (U32*)(alignedAddress - 1);
// 原书中代码为:U32* pAdjustment = (U32*)(alignedAddress - 4);
// 但是按书中描述,我觉得不符
*pAdjustment = adjustment;
return (void*)alignedAddress;
}
void freeAligned(void* p) {
U32 alignedAddress = (U32)p;
U8* pAdjustment = (U8*)(alignedAddress - 1);
U32 adjustment = (U32)*pAdjustment;
U32 rawAddress = alignedAddress - adjustment;
freeUnaligend((void*)rawAddress);
}

参考资料:

  1. 《游戏引擎架构》
  2. 《Memory allocation strategies: a pool allocator》