【C++内存管理】17_G4.9 的七个分配器
标准库规定，分配器最顶层在 《...\memory》 头文件下new_allocator new_allocator 的 allocate 直接调用的
::operator new ，deallocate 直接调用 ::operator delete
文章图片
malloc_allocator malloc_allocator 的 allocate 直接调用的
malloc，deallocate 直接调用 free。
文章图片
array_allocator
tr1 (Technical Report 1) 不是正式的库只是一个草案，作为C++ 2003标准的附加库被大多数编译器厂商所支持，它是个过渡性质的库，其实现将会作为C++11标准的一部分。
到 C++2011 时，其部分内容被正式包含到标准库，在使用方式上仍然保留 std::tr1，例如 std::tr1::array 可用 std::array 替代。
文章图片
在构造函数中需要传入一个指针，这个指针可以指向静态分配的数组，也可以指向动态分配的数组，所以说内存分配不是在array_allocator中进行的，array_allocator 只是对分配好的内存进行管理（因此 deallocate 什么都没做）。
array_allocator 并不会"回收"(指重新被array_allocator管理)已给出的内存空间，因此很少被使用
动态内存分配的方式使用
文章图片
静态内存分配的方式使用
文章图片
debug_allocator
文章图片
包裹另一个分配器，使用至少一个元素大小的空间，用于记录整个区块大小（子元素数量）（是不是相等于另一种 cookie? 但 allocator 的主要用途是减少 cookie，因此很少被使用）pool_allocator G2.9 容器使用的分配器不是 std::allocator 而是 std::alloc (缺点，只申请不归还)
文章图片
G4.9 中的进化
G4.9 标准库中有许多 extented allocators， 其中 __pool_alloc 就是 G2.9 的化身
文章图片
文章图片
#include #include
#include //內含 std::allocator
#include //欲使用 std::allocator 以外的 allocator, 就得自行 #include
#include
#include
#include
#include
#include
#include
#include //這其實已被 included, 它就是 std:allocator 的 base class
#include
#include
#include
#include using namespace std;
template
void cookie_test(Alloc alloc, size_t n)
{
typename Alloc::value_type *p1, *p2, *p3;
//需有 typename
p1 = alloc.allocate(n);
//allocate() and deallocate() 是 non-static, 需以 object 呼叫之.
p2 = alloc.allocate(n);
p3 = alloc.allocate(n);
cout << "p1= " << p1 << '\t' << "p2= " << p2 << '\t' << "p3= " << p3 << '\n';
alloc.deallocate(p1,sizeof(typename Alloc::value_type));
//需有 typename
alloc.deallocate(p2,sizeof(typename Alloc::value_type));
//有些 allocator 對於 2nd argument 的值無所謂
alloc.deallocate(p3,sizeof(typename Alloc::value_type));
}int main()
{
//從語法上試用各式各樣的 allocators
cout << sizeof(std::allocator) << endl;
//1
cout << sizeof(__gnu_cxx::new_allocator) << endl;
//1.
//觀察 STL source 可知: new_allocator 是 std::allocator 的 base
//我們無法改變 std::allocator 的 base class, 那該如何使用其他的 GNU allocators ?
//是否要寫個 custom_allocator (像上面) 並為它加上我想要的 base (例如 __pool_alloc) ?
//不，不必，就直接使用, 但需自行 #include cout << sizeof(__gnu_cxx::malloc_allocator) << endl;
//1. 大小 1者其實為 0, fields 都是 static.
cout << sizeof(__gnu_cxx::__pool_alloc) << endl;
//1
cout << sizeof(__gnu_cxx::__mt_alloc) << endl;
//1
cout << sizeof(__gnu_cxx::bitmap_allocator) << endl;
//1
cout << sizeof(__gnu_cxx::array_allocator) << endl;
//8 ==> 因為它有一個 ptr 指向 array 和一個 size_t 表示消耗到 array 哪兒
cout << sizeof(__gnu_cxx::debug_allocator>) << endl;
//8
//!cout << sizeof(__gnu_cxx::throw_allocator) << endl;
//只有 throw_allocator_base, throw_allocator_random, throw_allocator_limit, 沒有 throw_allocator !!cout << endl;
//搭配容器
list > list_malloc;
deque > deque_debug;
vector> vector_pool;
//! vector> vector_pool;
//如果沒加上 namespace : [Error] '__pool_alloc' was not declared in this scopecookie_test(std::allocator(), 1);
//相距 10h (表示帶 cookie)
cookie_test(__gnu_cxx::malloc_allocator(), 1);
//相距 10h (表示帶 cookie)
cookie_test(__gnu_cxx::__pool_alloc(), 1);
//相距 08h (表示不帶 cookie)//以下將 int 改為 double 結果不變，意味上述 ints 間隔 8 (而非 4) 乃是因為 alignment.
cookie_test(std::allocator(), 1);
//相距 10h (表示帶 cookie)
cookie_test(__gnu_cxx::malloc_allocator(), 1);
//相距 10h (表示帶 cookie)
cookie_test(__gnu_cxx::__pool_alloc(), 1);
//相距 08h (表示不帶 cookie)cout << endl;
try {
//示範使用 array_allocator: 須先 new an array, 將其 ptr 設給 array_allocator, 最後還要 delete array
std::tr1::array* arrayTR1 = new std::tr1::array;
//使用 tr1::array
cookie_test(__gnu_cxx::array_allocator>(arrayTR1), 1);
//相距 08h (表示不帶 cookie)
delete arrayTR1;
array* arraySTD = new array;
//使用 std::array
cookie_test(__gnu_cxx::array_allocator>(arraySTD), 1);
//相距 08h (表示不帶 cookie)
delete arraySTD;
std::tr1::array* p = new std::tr1::array;
//為搭配下一行 "default 2nd argument 是 std::tr1::array" (見 source), 我們需要做一個來.
cookie_test(__gnu_cxx::array_allocator(p), 1);
//未指明 2nd argument, 所以使用 default, 即 std::tr1::array
//bad allocation! 因為 cookie_test() 需 3 doubles 而
// 本處所用之 array_allocator 卻只能提供 1 double。
delete p;
}
catch(...)
{
cout << "bad allocation! \n";
}return 0;
}
输出：
1
1
1
1
1
1
8
8p1= 0xe91630p2= 0xe98328p3= 0xe98338
p1= 0xe91630p2= 0xe98328p3= 0xe98338
p1= 0xe98368p2= 0xe98370p3= 0xe98378
p1= 0xe91630p2= 0xe984b0p3= 0xe984c0
p1= 0xe91630p2= 0xe984b0p3= 0xe984c0
p1= 0xe98380p2= 0xe98388p3= 0xe98390p1= 0xe984b0p2= 0xe984b8p3= 0xe984c0
p1= 0xe984b0p2= 0xe984b8p3= 0xe984c0
bad allocation! bitmap_allocator
<.../ext/bitmap_allocator.h> 文件中template
class bitmap_allocator : private free_list {// 此处学习可不考虑 free_list
......
public:
pointer allocate(size_type __n) {
if (__n > this->max_size())
std::__throw_bad_alloc();
if (__builtin_expect(__b == 1, true))
return this->_M_allocate_single_object();
// 一次仅供应一个给客户！（因为主要被容器所使用，而容器一次申请只一个对象）
else {// 当直接使用 bitmap_allocator 时可能会走向这里
const size_type __b = __n * sizeof(value_type);
return reinterpret_cast(::operator new(__b));
}
}void deallocate(pointer __p, size_type __n) throw() {
if (__builtin_expect(__p != 0, true)) {
if (__builtin_expect(__n == 1, true))
this->_M_deallocate_single_object(__p);
else
::operator delete(__p);
}
}
};
关于 blocks，super-blocks, bitmap, mini-vector
文章图片
- block, 客户申请的一个节点，最小 8 字节，大小 8 的倍数增长（8, 16, 32 ...）
- super-blocks, 由 use-count + bitmap + blocks 组成[一次申请一大块，减少 cookie 使用，每次 2 倍增长]
- use-count, 已分配出的 blocks 数量
- bitmap, unsigned int 为单位（32bit）, 反方向标记对应 blocks 是否空闲 （1 空闲， 0 已分配出去）
- __mini_vector, 一个小的 vector 实现, 管理使用中的 super-blocks （每次 2 倍增长）
文章图片
1. use-count + 1 = 0 + 1 = 1
2. bitmap 修改为 0xFFFFFFFF FFFFFFFE第 2 次内存分配
文章图片
1. use-count + 1 = 1 + 1 = 2
2. bitmap 修改为 0xFFFFFFFF FFFFFFFC第 63 次内存分配 【【C++内存管理】17_G4.9 的七个分配器】
文章图片
1. use-count + 1 = 62 + 1 = 63
2. bitmap 修改为 0x10000000 00000000第 1 次内存归还
文章图片
1. use-count - 1 = 63 - 1 = 62
2. bitmap 修改为 0x10100000 000000001st super-block 用完，启动 2nd super-block
文章图片
2nd super-block 用完，启动 3nd super-block
文章图片
1st super-block 全回收
文章图片
问题1：如果 1st super-block 回收 2 blocks, 而尚未全回收，接下来分配 2 blocks, bitmap_allocator 会从 #0 super-block 取出亦或从 #2 super-block 取出?（假设 #0， #1， #2 block-size 一样大）
答：后者（其实都可以）
问题2：如果接下来把 #2 super-block 用光，然后分配 2 blocks, bitmap_allocator 会从 #0 super-block 取出亦或新建一个 #3 super-block 并从中取出（假设 #0， #1， #2 block-size 一样大）？
答：前者
2nd super-block 全回收
文章图片
3rd super-block 全回收
文章图片
问题：接下来分配 1 block， 如何处理？此时 _S_mem_blocks 为空而 _S_free_list 有三个 super-blicks, 于是取一个放进 _S_mem_blocks， 然后遵循先前法则完成分配
#include #include //欲使用 std::allocator 以外的 allocator, 就得自行 #include using namespace std;
int main()
{
cout << "\ntest_bitmap_allocators().......\n";
__gnu_cxx::bitmap_allocator alloc;
//形成一個 static __mini_vector, size=0
__gnu_cxx::bitmap_allocator::value_type* p[1000];
// __gnu_cxx::bitmap_allocator::value_type* ptr;
for (int i=0;
i<448;
++i) {
p[i] = alloc.allocate(1);
cout << "p[" << i << "]" << p[i] << endl;
}
} G4.9 分配器的使用
pool_allocator 和 bitmap_allocator 是最精巧的分配器，不仅减少了 cookies 的使用，同时更有速度优势(bitmap_allocator 还可归还os内存)
#include
#include
#include
#include // abort
#include // snprintf()
#include// find
#include
#include #include
#include // 内含 std::allocator// 欲使用 std::allocator 以外的 allocator, 得自行 #include
#include
#include
#include
#include
#include
#include
#include using namespace std;
void test_list_with_special_allocator(int choice, long value)
{
cout << "test_list_with_special_allocator() ......"<< endl;
cout << "choice: " << choice << " value: " << value << endl;
list> c1;
list> c2;
list> c3;
list> c4;
list> c5;
list> c6;
char buf[10];
clock_t timeStart = clock();
for (int i=0;
i alloc1;
p = alloc1.allocate(1);
alloc1.deallocate(p, 1);
__gnu_cxx::malloc_allocator alloc2;
p = alloc2.allocate(1);
alloc2.deallocate(p, 1);
__gnu_cxx::new_allocator alloc3;
p = alloc3.allocate(1);
alloc3.deallocate(p, 1);
__gnu_cxx::__pool_alloc alloc4;
p = alloc4.allocate(2);
alloc4.deallocate(p, 2);
__gnu_cxx::__mt_alloc alloc5;
p = alloc5.allocate(1);
alloc5.deallocate(p, 1);
__gnu_cxx::bitmap_allocator alloc6;
p = alloc6.allocate(3);
alloc6.deallocate(p, 3);
}int main()
{
test_list_with_special_allocator(1, 600000);
test_list_with_special_allocator(2, 600000);
test_list_with_special_allocator(3, 600000);
test_list_with_special_allocator(4, 600000);
test_list_with_special_allocator(5, 600000);
test_list_with_special_allocator(6, 600000);
return 0;
}
输出：
test_list_with_special_allocator() ......
choice: 1 value: 600000
a lot of push_back(), milli-seconds : 105
test_list_with_special_allocator() ......
choice: 2 value: 600000
a lot of push_back(), milli-seconds : 101
test_list_with_special_allocator() ......
choice: 3 value: 600000
a lot of push_back(), milli-seconds : 107
test_list_with_special_allocator() ......
choice: 4 value: 600000
a lot of push_back(), milli-seconds : 80
test_list_with_special_allocator() ......
choice: 5 value: 600000
a lot of push_back(), milli-seconds : 85
test_list_with_special_allocator() ......
choice: 6 value: 600000
a lot of push_back(), milli-seconds : 76推荐阅读
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