C++ STL空间配置源码分析以及实现一

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/80560066

本文主要内容如下:
1. STL为什么需要空间配置器
2. STL空间配置器实现的原理
3. STL空间配置器简单的测试

前言

很久以前看过侯捷先生的STL源码分析一书,也大致明白了STL实现的原理,但是对于编程而言,如果自己不去实现代码,调试代码,光看书,其实很难深刻的理解STL源码的逻辑(光是看书顶多也就是了解的水平,当然这是对于一般的程序员而言)。前段时间决定实现一下STL相关的容器(用到了C++11新特性),从而更加深入的理解STL,并提升自己的C++ 模板编程的功底。

先给出一张测试空间配置的运行截图(CLion + cmake):

首先本文给出的是类alloc的实现

class alloc{
//............
}

下篇blog给出allocator的实现(allocator主要是把上面的alloc作为静态的成员,做了一些简单的封装),并给出使用配置器allocator完成一个基本的vector(SimpleVec).

template<class T>
class allocator{
//..................
}

template <class T, class Alloc = allocator<T>>
class SimpleVec{
//.....
}

1. STL为什么需要空间配置器

程序中我们经常动态申请,释放内存,这会带来如下两个问题:

  • 问题1:就出现了内存碎片问题。(包括外碎片问题)
  • 问题2:一直在因为小块内存而进行内存申请,调用malloc,系统调用产生性能问题。

内碎片:因为内存对齐/访问效率(CPU取址次数)而产生 如 用户需要3字节,实际得到4或者8字节的问题,其中的碎片是浪费掉的。 外碎片:系统中内存总量足够,但是不连续,所以无法分配给用户使用而产生的浪费。下边简单图解


2. STL空间配置器实现的原理

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

  if 用户申请空间 > 128:
      调用一级空间配置器
  else:
       调用二级空间配置器

大致实现为:

二级空间配置器由内存池以及伙伴系统:自由链表组成 一级空间配置器直接封装malloc,free进行处理,增加了C++中的set_handler机制(这里其实也就是个略显牵强的装饰/适配模式了),增加内存分配时客户端可选处理机制。

二级空间配置器:

成员以及接口定义如下:

class alloc{
private:
   enum EAlign{ ALIGN = 8};//小型区块的上调边界
   enum EMaxBytes{ MAXBYTES = 128};//小型区块的上限,超过的区块由malloc分配
//free-lists的个数
   enum ENFreeLists{ NFREELISTS = (EMaxBytes::MAXBYTES / EAlign::ALIGN)}; 
enum ENObjs{ NOBJS = 20};//每次增加的节点数
private:
   //free-lists的节点构造
   union obj{
      union obj *next;
      char client[1];
   };

