美文网首页
关于STL内存管理的一点琐事(下)

关于STL内存管理的一点琐事(下)

作者: zhou的技术小庄园 | 来源:发表于2021-07-31 11:52 被阅读0次

前言

关于STL内存管理,不仅仅限于他的做法,也不仅仅使用于STL,他的一些思想和优秀的做法值得我们每一个工程师去参考、借鉴,并在此基础上添加一些属于你的技术元素。考虑到现在在读的你没有使用过STL的容器,更不知道其内部构造,所以导致你对内存管理这件事云里雾里,其实这些都没关系,你可以花十五分钟去了解就足够了。作者计划写一些关于STL中,各种容器的底部支撑相关的文章,比如从简单的array(数组),vector(一种动态数组),list(采用双向链表),deque(双向队列),stack(底部支撑可以是list和deque),queue(底部支撑位deque),set(RB-tree),multiset(RB-tree),hash-set(hash-table)等等,作者相信网上也有许多关于这些技术的讲解,各位也可以先参考。作者认为,仅仅学习一些工具的使用对于有些工程师而言这就足够了,但是对于一个有追求的工程师而言,不仅仅要会用,也要会知道底层原理。今后慢慢的,这些相关的文章会慢慢发布(如果工作之余,还有时间的话,作者会慢慢整理出来的)。

OK,言归正常,回到我们自己的主题——STL内存管理(分配器),上一章讲过,STL自己写了一套一级分配器叫(allcator),但是这个第一级分配器基本上不用的,这一章我们讲的是关于STL的二级分配器,也是作者认为,非常棒的一种做法,如何棒呢?他对内存的使用,对申请的内存有较为偏执的使用,对内存有着最大化的利用,如今作者在工作时刚好也接触到这方面的业务,刚刚好对比着去分析。

同样的,我们这些内容也需要一些前置知识(你至少使用过STL里面得一种容器,你得熟悉模板,你得熟悉c++基本语法,你得知道一些在常用编译器下,由分配器分配的内存,其内存模型是怎么样的。)本部分分为以下三个部分:1,关于内存相关的知识。2,标准库二级分配器的做法。3,在此之上的一些反思。

1,内存

关于内存分配,大家在学习相关知识的时候,都学过:如果我们要new一个内存,如果我们不用的话,需要将其释放掉(delete),因为我们new的内存在heap上拿的,那么就需要自己手动释放,如果在stack上的拿的,不需要自己释放,在其生命周期结束时,自然其就归还了。当然我们还学过,如果我们是new一个数组空间大小,如果我们不用的话,就需要用数组的方式去释放

例如:

class apple{

apple (int a):app(a){}

private:

int app;

};

apple* p = new apple(3);

......一系列操作

delete p;

如果是:

apple* p = new apple[5];

........一系列操作

delete[] p;

那为什么要进行上述操作呢?为什么delete前面,一个加了[],一个不加呢?其实,我们调用new的时候(底层也是调用malloc),我们得到的内存其实并不是我们想的那么简单,我们简单来看一下调用new,我们得到的内存长什么样:

指针指向的那个位置才是我们真正得到的内存地址,他上面还会有一个header,(那个header其实更加的复杂,他其中一个功能就是记录这一块内存的大小,这个涉及到另一个话题(操作系统下的内存管理,与我们现在讲的STL内存管理方向不符,有时间的话,作者也会写一下操作系统内存管理))。我们每调用一次new,就会产生像上面的那样的内存,但每一次分配的内存,总是带着一额外的内存开销(header),可能一次两次,那种开销不算什么,但是如果上百万次的内存分配,那种开销其实是非常大的,那么我们来看一下,真正在STL中,他的二级分配器是如何解决这种额外开销的:

2,实现

enum {align = 8};//对齐

enum {max_size  = 128};//小区块的最大长度

enum {n_free_list = max_size / align};//free_list最大长度

//第一参数代表是否是多线程,这个不在我们话题,有时间作者会慢慢讲解多线程的东西

template<bool threads,int ints>

class alloc_template{

    private:

    static size_t round_up(size_t size)

