设计商城网站建设,价格营销策略案例,小程序连接wordpress,网站设计咨询电话文章目录Ⅰ. 项目介绍1、这个项目要做什么2、项目的要求Ⅱ. 什么是内存池1、池化技术2、内存池3、mallocⅢ. 设计一个定长内存池1、定长内存池的概念2、实现如何实现定长❓❓❓如何绕开 malloc 向堆直接申请空间❓❓❓3、性能测试Ⅰ. 项目介绍
1、这个项目要做什么
tcmalloc源…
文章目录Ⅰ. 项目介绍1、这个项目要做什么2、项目的要求Ⅱ. 什么是内存池1、池化技术2、内存池3、mallocⅢ. 设计一个定长内存池1、定长内存池的概念2、实现如何实现定长❓❓❓如何绕开 malloc 向堆直接申请空间❓❓❓3、性能测试Ⅰ. 项目介绍
1、这个项目要做什么
tcmalloc源代码
当前项目是实现一个高并发的内存池他的原型是 google 的一个开源项目 tcmalloc全称为 Thread-Caching Malloc即线程缓存的 malloc实现了高效的多线程内存管理用于替代系统的内存分配相关的函数比如 malloc 和 free。
我们这个项目是把 tcmalloc 最核心的框架简化后拿出来模拟实现出一个自己的高并发内存池目的就是学习 tcamlloc 的精华这种方式有点类似我们之前学习 STL 容器的方式。但是相比 STL 容器部分tcmalloc 的代码量和复杂度上升了很多。
另一方面 tcmalloc 是全球大厂 google 开源的可以认为当时顶尖的 C 高手写出来的他的知名度也是非常高的不少公司都在用它Go 语言直接用它做了自己内存分配器。所以很多程序员是熟悉这个项目的那么有好处也有坏处。好处就是把这个项目理解扎实了会很受面试官的认可。坏处就是面试官可能也比较熟悉项目对项目会问得比较深比较细。如果你对项目掌握得不扎实那么就容易碰钉子。
2、项目的要求
这个项目会用到 C/C、数据结构链表、哈希桶、操作系统内存管理、单例模式、多线程、互斥锁等等方面的知识。
Ⅱ. 什么是内存池
1、池化技术
所谓 “池化技术”就是程序先向系统申请过量的资源然后自己管理以备不时之需。之所以要申请过量的资源是因为每次申请该资源都有较大的开销不如提前申请好了这样使用时就会变得非常快捷大大提高程序运行效率。
在计算机中有很多使用“池”这种技术的地方比如内存池、连接池、线程池、对象池等。以服务器上的线程池为例它的主要思想是先启动若干数量的线程让它们处于睡眠状态当接收到客户端的请求时唤醒池中某个睡眠的线程让它来处理客户端的请求当处理完这个请求线程又进入睡眠状态。
2、内存池
内存池Memory Pool是指程序预先从操作系统申请一块足够大内存此后当程序中需要申请内存的时候不是直接向操作系统申请而是直接从内存池中获取同理当程序释放内存的时候并不真正将内存返回给操作系统而是返回内存池。当程序退出或者特定时间时内存池才将之前申请的内存真正释放。
内存池通常由两个部分组成内存池管理器 和 内存块分配器它们的作用如下所示
内存池管理器负责管理内存池的大小和内存块的分配和释放。内存块分配器则负责分配和释放内存块。
内存池的优点包括
提高内存分配效率内存池可以减少频繁的内存分配和释放操作从而提高内存分配效率。减少内存碎片由于内存池中的内存块大小固定因此不会产生内存碎片从而减少了内存碎片的产生。提高程序性能内存池可以减少动态内存分配和释放操作从而减少了内存管理的开销提高了程序性能。简化代码实现内存池可以简化代码实现减少了内存管理相关的代码量。
尽管内存池可以提高程序性能和减少内存碎片的产生但是它的 缺点是需要预先分配一定数量的内存因此会占用一定的内存空间。此外如果内存池的大小预估不足可能会导致内存不够用的情况。因此在使用内存池时需要根据实际需求进行合理的配置。
这里需要补充说明的是内存碎片分为 外碎片 和 内碎片。
外碎片是一些空闲的连续内存区域太小这些内存空间不连续以至于合计的内存足够但是不能满足一些的内存分配申请需求内碎片 是由于一些对齐的需求导致分配出去的空间中一些内存无法被利用。内碎片的问题我们后面项目中就会看到。
3、malloc
C/C中我们要动态申请内存都是通过 malloc 去申请内存但是我们要知道实际上并不是直接去堆中获取内存的因为malloc 就是一个内存池。它相当于向操作系统预先申请了一块较大的内存空间然后按需分配给程序用。当全部用完或者程序有大量的内存需求时再根据实际需求向操作系统申请内存。
malloc 的实现方式有很多种一般不同编译器平台用的都是不同的。比如 Windows 的 vs 系列用的微软自己写的一套Linux gcc 用的 glibc 中的 ptmalloc。下面有几篇关于这块的文章大概可以去简单看看了解一下关于 ptmalloc学完我们的项目以后有兴趣大家可以去看看他的实现细节。
一文了解Linux内存管理malloc、free 实现原理
malloc()背后的实现原理——内存池
malloc的底层实现ptmalloc
Ⅲ. 设计一个定长内存池
1、定长内存池的概念
我们知道申请内存使用的是 malloc但 malloc 其实就是一个通用的大众货什么场景下都可以用但是什么场景下都可以用就意味着什么场景下都不会有很高的性能。下面我们就先来设计一个定长内存池做个开胃菜当然这个定长内存池在我们后面的高并发内存池中也是有价值的所以学习他目的有两层先熟悉一下简单内存池是如何控制的第二它会作为我们后面内存池的一个基础组件。
定长内存池是一种内存池技术它能够提高内存管理效率同时避免了动态内存分配和释放造成的内存碎片问题。与传统的内存池不同定长内存池中的内存块大小是固定的即所有内存块的大小都相同。定长内存池 和 动态内存分配 是两种不同的内存分配方式它们的主要区别如下 内存块大小 定长内存池中的内存块大小是固定的而动态内存分配中的内存块大小可以是不同的。 内存分配方式 定长内存池在程序启动时预先分配一定数量的内存块并将这些内存块放入一个空闲内存块链表中。当程序需要分配内存时从空闲内存块链表中取出一个内存块。而动态内存分配则是在程序运行时根据需要动态分配内存块。 内存分配效率 由于定长内存池中的内存块大小固定因此分配和释放内存块的效率比动态内存分配要高。动态内存分配需要进行内存分配和释放的操作这些操作都需要耗费额外的时间和内存开销。 内存碎片 由于定长内存池中的内存块大小固定因此不存在内存碎片问题而动态内存分配中会因为内存块大小不同导致内存碎片的产生。
总的来说定长内存池适用于需要频繁分配和释放同种类型的内存块的场景可以提高内存分配效率减少内存碎片的产生但需要预先分配一定数量的内存块。动态内存分配适用于需要灵活分配内存的场景可以根据需要动态分配内存但需要进行动态内存分配和释放的操作会产生额外的时间和内存开销。
它们的使用场景如下图所示 2、实现
如何实现定长❓❓❓
在实现定长内存池时要做到“定长”有很多种方法比如我们可以使用非类型模板参数使得在该内存池中申请到的对象的大小都是 N。
templatesize_t N
class fixed_size_pool
{}; 此外定长内存池也叫做对象池在创建对象池时对象池可以根据传入的对象类型的大小来实现“定长”因此我们可以通过使用模板参数来实现“定长”比如创建定长内存池时传入的对象类型是 int那么该内存池就只支持 4 字节大小内存的申请和释放。
templateclass T
class fixed_size_pool
{};如何绕开 malloc 向堆直接申请空间❓❓❓
既然是内存池那么我们首先得向系统申请一块内存空间然后对其进行管理。要想直接向堆申请内存空间在 Windows 下可以调用 VirtualAlloc 函数在 Linux 下可以调用 brk 或 mmap 函数。
这里我们可以通过条件编译将对应平台下向堆申请内存的函数进行封装此后我们就不必再关心当前所在平台当我们需要直接向堆申请内存时直接调用我们封装后的 SystemAlloc 函数即可。
#ifdef _WIN32#include Windows.h
#else//...
#endif//直接去堆上申请按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr VirtualAlloc(0, kpage13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else// linux下brk mmap等
#endifif (ptr nullptr)throw std::bad_alloc();return ptr;
}首先我们来思考一下如何让一个指针在 32 位平台下解引用后能向后访问 4 个字节在 64 位平台下解引用后能向后访问 8 个字节 ❓❓❓
首先我们得知道32 位平台下指针的大小是 4 个字节64 位平台下指针的大小是 8 个字节。而指针指向数据的类型决定了指针解引用后能向后访问的空间大小因此我们这里需要的是一个指向指针的指针这里使用二级指针就行了。
当我们需要访问一个内存块的前 4/8 个字节时我们可以 将内存块的地址强转为二级指针由于二级指针存储的是一级指针的地址二级指针解引用能向后访问一个指针的大小因此在 32 位平台下访问的就是 4 个字节在 64 位平台下访问的就是 8 个字节此时我们访问到了该内存块的前 4/8 个字节。
void* get_next(void* ptr)
{// 函数返回值为void*类型的引用是因为这个函数返回的是指针的引用即返回的是指针本身的地址而不是指针所指向的对象的地址。// 这样做的好处是可以通过修改函数返回值来修改指针本身所指向的地址从而实现对空闲链表的修改头插和头删的需要return (*(void**)ptr);
}需要注意的是在释放对象时我们应该显示调用该对象的析构函数清理该对象因为该对象可能还管理着其他某些资源如果不对其进行清理那么这些资源将无法被释放就会导致内存泄漏。下面的 release() 会讲到 下面我们设计的简易定长内存池包括以下几个方面 成员变量 private:size_t _left_size 0; // 定长内存池可用部分的剩余大小char* _memory nullptr; // 定长内存池可用部分的起始指针使用char类型是为了切内存块的时候更精细方便void* _freelist nullptr; // 空闲链表的头指针_left_size 表示定长内存池可用部分的剩余大小因为我们需要向内存池申请空间那么内存池的空间是不断变小的那么最后一次申请的时候可能会出现越界的情况所以我们可以使用一个整型变量来记录当前内存池的大小。 _memory 表示定长内存池可用部分的起始指针为什么是可用部分而不是整个内存池的起始位置呢其实也是起始位置但是这个起始位置是不断在变化的这和我们下面的实现有关系我们需要挪动 _memory 来表示申请了空间 _freelist 表示空闲链表的头指针它用来链接未被使用的内存块以方便我们在申请空间的时候无需向内存池拿取并且达到反复利用的效果提高利用率和效率这里我们还要注意一个点就是因为我们要使用模板所以传进来的类型是什么我们并不知道而 _freelist 是一个指针32 位为 4 个字节64 位为 8 个字节但是如果传进来的类型是个结构体大于我们指针可以指的范围此时就不对了有人可能说那么就用一个 T* 指针来指向结构体不就好了但是我们要明白的是我们以后申请内存块可能是不同大小的内存块所以不一定是 T 大小结构的内存块所以在链接自由链表的时候我们统一规则将内存块的开头大小为一个指针的空间作为链接部分所以要保证这个内存块的大小要超过 4/8 个字节否则会出现越界一般我们都会采取内存对其来防止这种小于 4/8 个字节的情况连接方式如上图中所连接的方式是一样的下面我们在讲成员函数的时候会说到 成员函数 apply() 这个函数负责申请内存块但是首先要判断一下自由链表是否有未使用的内存块有的话直接拿来用即可没有的话我们需要就得从内存池中拿注意也是要先判断判断申请的内存块是否超过了内存池的大小当大块内存已经不足以切分出一个对象时我们就应该调用我们封装的 SystemAlloc 函数再次向堆申请一块内存空间此时也要注意及时更新 _memory 指针的指向以及 _leftbytes 的值。 若成功申请到了内存块则使用 定位new 进行初始化因为我们是先分配了堆空间所以初始化一般都使用 定位new以便将内存分配交给内存池管理器来管理。 而具体在实现如何从空闲链表中拿取这个内存块并不难就是一个**头删操作**而对于从内存池中拿取就需要配合 _memory 来移动具体可以看下图 另外还有一个就是当自由链表中拿取内存块的时候我们之前规定了让内存块的前 4 个字节或前 8 个字节作为指针存储后面内存块的起始地址。所以访问的时候需要一个二级指针或者用判断语句这里使用二级指针的方式 // 向定长内存池申请一个T对象的空间
T* apply()
{T* obj nullptr;// 1. 如果可以的话直接从空闲链表中获取空闲的空间if (_freelist ! nullptr){// 就是一个链表头删的操作obj (T*)_freelist;_freelist get_next(_freelist);return obj;}// 2. 剩余内存不够一个对象大小时则重新开大块空间int size sizeof(T) sizeof(void*) ? sizeof(void*) : sizeof(T); // 防止申请空间不足一个指针的大小要最少开辟一个指针大小的空间if (_left_size size){// 剩余内存不够一个对象大小时则重新开大块空间_left_size 128 * 1024;_memory (char*)SystemAlloc(_left_size 13);if (_memory nullptr)throw std::bad_alloc(); // 申请空间失败的话就抛异常}// 3. 从内存池中取出一个对象的空间然后处理一下指针和大小即可obj (T*)_memory;_left_size - size;_memory size;// 4. 进行定位new操作调用对象的构造函数进行初始化最后进行返回即可new(obj)T;return obj;
}release() 释放已经不想使用的内存块空间防止内存块中一些数据的内存泄漏 对于还回来的定长内存块我们可以用空闲链表将其链接起来但我们并不需要为其专门定义链式结构我们可以让内存块的前 4 个字节或前 8 个字节作为指针存储后面内存块的起始地址即可。因此在向空闲链表插入被释放的内存块时先让该内存块的前 4 个字节或 8 个字节存储空闲链表中第一个内存块的地址可存储的原因是它们已经是空闲的不被使用的所以才能直接对它们的内存块进行操作然后再让 _freeList 指向该内存块即可也就是一个简单的链表头插操作。如下图所示 // 释放T对象的空间
void release(T* obj)
{// 1. 先调用对象的析构函数进行内部数据的释放obj-~T();// 2. 再进行空闲链表的头插操作get_next(obj) _freelist;_freelist obj;
} 空闲链表 FreeList 是一种常见的内存管理技术主要用于管理动态内存分配的空闲内存块。空闲链表通常是一种链表结构存储着当前未被使用的内存块当需要分配内存时可以从空闲链表中取出一个内存块进行使用当需要释放内存时将内存块放回空闲链表中。 空闲链表的实现方式通常是在程序启动时预先分配一定数量的内存块并将这些内存块放入一个空闲内存块链表中。当程序需要分配内存时从空闲内存块链表中取出一个内存块当程序需要释放内存时将内存块放回空闲内存块链表中。在使用空闲链表时需要注意内存块的大小和对齐方式以避免内存浪费和对齐问题。 优点 避免内存碎片由于空闲链表中的内存块大小相同因此不会产生内存碎片问题。提高内存分配效率由于空闲链表中的内存块已经被预先分配因此内存分配时无需再进行耗时的系统调用可以提高内存分配效率。简单易用空闲链表的实现相对简单易于理解和使用。 缺点 内存浪费由于空闲链表中的内存块大小是固定的因此可能会出现内存浪费的问题即内存块大小与应用程序需要的大小不匹配。内存池管理由于空闲链表需要预先分配一定数量的内存块因此需要对内存池进行管理包括内存池大小、内存块大小、内存块对齐方式等。静态内存分配空闲链表通常需要在程序启动时进行预先分配因此不适用于需要动态分配内存的场景。 完整代码
#pragma once
#include iostream
#include vector
using std::cout;
using std::endl;#ifdef _WIN32
#include Windows.h
#else
//...
#endif//直接去堆上申请按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32void* ptr VirtualAlloc(0, kpage 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else// linux下brk mmap等
#endifif (ptr nullptr)throw std::bad_alloc();return ptr;
}template class T
class fixed_size_pool
{
private:size_t _left_size 0; // 定长内存池可用部分的剩余大小char* _memory nullptr; // 定长内存池可用部分的起始指针使用char类型是为了切内存块的时候更精细方便void* _freelist nullptr; // 空闲链表的头指针
public:// 向定长内存池申请一个T对象的空间T* apply(){T* obj nullptr;// 1. 如果可以的话直接从空闲链表中获取空闲的空间if (_freelist ! nullptr){// 就是一个链表头删的操作obj (T*)_freelist;_freelist get_next(_freelist);return obj;}// 2. 剩余内存不够一个对象大小时则重新开大块空间int size sizeof(T) sizeof(void*) ? sizeof(void*) : sizeof(T); // 防止申请空间不足一个指针的大小要最少开辟一个指针大小的空间if (_left_size size){// 剩余内存不够一个对象大小时则重新开大块空间_left_size 128 * 1024;_memory (char*)SystemAlloc(_left_size 13);if (_memory nullptr)throw std::bad_alloc(); // 申请空间失败的话就抛异常}// 3. 从内存池中取出一个对象的空间然后处理一下指针和大小即可obj (T*)_memory;_left_size - size;_memory size;// 4. 进行定位new操作调用对象的构造函数进行初始化最后进行返回即可new(obj)T;return obj;}// 释放T对象的空间void release(T* obj){// 1. 先调用对象的析构函数进行内部数据的释放obj-~T();// 2. 再进行空闲链表的头插操作get_next(obj) _freelist;_freelist obj;}void* get_next(void* ptr){// 函数返回值为void*类型的引用是因为这个函数返回的是指针的引用即返回的是指针本身的地址而不是指针所指向的对象的地址。// 这样做的好处是可以通过修改函数返回值来修改指针本身所指向的地址从而实现对空闲链表的修改头插和头删的需要return (*(void**)ptr);}
};3、性能测试
// 测试数据
struct TreeNode
{int _val;TreeNode* _left;TreeNode* _right;TreeNode(): _val(0), _left(nullptr), _right(nullptr){}
};void TestObjectPool()
{// 申请释放的轮次const size_t Rounds 5;// 每轮申请释放多少次const size_t N 100000;// 测试new和delete的速度std::vectorTreeNode* v1;v1.reserve(N);size_t begin1 clock();for (size_t j 0; j Rounds; j){for (int i 0; i N; i)v1.push_back(new TreeNode);for (int i 0; i N; i)delete v1[i];v1.clear();}size_t end1 clock();// 测试我们实现的内存池的速度std::vectorTreeNode* v2;v2.reserve(N);fixed_size_poolTreeNode TNPool;size_t begin2 clock();for (size_t j 0; j Rounds; j){for (int i 0; i N; i)v2.push_back(TNPool.apply());for (int i 0; i N; i)TNPool.release(v2[i]);v2.clear();}size_t end2 clock();cout new cost time: end1 - begin1 endl;cout fixed_size_pool cost time: end2 - begin2 endl;
}// 运行结果
// debug下
new cost time:149
fixed_size_pool cost time:37// release下
new cost time:31
fixed_size_pool cost time:2在代码中我们先用new申请若干个 TreeNode 对象然后再用 delete 将这些对象再释放通过 clock 函数得到整个过程消耗的时间。new 和 delete 底层就是封装的 malloc 和 free
然后再重复该过程只不过将其中的 new 和 delete 替换为定长内存池当中的 apply 和 release此时再通过 clock 函数得到该过程消耗的时间。
可以看到在这个过程中定长内存池消耗的时间比 malloc/free 消耗的时间要短。这就是因为 malloc 是一个通用的内存池而定长内存池是专门针对申请定长对象而设计的因此在这种特殊场景下定长内存池的效率更高正所谓 “尺有所短寸有所长”。
