详解STL中的空间配置器(SGI版本)

  • Post author:
  • Post category:其他




空间配置器



1.什么是空间配置器

为各个容器高效的管理空间(空间的申请与回收)的



2.为什么需要空间配置器

各种容器—–>可以存放元素—->底层需要空间



new 申请空间
  1. operator new —->malloc
  2. 调用构造函数——完成对象的构造



动态内存管理总结

前面的容器中,每次开辟空间都用的是new,但是用new有一些不好的地方

  • 空间申请与释放需要用户自己管理,

    容易造成内存泄漏
  • 频繁向系统申请小块内存块,

    容易造成内存碎片

    例如:结点
  • 频繁向系统申请小块内存,

    影响程序运行效率
  • 直接使用malloc与new进行申请,

    每块空间前有额外空间浪费

    (malloc会在申请的空间前后添加新的东西)
  • 申请空间失败怎么处理
  • 代码结构比较混乱,

    代码复用率不高
  • 未考虑

    线程安全问题

高效的内存管理方式



3.SGI–STL空间配置器如何实现



小块内存
  1. 大于128字节—–>大块内存
  2. 小于等于128字节—–>小块内存
  • 一级空间配置器处理大块内存,
  • 二级空间配置器处理小块内存。



一级空间配置器

malloc+free—–>set_new_handle



_malloc_alloc_template:



申请空间
void * allocate(size_t n)
{
	// 申请空间成功,直接返回,失败交由oom_malloc处理
	void * result =malloc(n);
	if(nullptr == result)
		result = oom_malloc(n);
	return result;
}


释放空间
static void deallocate(void *p, size_t /* n */)
{ 
	free(p);
}


malloc失败后的处理oom_malloc
  1. 接受函数指针(调用set_new_handle)
  2. 验证该函数指针是否为空

    • 是:直接抛异常
  3. 调用该函数指针对应的函数
  4. 调用malloc继续申请空间

    • 申请成功:直接返回
    • 申请失败:循环继续
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
	void (* my_malloc_handler)();
	void *result;
	for (;;)
	{
		// 检测用户是否设置空间不足应对措施,如果没有设置,抛异常,模式new的方式
		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);
	}
}


set_new_handle

返回值类型以及参数类型都是void*()函数指针

// 该函数的参数为函数指针,返回值类型也为函数指针
// void (* set_malloc_handler( void (*f)() ) )()
static void (* set_malloc_handler(void (*f)()))()
{
	void (* old)() = __malloc_alloc_oom_handler;
	__malloc_alloc_oom_handler = f;
	return(old);
}



二级空间配置器

频繁向系统申请小的内存块造成的缺陷

SGI—STL采用了

内存池

的技术来

提高申请空间的速度以及减少额外空间的浪费



采用哈希桶的方式来提高用户获取空间的速度与高效管理



内存池

内存池就是:先申请一块比较大的内存块已做备用,当需要内存时,直接到内存池中去去,当池中空间不够时,再向内存中去取,当用户不用时,直接还回内存池即可。避免了频繁向系统申请小块内存所造成的效率低、内存碎片以及额外浪费的问题

char* _start,*finish

在这里插入图片描述



申请空间
  1. 现在已经归还的内存块中找合适的块
  2. 找到—->是否需要分割—->不需要—->直接分配

    需要—–>再对内存块进行分割
  3. 未找到—–>去内存池中申请


申请空间的缺陷
  1. 链表查找合适内存块,需要遍历,效率低
  2. 分割


注意问题
  1. 当用户需要空间时,能否直接从内存池中大块空间中直接截取?为什么?

    答:优先从链表中选,先从大块中拿,如果用户需要大块的空间,可能就给不了了
  2. 对用户归还的空间能否直接拼接在大块内存前?

    答:不行
  3. 对用户归还的空间如何进行管理?

    答:用链表连接起来
  4. 不断切割会有什么后果?

    答:内存碎片



二级空间配置器的设计

SGI-STL中的二级空间配置器使用了内存池技术,但没有采用链表的方式对用户已经归还的空间进行管理(因为用户申请空间时在查找合适的小块内存时效率比较低),

而是采用了哈希桶的方式进行管理效率更高

。那是否需要128桶个空间来管理用户已经归还的内存块呢?答案是不需要,

因为用户申请的空间基本都是4的整数倍,其他大小的空间几乎很少用到

。因此:

SGI-STL将用户申请的内存块向上对齐到了8的整数倍

32位系统用4的倍数

64位系统用8的倍数

每个链表中肯定必须有一个指针,32位指针是4个字节,64位下是8个字节

