微信号:BitTechnology

介绍:关注比特科技,即时收到C,C++,Linux核心技术文章,抢先了解互联网最新资讯,提早知道IT行业职业规划.

STL空间配置器那点事

2016-06-20 22:39 西安比特教育

STL简介


STL(Standard Template Library,标准模板库),从根本上说,STL是一些“容器”的集合,这些“容器”有list,vector,set,map等,STL也是算法和其他一些组件的集合。


谈及组件,那么我们就首先来简单谈下STL六大组件,其相关的设计模式使用,以及各组件之间的协作关系。

设计模式一览

六大组件简单介绍
  • 空间配置器:内存池实现小块内存分配,对应到设计模式--单例模式(工具类,提供服务,一个程序只需要一个空间配置器即可),享元模式(小块内存统一由内存池进行管理)。

  • 迭代器:迭代器模式,模板方法

  • 容器:STL的核心之一,其他组件围绕容器进行工作:迭代器提供访问方式,空间配置器提供容器内存分配,算法对容器中数据进行处理,仿函数伪算法提供具体的策略,类型萃取  实现对自定义类型内部类型提取。保证算法覆盖性。其中涉及到的设计模式:组合模式(树形结构),门面模式(外部接口提供),适配器模式(stack,queue通过deque适配得到),建造者模式(不同类型树的建立过程)。

  • 类型萃取:基于范型编程的内部类型解析,通过typename获取。可以获取迭代器内部类型value_type,Poter,Reference等。

  • 仿函数:一种类似于函数指针的可回调机制,用于算法中的决策处理。涉及:策略模式,模板方法。

  • 适配器:STL中的stack,queue通过双端队列deque适配实现,map,set通过RB-Tree适配实现。涉及适配器模式。

关于六大组件之间的具体关系如图简单描述:

ps(图技术比较水,见谅,如有bug,请指正)貌似扯的多了,来谈谈主题《空间配置器》问题吧。

STL空间配置器产生的缘由:

在软件开发,程序设计中,我们不免因为程序需求,使用很多的小块内存(基本类型以及小内存的自定义类型)。在程序中动态申请,释放。这个过程过程并不是一定能够控制好的,于是乎,

问题1:就出现了内存碎片问题。(ps外碎片问题)  

问题2:一直在因为小块内存而进行内存申请,调用malloc,系统调用产生性能问题。

注:

内碎片:因为内存对齐/访问效率(CPU取址次数)而产生 如 用户需要3字节,实际得到4或者8字节的问题,其中的碎片是浪费掉的。

外碎片:系统中内存总量足够,但是不连续,所以无法分配给用户使用而产生的浪费。下边简单图解:

这两个问题解释清楚之后,就来谈STL空间配置器的实现细节了

实现策略

用户申请空间大于128?   

yes:调用一级空间配置器    

no:调用二级空间配置器

大致实现为:

  • 二级空间配置由内存池以及伙伴系统:自由链表组成    

  • 一级空间配置器直接封装malloc,free进行处理,增加了C++中的set_handler机制(这里其实也就是个略显牵强的装饰/适配模式了),增加内存分配时客户端可选处理机制。

可配置性

  • 客户端可以通过宏__USE_MALLOC进行自定义选择是否使用二级空间配置器。  

  • 一级空间配置器就主要封装malloc,添加handler机制了,这里就不罗嗦了,相信各位都是可以通过源码了解到的

关于二级空间配置器

最后再罗嗦一点,说说Trace问题,然后就给出代码了。

Trace使用

对于内存池的内部实现过程共还是比较复杂的,虽然代码量,函数比较简单。但是调用过程可能比较复杂。这时,如果我们选择debug调试,过程会相当的繁琐,需要仔细记录调用堆栈过程以及数据流向,逻辑变更等。对于楼主这种水货来说,估计完事就要苦了。

所以,就使用Trace进行跟踪,打印数据流向,逻辑走向,文件,函数,方法,行位置。那么我们就能根据这个记录进行程序的排错以及调优了。

具体Trace简单如下:

#pragma once
#define ___TRACE(...) fprintf(fout, "file[%s]line[%u]func[%s]::",__FILE__,__LINE__,__func__);\fprintf(fout,__VA_ARGS__)

没错,就是这么简单,利用宏打印文件,行,函数位置,然后利用可变参数列表方式接收代码中具体位置的记录跟踪。  如下是代码摘取的Alloc中的跟中。

static void *Allocate(size_t n)    {        ___TRACE("__MallocAllocTemplate to get  n = %u\n",n);        

void *result = malloc(n);        

if (0 == result)        {            result = OomMalloc(n);        }        return result;    }

我的天:组织不好,手速太差,终于前奏完成。那么就给出空间配置器的代码了。  具体也可以在个人的github中获取源码。

https://github.com/langya0/llhProjectFile/tree/master/STL

文件:Alloc.h

文件:Trace.h

#pragma once
#define ___TRACE(...) fprintf(fout, "file[%s]line[%u]func[%s]::",__FILE__,__LINE__,__func__);\fprintf(fout,__VA_ARGS__)

文件Config.h

终于大功告成,源码finished,那么,再给出测试结果截图了

最后,完成了主题工作之后。

再来说一些空间配置器的遗留问题

1仔细探究源码之后,你一定会发现一个问题

貌似二级空间配置器中的空间重头到尾都没看到他归还给系统。那么问题就是,内存池空间何时释放?  对于这个问题,在回头浏览一下源码及结构图,你就会发现大于128的内存,客户程序Deallocate之后会调free释放掉,归还给了系统。但是呢..........

内存池中获取的空间,最终,假定用户都调用Dealloc释放调了,那么他们又在哪里呢?没有还给系统,没有在内存池,在自由链表中。

Got it:程序中不曾释放,只是在自由链表中,且配置器的所有方法,成员都是静态的,那么他们就是存放在静态区。释放时机就是程序结束。

2如果需要释放,那么应该怎么处理呢?

因为真正可以在程序运行中就归还系统的只有自由链表中的未使用值,但是他们并不一定是连续的(用户申请空间,释放空间顺序的不可控制性),所以想要在合适时间(eg一级配置器的handler中释放,或者设置各阀值,分配空间量到达时处理),就必须保证释放的空间要是连续的。保证连续的方案就是:跟踪分配释放过程,记录节点信心。释放时,仅释放连续的大块。

3关于STL空间配置器的效率考究

既然已经存在,而又被广泛使用,那么,整体的效率,以及和STL内部容器之间的使用配合还是没问题的。  我们考虑几种情况:

  • 用户只需要无限的char类型空间,然而配置器中却对齐到8,于是乎,整个程序中就会有7/8的空间浪费。    

  • 对于假定用户申请N次8空间,将系统资源耗到一定程度,然后全部释放了,自由链表中的空间都是连续的。却没有释放。

  • 但是用户需要申请大于8的空间时,却依旧没有空间可用。

总之:这个问题就是,空间可能全部积攒在小块自由链表中,却没有用户可用的。这就尴尬了。  

最后,关于配置器的其它问题,如果各位有什么新的思考,欢迎交流。

END

目前8623人已关注加入我们

 
西安比特教育 更多文章 序列化和反序列化 布隆过滤器(Bloom Filter)详解 深度探索C++对象模型(3) 【比特科技\/CVTE实习生面试经验】 深入探索C++对象模型(2)
猜您喜欢 当今网络最红的神曲---火爆了 线性代数的核心问题分析 就从这鄙视链说起好了 Python 爱好者专用技术头条 运维帮技术沙龙第二期总结及PPT大放送