为什么要实现内存池?
一方面 是为了减少 调用 malloc() 的次数(尽管 malloc() 不慢) 但是调多了 会产生(外碎片)
另一方面 是因为 每次用 malloc() 分配到的内存 是要交税的 就是上一节中讲的 cookie 里面记录着 这一块内存的大小信息(内碎片) 特别是在频繁申请小内存的时候尤为明显
最终 pool_allocator 版本
具体代码可见 Memory_Pool
原理可见 C++ 内存管理 之 STL内存分配实现原理
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
#ifndef YY_ALLOCATOR_H
#define YY_ALLOCATOR_H
namespace YY {
static const int ALIGN = 8;
static const int MAX_BYTES = 128;
static const int FREE_LIST_NUMS = MAX_BYTES / ALIGN;
class Alloc {
public:
static void *allocate(size_t n) {
obj **my_free_list;
obj *result;
if (n > (size_t)MAX_BYTES) {
return ::operator new(n);
}
my_free_list = free_list + FREE_LIST_INDEX(n);
result = *my_free_list;
if (result == nullptr) {
void *r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result->next;
return result;
}
static void deallocate(void *p, size_t n) {
obj *q = (obj *)p;
obj **my_free_list;
if (n > (size_t)MAX_BYTES) {
return ::operator delete(p);
}
my_free_list = free_list + FREE_LIST_INDEX(n);
q->next = *my_free_list;
*my_free_list = q;
}
private:
union obj {
union obj *next;
};
private:
static char *start_free;
static char *end_free;
static size_t heap_size;
private:
static obj *free_list[FREE_LIST_NUMS];
static void *refill(size_t n);
static char *chunk_alloc(size_t n, int &blocks);
private:
static size_t FREE_LIST_INDEX(size_t bytes) {
return ((bytes + ALIGN - 1) / (ALIGN - 1));
}
static size_t ROUND_UP(size_t bytes) {
return ((bytes + ALIGN - 1) & ~(ALIGN - 1));
}
};
Alloc::obj *Alloc::free_list[FREE_LIST_NUMS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
char *Alloc::start_free = nullptr;
char *Alloc::end_free = nullptr;
size_t Alloc::heap_size = 0;
void *Alloc::refill(size_t n) {
int blocks = 20;
char *chunk = chunk_alloc(n, blocks);
obj **my_free_list;
obj *result;
obj *next_obj, *current_obj;
if (blocks == 1) {
return chunk;
}
my_free_list = free_list + FREE_LIST_INDEX(n);
result = (obj*)chunk;
*my_free_list = next_obj = (obj*)(chunk + n);
for (int i = 1; ; ++ i) {
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj + n);
if (blocks - 1 == i) {
current_obj->next = nullptr;
break;
} else {
current_obj->next = next_obj;
}
}
return result;
}
char *Alloc::chunk_alloc(size_t n, int &blocks) {
size_t bytes_left = end_free - start_free;
size_t total_bytes = n * blocks;
char *result;
if (bytes_left >= total_bytes) {
result = start_free;
start_free += total_bytes;
return result;
} else if (bytes_left >= n) {
blocks = bytes_left / n;
total_bytes = n * blocks;
result = start_free;
start_free += total_bytes;
return result;
} else {
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
if (bytes_left > 0) {
obj **my_free_list = free_list + FREE_LIST_INDEX(bytes_left);
((obj*)start_free)->next = *my_free_list;
*my_free_list = (obj*)start_free;
}
start_free = (char*)malloc(bytes_to_get);
if (start_free == nullptr) {
obj **my_free_list;
obj *p;
for (int i = n + ALIGN; i <= MAX_BYTES; i += ALIGN) {
my_free_list = free_list + FREE_LIST_INDEX(i);
p = *my_free_list;
if (p != nullptr) {
*my_free_list = p->next;
start_free = (char *) p;
end_free = (char *) p + i;
return chunk_alloc(n, blocks);
}
}
end_free = nullptr;
start_free = (char*)::operator new(bytes_to_get);
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return chunk_alloc(n, blocks);
}
}
}
#endif
|
内存管理迭代之一
最简陋的版本 简单的来说就是 一次获取 一大块内存 然后串成链表 每次要就返回其中一块
多用了一个指针 成员变量也就4个字节 一个指针多占用了 8 个字节
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
| class Screen {
public:
Screen(int x) : i(x) { };
void *operator new(size_t size) {
Screen *p;
if (!freeStore) {
size_t chunk = screenChunk * size;
freeStore = p = reinterpret_cast<Screen*> (new char[chunk]);
while (p != &freeStore[screenChunk - 1]) {
p->next = p + 1;
p ++;
}
p->next = nullptr;
}
p = freeStore;
freeStore = freeStore->next;
return p;
}
void operator delete(void* p, size_t) {
(static_cast<Screen*> (p))->next = freeStore;
freeStore = static_cast<Screen*> (p);
}
private:
Screen *next;
static Screen *freeStore;
static const int screenChunk;
private:
int i;
};
Screen *Screen::freeStore = nullptr;
const int Screen::screenChunk = 24;
|
内存管理迭代之二
上一个版本 最大的缺陷就是说 多占用了个指针 这对于只有 一个 int 的类来说 有点浪费
使用 union 将类 的 成员变量和链表指针包起来 节约内存
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
| class Airplane {
private:
struct AirplaneRep {
unsigned long miles;
char type;
};
private:
union {
Airplane *next;
AirplaneRep rep;
};
public:
void *operator new(size_t size) {
if (size != sizeof(Airplane)) {
return ::operator new(size);
}
Airplane *p = head;
if (p) {
head = p->next;
} else {
Airplane *newBlock = static_cast<Airplane*> (::operator new(BLOCK_SIZE * sizeof(Airplane)));
for (int i = 1; i < BLOCK_SIZE - 1; i ++) {
newBlock[i].next = &newBlock[i + 1];
}
newBlock[BLOCK_SIZE - 1].next = nullptr;
p = newBlock;
head = &newBlock[1];
}
return p;
}
void operator delete(void *p, size_t size) {
if(p == nullptr) {
return;
}
if (size != sizeof(Airplane)) {
::operator delete(p);
return;
}
Airplane *rp = static_cast<Airplane*> (p);
rp->next = head;
head = rp;
}
private:
static const int BLOCK_SIZE;
static Airplane *head;
};
Airplane *Airplane::head = nullptr;
const int Airplane::BLOCK_SIZE = 512;
|
内存管理迭代之三
静态版本
前面两个 必须要为不同的 classes 重写一个几乎相同的 member operator new 和 member operator delete
因此这个版本 将其抽取出来 放到一个 class 中
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
| class allocator {
private:
struct obj {
struct obj *next;
};
public:
void *allocate(size_t size) {
obj *p;
if (!freeStore) {
size_t chunk = CHUNK * size;
freeStore = p = (obj*)malloc(chunk);
for (int i = 0; i < CHUNK - 1; i ++) {
p->next = (obj*)((char*)p + size);
p = p->next;
}
p->next = nullptr;
}
p = freeStore;
freeStore = freeStore->next;
return p;
}
void deallocate(void *p, size_t) {
((obj*)p)->next = freeStore;
freeStore = (obj*)p;
}
public:
obj *freeStore = nullptr;
const int CHUNK = 5;
};
|