在这里插入图片描述

template <int inst>
class __default_alloc_template
{
private:
	enum { __ALIGN = 8 }; // 如果用户所需内存不是8的整数倍,向上对齐到8的整数倍
	enum { __MAX_BYTES = 128 }; // 大小内存块的分界线
	enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // 采用哈希桶保存小块内存时所需桶的个数
	// 如果用户所需内存块不是8的整数倍,向上对齐到8的整数倍
	static size_t ROUND_UP(size_t bytes)
	{
		return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));
	}
private:
	// 用联合体来维护链表结构----同学们可以思考下此处为什么没有使用结构体
	union obj
	{
		union obj * free_list_link;
		char client_data[1]; /* The client sees this. */
	};
private:
	static obj * free_list[__NFREELISTS];
	// 哈希函数,根据用户提供字节数找到对应的桶号
	static size_t FREELIST_INDEX(size_t bytes)
	{
		return (((bytes)+__ALIGN - 1) / __ALIGN - 1);
	}
	// start_free与end_free用来标记内存池中大块内存的起始与末尾位置
	static char *start_free;
	static char *end_free;
	// 用来记录该空间配置器已经想系统索要了多少的内存块
	static size_t heap_size;
	// ...跨平台操作,封装锁,申请空间方式等
};



二级空间配置器的管理空间

void allocate(size_t n)

{


if(n>128)

; //调用一级空间配置器

1. 用n计算桶号

2. 检测该桶中是否有结点(内存块)

有:使用头删法将第一个内存块返回

没有:

return refill(Round_up(n));


}

void refill(size_t/

已经是8的整数倍

/)

{


size_t nobjs =20;

char* chunk = chunk_alloc(n,nobjs);

if(nobjs == 1) //只要了一块

return chunk;

//1<nobjs<=20

将第一个内存保存,最后要返回给外部用户

将剩余nobjs-1个内存块挂接到对应的桶中

}

