C++內存池的簡單實現

Posted on by

一、內存池基礎知識

1、什麼是內存池

1.1 池化技術

池化技術是計算機中的一種設計模式，主要是指：將程序中經常要使用的計算機資源預先申請出來，由程序自己管理，程序在使用時直接從“池”中獲取，不僅保證瞭程序占有的資源數量同時減少資源的申請和釋放時間。常見的池化技術有內存池、線程池、連接池等。

1.2 內存池

內存池是一種動態內存分配與管理技術。它的核心思想是：預先申請一段內存空間，使用一種高效的數據結構（哈希、鏈表）進行管理，當程序需要內存時直接從內存池中分配一塊內存給程序，同樣當使用完時在歸還給內存池。這樣做的好處是，減少直接使用new/delete、malloc/free等API申請和釋放內存的時間，提高程序運行效率；同時，程序每次直接使用new/delete、malloc/free從內存中申請空間，會導致內存碎片問題，內存池直接申請大塊內存就減少瞭內存碎片。

2、內存池的作用

2.1 效率問題

通常申請內存都是通過new/delete、malloc/free接口直接從內存的堆區申請一塊內存，釋放也是直接釋放到堆中。頻繁的申請和釋放必然消耗大量時間，降低程序的運行效率。

例如：假設每個鏈表的節點大小為16字節，當鏈表需要經常插入節點時，必然就需要頻繁的內存申請操縱，每次從堆中申請16個字節都要一定的時間開銷，釋放內存也需要時間開銷。使用內存池，我們可以直接從內存中申請“一批節點”，當程序需要內存時不用直接去堆中申請，直接將預先申請好的內存分配給程序。

2.2 內存碎片

頻繁的從內存中申請小塊內存會導致內存碎片問題。內存碎片分為內碎片和外碎片兩種。

1）外碎片

外碎片也就是我們常說的內存碎片。例如：我們每次從內存中申請一塊16字節大小的內存，內存中就會存在很多16個字節大小的塊，當該內存釋放時就可能造成內存碎片，如下圖：

內存中空閑內存大小為88字節，但是我們能申請的最大內存塊為21字節。

2）內碎片

內碎片是指已經分配出去的內存中存在的未使用的小塊內存。內存池技術雖然解決瞭內存隨便但是又造成瞭內碎片問題，內碎片不可避免但是可以通過程序的優化減少內存內碎片。

例如：實際需要是申請10byte的內存，定長內存池可能會進行內存對齊，一次性分配瞭16個字節的內存，多餘的6字節實際並未使用，這6字節就是內存內碎片。

3、內存池技術的演進

1）最最最最“簡單”的內存池

做一個鏈表，指向空閑的內存。分配就是從鏈表中取出來一塊返回pop,釋放就是將內存在push到鏈表中。需要做好歸並，標記和保護，防止內存二次釋放問題。

2）定長內存池

實現一個FreeList類，它的本質是一個鏈表，節點是一塊固定大小的內存，采用頭插和頭刪的方式申請釋放內存。每個固定內存分配器裡面有兩個鏈表：OpenList用於存儲未分配的空閑內存對象（FreeList對象），CloseList用於存儲已經分配的內存對象。

分配內存就是從IOpenLsit中取出一個對象給程序，釋放內存就是將對象push到CloseList裡。當內存不夠時，OpenList申請一個大塊內存在切割成固定的長度大小的小塊內存。

3）C++STL庫中的內存池

定長內存池存在的問題就是隻能申請固定長度的內存，而實際中我們需要申請的內存大小可能是不管固定，在C++STL庫中，采用哈希表和定長內存池結合的方式實現瞭一個內存池。具體如下

構造多個定長內存池，以一個固定的對齊數進行對齊（例如以8字節進行對齊），第一個定長內存池的內存對象大小為8（至少得能保證無論在64位還是32位系統下都可以保存下一個指針類型），第二個內存池對象大小為16…最後一個內存池對象大小為128byte，當申請的內存大小超過128字節時，通過二級空間配置器申請（直接從內存中申請）。

構造一個哈希表，將不同大小的內存對象掛在哈希表中。如下圖：

申請內存：加入要申請的內存大小為8字節直接在index  = 0處分配一塊內存，當然申請的內存小於8字節時也會直接分配8字節的內存。當Free_list[index]為nullptr時從內存中申請一塊內存，切割成固定大小‘掛在’Free_list[index]位置。

釋放內存：根據內存對象大小，計算index在插入到哈希表中的index位置。

二、簡易內存池原理

1、整體設計

1.1 內存池結構

兩個鏈表，RequestMemory和ReleaseMemory。

RequestMemory鏈表存儲的是使用new或者malloc從物理內存申請的還沒有被使用的內存塊，是一個個的memNode節點。

ReleaseMemory鏈表存儲的是使用完釋放回來的固定大小的內存塊。

