【C++】空间配置器 allocator：原理及底层解析

2023-10-09 17:36
文章标签 配置 c++ 原理 解析 底层 空间 allocator

本文主要是介绍【C++】空间配置器 allocator：原理及底层解析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 空间配置器
    • 一级空间配置器
    • 二级空间配置器
      • 1. 内存池
      • 2. SGI-STL中二级空间配置器设计 - - 哈希桶
      • 3. 二级空间配置器的空间申请
    • 空间配置器的默认选择
    • 空间配置器的在封装：添加了数据类型大小
    • 空间配置器对象的构造与析构
  • 容器中的 allocator

空间配置器

提到空间配置，难免让人联想到 malloc 系列函数。malloc 可以设定用户自己需要的类型为其开辟空间，而空间配置器是专门为 STL 容器进行空间配置的。

空间配置器 allocator：为各个容器进行高效的空间管理 - - 空间的申请与回收。

如果我们用 new 自己设计空间管理，容易因为 频繁向系统申请小块内存而造成内存碎片、影响程序运行效率。而 SGI-STL以128作为小块内存与大块内存的分界线，将空间配置器其分为两级结构，一级空间配置器处理大块内存，二级空间配置器处理小块内存。

一级空间配置器

一级空间配置器原理非常简单，直接对malloc与free进行了封装，并增加了C++中 set_new_handle 思想。

template <int inst>
class __malloc_alloc_template
{
private:static void *oom_malloc(size_t);
public:
// 对malloc的封装static void * allocate(size_t n){// 申请空间成功，直接返回，失败交由oom_malloc处理void *result = malloc(n);if (0 == result) result = oom_malloc(n);return result;}
// 对free的封装static void deallocate(void *p, size_t /* n */){ free(p);}// 模拟set_new_handle// 该函数的参数为函数指针，返回值类型也为函数指针// 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);}
};// 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);}
}
typedef __malloc_alloc_template<0> malloc_alloc;

二级空间配置器

二级空间配置器专门负责处理小于 128 字节的小块内存。SGI-STL 采用了 内存池 的技术来提高申请空间的速度以及减少额外空间的浪费，采用 哈希桶 的方式来提高用户获取空间的速度与高效管理。

1. 内存池

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

2. SGI-STL中二级空间配置器设计 - - 哈希桶

内存池的空间是以哈希桶结构管理的，这里的哈希桶是以 8 字节 的 整数倍 进行设置的， 如果用户所需内存块不是8的整数倍，向上对齐到8的整数倍。原因有两个：

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

  2. 每个桶下面悬挂一个个的未被分配的空间，他们的首部 4/8 个字节 储存的都是下一块空间的地址（或者 nullptr），而 64 位空间下的地址就是 8 字节。

在这里插入图片描述

小于 128 的小块内存申请和释放，在哈希桶中以头删和头插的方式实现。

3. 二级空间配置器的空间申请

申请空间：

  • 申请空间大于 128 一级 allocator 进行分配
  • 小于 128 去找相应大小的桶，如果下面有悬挂内存，就把第一个给用户
  • 如果桶下没有内存，去找内存池索要（见下），并将第一个内存块返回给用户

在这里插入图片描述

// 函数功能：向空间配置器索要空间
// 参数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);
};

填充内存块：

  • 用户申请空间桶下没有空闲空间，于是需要向 内存池申请空间（见下）
  • 一次申请 nobjs(20) 个小块内存，按用户需要分配，剩余的挂在桶下
    在这里插入图片描述
// 函数功能：向哈希桶中补充空间
// 参数n：小块内存字节数
// 返回值：首个小块内存的首地址
template <int inst>
void* __default_alloc_template<inst>::refill(size_t n)
{// 一次性向内存池索要20个n字节的小块内存int nobjs = 20;char * chunk = chunk_alloc(n, nobjs);obj ** 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);// 将第一块返回值用户，其他块连接在对应的桶中// 注：此处代码逻辑比较简单，标准库实现更复杂一些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);
}

