网站建设技术员,深圳招聘网站排行,wordpress 无法将上传,网站排名 各因素文章目录 1、什么是空间配置器#xff1f;1.1设计一个简单的空间配置器#xff0c;JJ::allocator 2、具备次配置力( sub-allocation)的 SGI 空间配置器2.1 什么是次配置力2.2 SGI标准的空间配置器#xff0c;std::allocator2.2 SGI特殊的空间配置器#xff0c;std::alloc2.… 文章目录 1、什么是空间配置器1.1设计一个简单的空间配置器JJ::allocator 2、具备次配置力( sub-allocation)的 SGI 空间配置器2.1 什么是次配置力2.2 SGI标准的空间配置器std::allocator2.2 SGI特殊的空间配置器std::alloc2.3 构造和析构的基本工具construct()和destroy()补充2.3.1、什么是 **trivial destruct:**2.3.2、从__destroy_aux来看他的销毁范围是[first,last),为什么没有销毁最后一个 2.4 空间的配置和释放std::alloc2.5 第一级配置器 __malloc_alloc_template剖析2.6 第二级配置器 __default_alloc_template剖析2.6.2 自由链表自由在哪?又该如何维护呢?2.6.3 第二级配置器的部分实现内容 2.7空间配置函数allocate()2.7.1空间配置函数allocate()实现原理2.7.2空间配置函数allocate()代码实现 2.8 空间释放函数 deallocate()2.8.1空间释放函数 deallocate()实现原理2.8.2空间释放函数 deallocate()代码实现 2.9 重新填充 free lists2.9.1重新填充 free lists()实现原理2.9.2重新填充 free lists()代码实现 2.10 内存池 memory pool2.10.1内存池 memory pool实现原理2.10.2内存池 memory pool代码实现 3、内存 基本处理工具3.1 uninitialized_copy3.2 uninitialized_fill3.3 uninitialized_fill_n 4、总结5、参考 1、什么是空间配置器
空间配置器是STL标准模板库中的一个重要组件它的主要作用是高效管理各个容器的空间包括空间的申请与回收。在程序运行时内存可能存在于栈上由系统自动分配或堆上由用户自行申请。如果用户频繁地申请和释放空间而不加以管理可能会导致内存碎片从而影响内存使用效率并降低程序效率。为了解决这些问题STL库提供了空间配置器其原理类似于利用内存池来提高效率。
1.1设计一个简单的空间配置器JJ::allocator
jjalloc.h
#include jjalloc.h
#include vector
#include iostream
using namespace std;
int main(){int ia[5] {0,1,2,3,4};unsigned int i;vectorint,JJ::allocatorint iv(ia,ia5);for(i 0;i iv.size();i){cout iv[i] ;}cout endl;
}jjalloc.cpp
#ifndef _JJALLOC_
#define _JJALLOC_#include new
#include cstddef
#include cstdlib
#include iostream
#include climits
using namespace std;namespace JJ {
//分配内存空间来存储指定类型的对象
template class T
inline T* _allocate(ptrdiff_t size,T*){//禁用新的处理器set_new_handler(0); //调用全局的operator new来分配内存T* tmp (T*)(::operator new ((size_t)(size * sizeof(T))));if(tmp 0){std::cerr out of memory endl;exit(1);}return tmp;
}//处理动态分配的内存的释放
template class T
inline void _deallocate(T* buffer){::operator delete(buffer);
}//在已分配但尚未构造的内存中构造一个对象。
//它接受两个参数
//一个指向 T1 类型对象的指针 p
//一个 T2 类型的常量引用 value
template class T1,class T2
inline void _construct(T1*p ,const T2 value){new(p) T1(value);
}//显式调用对象的析构函数来销毁对象但不释放内存。
//它接受一个指向 T 类型对象的指针 ptr并调用该对象的析构函数。
template class T
inline void _destroy(T* ptr){ptr-~T();
}
//定义allocator的模板类
template class T
class allocator{
public://定义类型别名typedef T value_type;typedef T* pointer;typedef const T* const_pointer;typedef T reference;typedef const T const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type;//从一个类型的分配器“重新绑定”到另一个类型的分配器templateclass Ustruct rebind{typedef allocatorU other;};// 用于分配内存来存储 n 个 value_type 类型的对象。// 它调用之前定义的 _allocate 函数来执行实际的内存分配// 并将返回的内存地址转换为正确的指针类型。pointer allocate(size_type n,const void* hint 0){return _allocate((difference_type)n,(pointer)0);}// 用于释放之前通过 allocate 函数分配的内存。//它调用 _deallocate 函数来执行实际的内存释放void deallocate(pointer p,size_type n){_deallocate(p);}//在已分配但尚未构造的内存中构造一个对象。//它调用 _construct 函数void construct(pointer p,const T value){_construct(p,value);}//显式调用对象的析构函数以销毁对象但不释放内存。//它调用 _destroy 函数来执行此操作void destroy(pointer p){_destroy(p);}//返回对象的地址pointer address(reference x){return (pointer) x;}//返回常量对象的地址const_pointer const_address(const_reference x){return (const_pointer) x;}//返回分配器可以分配的最大对象数size_type max_size() const{return size_type(UINT_MAX/sizeof(T));}
};// end of allocator } //end of namespce JJ#endif //_JJALLOC_2、具备次配置力( sub-allocation)的 SGI 空间配置器
2.1 什么是次配置力
“次配置力”sub-allocator这个概念不是C标准中的术语但在某些上下文中特别是在讨论更复杂的内存管理策略时可能会使用这个概念。次配置器通常指的是用于管理较小内存块或特定类型对象的配置器。在复杂的内存管理系统中你可能会有一个主配置器用于处理大块内存分配和多个次配置器用于处理不同类型的对象或更小的内存块。 次配置器的使用可以提高内存管理的效率因为它们可以针对特定类型的对象或特定大小的内存块进行优化。例如一个次配置器可能使用内存池技术来快速分配和回收小块内存而另一个次配置器可能使用特定的对齐策略来优化特定类型对象的存储。
2.2 SGI标准的空间配置器std::allocator
虽然 SGI 也配置了 allocatalor但是它自己并不使用也不建议我们使用原因是效率比较 感人因为它只是在基层进行配置/释放空间而已而且不接受任何参数。 看一下std::allocator的代码示例
#ifndef DEFALLOC_H
#define DEFALLOC_H#include new.h
#include stddef.h
#include stdlib.h
#include limits.h
#include iostream.h
#include algobase.h
template class T
inline T* allocate(ptrdiff_t size,T*){set_new_handler(0);T* tmp (T*)(::operator new((size_t)(size*(sizeof(T))));if(tmp 0){cerrout of memoryendl;exit(1);}return tmp;
}
template class T
inline void deallocate(T* buffer){::operator delete(buffer);
}
template class T
class allocator{
public:typedef T value_type;typedef T* pointer;typedef const T* const_pointer;typedef T reference;typedef const T const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type; pointer allocate(size_type n){return ::allocate((difference_type)n,(pointer)0);}void deallocate(pointer p){::deallocate(p);}pointer address(reference x){return (pointer)x;}const_pointer const_address(const_refernce x){return (const_pointer)x;}//确定一个“页面”或“块”的大小size_type int_page_size(){return max(size_type(1),size_type(4096/sizeof(T)));}size_type max_size() const{return max(size_type(1),size_type(UINT_MAX/sizeof(T)));}
};
class allocatorvoid{
public:typedef void* pointer;
}
#endif //DEFALLOC_H从源码可以看到allocator只是基层内存配置/释放行为的简单包装在效率上没有任何的提升。
2.2 SGI特殊的空间配置器std::alloc
一般而言对C内存配置操作和释放操作
class Foo{...};
Foo* pf new Foo; //配置内存然后构造对象
delete pf; //将对象析构然后释放内存为了精密分工STL allocator决定将这两阶段的操作区分开来 内存配置操作由alloc:allocate()负责内存释放操作由alloc:deallocate()负责 对象构造操作由::construct()负责对象析构操作由::destroy()负责。 SGI内含有以下两个文件
#includestl_alloc.h //负责内存空间的配置与释放
#includestl_construct.h //负责对象内容的构造与析构图1. STL配置器的框架 2.3 构造和析构的基本工具construct()和destroy()
以下是stl_construct.h的部分内容
#includenew.h //欲使用placement new,需要包含次文件
template class T1,class T2{
inline void construct(T1* p,const T2 value){new(p) T1(value); //placement new
}//destroy有2个版本
//版本1接受一个指针
templateclass T1
inline void destroy(T* pointer){pointer-~T();
}
//版本2接受2个迭代器此函数设法找出元素的数值型别
templateclass ForwardIterator
inline void destroy(ForwardIterator first,ForwardIterator last){__destroy(first,last,value_type(first));
}//判断元素的数值类型是否有trivial destructor
templateclass ForwardIterator, class T
inline void __destroy(ForwardIterator first,ForwardIterator last, T*){typedef typename __type_traitsT::has_trivial_destructor trivial_destructor;__destroy_aux(first,last,trivial_destructor());
}
//如果元素的数值型别有 non-trivial destructor
templateclass ForwardIterator
inline void __destroy_aux(ForwardIterator first,ForwardIterator last, __false_type){for(;firstlast;first)destroy( *first);
}
//如果元素的数值型别有 trivial destructor
templateclass ForwardIterator
inline void __destroy_aux(ForwardIterator first,ForwardIterator last, __true_type){}//destroy()第二版本对迭代器char* wchar_t*的特化版
inline void destroy(char*,char*){}
inline void destroy(wchar_t*,wchar_t*){}construct()接受一个指针p和一个初值value该函数的用途就是将初值设定到指针所指的空间上。 destruct()有2个版本。版本1接受一个指针准备将该指针所指之物析构调直接调用该对象的析构函数即可版本2接受firstlast两个迭代器讲[first,last)范围内的对象都析构掉。做了一些处理万一对象有(trivial destructor)每一次调用他们会极大的降低效率。所以做了一些处理来判断析构函数是否是trivial destruct如果是的话什么也不做就立马结束。如果不是的话以循环方式巡访整个范围在循环中每访问一个对象就调用第一个版本的destroy()。 图2. construct()和destroy()函数 补充
2.3.1、什么是 trivial destruct:
“trivial destructor”指的是用户没有自定义析构函数而是由系统生成的析构函数。这种析构函数在对象生命周期结束时
被调用但由于用户没有定义任何特定的析构逻辑它实际上并不执行任何特定的清理或资源释放操作。因此它被称
为“trivial”即无用的或无关紧要的析构函数。
相对而言如果用户为某个类定义了特定的析构函数那么这个析构函数就被称为“non-trivial destructor”。在这种情况
下析构函数可能会执行一些必要的清理操作如释放动态分配的内存、关闭文件句柄或断开网络连接等。需要注意的是即
使析构函数是trivial的它仍然会在对象生命周期结束时被自动调用。这是因为C的析构机制确保了每个构造的对象最终都会
被正确地销毁。然而对于trivial destructor来说由于它不执行任何实质性的操作频繁地调用它可能会对性能产生一定的
影响。因此在一些高级编程场景中可能会使用特定的技术或工具来优化或避免不必要的trivial destructor调用。2.3.2、从__destroy_aux来看他的销毁范围是[first,last),为什么没有销毁最后一个
在C中迭代器通常遵循“左闭右开”的原则即迭代器first指向的范围是包括的而迭代器last指向的位置是不包括的。这意味着 last迭代器实际上指向的是范围之外的第一个位置 而不是范围内的最后一个元素的下一个位置。因此循环在first小于last时继续这样last指向的元素就不会被包括在销毁的范围内。 这种设计有几个原因 1一致性C标准库中的许多算法和容器都遵循这种 “左闭右开” 的范围定义方式保持一致性使得代码更容易理解和使用。 2避免越界访问安全性如果尝试访问或销毁last指向的元素那么可能会越界访问内存导致未定义行为。保持“左闭右开”的范围定义可以避免这种潜在的问题。 3效率在某些情况下last可能正好指向一个容器的末尾之后的位置这个位置本身并不存储任何对象因此没有销毁的必要。 4语义清晰对于用户来说知道last不指向要销毁的最后一个元素可以更容易地理解函数的行为特别是当使用自定义迭代器或特殊容器时。 综上所述不将last销毁是出于一致性、安全性、效率和语义清晰性的考虑。在设计类似的算法或函数时通常应该遵循这些原则来确保代码的正确性和可维护性。
2.4 空间的配置和释放std::alloc
2.3讲的是对象构造行为与对象析构行为现在来看一下内存的配置与释放。这一部分代码都在stl_alloc.h中。stl对此的设计哲学是
1向 system heap 要求空间2考虑多线程 (multi-threads) 状态3考虑内存不足时的应变措施4考虑过多“小型区块”可能造成的内存碎片 (fragment) 问题 考虑到小型区块可能造成的内存破碎问题SGI 为此设计了双层级配置器。当配置区块超过 128bytes 时称为足够大使用第一级配置器直接使用 malloc() 和 free()。 当配置区块不大于 128bytes 时为了降低额外负担直接使用第二级配置器采用复杂的 memory pool 处理方式。
#ifdef __USE_MALLOC
...
typedef __malloc_alloc_template0 malloc_alloc;
typedef malloc_alloc alloc; //另alloc为第一级配置器
#else
...
typedef __default_alloc_template__NODE_ALLOCATOR_THREADS,0 alloc;
#endif /* !__USE_MALLOC*/其中 __malloc_alloc_template 就是第一级配置器; __default_alloc_template 就是第二级配置器。无论使用第一级配接器(malloc_alloc_template)或是第二级配接器 (default_alloc_template)alloc 都为其包装了接口使其能够符合 STL 标准。
templateclass T,class Alloc
class simple_alloc{
public:static T*allocate(size_t n){return 0n?:(T*)Alloc::allocate(n*sizeof(T));}static T*allocate(void){return (T*) Alloc::allocate(sizeof(T));}static T*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));}
};图3. 第一级配置器与第二级配置器 图4. 第一级配置器与第二级配置器包装接口和运用方式 2.5 第一级配置器 __malloc_alloc_template剖析
#if 0
# includenew
# define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
# includeiostream.h
# define __THROW_BAD_ALLOC cerr out of memoryendl; exit(1)
#endiftemplate int inst
class __malloc_alloc_template{
private:
//以下都是函数指针所代表的函数将用来处理内存不足的情况
//oom:out of memory
static void *oom_malloc(size_t);
static void *oom_realloc(void* ,size_t);
static void (* __malloc_alloc_oom_handler());public:static void *allocate(size_t n)
{//第一级配置器直接使用malloc()void *result malloc(n);if(0 result) result oom_malloc(n);return result;
}
static void deallocate(void *p ,size_t /* n */)
{//第一级配置器直接使用free()free(p);
}
static void* reallocate(void *p,size_t/*old_sz*/,size_t new_sz){//第一级配置器直接使用realloc()void * result realloc(p,new_sz);//当以下无法满足要求时改用oom_realloc()if(0 result) result oom_realloc(p,new_sz);return result;
}
static void(* set_malloc_handler(void(*f)()))()
{void(*old) __malloc_alloc_oom_handler;_malloc_alloc_oom_handler f;return (old);
}
};
//malloc_alloc out-of-memory handling
//初值为0有待客段设定
template int inst
void (* __malloc_alloc_templateinst::_malloc_alloc_oom_handler)() 0;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);}
}template int inst
void * __malloc_alloc_templateinst::oom_realloc(void *p ,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 realloc(p,n); //再次尝试配置内存if(result) return (result);}
}
//以下直接将参数inst指定为0
typedef __malloc_alloc_template0 malloc_alloc;(1)第一级配置器以 malloc(), free(), realloc() 等 C 函数执行实际的内存配置、释放和重配置 操作并实现类似 C new-handler 的机制(因为它并非使用 ::operator new 来配置内存 所以不能直接使用C new-handler 机制)。 (2)SGI 第一级配置器的 allocate() 和 reallocate() 都是在调用malloc() 和 realloc() 不成功 后改调用 oom_malloc() 和oom_realloc()。 (3)oom_malloc() 和 oom_realloc() 都有内循环不断调用“内存不足处理例程”期望某次 调用后获得足够的内存而圆满完成任务哪怕有一丝希望也要全力以赴申请啊如果用户并 没有指定“内存不足处理程序”这个时候便无力乏天真的是没内存了STL 便抛出异常。或 调用exit(1) 终止程序。
2.6 第二级配置器 __default_alloc_template剖析
第二级配置器多了一些机制专⻔针对内存碎片。内存碎片化带来的不仅仅是回收时的困难配置也是一个负担额外负担永远无法避免毕竟系统要划出这么多的资源来管理另外的资源但是区块越小额外负担率就越高。 图5. 索取内存需要cookie记录大小 ### 2.6.1 SGI 第二级配置器到底解决了多少问题呢? 简单来说 SGI第二级配置器的做法是:**sub-allocation (层次架构):** 前面也说过了SGI STL 的第一级配置器是直接使用 malloc() free(), realloc() 并配合类似 C new-handler 机制实现的。第二级配置器的工作机制要根据区块的大小是否大于 128bytes 来采取不同的策略这种方法叫做层次配置。 图6. 层次配置 图7. 内存池原理 二级配置器内存池的原理主要涉及两个方面内存池的管理和两级配置器的使用。 1首先内存池的主要作用是在应用程序初始化时分配一块连续的内存空间并将其划分为多个固定大小的块也称为“内存池对象”。这些块可以被反复使用从而避免了频繁地向操作系统请求新的内存空间。当应用程序需要分配新的内存时它可以直接从预先分配好的内存池中取出一个可用的块而不是向操作系统申请。这样可以减少系统开销提高程序效率同时也可以避免内存碎片和泄漏等问题。 2其次二级配置器则是对内存池管理的一种优化策略。它采用两级策略来配置内存当所需内存区块小于某个阈值如128字节时使用第二级配置器进行管理。这个配置器会一次性配置一大块内存并维护对应的空闲链表free-list。当下次有相同大小的内存需求时直接从空闲链表中取出。如果有小的内存区块被释放它们会被回收到空闲链表中以供后续使用。这种策略有效地避免了由于太多小区块造成的内存碎片问题同时减少了配置时的额外负担。 具体来说二级配置器会维护多个空闲链表每个链表管理不同大小的内存块。例如可以维护16个空闲链表分别管理大小为8、16、24…120、128字节的数据块。当需要分配内存时根据所需大小计算索引从对应的空闲链表中取出内存块。当内存块被释放时它会被回收到对应的空闲链表中。 最后内存池的管理涉及对内存空间的分配和释放。当向系统申请一块内存放入内存池时会使用start和end指针来标记这块空间的起始和结束位置。每分配一部分内存start指针就会向后移动相应的距离。当start和end指针重合时表示内存池中的空间已全部分配完毕。释放内存时需要将释放的内存块归还到内存池中并更新start指针的位置。 综上所述二级配置器内存池的原理通过预分配连续内存空间、划分固定大小的块、使用两级配置器以及维护空闲链表等方式实现了对内存的高效管理和利用避免了内存碎片和泄漏等问题提高了程序的运行效率。
2.6.2 自由链表自由在哪?又该如何维护呢?
我们知道一方面自由链表中有些区块已经分配给了客端使用所以 free_list 不需要再指向它们;另一方面为了维护 free-list每个节点还需要额外的指针指向下一个节点。 那么问题来了如果每个节点有两个指针?这不就造成了额外负担吗?本来我们设计 STL 容 器就是用来保存对象的这倒好对象还没保存之前已经占据了额外的内存空间了。 STL给出的解决办法是
union obj{union obj* free_list_link;char client_data[1]
}在 union obj 中定义了两个字段再结合上图来分析: 从第一个字段看obj 可以看做一个指针指向链表中的下一个节点; 从第二个字段看obj 可以也看做一个指针不过此时是指向实际的内存区。 一物二用的好处就是不会为了维护链表所必须的指针而造成内存的另一种浪费
在二级配置器中的自由链表free-list**“自由”**体现在链表中的内存块是未被应用程序当前使用的即它们是“空闲”的随时可以被分配给需要内存的空间。自由链表的存在允许内存块在被释放后能够被回收和重用而不是直接归还给操作系统从而提高了内存的使用效率。 自由链表的维护主要涉及以下几个方面 (1) 插入操作当释放一个内存块时该内存块会被插入到相应的自由链表中。通常链表会按照内存块的大小进行划分每个链表管理特定大小的内存块。因此释放内存块时需要根据其大小计算它应该插入到哪个链表中。 (2) 删除操作当应用程序请求分配内存时二级配置器会从自由链表中删除一个内存块并将其分配给应用程序。这通常涉及到从链表中取出第一个节点或根据某种策略选取一个节点并更新链表的结构。 (3) 链表合并如果两个相邻大小的自由链表都只有少量的内存块为了提高内存管理的效率可能会将它们合并成一个更大的链表。这样可以减少链表的数量简化管理。 (4) 内存块合并当连续的内存块都被释放时可以考虑将它们合并成一个更大的内存块以减少碎片并便于后续的分配。 (5) 内存块分割当请求的内存大小与自由链表中现有内存块的大小不完全匹配时可能需要将现有的内存块分割成两部分一部分用于满足当前的请求另一部分作为新的空闲内存块加入自由链表。 (6) 链表大小调整随着程序的运行某些大小的内存块可能会被频繁地申请和释放导致某些链表特别长或特别短。此时可以根据实际情况调整链表的大小例如通过合并或分割链表来平衡内存的使用。 (7) 内存泄露检查定期检查自由链表中的内存块是否都被正确管理防止因为编程错误导致的内存泄露。 为了实现这些操作二级配置器通常会维护一些数据结构来跟踪每个链表的状态例如链表的头指针、链表长度、已分配和未分配的内存块数量等。这些数据结构可以帮助配置器高效地管理内存块确保它们能够在需要时被正确地分配和回收。 总的来说自由链表的维护涉及到内存块的插入、删除、合并和分割等操作以及链表本身的调整和优化。这些操作共同确保了内存的有效利用和程序的稳定运行。
2.6.3 第二级配置器的部分实现内容
enum{__ALIGN 8}; //小型区块的上调边界
enum{__MAX_BYTES 128}; //小型区块的上限
enum{__NFREELISTS __MAX_BYTES/__ALIGH}; //free_lists的个数template bool threads,int inst
class __default_alloc_template{
private:
//ROUND UP
static size_t ROUND_UP(size_t bytes){return (((bytes) __ALIGN_1) ~(__ALIGN-1));
}
private:union obj{ //free lists的节点构造union obj * free_list_link;char clinet_data[1]};
private://16个free-listsstatic obj* volatile free_list[__NFREELISTS];//根据区块大小决定使用第n号listsstatic size_t FREELIST_INDEX(size_t bytes){return (((bytes) __ALIGN -1)/__ALIGN -1);}
static void *refill(size_t n)
//配置一大块空间可容纳nobjs个大小为size的区域
//如果配置nobjs个区域有所不便nobjs可能会降低
static char* chunk_alloc(size_t size,int nobjs);
//chunk allocation state
static char* start_free; //内存池起始位置
static char* end_free; //内存池结束位置
static char* heap_size;public:static void * allocate(size_t n)static void * deallocate(void *p,size_t n)static void * reallocate(void *p,size_t old_sz,size_t new_sz);
};
//以下是 static data member的定义与初值设定
templatebool threads,int inst
char *__default_alloc_templatethreads,inst::start_free 0;templatebool threads,int inst
char *__default_alloc_templatethreads,inst::end_free 0;templatebool threads,int inst
char *__default_alloc_templatethreads,inst::heap_size 0;templatebool threads,int inst
__default_alloc_templatethreads,inst::obj* volatile
__default_alloc_templatethreads,inst::free_list[__NFREELISTS]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
}2.7空间配置函数allocate()
我们知道第二级配置器拥有配置器的标准接口函数 allocate()。此函数首先判断区块的大小 如果大于 128bytes – 调用第一级配置器;小于128bytes– 就检查对应的 free_list(如果没 有可用区块就将区块上调至 8 倍数的边界然后调用 refill(), 为 free list 新填充空间。
2.7.1空间配置函数allocate()实现原理
allocate()代码实现了一个简单的内存分配策略它首先检查请求的内存大小是否超过预设的阈值如果是则调用另一个配置器进行分配。对于小块内存它使用一组free lists来快速分配和回收固定大小的内存块。当free list为空时它会调用 refill 函数来重新填充free list。这种策略有助于减少内存碎片并提高小块内存的分配和回收效率。
2.7.2空间配置函数allocate()代码实现
//n must be 0
static void *allocate(size_t n){obj* volatile *my_free_list;obj* result;//大于128就调用第一级配置器if(n (size_t)__MAX_BYTES){return (malloc_alloc::allocate(n));}//寻找16个free lists中符合的一个my_free_list free_list FREELIST_INDEX(n);result *my_free_list;if(result 0){//没找到可用的free lists,准备重新填充 free lstsvoid *r refill(ROUND_UP(n));return r;}//调整free lists*my_free_list result-free_list_link;return(result);
};图8. allocate()函数工作原理 2.8 空间释放函数 deallocate()
身为一个配置器__default_alloc_template 拥有配置器标准接口函数 deallocate()。该函数首先判断区块大小大于 128bytes就调用第一级配置器 小于 128bytes就找出对应的free lists将区块进行回收。
2.8.1空间释放函数 deallocate()实现原理
这个函数是一个自定义内存分配器的一部分用于将释放的内存块添加到适当的空闲链表中以便将来可以重新使用。对于大于某个阈值的内存块它使用另一个可能是更通用的分配器来释放内存。这种自定义的内存分配器通常用于优化特定类型的内存使用例如小对象的快速分配和释放。
2.8.2空间释放函数 deallocate()代码实现
//p不可以是0
static void *allocate(void* p,size_t n){obj *q (obj*)p;obj *volatile *my_free_list;//大于128就调用第一级配置器if(n (size_t)__MAX_BYTES){malloc_alloc::deallocate(p,n);return ;}//寻找对应的free listmy_free_list free_list FREELIST_INDEX(n);//调整free list收回区块q-free_list_link *my_free_list;*my_free_list q;
}图9. deallocate()函数工作原理 2.9 重新填充 free lists
先前说过的allocate()当它发现freelist 中没有可用区块了时 就调用 refill(}准备为freelist重新填充空间.新的空间将取自内存池(经由 chu出_alloc()完成)。缺省取得20 个新节点(新区块)但万一内存池空间不 足获得的节点数(区块数)可能小于 20:
2.9.1重新填充 free lists()实现原理
这个函数的主要目的是为自定义内存分配器“refill”空闲链表。它首先分配一个较大的内存块chunk然后将其分割成多个较小的对象并将这些对象链接成一个空闲链表。最后它返回第一个对象的地址给调用者以便该对象可以被分配给客户端。这种策略通常用于优化内存分配和释放特别是在需要频繁分配和释放小块内存的情况下。
2.9.2重新填充 free lists()代码实现
(1)当发现 free_list 中没有可用区块时就会调用 refill() 为free_list 重新填充空间; (2)新的空间将取自内存池(经由 chunk_alloc() 完成); (3)缺省取得20个新节点(区块)但万一内存池空间不足获得的节点数可能小于 20。
/* Returns an object of size n, and optionally adds to size n free list.*/
/* We assume that n is properly aligned. */
/* We hold the allocation lock. */
template bool threads, int inst
void* __default_alloc_templatethreads, inst::refill(size_t n)
{int nobjs 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); // my_free_list 跳过第一块内存 从第2块开始 result指向第一块 返回给客户端for (i 1; ; i) {current_obj next_obj;next_obj (obj *)((char *)next_obj n);if (nobjs - 1 i) { // 19 块空间 放到相应的 free_list 里面 current_obj - free_list_link 0;break;} else {current_obj - free_list_link next_obj;}}return(result);
}
2.10 内存池 memory pool
首先我们要知道从内存池中取空间给 free_list 使用是 chunk_alloc() 在工作它是怎么工 作的呢? 我们先来分析 chunk_alloc() 的工作机制:chunk_alloc() 函数以 end_free – start_free 来判断内存池的“水量”。具体逻辑如下。 图10. chunk_alloc()函数工作原理 如果第一级配置器的 malloc() 也失败了就发出 bad_alloc 异常。
2.10.1内存池 memory pool实现原理 图11. memory_pool()函数工作原理 举个例子 假设程序一开始客端就调用 chunk_alloc (32, 20), 于是 malloc()配置 40 个 32 bytes 区块其中第 1 个交出另 19 个交给free_list[3]维护余 20 个留给内存池。接下来客端调用chunk_alloc(64,20)此时 free_list[7]空空如也必须向内存池要求支持。内存池只够供应 ( 32*20)/6410 个 64 bytes 区块就把这 10 个区块返回第 1 个 交给客端余 9 个由 free_list[7]维护。此时内存池全空。接下来再调用 chunk_alloc(96, 20)此时 free_list[11]空空如也必须向内存池要求支持 而内存池此时也是空的于是以 malloc()配置40n (附加量)个96bytes区块其中第 1 个交出另 19 个交给 free_list[11]维护余 20n (附加量)个区块 留给内存池。
2.10.2内存池 memory pool代码实现
template bool __threads, int __inst
char*
__default_alloc_template__threads, __inst::_S_chunk_alloc(size_t __size, int __nobjs)
{char* __result;size_t __total_bytes __size * __nobjs;size_t __bytes_left _S_end_free - _S_start_free; //内存池剩余空间if (__bytes_left __total_bytes) //满足内存需求{__result _S_start_free;_S_start_free __total_bytes;return(__result);} else if (__bytes_left __size) //满足至少一个区块的需求{__nobjs (int)(__bytes_left/__size);__total_bytes __size * __nobjs;__result _S_start_free;_S_start_free __total_bytes;return(__result);} else //完全不满足需求{size_t __bytes_to_get 2 * __total_bytes _S_round_up(_S_heap_size 4);//利用剩下的一点点零头.if (__bytes_left 0) {_Obj* __STL_VOLATILE* __my_free_list _S_free_list _S_freelist_index(__bytes_left);((_Obj*)_S_start_free) - _M_free_list_link *__my_free_list;*__my_free_list (_Obj*)_S_start_free;}_S_start_free (char*)malloc(__bytes_to_get);if (0 _S_start_free) {size_t __i;_Obj* __STL_VOLATILE* __my_free_list;_Obj* __p;//看free-list是否还有内存区块for (__i __size; __i (size_t) _MAX_BYTES; __i (size_t) _ALIGN){__my_free_list _S_free_list _S_freelist_index(__i);__p *__my_free_list;//有的话编入并循环调用自身直至彻底使用所有零头if (0 ! __p) {*__my_free_list __p - _M_free_list_link;_S_start_free (char*)__p;_S_end_free _S_start_free __i;return(_S_chunk_alloc(__size, __nobjs)); //反复压榨内存}}//执行到了这一步说明没内存了_S_end_free初始化置于零并调用第一级配置器配置内存重新设定_S_start_free。_S_end_free 0; _S_start_free (char*)malloc_alloc::allocate(__bytes_to_get);}_S_heap_size __bytes_to_get;_S_end_free _S_start_free __bytes_to_get;//return(_S_chunk_alloc(__size, __nobjs));}
}
3、内存 基本处理工具
STL定义了五个全局函数分别是construct(),destroy(),uninitialized_copy(),uninitialized_fill(), uninitialized_fill_n()。构造析构函数已经说过现在考虑后面3个函数。
3.1 uninitialized_copy
std::uninitialized_copy() std::uninitialized_copy() 用于从输入范围复制元素到未初始化的内存区域。它接收两个输入迭代器表示要复制的元素的范围和一个指向目标内存区域的原始指针。 函数原型可能类似于
templateclass InputIt, class ForwardIt
ForwardIt uninitialized_copy(InputIt first, InputIt last, ForwardIt result);first 和 last 定义了输入范围的开始和结束。 d_first 是指向目标内存区域的原始指针。 这个函数会将 [first, last) 范围内的所有元素复制到从 d_first 开始的内存区域并返回指向目标区域中最后一个复制元素的下一个位置的原始指针。
3.2 uninitialized_fill
std::uninitialized_fill() 用于在未初始化的内存区域中填充指定值。它接收一个原始指针指向目标内存区域的开始和一个表示要填充的值的参数以及要填充的元素数量。 函数原型可能类似于
templateclass ForwardIt, class T
void uninitialized_fill(ForwardIt first, ForwardIt last, const T value);first 和 last 定义了目标内存区域的开始和结束。 value 是要填充的值。 这个函数会将 [first, last) 范围内的所有元素初始化为 value。
3.3 uninitialized_fill_n
std::uninitialized_fill_n() 类似于 std::uninitialized_fill()但它允许你指定要填充的元素数量而不是通过两个迭代器来定义范围。 函数原型可能类似于
templateclass ForwardIt, class Size, class T
ForwardIt uninitialized_fill_n(ForwardIt first, Size n, const T value);first 是指向目标内存区域的原始指针。 n 是要填充的元素数量。 value 是要填充的值。 这个函数会将从 first 开始的 n 个元素初始化为 value并返回指向最后一个填充元素的下一个位置的原始指针。
4、总结
天堂有路你不走地狱无门你自来。
5、参考
1、《STL源码剖析》 2、《C八股文小贺》图片均来自于他
