高并发内存池
本项目基于google的开源项目tcmalloc(Thread-Caching Malloc),是一个能够在高并发情况下依旧保持高效的多线程内存管理项目(对比malloc,free)。1.1池化技术所谓“池化技术”，就是程序先向系统申请过量的资源，然后自己管理，以备不时之需。之所以要申请过量的资源，是因为每次申请该资源都有较大的开销，不如提前申请好了，这样使用时就会变得非常快捷，大大提高程序运行效
目录
项目介绍
本项目基于google的开源项目tcmalloc(Thread-Caching Malloc),是一个能够在高并发情况下
依旧保持高效的多线程内存管理项目(对比malloc,free)。
1.什么是内存池
1.1池化技术
所谓“池化技术”，就是程序先向系统申请过量的资源，然后自己管理，以备不时之需。之所以要申请过量的资源，是因为每次申请该资源都有较大的开销，不如提前申请好了，这样使用时就会变得非常快捷，大大提高程序运行效率。
在计算机中，有很多使用“池”这种技术的地方，除了内存池，还有连接池、线程池、对象池等。以服务器上的线程池为例，它的主要思想是：先启动若干数量的线程，让它们处于睡眠状态，当接收到客户端的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求，线程又进入睡眠状态。
1.2内存池
内存池是指程序预先从操作系统申请一块足够大内存，此后，当程序中需要申请内存的时候，不是直接向操作系统申请，而是直接从内存池中获取；
同理，当程序释放内存的时候，并不真正将内存返回给操作系统，而是返回内存池。当程序退出(或者特定时间)时，内存池才将之前申请的内存真正释放。
2.ptmalloc vs tcmalloc
2.1malloc和free的问题
new/delete用于c++中动态内存管理而malloc/free在c++和c中都可以使用，本质上new/delete底层封装了malloc/free。无论是上面的那种内存管理方式，都存在以下两个问题：
效率问题：频繁的在堆上申请和释放内存必然需要大量时间，降低了程序的运行效率。对于一个需要频繁申请和释放内存的程序来说，频繁调用new/malloc申请内存,delete/free释放内存都需要花费系统时间，频繁的调用必然会降低程序的运行效率。
内存碎片：经常申请小块内存，会将物理内存“切”得很碎，导致内存碎片。申请内存的顺序并不是释放内存的顺序，因此频繁申请小块内存必然会导致内存碎片，造成“有内存但是申请不到大块内存”的现象。
2.2普通内存池的优点和缺点
针对直接使用new/delete、malloc/free存在的问题，普通内存池的设计思路是：预先开辟一块大内存，程序需要内存时直接从该大块内存中“拿”一块，提高申请和释放内存的效率，同时直接分配大块内存还减少了内存碎片问题。
优点：申请和释放内存的效率有所提高；一定程度上解决了内存碎片问题。
缺点：多线程并发场景下申请和释放内存存在锁竞争问题造成申请和释放内存的效率降低。
2.3高并发内存池要解决的问题
基于以上原因，设计高并发内存池需要解决以下三个问题：
效率问题
内存碎片问题
多线程并发场景下的内存释放和申请的锁竞争问题
3.总体设计思路
现代很多的开发环境都是多核多线程，在申请内存的场景下，必然存在激烈的锁竞争问题。malloc本身其实已经很优秀，tcmalloc就是在多线程高并发的场景下更胜一筹，所以这次实现的内存池需要考虑以下几方面的问题。
1.性能问题。
2.多线程环境下，锁竞争问题。 (tcmalloc增加的部分)
3.内存碎片问题。
concurrent memory pool主要由以下3个部分构成：
1. thread cache：线程缓存是每个线程独有的，用于小于256KB的内存的分配，线程从这里申请内存不需要加锁，每个线程独享一个cache，这也就是这个并发线程池高效的地方。 thread cache中的内存不是无穷无尽的，内存不够了线程就去下一层central cache获取。
2. central cache：中心缓存是所有线程所共享，thread cache是按需从central cache中获取的对象。central cache合适的时机回收thread cache中的对象，避免一个线程占用了太多的内存，而其他线程的内存吃紧(起到均衡调度的作用)，达到内存分配在多个线程中更均衡的按需调度的目的。central cache是存在竞争的，所以从这里取内存对象是需要加锁，首先这里用的是桶锁(当多个线程访问同一个桶时加锁)，其次只有thread cache的没有内存对象时才会找central cache，所以这里竞争不会很激烈。
3. page cache：页缓存是在central cache缓存上面的一层缓存，存储的内存是以页为单位存储及分配的，central cache没有内存对象时，从page cache分配出一定数量的page，并切割成定长大小的小块内存，分配给central cache。**当一个span的几个跨度页的对象都回收以后，page cache 会回收central cache满足条件的span对象，并且合并相邻的页，组成更大的页，缓解内存碎片的问题。**当page cache没有缓存之后就会使用系统调用(windows—VirtualAlloc,linux——mmap和brk向系统进行申请堆上的空间。)
4.详细设计
4.1 定长内存池
malloc其实就是一个通用的内存池，在什么场景下都可以使用，但这也意味着malloc在什么场景下都不会有很高的性能，因为malloc并不是针对某种场景专门设计的。定长内存池就是针对固定大小内存块的申请和释放的内存池，由于定长内存池只需要支持固定大小内存块的申请和释放，因此我们可以将其性能做到极致，并且在实现定长内存池时不需要考虑内存碎片等问题，因为我们申请/释放的都是固定大小的内存块。
我们可以通过实现定长内存池来熟悉一下对简单内存池的控制，其次，这个定长内存池后面会作为高并发内存池的一个基础组件。
定长内存池也叫做对象池，在创建对象池时，对象池可以根据传入的对象类型的大小来实现“定长”，因此我们可以通过使用模板参数来实现“定长”，比如创建定长内存池时传入的对象类型是int，那么该内存池就只支持4字节大小内存的申请和释放。
对于向堆申请到的大块内存，我们可以用一个指针来对其进行管理，但仅用一个指针肯定是不够的，我们还需要用一个变量来记录这块内存的长度。
其次，释放回来的定长内存块也需要被管理，我们可以将这些释放回来的定长内存块链接成一个链表，这里我们将管理释放回来的内存块的链表叫做自由链表，为了能找到这个自由链表，我们还需要一个指向自由链表的指针。
因此，定长内存池当中包含三个成员变量：
- _memory：指向大块内存的指针。
- _remainBytes：大块内存切分过程中剩余字节数。
- _freeList：还回来过程中链接的自由链表的头指针
实际代码如下
template<class T>
class ObjectPool
{
public:
T* New()
{
T* obj = nullptr;
// 优先把还回来内存块对象，再次重复利用
if (_freeList)
{
void* next = *((void**)_freeList);
obj = (T*)_freeList;
_freeList = next;
}
else
{
// 剩余内存不够一个对象大小时，则重新开大块空间
if (_remainBytes < sizeof(T))
{
_remainBytes = 128 * 1024;
//_memory = (char*)malloc(_remainBytes);
_memory = (char*)SystemAlloc(_remainBytes >> 13);
if (_memory == nullptr)
{
throw std::bad_alloc();
}
}
obj = (T*)_memory;
size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
_memory += objSize;
_remainBytes -= objSize;
}
// 定位new，显示调用T的构造函数初始化
new(obj)T;
return obj;
}
void Delete(T* obj)
{
// 显示调用析构函数清理对象
obj->~T();
// 头插
*(void**)obj = _freeList;
_freeList = obj;
}
private:
char* _memory = nullptr; // 指向大块内存的指针
size_t _remainBytes = 0; // 大块内存在切分过程中剩余字节数
void* _freeList = nullptr; // 还回来过程中链接的自由链表的头指针
};
4.2 thread cache
thread cache的主要功能就是为每一个线程提供64K以下大小内存的申请。为了方便管理，需要提供一种特定的管理模式，来保存未分配的内存以及被释放回来的内存，以方便内存的二次利用。这里的管理通常采用将不同大小的内存映射在哈希表中，链接起来。而内存分配的最小单位是字节，64k = 1024*64Byte如果按照一个字节一个字节的管理方式进行管理，至少也得需要1024*64大小的哈希表对不同大小的内存进行映射。为了减少哈希表长度，这里采用按一定数字对齐的方式进行内存分配，将浪费率保持在1%~12%之间。具体结构如下：
具体说明如下：
1）使用数组进行哈希映射，每一个位置存放的是一个链表freelists，该链表的作用是将相同大小的内存对象链接起来方便管理。
2）每个数组元素链接的都是不同大小的内存对象。
3）第一个元素表示对齐数是8，第2个是16....依次类推。对齐数表示在上一个对齐数和这个对齐数之间的大小的内存都映射在这个位置，即要申请1字节或者7字节的内存都在索引位置为0出找8字节大小的内存，要申请9~16字节大小的内存都在索引为1的位置找16字节的内存对象。
4）通过上面的分析，可以看出如果进行8字节对齐，最多会浪费7字节的内存（实际申请1字节内存，返回的是8字节大小的内存对象）,将这种现象称为内存碎片浪费。
5）为了将内存碎片浪费保持在12%以下，也就是说最多容忍有12%的内存浪费，这里使用不同的对齐数进行对齐。
6）0~128采用8字节对齐，129~1024采用16字节对齐，1025~8*1024采用128字节对齐，8*1024~64*1024采用1024字节对齐；内存碎片浪费率分别为：1/8，129/136，1025/1032，8102/8199均在12%左右。同时，8字节对齐时需要[0,15]共16个哈希映射；16字节对齐需要[16,71]共56个哈希映射；128字节对齐需要[72,127]共56个哈希映射;1024字节对齐需要[128,184]共56个哈希映射。
7）哈希映射的结构如下：
注意：
每个线程都有一个自己独享的thread cache，那应该如何创建这个thread cache呢？我们不能将这个thread cache创建为全局的，因为全局变量是所有线程共享的，这样就不可避免的需要锁来控制，增加了控制成本和代码复杂度。
要实现每个线程无锁的访问属于自己的thread cache，我们需要用到线程局部存储TLS(Thread Local Storage)，这是一种变量的存储方法，使用该存储方法的变量在它所在的线程是全局可访问的，但是不能被其他线程访问到，这样就保持了数据的线程独立性。
class ThreadCache
{
public:
void* Alloc(size_t size);
void Dealloc(void* ptr, size_t size);
void* FetchFromCentralCache(size_t index,size_t size);
void ListTooLong(FreeList& list, size_t size);
private:
FreeList _freelists[NFREELIST];
};
static _declspec(thread) ThreadCache* pTLSThreadCache = nullptr;//TLS(线程本地储存)void* ThreadCache::Alloc(size_t size)
{
size_t bytes = SizeClass::RoundUp(size);
size_t index = SizeClass::Index(bytes);
void* obj;
if (_freelists[index].Empty())
{
obj = FetchFromCentralCache(index,bytes);
}
else {
obj = _freelists[index].Pop();
}
return obj;
}
void* ThreadCache::FetchFromCentralCache(size_t index,size_t size)
{
//类似调节窗口大小的慢启动算法
// 1、最开始不会一次向central cache一次批量要太多，因为要太多了可能用不完
// 2、如果你不要这个size大小内存需求，那么batchNum就会不断增长，直到上限
// 3、size越大，一次向central cache要的batchNum就越小
// 4、size越小，一次向central cache要的batchNum就越大
size_t& ThresholdValue = _freelists[index].ThresholdValue();
size_t batch = min(ThresholdValue,SizeClass::NumMoveSize(size));
void* start = nullptr; void* end = nullptr;
size_t actualNum= CentralCache::GetInstance()->FetchRangeObj(start,end,batch,size);
assert(actualNum > 0);
if (batch == ThresholdValue)
{
ThresholdValue += 1;
}
if (actualNum == 1)
{
assert(start == end);
return start;
}
else {
_freelists[index].Push(NextObj(start), end,actualNum-1);
}
return start;
}
4.3 central cache
central cache也是一个哈希桶结构，他的哈希桶的映射关系跟thread cache是一样的。不同的是他的每个哈希桶位置挂是SpanList链表结构，不过每个映射桶下面的span中的大内存块被按映射关系切成了一个个小内存块对象挂在span的自由链表中。
thread cache是每个线程独享的，而central cache是所有线程共享的，因为每个线程的thread cache没有内存了都会去找central cache，因此在访问central cache时是需要加锁的。但central cache在加锁时并不是将整个central cache全部锁上了，central cache在加锁时用的是桶锁，也就是说每个桶都有一个锁。此时只有当多个线程同时访问central cache的同一个桶时才会存在锁竞争，如果是多个线程同时访问central cache的不同桶就不会存在锁竞争。
申请内存：
1.当central cache向page cache申请内存时，page cache先检查对应位置有没有span，如果没有则向更大页寻找一个span，如果找到则分裂成两个。比如：申请的是4页page，4页page后面没有挂span，则向后面寻找更大的span，假设在10页page位置找到一个span，则将10页page span分裂为一个4页page span和一个6页page span。
2.如果找到_spanList[128]都没有合适的span，则向系统使用mmap、brk或者是VirtualAlloc等方式申请128页page span挂在自由链表中，再重复1中的过程。
3.需要注意的是central cache和page cache 的核心结构都是spanlist的哈希桶，但是他们是有本质区别的，central cache中哈希桶，是按跟thread cache一样的大小对齐关系映射的，他的spanlist中挂的span中的内存都被按映射关系切好链接成小块内存的自由链表。而page cache 中的spanlist则是按下标桶号映射的，也就是说第i号桶中挂的span都是i页内存。
注意：
当每个线程的thread cache没有内存时都会向central cache申请，此时多个线程的thread cache如果访问的不是central cache的同一个桶，那么这些线程是可以同时进行访问的。这时central cache的多个桶就可能同时向page cache申请内存的，所以page cache也是存在线程安全问题的，因此在访问page cache时也必须要加锁。
但是在page cache这里我们不能使用桶锁，因为当central cache向page cache申请内存时，page cache可能会将其他桶当中大页的span切小后再给central cache。此外，当central cache将某个span归还给page cache时，page cache也会尝试将该span与其他桶当中的span进行合并。
也就是说，在访问page cache时，我们可能需要访问page cache中的多个桶，如果page cache用桶锁就会出现大量频繁的加锁和解锁，导致程序的效率低下。因此我们在访问page cache时使用没有使用桶锁，而是用一个大锁将整个page cache给锁住。
central cache向page cache申请span的页数如何确定？
可以根据具体所需对象的大小来决定，就像之前我们根据对象的大小计算出，thread cache一次向central cache申请对象的个数上限，现在我们是根据对象的大小计算出，central cache一次应该向page cache申请几页的内存块。
根据对象的大小计算出，thread cache一次向central cache申请对象的个数上限，然后将这个上限值乘以单个对象的大小，就算出了具体需要多少字节，最后再将这个算出来的字节数转换为页数，如果转换后不够一页，那么我们就申请一页，否则转换出来是几页就申请几页。
4.4 整体内存的回收
ThreadCache :
- 当释放内存小于256k时将内存释放回thread cache，计算size映射自由链表桶位置i，将对象Push到_freeLists[i]。
- 当链表的长度过长，则回收一部分内存对象到central cache
CentralCache:
当thread_cache过长或者线程销毁，则会将内存释放回central cache中的，释放回来时use_count--。当use_count减到0时则表示所有对象都回到了span，则将span释放回page cache，page cache中会对前后相邻的空闲页进行合并。
有两个要注意的点：1. 接口原因，我们需要通过回收的地址得到地址所在的页号，实际上页号的计算方案是是Page_t _id = (Page_t)ptr<<PAGESGFIT 2. 一个span管理的可能是多个页。为了解决这个问题，我们可以建立页号和span之间的映射。由于这个映射关系在page cache进行span的合并时也需要用到，因此我们直接将其存在一个固定的容器里，之前的代码用的是unorder_map储存，优化代码后把容器换成了基数树(后面会讲)。
void CentralCache::ReleaseListToSpans(void* start, size_t size)
{
size_t index = SizeClass::Index(size);
_spanLists[index]._mtx.lock();
while (start)
{
void* next = NextObj(start);
Span* span = PageCache::GetInstance()->MapObjectToSpan(start);
NextObj(start) = span->_freeList;
span->_freeList = start;
span->_useCount--;
// 说明span的切分出去的所有小块内存都回来了
// 这个span就可以再回收给page cache，pagecache可以再尝试去做前后页的合并
if (span->_useCount == 0)
{
_spanLists[index].Erase(span);
span->_freeList = nullptr;
span->_next = nullptr;
span->_prev = nullptr;
// 释放span给page cache时，使用page cache的锁就可以了
// 这时把桶锁解掉
_spanLists[index]._mtx.unlock();
PageCache::GetInstance()->_pageMtx.lock();
PageCache::GetInstance()->ReleaseSpanToPageCache(span);
PageCache::GetInstance()->_pageMtx.unlock();
_spanLists[index]._mtx.lock();
}
start = next;
}
_spanLists[index]._mtx.unlock();
}PageCache:
- 如果central cache释放回一个span，则依次寻找span的前后page id的没有在使用的空闲span，看是否可以合并，如果合并继续向前寻找。这样就可以将切小的内存合并收缩成大的span，减少内存碎片。
span的前后合并
合并的过程可以分为向前合并和向后合并。因此page cache在合并span时，是需要通过页号获取到对应的span的，这就是我们要把页号与span之间的映射关系存储到page cache的原因。但需要注意的是，当我们通过页号找到其对应的span时，这个span此时可能挂在page cache，也可能挂在central cache。而在合并时我们只能合并挂在page cache的span，因为挂在central cache的span当中的对象正在被其他线程使用。鉴于此，我们可以在span结构中再增加一个_isUse成员，用于标记这个span是否正在被使用，而当一个span结构被创建时我们默认该span是没有被使用的。
由于在合并page cache当中的span时，需要通过页号找到其对应的span，而一个span是在被分配给central cache时，才建立的各个页号与span之间的映射关系，因此page cache当中的span也需要建立页号与span之间的映射关系。与central cache中的span不同的是，在page cache中，只需建立一个span的首尾页号与该span之间的映射关系。因为当一个span在尝试进行合并时，如果是往前合并，那么只需要通过一个span的尾页找到这个span，如果是向后合并，那么只需要通过一个span的首页找到这个span。
需要注意的是，在向前或向后进行合并的过程中：
1.如果没有通过页号获取到其对应的span，说明对应到该页的内存块还未申请，此时需要停止合并。
2.如果通过页号获取到了其对应的span，但该span处于被使用的状态，那我们也必须停止合并。
3.如果合并后大于128页则不能进行本次合并，因为page cache无法对大于128页的span进行管理。
void PageCache::ReleaseSpanToPageCache(Span* span)
{
assert(span);
if (span->_n > NPAGES )
{
void* ptr = (void*)(span->_id << PAGESHFIT);
SystemFree(ptr);
//delete span;
_spanPool.Delete(span);
return;
}
//向前合并
while (1)
{
Pageid_t pid = span->_id - 1;
auto ret = _idSpanMap.get(pid);
if (ret== nullptr)
{
break;
}
// 前面相邻页的span在使用，不合并了
auto pspan = (Span * )ret;
if (pspan->_inuse)
{
break;
}
// 合并出超过128页的span没办法管理，不合并了
if (pspan->_n + span->_n > NPAGES )
{
break;
}
spanlists[pspan->_n].Erase(pspan);
span->_id = pspan->_id;
span->_n += pspan->_n;
_spanPool.Delete(pspan);
pspan = nullptr;
}
//向后合并
while (1)
{
Pageid_t pid = span->_id + span->_n ;
auto ret = _idSpanMap .get(pid);
if (ret == nullptr)
{
break;
}
auto nspan = (Span*)ret;
if (nspan->_inuse)
{
break;
}
if (nspan->_n + span->_n > NPAGES )
{
break;
}
spanlists[nspan->_n].Erase(nspan);
span->_n += nspan->_n;
_spanPool.Delete(nspan);
nspan = nullptr;
}
span->_inuse = false;
_idSpanMap.set(span->_id,span);
_idSpanMap.set(span->_id + span->_n - 1,span);
spanlists[span->_n].PushFront(span);
}
5 代码优化
5.1 大于256KB的大块内存申请问题
5.1.1 使用定长内存池配合脱离使用new
tcmalloc是要在高并发场景下替代malloc进行内存申请的，因此tcmalloc在实现的时，其内部是不能调用malloc函数的，我们当前的代码中存在通过new获取到的内存，而new在底层实际上就是封装了malloc。
为了完全脱离掉malloc函数，此时我们之前实现的定长内存池就起作用了，代码中使用new时基本都是为Span结构的对象申请空间，而span对象基本都是在page cache层创建的，因此我们可以在PageCache类当中定义一个_spanPool，用于span对象的申请和释放。
5.1.2 释放对象时优化为不传对象大小
当我们使用malloc函数申请内存时，需要指明申请内存的大小；而当我们使用free函数释放内存时，只需要传入指向这块内存的指针即可。
而我们目前实现的内存池，在释放对象时除了需要传入指向该对象的指针，还需要传入该对象的大小。如果我们也想做到，在释放对象时不用传入对象的大小，那么我们就需要建立对象地址与对象大小之间的映射。由于现在可以通过对象的地址找到其对应的span，而span的自由链表中挂的都是相同大小的对象。因此我们可以在Span结构中再增加一个_objSize成员，该成员代表着这个span管理的内存块被切成的一个个对象的大小。
5.1.3 malloc 与 tcmalloc对比代码
void BenchmarkMalloc(size_t ntimes, size_t nworks, size_t rounds)
{
std::vector<std::thread> vthread(nworks);
std::atomic<unsigned int> malloc_costtime = 0;
std::atomic<unsigned int> free_costtime = 0;
for (size_t k = 0; k < nworks; ++k)
{
vthread[k] = std::thread([&, k]() {
std::vector<void*> v;
v.reserve(ntimes);
for (size_t j = 0; j < rounds; ++j)
{
size_t begin1 = clock();
for (size_t i = 0; i < ntimes; i++)
{
v.push_back(malloc(16));
//v.push_back(malloc((16 + i) % 8192 + 1));
}
size_t end1 = clock();
size_t begin2 = clock();
for (size_t i = 0; i < ntimes; i++)
{
free(v[i]);
}
size_t end2 = clock();
v.clear();
malloc_costtime += (end1 - begin1);
free_costtime += (end2 - begin2);
}
});
}
for (auto& t : vthread)
{
t.join();
}
cout << nworks << "个线程并发执行" << rounds << " 轮次，每轮次malloc" << ntimes << "次: 花费：" << malloc_costtime << "ms" << endl;
cout << nworks << "个线程并发执行" << rounds << " 轮次，每轮次malloc" << ntimes << "次: 花费：" << free_costtime << "ms" << endl;
cout << nworks << "个线程并发执行" << rounds << " 轮次，每轮次malloc" << ntimes << "次: 花费：" << malloc_costtime+free_costtime << "ms" << endl;
}
// 单轮次申请释放次数 线程数 轮次
void BenchmarkConcurrentMalloc(size_t ntimes, size_t nworks, size_t rounds)
{
std::vector<std::thread> vthread(nworks);
std::atomic<size_t> malloc_costtime = 0;
std::atomic<size_t> free_costtime = 0;
for (size_t k = 0; k < nworks; ++k)
{
vthread[k] = std::thread([&]() {
std::vector<void*> v;
v.reserve(ntimes);
for (size_t j = 0; j < rounds; ++j)
{
size_t begin1 = clock();
for (size_t i = 0; i < ntimes; i++)
{
//v.push_back(ConcurrentAlloc(16));
v.push_back(ConcurrentAlloc((16 + i) % 8192 + 1));
}
size_t end1 = clock();
size_t begin2 = clock();
for (size_t i = 0; i < ntimes; i++)
{
ConcurrentFree(v[i]);
}
size_t end2 = clock();
v.clear();
malloc_costtime += (end1 - begin1);
free_costtime += (end2 - begin2);
}
});
//vthread[k].detach();
}
//cout << nworks << "个线程并发执行" << rounds << " 轮次，每轮次malloc" << ntimes << "次: 花费：" << malloc_costtime << "ms" << endl;
for (auto& t : vthread)
{
t.join();
}
cout << nworks << "个线程并发执行" << rounds << " 轮次，每轮次malloc" << ntimes << "次: 花费：" << malloc_costtime << "ms" << endl;
cout << nworks << "个线程并发执行" << rounds << " 轮次，每轮次free" << ntimes << "次: 花费：" << free_costtime << "ms" << endl;
cout << nworks << "个线程并发执行" << rounds << " 轮次，每轮次malloc" << ntimes << "次: 花费：" << malloc_costtime + free_costtime << "ms" << endl;
}
int main()
{
size_t n = 10;
cout << "==========================================================" << endl;
BenchmarkConcurrentMalloc(10,100 ,1000);
cout << endl << endl;
BenchmarkMalloc(10, 100, 1000);
cout << "==========================================================" << endl;
return 0;
}此时我们发现，本项目实现的内存池比原生的malloc和free的效率要低不少。通过在VS编译器中带有的性能分析的工具的分析，我们发现，原因主要是MapObjectToSpan函数中的锁导致了性能低下。
因此当前项目的瓶颈点就在锁竞争上面，需要解决调用MapObjectToSpan函数访问映射关系时的加锁问题。tcmalloc当中针对这一点使用了基数树进行优化，因为基数树可以做到同时只有一个线程对一个页进行修改(修改部分的代码加了锁，一个页的读写事件并不同时成立，因为当一个页进入写阶段时，说明Span中的 Inuse = false,它已经回到pagecache中了，其他线程无法看见这个span) 使得在读取这个映射关系时可以做到不加锁。
基数树实际上就是一个分层的哈希表，根据所分层数不同可分为单层基数树、二层基数树、三层基数树等。单层基数树实际采用的就是直接定址法，每一个页号对应span的地址就存储数组中在以该页号为下标的位置。
扩展学习及项目实现的不足
不足：首先，实际上在释放内存时，由thread cache将自由链表对象归还给central cache只使用了链表过长这一个条件，但是实际中这个条件大概率不能恰好达成，那么就会出现thread cache中自由链表挂着许多未被使用的内存块，从而出现了线程结束时可能导致内存泄露的问题。解决方法就是使用动态tls或者通过回调函数来回收这部分的内存，并且通过申请批次统计内存占有量，保证线程不会过多占有资源。
tc_malloc实际上替换到系统调用malloc不同平台替换方式不同。 基于unix的系统上的glibc，使用了weak alias的方式替换。具体来说是因为这些入口函数都被定义成了weak symbols，再加上gcc支持 alias attribute，所以替换就变成了这种通用形式：void* malloc(size_t size) THROW attribute__ ((alias (tc_malloc)))。因此所有malloc的调用都跳转到了tc_malloc的实现。GCC attribute 之weak,alias属性。Windows下需要使用hook的钩子技术来做。
完整项目代码：https://gitee.com/ztlink/object.git
瓜分20万奖金 获得内推名额 丰厚实物奖励 易参与易上手
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)