   static obj *free_list[ENFreeLists::NFREELISTS];
private:
   static char *start_free;//内存池起始位置
   static char *end_free;//内存池结束位置
   static size_t heap_size;//
private:
   //将bytes上调至8的倍数,例如 (1, 3, 7) -> 8, (9, 13) -> 16
   static size_t ROUND_UP(size_t bytes){
      return ((bytes + EAlign::ALIGN - 1) & ~(EAlign::ALIGN - 1));
   }
   //根据区块大小,决定使用第n号free-list,n从0开始计算
   //例如 (1, 3, 7) -> 0, (9, 13) -> 1
   static size_t FREELIST_INDEX(size_t bytes){
      return (((bytes)+EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
   }
   //返回一个大小为n的对象,并可能加入大小为n的其他区块到free-list
   static void *refill(size_t n);
   //配置一大块空间,可容纳nobjs个大小为size的区块
   //如果配置nobjs个区块有所不便,nobjs可能会降低
   static char *chunk_alloc(size_t size, size_t& nobjs, int print_count=1);

public:
   static void *allocate(size_t bytes);//分配内存
   static void deallocate(void *ptr, size_t bytes);//内存回收
   // 回收旧内存,分配新内存
   static void *reallocate(void *ptr, size_t old_sz, size_t new_sz);
};

首先空间配置会将<128字节的大小转化为8的倍数,分析如下:

// 将任意的整数调整为8的倍数

void test_or_align(){
    int a =(5 + 8 - 1) & ~(8 - 1);
    int b =(9 + 8 - 1) & ~(8 - 1);
    int c =(13 + 8 - 1) & ~(8 - 1);
    int d =(17 + 8 - 1) & ~(8 - 1);
    cout<<a<<endl;  // 8  (5 -》 8)
    cout<<b<<endl;  // 16  (9 -》 16)
    cout<<c<<endl;  // 16   (13 -》 16)
    cout<<d<<endl;  // 24    (17 -》 24)
}

8的倍数转化为free_list的index,分析如下:

void test_freelist_index(){
    size_t bytes = 5;
    size_t idx = (((bytes) + EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
    std::cout<<idx<<endl;  //0

    bytes = 13;
    idx = (((bytes) + EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
    std::cout<<idx<<endl; // 1

}

初始化:指针数组全部为空:

char *alloc::start_free = 0;
char *alloc::end_free = 0;
size_t alloc::heap_size = 0;

alloc::obj *alloc::free_list[alloc::ENFreeLists::NFREELISTS] = {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
};

首先分析,内存分配allocate函数(注意下面的printf主要是为了分析代码的输出)

void *alloc::allocate(size_t bytes){

    if (bytes > EMaxBytes::MAXBYTES){//分配大于128字节的内存,直接分配返回
        printf("%sallocate size: %d greater than 128, use malloc\n", s4space.c_str(), bytes);
        return malloc(bytes);
    }
    size_t round_up = ROUND_UP(bytes);//输出round up的大小(这里没有意义仅仅输出查看)
    printf("allocate size: %d. after round up size is: %d \n", bytes, round_up);

 //定位bytes应该分配到那个链表中
    size_t index = FREELIST_INDEX(bytes);
    obj *list = free_list[index];
    if (list){//此list还有空间给我们
        printf("free_list has free node, index is: %d\n", index);
        free_list[index] = list->next;//使当前空闲节点指向下一个
        return list;
    }
    else{//此list没有足够的空间,需要从内存池里面取空间
        return refill(ROUND_UP(bytes));
    }
}

可以看到:

1. 当需要的内存 > 128字节,分配器alloc直接free对应的内存
2. 当小于 128 字节,则直接在free_list里面查找看是否有内存可用
3. 2中如果满足不了,则需要在内存池中获取
至于refill后面我们在看。

下面给出deallocate的使用:

void alloc::deallocate(void *ptr, size_t bytes){
    if (bytes > EMaxBytes::MAXBYTES){//大于128的节点直接free释放
        free(ptr);
    }
    else{//小于128的节点重新分配给free_list(不释放内存)
        size_t index = FREELIST_INDEX(bytes);
        obj *node = static_cast<obj *>(ptr);
        node->next = free_list[index];
        free_list[index] = node;
    }
}
1 > 128字节的直接free
2 < 128字节,首先定位到free_list然后指针移位即可

refill代码如下:

//返回一个大小为n的对象,并且有时候会为适当的free list增加节点
//假设bytes已经上调为8的倍数
void *alloc::refill(size_t bytes){
    size_t nobjs = ENObjs::NOBJS; // 默认为free_list bytes节点分配20个元素空间
    //从内存池里取,nobjs可能没有20个,因此参数是引用
    char *chunk = chunk_alloc(bytes, nobjs);
    obj **my_free_list = 0;
    obj *result = 0;
    obj *current_obj = 0, *next_obj = 0;
    printf("%srefill %d, objs\n", s4space.c_str(), nobjs);

    if (nobjs == 1){//取出的空间只够一个对象使用
        return chunk;
    }
    else{
        my_free_list = free_list + FREELIST_INDEX(bytes);
        result = (obj *)(chunk);//首个节点直接返回
//剩余的节点分配到对应的free_list中去
        *my_free_list = next_obj = (obj *)(chunk + bytes);
        //将取出的多余的空间加入到相应的free list里面去
        for (int i = 1;; ++i){
            current_obj = next_obj;
            next_obj = (obj *)((char *)next_obj + bytes);
            if (nobjs - 1 == i){
                current_obj->next = 0;//最后一个指针next 赋值null
                break;
            }
            else{
                current_obj->next = next_obj;
            }
        }
        return result;
    }
}

接下来chunk_alloc函数:

//假设bytes已经上调为8的倍数
char *alloc::chunk_alloc(size_t bytes, size_t& nobjs, int print_count){
    char *result = 0;
    size_t total_bytes = bytes * nobjs;
    size_t bytes_left = end_free - start_free;//当前有多少剩余的内存
    printf("%schunk_alloc round: %d,  need total_bytes: %d,  bytes_left: %d\n",
           s4space.c_str(), print_count, total_bytes, bytes_left);

    if (bytes_left >= total_bytes){//内存池剩余空间完全满足需要
        result = start_free;
        start_free = start_free + total_bytes;
        printf("%schunk_alloc round: %d, cater all, return %d objs bytes_left: %d >= total_bytes: %d\n",
               s8space.c_str(), print_count, nobjs, bytes_left, total_bytes);

        return result;
    }//内存池剩余空间不能完全满足需要,但足够供应一个或以上的区块
    else if (bytes_left >= bytes){
        nobjs = bytes_left / bytes;
        total_bytes = nobjs * bytes;

        result = start_free;
        start_free += total_bytes;
        printf("%schunk_alloc round: %d, cater part, return %d objs, size: %d return %d bytes\n",
               s8space.c_str(), print_count, nobjs, bytes, total_bytes);

        return result;
    }
    else{//内存池剩余空间连一个区块的大小都无法提供,重新申请
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        printf("%schunk_alloc round: %d, malloc %d\n",
               s8space.c_str(), print_count, bytes_to_get);

        if (bytes_left > 0){//将原有的剩余的bytes分配给free_list
            obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((obj *)start_free)->next = *my_free_list;
            *my_free_list = (obj *)start_free;
        }
// start_free 重新分配
        start_free = (char *)malloc(bytes_to_get);
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;//每次只会递归一次
        return chunk_alloc(bytes, nobjs, ++print_count);
    }
}
1. 默认的返回给free_list 20个bytes,如果有则直接返回,
   没有则能返回多少个bytes就返回多少个。

2. 满足不了1,则内存中申请需要内存的两倍。

3. STL空间配置器简单的测试

测试函数如下:

void test_alloc_2(){
    void * ptr;
    size_t n = 10;
    ptr = alloc::allocate(n);
    cout<<"\n===========================\n"<<endl;
    void * ptr2;
    size_t n2 = 18;
    ptr2 = alloc::allocate(n2);

    cout<<"\n===========================\n"<<endl;
    void * ptr3;
    size_t n3 = 10;
    ptr3 = alloc::allocate(n3);

    cout<<"\n===========================\n"<<endl;
    void * ptr5;
    size_t n5 = 7;
    ptr5 = alloc::allocate(n5);

    cout<<"\n===========================\n"<<endl;
    void * ptr4;
    size_t n4 = 26;
    ptr4 = alloc::allocate(n4);

    cout<<"\n===========================\n"<<endl;
    void * ptr6;
    size_t n6 = 47;
    ptr6 = alloc::allocate(n6);

    cout<<"\n===========================\n"<<endl;
    void * ptr7;
    size_t n7 = 5;
    ptr7 = alloc::allocate(n7);

    alloc::deallocate(ptr, n);
    alloc::deallocate(ptr2, n2);
    alloc::deallocate(ptr3, n3);
    alloc::deallocate(ptr4, n4);
    alloc::deallocate(ptr5, n5);
    alloc::deallocate(ptr6, n6);
    alloc::deallocate(ptr7, n7);
}

1.ptr = alloc::allocate(n);输出如下:

2 size_t n2 = 18;

ptr2 = alloc::allocate(n2); 输出如下:

allocate size: 18. after round up size is: 24
chunk_alloc round: 1,  need total_bytes: 480,  bytes_left: 320
chunk_alloc round: 1, cater part, return 13 objs, size: 24 return 312 bytes
refill 13, objs

默认需要20 * 24个元素,但是内存池中还有320个字节剩余,因此返回 320/24=13个元素。

3 接下来

size_t n3 = 10; ptr3 = alloc::allocate(n3); 输出如下:

allocate size: 10. after round up size is: 16
free_list has free node, index is: 1

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

Linux命令(12)——wc命令

(3)从文件读取输入文件名。如果有多个文件名,并且希望 wc 从一个文件中读取它们,那么使用-files0-from 选项。这里将文件名称必须以NULL字符结束...

11710
来自专栏数据小魔方

ggplot2学习笔记之——ggplot2主题调整系统

ggplot2绘图系统拥有庞大、健全的图形美化系统,这一套图形美化依赖于图例调整系统、标度调整系统、标签调整系统、主题调整系统以及分面系统。 本节仅从主题调整系...

31550
来自专栏一个会写诗的程序员的博客

一致性(连续性)hash算法(Consistent hashing)一致性(连续性)hash算法(Consistent hashing)

Consistent hashing is a scheme that provides hash table functionality in a way t...

14320
来自专栏Laoqi's Linux运维专列

正则扩展练习

grep命令的-P选项: 最典型的用法是,匹配指定字符串之间的字符。 比如,我们想在一句话(Hello,my name is aming.)中匹配中间的一段字符...

41660
来自专栏CSDN技术头条

使用Go语言来理解Tensorflow

【译者注】本文通过一个简单的Go绑定实例,让读者一步一步地学习到Tensorflow有关ID、作用域、类型等方面的知识。以下是译文。 Tensorflow并不是...

281100
来自专栏小白安全

【PHP】WEBSHELL各类变形方法总结

简介 WebShell的变形技术与各种防护软件的检测方法一直都在相互对抗,本篇文章就对目前常见的WebShell的变形技术进行总结。 ...

58170
来自专栏deepcc

JavaScript检测IE浏览器(最短代码)

45880
来自专栏区块链入门

【链安科技】EOS资产Asset乘法运算溢出漏洞

asset是EOS官方头文件中提供的用来代表货币资产(如官方货币EOS或自己发布的其它货币单位)的一个结构体。在使用asset进行乘法运算(operator *...

10530
来自专栏ascii0x03的安全笔记

PySide——Python图形化界面入门教程(四)

PySide——Python图形化界面入门教程(四)               ——创建自己的信号槽               ——Creating Yo...

361100
来自专栏丁科的专栏

pytorch 学习笔记之编写 C 扩展

在之前的文章中,我们已经了解了如何自定义 Module。这篇主要讲解pytorch利用 CFFI 进行 C 语言扩展。包括两个基本的步骤(docs):编写 C ...

1K00

扫码关注云+社区

领取腾讯云代金券