向内存池中索要空间：

  • 桶下无可使用空间，向内存池接着索要 nobjs（20） 个 n 字节小块，需要计算内存池剩余空间是否足够给出
  • 如果剩余空间足够，就给出空间
  • 如果剩余空间不够 20 块，就把能分配整数块空间一块一块的先切割出去
    • 不足一块时，将剩余内存挂接到链表中，通过系统堆向内存池中补充内存
    • 如果补充成功正常使用
    • 如果补充失败，从哈希表中找到比请求空间更大的内存块进行补充
      • 如果补充成功正常使用
      • 如果再次补充失败，向一级空间配置器申请补充
        在这里插入图片描述
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{// 内存池空间不足，连一块小块村内都不能提供// 向系统堆求助，往内存池中补充空间// 计算向内存中补充空间大小：本次空间总大小两倍 + 向系统申请总大小/16size_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;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 二级空间配置器之空间回收：

  • 和申请一样，以 128 为分界线
  • 大于 128 交给 一级空间配置器来释放
  • 小与 128 则找到对应的哈希桶，头插 到其中
    在这里插入图片描述
// 函数功能：用户将空间归还给空间配置器
// 参数：p空间首地址   n空间总大小
static void deallocate(void *p, size_t n)
{obj *q = (obj *)p;obj ** my_free_list;// 如果空间不是小块内存，交给一级空间配置器回收if (n > (size_t) __MAX_BYTES){malloc_alloc::deallocate(p, n);return;}// 找到对应的哈希桶，将内存挂在哈希桶中my_free_list = free_list + FREELIST_INDEX(n);q -> free_list_link = *my_free_list;*my_free_list = q;
}

空间配置器的默认选择

SGI-STL 使用一级还是二级空间配置器，通过 USE_MALLOC 宏进行控制：

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

在 SGI_STL 中该宏没有定义，故，默认情况下 SGI_STL 使用二级空间配置器

空间配置器的在封装：添加了数据类型大小

// T: 元素类型
// Alloc: 空间配置器
// 注意：该类只负责申请与归还对象的空间，不否则空间中对象的构造与析构
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);
}
  • 在释放对象时，需要根据对象的类型确定是否调用析构函数（类型萃取）
  • 对象的类型可以通过迭代器萃取到

容器中的 allocator

展示 vector 的部分源码：

template <class T, class Alloc = alloc>
class list
{// ...// 实例化空间配置器typedef simple_alloc<list_node, Alloc> list_node_allocator;// ...protected:link_type get_node(){// 调用空间配置器接口先申请节点的空间return list_node_allocator::allocate(); }// 将节点归还给空间配置器void put_node(link_type p) {list_node_allocator::deallocate(p);}// 创建节点：1. 申请空间 2. 完成节点构造link_type create_node(const T& x){link_type p = get_node();construct(&p->data, x);return p;}// 销毁节点： 1. 调用析构函数清理节点中资源 2. 将节点空间归还给空间配置器void destroy_node(link_type p){destroy(&p->data);put_node(p);}// ...iterator insert(iterator position, const T& x){link_type tmp = create_node(x);tmp->next = position.node;tmp->prev = position.node->prev;(link_type(position.node->prev))->next = tmp;position.node->prev = tmp;return tmp;}iterator erase(iterator position) {link_type next_node = link_type(position.node->next);link_type prev_node = link_type(position.node->prev);prev_node->next = next_node;next_node->prev = prev_node;destroy_node(position.node);return iterator(next_node);}// ...
};

🥰如果本文对你有些帮助，请给个赞或收藏，你的支持是对作者大大莫大的鼓励！！(✿◡‿◡) 欢迎评论留言~~

这篇关于【C++】空间配置器 allocator：原理及底层解析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/174468。

相关文章

Redis多种内存淘汰策略及配置技巧分享

Redis多种内存淘汰策略及配置技巧分享

《Redis多种内存淘汰策略及配置技巧分享》本文介绍了Redis内存满时的淘汰机制,包括内存淘汰机制的概念,Redis提供的8种淘汰策略（如noeviction、volatile-lru等）及其适用场... 目录前言一、什么是 Redis 的内存淘汰机制？二、Redis 内存淘汰策略1. pythonnoe
阅读更多...
Linux中shell解析脚本的通配符、元字符、转义符说明

Linux中shell解析脚本的通配符、元字符、转义符说明