    {

        return (((size) + align -1) & ~(align-1));//将传入的size上调到8的倍数

    }

    private:

    //联合体,这个是使用嵌入式指针的形式,关于什么是嵌入式指针,读者自行去查

    union obj{

        union obj *free_list_next;

    }

    private:

    static obj *free_list[n_free_list] ={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

    static size_t free_list_index(size_t bytes)

    {

        retrun (((bytes) + align-1)/align-1);

    }

    //返回一个大小为n的对象,并可能加入大小为你的其他区块到free_list

    static void *refill(size_t n);

    //内存池,配置nobjs个大小为size的区块

    static char *chunk_alloc(size_t size,int &nobjs);

    //内存池的首指针

    static char * start_free = NULL;

    //内存池的尾指针

    static char * end_free = NULL;

    public:

    //内存分配

    static void * allocate(size_t n);

    //回收内存

    static void deallocate(void *p,size_t n);

    //重注内存

    static void * reallocate(void *p,size_t old_size,size_t new_size);

};

//内存分配

template<bool threads , int ints>

static void * alloc_template<threads,ints>::allocate(size_t n)

{

    obj** my_free_list = NULL;

    obj* result;

    if (n > (size_t)max_size)

    {

        //回到第一级分配器,第一章讲过

        return allocate(n);

    }

    my_free_list = free_list + free_list_index(n);

    result = *my_free_list;

    if (NULL == result)

    {

        void *r = refill(round_up(n));

        return r;

    }

    //调整free_list

    *my_free_list = result -> free_list_next;

    return (result);

}

//释放函数

template<bool threads , int ints>

static void alloc_template<threads,ints>::deallocate(void * p,size_t n)

{

    obj *q = (obj*)p;

    obj ** my_free_list = NULL:

    if (n > (size_t)max_size)

    {

        //这里调用第一级的空间释放函数,但这里并没有写出来

        /*

        malloc_alloc::deallocate(p,n);

        return;

        */

    }

    my_free_list = free_list + free_list_index(n);

    q-> free_list_next = *my_free_list;

    *my_free_list = q;

}

//重新填充

template<bool threads ,int ints>

void * alloc_template<threads,ints>::refill(size_t n)

{

    int nobjs = 20;

    char * chunk = chunk_alloc(n,nobjs);

    obj **my_free_list = NULL;

    obj *result = NULL;

    obj *current = NULL;

    obj *next = NULL;

    int i;

    if (1 == nobjs)

    {

        retrun (chunk);

    }

    my_free_list = free_list + free_list_index(n);

    result = (obj*)chunk;

    *my_free_list = next = (obj*)(chunk + n);

    for (i = 1; ; i++)

    {

        current =next;

        next = (obj*)((char*)next + n);

        if (i == nobjs -1)

        {

            current ->free_list_next = NULL;

            break;

        }

        else

        {

            current ->free_list_next =next;

        }

    }

    return result;

}

//内存池的设计

template<bool threads ,int ints>

char * alloc_template<threads,ints>::chunk_alloc(size_t size,int & nobjs)

{

    char *result = NULL;

    size_t total_bytes = size * nobjs;

    size_t bytes_left  = end_free - start_free;//内存池还剩多少

    //不够全部

    if (bytes_left >=total_bytes)

    {

        result = start_free;

        start_free += total_bytes;

        return result;

    }

    else if (bytes_left >= size)//只够一个

    {

        nobjs = bytes_left/size;

        total_bytes = size * nobjs;

        result = start_free;

        start_free += total_bytes;

        return result;

    }

    else//一个也无法满足了

    {

        size_t bytes_to_get = 2 * total_bytes;//这里操作给出了一个追加量,但是这里省去了,因为我觉得没必要

        //尝试让剩余内存还有利用价值

        if (bytes_left > 0)

        {   

            obj **my_free_list = free_list + free_list_index(bytes_left);

            ((obj*)start_free)->free_list_next = *my_free_list;

            *my_free_list = (obj*)start_free;

        }

    }

    //配置内存空间.看!!!这里居然调用malloc!!神奇吧!

    //其实,这个这这里太正常不够了,我们几乎所以的内存管理,几乎都是建立在malloc之上的,也就是我们是踩在巨人的肩膀了干事

    start_free = (char*)malloc(bytes_to_get);

    if (NULL == start_free)

    {

        //开始在free_list中找空余的空间

        int i;

        obj **my_free_list = NULL;

        obj *p = NULL;

        for (i = size; i <= max_size; i += align)

        {

            my_free_list = free_list + free_list_index(i);

            p = * my_free_list;

            if (NULL != p)

            {

                *my_free_list = p->free_list_next;

                start_free = (char*)p;

                end_free = start_free + i;

                //递归调用自己

                retrun (chunk_alloc(size,nobjs));

            }

        }

    //就连free_list中都没有空间可利用了

    end_free = NULL;

    //这里调用第一级分配器,第一章写过!这里调用的allocate是第一级的,不是上面那个其注意!!!!名字一样,那是我懒得改了!!!

    start_free = (char*)allocate(bytes_to_get);

    //这里本来有一个追加量的,但是我觉得没必要,多此一举,就没有写。

    end_free = start_free + bytes_to_get;

    return (chunk_alloc(size,nobjs));

    }

}

3,反思

我们可以从上述看出,其实STL回收的内存,并没有归还给操作系统,而是一直在自己free_list链表中。那为什么我再标题二中说,STL中的内存分配少了额外的开销呢?其实关键在于那个嵌入式指针的设计上。简单来说,那个嵌入式指针,即可以当指针来用,也可以作为数据填充单元,闲时,当做指针,需要使用了,那个指针将会被覆盖,被当成数据单元来使用,这样,他就可以使用内存池,一下子分配一大堆内存,然后使用嵌入式指针将每一小区块链接起来,需要用到了,在分配出去。这样,不就省掉了那个header了嘛?但是缺点就是,没有将回收的内存归还给操作系统,而是在自己手中,这个其实是可以改进的。

到此呢,我们关于STL的内存管理就完结了,当然有不完善的地方,就是代码中没有写注释,不是不写,而是给读者有自己的思考过程,为什么那部分代码要那样写,这个需要读者自己去思考的,在思考过程中不妨去画个图,是自己能深入理解(可以结合上述我画的那个图,继续增删查改!!!)

相关文章

