C++内存管理机制(侯捷)
本文是学习笔记,仅供个人学习使用。如有侵权,请联系删除。
参考链接
Youtube: 侯捷-C++内存管理机制
Github课程视频、PPT和源代码: https://github.com/ZachL1/Bilibili-plus
介绍
下面是第四讲和第五讲的笔记。
第四讲:loki库的allocator
第五讲:other issues,主要介绍GNU C++提供的其他分配器的使用
截至2024年1月12日,花费3天时间完成《C++内存管理——从平地到万丈高楼》的学习。
45 上中下三个classes分析
loki的allocator
Loki 是 C++ 中一个开源的库,其中包含一组通用的 C++ 组件。在 Loki 库中,有一个称为 Loki::Allocator 的组件,它是一个用于内存分配的工具。
讲这个分配器是为了和GNU C++中的alloc分配器作比较,alloc分配器最后的内存并没有还给操作系统。
Loki allocator的三个类,从低阶到高阶分别为:Chunk, FixedAllocator, SmallObjAllocator。
Chunk
pData_: unsigned char* // 指针,指向分配的一个chunk
firstAvailableBlock_:unsigned char // 第一个可用区块
blocksAvailable_: unsigned char // 目前还可以供应几个区块
FixedAllocator
chunks_: vector<Chunk> // vector里面放了很多chunk
// 两个指针,指向某两个Chunk
allocChunk_: Chunk*
deallocChunk_: Chunk*
SmallObjAllocator
pool_: vector<FixedAllocator> // 里面放了很多FixedAllocator
// 两个指针,指向某两个FixedAllocator
pLastAlloc: FixedAllocator*
pLastDealloc: FixedAllocator*
chunkSize: size_t
maxObjectSize: size_t
46 Class Chunk分析
Loki allocator里面的Chunk
Init函数:new调用malloc创建对象,分配一大块chunk
调用Reset函数,下图中可用的block个数为64,第一个可以的block的编号为0,然后一个for循环,把每个block的第一个字节当作索引index使用(类似于嵌入式指针)
还有Release函数,使用delete[],释放空间,还给操作系统。
Chunk的Allocate函数
分配一个可用区块(最高优先权),然后firstAvailableBlock_指向下一个可用区块,比如这里可用区块的索引从左边的4变成了右边的3,剩余区块个数也相应调整。
Chunk的Deallocate函数
释放的指针p已经确定在这个Chunk中,但是p是这个Chunk中的第几个block呢?用p指针减去头指针然后除以每个block的大小,得到该释放的block的索引,这个释放回收的块block具有最高优先权,成为firstAvailableBlock_,然后可利用的block个数+1.
47 class FixedAllocator分析(上)
FixedAllocator
chunks_: vector<Chunk> // vector里面放了很多chunk
// 两个指针,指向某两个Chunk
allocChunk_: Chunk*
deallocChunk_: Chunk*
allocChunk_指向最近一次满足分配动作的Chunk,deallocChunk _指向最近一次回收的Chunk。因为有很多chunk,要指定最近用过的chunk,这符合数据的局部性原理。
Allocate的逻辑如下图所示:如果有最近的allocChunk_,那么直接取区块,否则就要for循环从头开始遍历每个chunk,直到找到有可用空间的chunk。return allocChunk->Allocate(blockSize_);
是向这个chunk取区块。
48 class FixedAllocator分析(下)
第二级FixedAllocator类的Deallocate函数,调用VicinityFind函数查找还回来的指针p落在哪个chunk,找到之后交给第一级Chunk类的Deallocate来处理。
VicinityFind(临近搜寻)函数如下:功能是进行查找。
chunkLength是chunk的大小,后面查找的时候要用
lo是上次还回来的chunk,hi是下一个chunk
loBound和hiBound是vector的头跟尾
整体思路是:兵分两路,一路往上查找,一路往下查找。
在lo里面找,找不到的话就往上面的chunk去查找,一直往上,一个接一个的chunk去找。
然后在hi里面找,找不到就往下面的chunk去查找,一直往下,一个接一个的chunk去找。
下面是FixedAllocator类的DoDeallocate函数
调用Deallocate函数进行回收,然后确认是否是全回收的情况处理。
全回收的时候,需要确认有2个chunk,才回收一个,就是上文讲到的deferring延缓回收。
49 Loki::allocator总结
很简单的方式判断chunk全回收,指的是记录可用区块个数,当它变成0的时候表示全分配出去,当它恢复到原来的状态,就表示可全回收。
50 GNU C++对allocators的描述
第五讲 other issues
GNU C++ 对于allocator的描述
下面介绍两个分配器: new_allocator 和malloc_allocator,它们都没有特别的动作,无非底部调用operator new和malloc。它们没有用内存池。
另一种做法是使用智能型的allocator,使用内存池,分一大块然后切分成小块。
这类allocator有bitmap_allocator, pool_allocator, _mt_alloc(multithread多线程的分配器)
GNU C++ 提供三种测试,用于测速:插入数据测试,多线程状态下的插入和删除测试,多线程的生产者和消费者模型测试。
另外两个智能型allocator是 debug_allocator 和 array_allocator
51 VS2013标准分配器&G4.9标准分配器与new_allocator以及G4.9malloc
VS2013版本的标准分配器allocator,里面的allocate函数就是调用operator new,底层调用malloc,这是一种没有包装的分配器。
GNU C++4.9版本的标准分配器 allocator,继承自new_allocator,里面的动作也是operator new 和operator delete,也是没有包装的分配器。
GNU C++4.9版本的malloc_allocator,里面就是调用malloc和free,没有包装。
52 G4.9array_allocator
array_allocator
指针_M_array指向一个C++数组,静态数组不需要释放,归还
看看array_allocator怎么使用
int my[65536];
array_allocator<int, array<int, 65536>> myalloc(&my); // 传入数组的地址
第二种用法,是用动态的new一块数组,其他用法与上面一致。
53 G4.9 debug_allocator
debug_allocator是一个包装器,把另一个分配器包装进来,这里是_Alloc分配器,定义为_M_allocator,实际分配的时候就是调用这个分配器的allocate,分配n + extra个大小的空间。
GNU C++2.9容器使用的不是std::allocator,而是std::alloc,这是一个好的分配器。
在GNU C++4.9版本的__pool_alloc就是上面2.9版本的alloc。它的缺点是什么呢?只拿不还,不把分配的空间还给操作系统。
GNU C++4.9版本 __pool_alloc测试用例
54 bitmap_allocator上
这里重要的是_M_allocate_single_object
和_M_deallocate_single_object
,这是什么意思呢?所有的allocator都是供给容器使用的,容器每次请求的都是一个元素的内存分配,所以这里就是单独处理一个object的请求。当不是一个object的时候,就会退化到operator new和operator delete,但是这种情况一般遇不到。
当客户是容器的使用,容器要的一个元素的内存空间就是block,如果是std::list的时候,这个block还包括node里面的指针。
下图中64blocks指的是一次性挖64个blocks开始供应,这个是两倍成长,下次挖128个,再是256个,…
挖的这些blocks,加上前面的bitmap,还有前面的数值,一起称为super block。
bitmap中是64bits(对应于blocks的数量),每个bit表示单个block的状态,bitmap是unsigned int,一个bitmap是32位,只能记录32个blocks的情况。这里是64个blocks,需要2个bitmap来记录。
前面还有一个整数use count,记录有几个block被分配
最前面还有一个整数,记录super block的大小
有一个mini vector(模拟标准库中的vector写出来的)来操纵super block,里面的start指针和finish指针分别指向super block的头和尾
现在客户需要分配内存:下面深灰色这个block被分配出去,use count = 1,然后bitmap[0]最后一位变成0,表示已经分配出去
然后请求分配第二个block,下面两个灰色的block表示被分配出去,use count = 2,bitmap[0]后两位变成0,表示这两个block被分配出去。
后面一直分配block出去,下图表示已经分配出去63个block,对应的use count = 63,bitmap[1]和bitmap[0]变成80000000H和00000000H,只有最后一个block对应的bitmap中的bit才为1,表示未被分配出去。
下面客户归还其中一个block,对应的bitmap要变成1,表示未分配(回收回来),然后use count由63变成62
当1个super block(有64个blocks)用完后,开始启用第二号super block,这时候super block中的block块数由64扩大两倍变成128个,由4个bitmap整数表示。
而且mini vector中由一个单元,变成两个单元,每个单元指向一个super block。
第二个super block用完(前面已经用完第一个super block,其含有64个blocks,第二个super block包含128个blocks,也已经用完),启用第三个super bloc,其包含的blocks为128 x 2 = 256个。
mini vector中也有第三个单元来控制这个super block。
55 bitmap_allocator(下)
上面谈的是bitmap_allocator的分配,下面谈它的回收(容器归还元素空间)机制
第一个super block全回收,用另一个mini vector(称为free list)中的entry指针指向这个super block,表示已经回收。
如果下次新分配一个super block,它其中blocks的数量要减半,如下图所示,如果前三个superblocks大小分别为64个,128个,256个,由于第一个superblock被回收,那么下次分配的superblock大小由已经分配的最大值256变成一半,为128个blocks。
原来的mini vector里面的指向回收的这个superblock头和尾的entry被删除。
第二个super block也全回收,则free list里的entry加一个,指向这个super block。
原来的mini vector里面指向这个superblock头尾的entry被删除。
第三个super block被全回收,被free list的指针指向。
文章来源:https://www.toymoban.com/news/detail-784852.html
后记
截至2024年1月12日22点09分,完成《C++内存管理机制》的第四讲和第五讲的笔记。主要涉及Loki库中allocator的设计,以及对GNU C++4.9其他allocator的介绍,主要包含bitmap_allocator。文章来源地址https://www.toymoban.com/news/detail-784852.html
到了这里,关于C++内存管理机制(侯捷)笔记4(完结)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!