void * chunk_alloc(size_t size,size_t& nobjs//20)

{


size_t totalBytes = nobjs*size;

size_t leftBytes = finish-start;

void * res =null;

if(leftBytes > = totalBytes) //内存池空间足以提供20

{res = start;start+=totalBytes;return res;}

else if(leftBytes>=size)//不够20至少提供1块

{nobjs =leftBytes/size;res=start;start+=nobjs

size;return res;}//实际能提供多少块

else //内存池的空间也不足,连一块也提供不了

{


//1.将内存池中剩余的内存—>挂接到相应桶中

//total_get = 2

total_bytes+RoundUP(heap_size>>4);

}

}


  1. 申请空间


    在这里插入图片描述
// 函数功能:向空间配置器索要空间
// 参数n: 用户所需空间字节数
// 返回值:返回空间的首地址
static void * allocate(size_t n)
{
	obj * __VOLATILE * my_free_list;
	obj * __RESTRICT result;
	// 检测用户所需空间释放超过128(即是否为小块内存)
	if (n > (size_t)__MAX_BYTES)
	{
		// 不是小块内存交由一级空间配置器处理
		return (malloc_alloc::allocate(n));
	}
	// 根据用户所需字节找到对应的桶号
	my_free_list = free_list + FREELIST_INDEX(n);
	result = *my_free_list;
	// 如果该桶中没有内存块时,向该桶中补充空间
	if (result == 0)
	{
		// 将n向上对齐到8的整数被,保证向桶中补充内存块时,内存块一定是8的整数倍
		void *r = refill(ROUND_UP(n));
		return r;
	}
	// 维护桶中剩余内存块的链式关系
	*my_free_list = result->free_list_link;
	return (result);
};

  1. 回收空间


    在这里插入图片描述


    二级空间配置器中没有释放空间
// 函数功能:用户将空间归还给空间配置器
// 参数:p空间首地址 n空间总大小
static void deallocate(void *p, size_t n)
{
	obj *q = (obj *)p;
	obj ** my_free_list;
	// 如果空间不是小块内存,交给一级空间配置器回收
	if (n > (size_t)__MAX_BYTES)	//超过128,按照一级空间配置进行释放
	{
		malloc_alloc::deallocate(p, n);
		return;
	}
	//没到128
	// 找到对应的哈希桶,将内存挂在对应哈希桶中
	my_free_list = free_list + FREELIST_INDEX(n);
	q->free_list_link = *my_free_list;
	*my_free_list = q;
}

  1. 向内存中补充空间

在这里插入图片描述

template <int inst>
char* __default_alloc_template<inst>::chunk_alloc(size_t size, int& nobjs)
{
	// 计算nobjs个size字节内存块的总大小以及内存池中剩余空间总大小
	char * result;
	size_t total_bytes = size * nobjs;
	size_t bytes_left = end_free - start_free;
	// 如果内存池可以提供total_bytes字节,返回
	if (bytes_left >= total_bytes)
	{
		result = start_free;
		start_free += total_bytes;
		return(result);
	}
	else if (bytes_left >= size)
	{
		// nobjs块无法提供,但是至少可以提供1块size字节内存块,提供后返回
		nobjs = bytes_left / size;
		total_bytes = size * nobjs;
		result = start_free;
		start_free += total_bytes;
		return(result);
	}
	else
	{
		// 内存池空间不足,连一块小块村内都不能提供
		// 向系统堆求助,往内存池中补充空间
		// 计算向内存中补充空间大小:本次空间总大小两倍 + 向系统申请总大小/16
		size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
		// 如果内存池有剩余空间(该空间一定是8的整数倍),将该空间挂到对应哈希桶中
		if (bytes_left > 0)
		{
			// 找对用哈希桶,将剩余空间挂在其上
			obj ** my_free_list = free_list + FREELIST_INDEX(bytes_left);
			((obj *)start_free)->free_list_link = *my_free_list;
			*my_ree_list = (obj *)start_free;
		}
		// 通过系统堆向内存池补充空间,如果补充成功,递归继续分配
		start_free = (char *)malloc(bytes_to_get);
		if (0 == start_free)
		{
			// 通过系统堆补充空间失败,在哈希桶中找是否有没有使用的较大的内存块
			int i;
			obj ** my_free_list, *p;
			for (i = size; i <= __MAX_BYTES; i += __ALIGN)
			{
				my_free_list = free_list + FREELIST_INDEX(i);
				p = *my_free_list;
				// 如果有,将该内存块补充进内存池,递归继续分配
				if (0 != p)
				{
					*my_free_list = p->free_list_link;
					start_free = (char *)p;
					end_free = start_free + i;
					return(chunk_alloc(size, nobjs));
				}
			}
			// 山穷水尽,只能向一级空间配置器求助
			// 注意:此处一定要将end_free置空,因为一级空间配置器一旦抛异常就会出问题
			end_free = 0;//end_free作用是标记内存池空间的末尾
			start_free = (char *)malloc_alloc::allocate(bytes_to_get);
		}
		// 通过系统堆向内存池补充空间成功,更新信息并继续分配
		heap_size += bytes_to_get;
		end_free = start_free + bytes_to_get;
		return(chunk_alloc(size, nobjs));
	}
}



空间配置器的默认选择

SGI-STL默认使用一级还是二级空间配置器,通过USE_MALLOC宏进行控制:

#ifdef __USE_MALLOC
	typedef malloc_alloc alloc;
	typedef malloc_alloc single_client_alloc;
#else
	// 二级空间配置器定义
#endif

在SGI_STL中该宏没有定义,因此:

默认情况下SGI_STL使用二级空间配置器



空间配置器的再次封装

在C++中,用户所需空间可能是任意类型的,有单个对象空间,有连续空间,每次让用户自己计算所需空间总大小不是很友好,因此SGI-STL将空间配置器重新再封装了一层:

template<class T, class Alloc>
class simple_alloc
{
public:
	// 申请n个T类型对象大小的空间
	static T *allocate(size_t n)
	{
		return 0 == n ? 0 : (T*)Alloc::allocate(n * sizeof (T));
	}
	// 申请一个T类型对象大小的空间
	static T *allocate(void)
	{
		return (T*)Alloc::allocate(sizeof (T));
	}
	// 释放n个T类型对象大小的空间
	static void deallocate(T *p, size_t n)
	{
		if (0 != n)
			Alloc::deallocate(p, n * sizeof (T));
	}
	// 释放一个T类型对象大小的空间
	static void deallocate(T *p)
	{
		Alloc::deallocate(p, sizeof (T));
	}
};



对象构造与释放

一切为了效率考虑,SGI-STL决定将空间申请释放和对象的构造析构两个过程分离开,因为有些对象的构造不需要调用析构函数,销毁时不需要调用析构函数,将该过程分离开可以提高程序的性能:

// 归还空间时,先先调用该函数将对象中资源清理掉
template <class T>
inline void destroy(T* pointer)
{
	pointer->~T();
}
// 空间申请好后调用该函数:利用placement-new完成对象的构造
template <class T1, class T2>
inline void construct(T1* p, const T2& value)
{
	new (p)T1(value);
}



版权声明:本文为liuyuchen282828原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。