  • 关于STL内存管理的一点琐事(下)

    前言 关于STL内存管理,不仅仅限于他的做法,也不仅仅使用于STL,他的一些思想和优秀的做法值得我们每一个工程师去...

  • 关于STL内存管理的一点琐事(上)

    前言: (前置知识:你至少使用过STL里面得一种容器,你得熟悉模板,你得熟悉c++基本语法) 以程序员使用STL的...

  • STL内存管理详细分析

    STL中内存管理非常精妙,本文以SGI STL为例,分析其内存管理的设计思路,也是对侯捷老师的《STL源码剖析》中...

  • 玩一玩vector吧~

    (关于前几篇文章埋下的坑) 自作者开始浅谈STL以来,虽然只出过STL的内存管理方式,但是讲到的东西真的远远不及他...

  • 一些面试题记录

    STL1、对STL有哪些了解2、STL中的内存管理3、什么是函数对象,用在哪些情况4、用过哪些STL算法5、基本容...

  • STL源码解析-空间配置器

    STL源码解析-空间配置器 STL中非常重要的一个模块就是空间配置器,用来管理程序内存的。 空间配置器 这是stl...

  • linux内核

    虚拟内存的作用? 虚拟内存的实现? 操作系统层面对内存的管理? 内存池的作用?STL里[内存池如何实现] 进程空间...

  • 栈的三种实现

    一、基于deque实现 优点:利用deque动态管理内存,栈的内存无上限,STL中的栈也是基于deque实现的。 ...

  • Swift 内存管理

    Swift 内存管理 [TOC] 前言 本文将介绍一下Swift中的内存管理,关于内存的一些基础知识可以参考我以前...

  • 内存管理

    内存管理 关于内存的描述

网友评论

      本文标题:关于STL内存管理的一点琐事(下)

      本文链接:https://www.haomeiwen.com/subject/pqnhvltx.html