《Linux中shell解析脚本的通配符、元字符、转义符说明》：本文主要介绍shell通配符、元字符、转义符以及shell解析脚本的过程,通配符用于路径扩展,元字符用于多命令分割,转义符用于将特殊... 目录一、linux shell通配符(wildcard)二、shell元字符（特殊字符 Meta）三、s
阅读更多...
windos server2022的配置故障转移服务的图文教程

windos server2022的配置故障转移服务的图文教程

《windosserver2022的配置故障转移服务的图文教程》本文主要介绍了windosserver2022的配置故障转移服务的图文教程,以确保服务和应用程序的连续性和可用性,文中通过图文介绍的非... 目录准备环境：步骤故障转移群集是 Windows Server 2022 中提供的一种功能，用于在多个
阅读更多...
windos server2022里的DFS配置的实现

windos server2022里的DFS配置的实现

《windosserver2022里的DFS配置的实现》DFS是WindowsServer操作系统提供的一种功能,用于在多台服务器上集中管理共享文件夹和文件的分布式存储解决方案,本文就来介绍一下wi... 目录什么是DFS？优势：应用场景：DFS配置步骤什么是DFS？DFS指的是分布式文件系统（Distr
阅读更多...
关于Maven中pom.xml文件配置详解

关于Maven中pom.xml文件配置详解

《关于Maven中pom.xml文件配置详解》pom.xml是Maven项目的核心配置文件,它描述了项目的结构、依赖关系、构建配置等信息,通过合理配置pom.xml,可以提高项目的可维护性和构建效率... 目录1. POM文件的基本结构1.1 项目基本信息2. 项目属性2.1 引用属性3. 项目依赖4. 构
阅读更多...
龙蜥操作系统Anolis OS-23.x安装配置图解教程(保姆级)

龙蜥操作系统Anolis OS-23.x安装配置图解教程(保姆级)

《龙蜥操作系统AnolisOS-23.x安装配置图解教程(保姆级)》：本文主要介绍了安装和配置AnolisOS23.2系统，包括分区、软件选择、设置root密码、网络配置、主机名设置和禁用SELinux的步骤，详细内容请阅读本文，希望能对你有所帮助... ‌AnolisOS‌是由阿里云推出的开源操作系统，旨
阅读更多...
Redis主从/哨兵机制原理分析

Redis主从/哨兵机制原理分析

《Redis主从/哨兵机制原理分析》本文介绍了Redis的主从复制和哨兵机制,主从复制实现了数据的热备份和负载均衡,而哨兵机制可以监控Redis集群,实现自动故障转移,哨兵机制通过监控、下线、选举和故... 目录一、主从复制1.1 什么是主从复制1.2 主从复制的作用1.3 主从复制原理1.3.1 全量复制
阅读更多...
C++中实现调试日志输出

C++中实现调试日志输出

《C++中实现调试日志输出》在C++编程中,调试日志对于定位问题和优化代码至关重要,本文将介绍几种常用的调试日志输出方法,并教你如何在日志中添加时间戳,希望对大家有所帮助... 目录1. 使用 #ifdef _DEBUG 宏2. 加入时间戳：精确到毫秒3.Windows 和 MFC 中的调试日志方法MFC
阅读更多...
mysql-8.0.30压缩包版安装和配置MySQL环境过程

mysql-8.0.30压缩包版安装和配置MySQL环境过程

《mysql-8.0.30压缩包版安装和配置MySQL环境过程》该文章介绍了如何在Windows系统中下载、安装和配置MySQL数据库,包括下载地址、解压文件、创建和配置my.ini文件、设置环境变量... 目录压缩包安装配置下载配置环境变量下载和初始化总结压缩包安装配置下载下载地址：https://d
阅读更多...
Redis主从复制的原理分析

Redis主从复制的原理分析

《Redis主从复制的原理分析》Redis主从复制通过将数据镜像到多个从节点,实现高可用性和扩展性,主从复制包括初次全量同步和增量同步两个阶段,为优化复制性能,可以采用AOF持久化、调整复制超时时间、... 目录Redis主从复制的原理主从复制概述配置主从复制数据同步过程复制一致性与延迟故障转移机制监控与维
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2