1.2 申請內存

  •  先在ReleaseMemory找，如果有內存則直接pop使用
  • ReleaseMemory為nullptr時，在RequestMemory中找。
  • RequestMemory的頭節點表示的是新申請的，申請內存時隻需要在頭結點中找，判斷頭結點的useCount和sumCount是否相等。當useCount等於sumCount時表示已經用完瞭，就需要去物理內存中申請，否則直接從表頭push一塊。
  • 去物理內存申請內存時，申請的大小是上一次申請內存塊大小的二倍，並將申請的內存塊push到RequestMemory頭部。

1.3 釋放內存

釋放內存時，直接將要釋放的內存push到ReleaseMemory的頭部即可。

2、詳細剖析

2.1 blockNode結構

blockNode表示一個個新申請的內存塊，用一個結構體進行管理。blockNode成員如下：

  • void* _memory：表示新申請的內存塊的首地址
  • BlockNode * _next：存儲next節點
  • _objNum：內存塊對象的個數

註意：blockNode的大小每次都是上一次的二倍，是一個質數增長，因此應該設置一個上限，當到達一定大小後進行線性增長。這裡規定，最大內存塊的大小為100000*sizeof(T),T表示的是申請的節點類型。

2.2 單個對象的大小

這裡的單個對象指的ReleaseMemory的節點大小，當用戶申請的內存大小sizeof(T)小於sizeof(T*)時，為瞭能夠將該對象鏈接到ReleaseMemory中，應該按照T*進行分配。

3、性能比較

分別使用malloc/free、new/delete、memPool申請和釋放110000個內存，時間如下：

三、簡易內存池完整源碼

#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
 
template<class T>
class MemPool
{
private:
	//內存塊結構
	typedef struct BlockNode
	{
		void* _memory;//內存塊地址
		BlockNode* _next;//下一個blockNode
		size_t _objNum;//內存塊對象的個數
		//構造函數---num表示申請對象的個數
		BlockNode(size_t num)
			:_objNum(num),
			_next(nullptr)
		{
			_memory = malloc(_objNum*_size);
		}
 
		~BlockNode()
		{
			free(_memory);
			_memory = nullptr;
			_next = nullptr;
			_objNum = 0;
		}
	}BlockNode;
protected:
	static size_t _size;//單個對象的大小
	T* _releaseMemory = nullptr;//釋放的內存
	BlockNode* _requestMemory;//申請的內存塊
	size_t _maxNum;//內存塊最大的大小
	size_t _useCount;//當前內存塊已經使用的對象個數
protected:
	//設置單個對象的大小
	static size_t setSize()
	{
		return (sizeof(T) >= sizeof(T*) ? sizeof(T):sizeof(T*));
	}
public:
	MemPool()
		:_useCount(0),
		_releaseMemory(nullptr),
		_maxNum(100000*_size)
	{
		//開始先申請32個_size大小的空間
		_requestMemory = new BlockNode(32);
	}
 
	~MemPool()
	{
		BlockNode *cur = _requestMemory;
		while (cur)
		{
			BlockNode* del = cur;
			cur = cur->_next;
			delete del;            //會自動調用~BlockNode()
		}
	}
 
	T* New()
	{
		//先在releaseMemory中找
		if (_releaseMemory)
		{
			T* obj = _releaseMemory;
			_releaseMemory = *((T**)_releaseMemory);//releaseMemory的前幾個字節存儲的是下一個節點的地址
			return obj;
		}
		else
		{
			//判斷requesetMemory中是否還有空閑內存
			if (_requestMemory->_objNum == _useCount)
			{
				//取物理內存中申請一塊內存
				size_t size = 2 * _useCount >= _maxNum ? _maxNum : 2 * _useCount;
				BlockNode* newBlock = new BlockNode(size);
 
				newBlock->_next = _requestMemory;
				_requestMemory = newBlock;
				_useCount = 0;
			}
			//走到這裡，一定有內存
			T* obj = (T*)((char*)_requestMemory->_memory+_useCount*_size);
 
			_useCount++;
			return new(obj)T();//用定位new對這塊空間初始化
		}
	}
 
	void Delete(T* obj)
	{
		if (obj)
		{
			obj->~T();
 
			*((T**)obj) = _releaseMemory;
			_releaseMemory = obj;
		}
	}
};
 
//靜態成員變量，類外初始化
template<typename T>
size_t MemPool<T>::_size = MemPool<T>::setSize();
 
struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;
};
void test1()
{
	MemPool<TreeNode> mp;
 
	vector<TreeNode*> v;
	for (int i = 0; i < 10; i++)
	{
		TreeNode* mem = mp.New();
		v.push_back(mem);
	}
 
	for (int i = 0; i < 10; i++)
	{
		mp.Delete(v[i]);
	}
}

到此這篇關於C++內存池的簡單實現的文章就介紹到這瞭,更多相關C++ 內存池內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：