个人主页网站建设,网站制作多少钱资讯,网络服务模型,手机 写wordpress空间配置器#xff0c;听起来高大上#xff0c;那它到底是什么东西呢#xff1f; 1.什么是空间配置器#xff1f;
空间配置器是STL源码中实现的一个小灶#xff0c;用来应对STL容器频繁申请小块内存空间的问题。他算是一个小型的内存池#xff0c;以提升STL容器在空间申…空间配置器听起来高大上那它到底是什么东西呢 1.什么是空间配置器
空间配置器是STL源码中实现的一个小灶用来应对STL容器频繁申请小块内存空间的问题。他算是一个小型的内存池以提升STL容器在空间申请方面的效率 2.了解空间配置器
STL以128个字节为分界线将空间配置器分为了一级和二级
2.1 一级
一级空间配置器中allocate/deallocate函数实际上就是对malloc/free做了一个简单的封装
static void * allocate(size_t n)
{void *result malloc(n);if (0 result) result oom_malloc(n);return result;
}static void deallocate(void *p, size_t /* n */)
{free(p);
}//这个函数是malloc失败的时候才会调用的
template int inst
void * __malloc_alloc_templateinst::oom_malloc(size_t n)
{void (* my_malloc_handler)();void *result;for (;;) {my_malloc_handler __malloc_alloc_oom_handler;if (0 my_malloc_handler) { __THROW_BAD_ALLOC; }//抛异常(*my_malloc_handler)();result malloc(n);if (result) return(result);}
}当malloc失败的时候一级空间配置器会抛异常
2.2 二级
在二级空间配置器中会先判断带申请空间大小是否大于128个字节如果超过了则会去调用一级空间配置器
# ifndef __SUNPRO_CC
enum {__ALIGN 8};
enum {__MAX_BYTES 128};
enum {__NFREELISTS __MAX_BYTES/__ALIGN};
# endif
/* n must be 0 */
static void * allocate(size_t n)
{obj * __VOLATILE * my_free_list;obj * __RESTRICT result;if (n (size_t) __MAX_BYTES) {return(malloc_alloc::allocate(n));}my_free_list free_list FREELIST_INDEX(n);// Acquire the lock here with a constructor call.// This ensures that it is released in exit or during stack// unwinding.# ifndef _NOTHREADS/*REFERENCED*/lock lock_instance;# endifresult *my_free_list;if (result 0) {void *r refill(ROUND_UP(n));return r;}*my_free_list result - free_list_link;return (result);
};/* p may not be 0 */
static void deallocate(void *p, size_t n)
{obj *q (obj *)p;obj * __VOLATILE * my_free_list;if (n (size_t) __MAX_BYTES) {malloc_alloc::deallocate(p, n);return;}my_free_list free_list FREELIST_INDEX(n);// acquire lock# ifndef _NOTHREADS/*REFERENCED*/lock lock_instance;# endif /* _NOTHREADS */q - free_list_link *my_free_list;*my_free_list q;// lock is released here
}二级空间配置器中主要的几个成员变量如下
static obj * __VOLATILE free_list[__NFREELISTS]; //哈希桶
// Chunk allocation state.
static char *start_free;
static char *end_free;
static size_t heap_size;这里是一个内存池 一个哈希桶,内存池的长度为heap_size 哈希桶以8字节对齐分为了16个桶。最开始的时候free_list哈希桶是空的 当我们需要小于128个字节空间的时候以16字节为例二级空间配置器会直接去上面的内存池当中申请20个16字节的空间链接到16字节对应的哈希桶的位置1号桶
在下面的refill函数中可以看到这一点
template bool threads, int inst
void* __default_alloc_templatethreads, inst::refill(size_t n)
{int nobjs 20;//一次性申请20个char * chunk chunk_alloc(n, nobjs);obj * __VOLATILE * my_free_list;obj * result;obj * current_obj, * next_obj;int i;if (1 nobjs) return(chunk);my_free_list free_list FREELIST_INDEX(n);/* Build free list in chunk */result (obj *)chunk;*my_free_list next_obj (obj *)(chunk n);for (i 1; ; i) {current_obj next_obj;next_obj (obj *)((char *)next_obj n);if (nobjs - 1 i) {current_obj - free_list_link 0;break;} else {current_obj - free_list_link next_obj;}}return(result);
}8字节对齐的妙处
假设我们的list单个节点需要12个字节set单个字节需要16个字节
当list需要空间的时候二级空间配置器也会去申请16个字节的空间而不会去申请12个字节。这时候当list将用完的空间还回来之后就能拿过去给set用了
关于哈希桶的特殊处理
当我们用完了申请的空间准备“释放”的时候二级空间配置器会将释放回来的空间插入进哈希桶头插
这里有一个特殊处理当用完的空间或者说是刚申请的空间插入进哈希桶的时候二及空间配置器会将其强转为一个obj类型这个类型的前4/8个字节会用来存放一个指针指向下一个空间以此构成链表
union obj {union obj * free_list_link;char client_data[1]; /* The client sees this. */
};当我们再次需要这部分大小的空间的时候只需要将哈希桶头指针的指向直接修改就能链接上下一个空间并将之前头指针指向的空间拿去用
用的时候也不用管之前在此处存放的指针毕竟下一次放回来的时候二级空间配置器会来处理它的 内存池空间不够用了咋办
之前提到了二级空间配置器里面有一个小内存池。要是这个内存池用完了要咋整呢
二级空间配置器想出来了一种很骚的做法
假设当前我们需要24字节的空间对应的桶下面没有空间给我们用内存池也用光了但是48字节的桶下面还有空间可以用直接把这个空间拿过来拆成两个24链接到24的桶下面
这样便有效提高了空间利用率也避免了realloc造成的时间消耗。
当然要是桶里面也没有多余空间了那就只能老老实实去扩容了 只能大的拆小的小的空间不连续无法组成大的 //二级空间配置器里面的reallocate封装
template bool threads, int inst
void*
__default_alloc_templatethreads, inst::reallocate(void *p,size_t old_sz,size_t new_sz)
{void * result;size_t copy_sz;if (old_sz (size_t) __MAX_BYTES new_sz (size_t) __MAX_BYTES) {return(realloc(p, new_sz));}if (ROUND_UP(old_sz) ROUND_UP(new_sz)) return(p);result allocate(new_sz);copy_sz new_sz old_sz? old_sz : new_sz;memcpy(result, p, copy_sz);deallocate(p, old_sz);return(result);
}2.3 关于单例的说明
在同一个进程里面空间配置器只会有一个
但STL库中的空间配置器并没有把自己设计成单例类而是用了一个间接的做法
static obj * __VOLATILE free_list[__NFREELISTS]; //哈希桶
// Chunk allocation state.
static char *start_free;
static char *end_free;
static size_t heap_size;那就是所有成员变量都是static静态的
我们知道在类和对象中静态成员变量是属于整个类的所以它也是一种单例模式 2.4 空间配置器的优点
空间配置器的时间复杂度是O(1)申请空间的效率很高空间配置器能解决频繁申请空间导致的内存碎片问题
当我们使用STL容器频繁申请小块空间比如list就容易导致堆区中有非常多的小块空间被使用而无法申请一个大的空间
空间配置器提前申请了一个大块空间再私下管理可以有效解决这个问题
内存外碎片/内碎片
外碎片多次申请小块空间造成。有足够内存但是不连续无法申请大块内存内碎片list只需要12个字节而空间配置器因为内存对齐而给了它16个字节浪费了4个字节造成的内存碎片
3.容器和空间配置器
之前学习stl容器的时候就在定义中看到过这里的alloc默认模板参数 这里默认传的便是stl库中的二级空间配置器 只要你自己写的空间配置器符合stl的接口需求你便可以将自己的空间配置器传入此处让容器使用 typedef __default_alloc_template__NODE_ALLOCATOR_THREADS, 0 alloc;
typedef __default_alloc_templatefalse, 0 single_client_alloc;在list中alloc又被封装了一层用来处理节点申请的问题
template class T, class Alloc alloc
class list {
protected:typedef void* void_pointer;typedef __list_nodeT list_node;typedef simple_alloclist_node, Alloc list_node_allocator;templateclass T, class Alloc
class simple_alloc {public:static T *allocate(size_t n){ return 0 n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }static T *allocate(void){ return (T*) Alloc::allocate(sizeof (T)); }static void deallocate(T *p, size_t n){ if (0 ! n) Alloc::deallocate(p, n * sizeof (T)); }static void deallocate(T *p){ Alloc::deallocate(p, sizeof (T)); }
};随后当创建节点、销毁节点的时候list就会调用封装好的simple_alloc来处理空间
link_type get_node() { return list_node_allocator::allocate(); }
void put_node(link_type p) { list_node_allocator::deallocate(p); }
link_type create_node(const T x) {link_type p get_node();__STL_TRY {construct(p-data, x);//调用节点的构造函数}__STL_UNWIND(put_node(p));return p;}void destroy_node(link_type p) {destroy(p-data);//调用节点的析构函数put_node(p);}construct通过定位new显式调用节点的构造函数destroy通过指针来调用析构函数
template class T
inline void destroy(T* pointer) {pointer-~T();
}template class T1, class T2
inline void construct(T1* p, const T2 value) {new (p) T1(value);
}在stl_tree.h中可以看到库里面的红黑树也对空间配置器进行了类似的封装
template class Key, class Value, class KeyOfValue, class Compare,class Alloc alloc
class rb_tree {
protected:typedef void* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_nodeValue rb_tree_node;typedef simple_allocrb_tree_node, Alloc rb_tree_node_allocator;typedef __rb_tree_color_type color_type;结语
关于空间配置器的内容了解这些就差不多啦
其实就是通过库里面的这个设计来了解一个提高小空间内存申请效率的方法感觉还是很666的 有啥问题可以在评论提出哦
