【高并發內存池】一、簡介定長內存池實現

文章目錄

Ⅰ. 項目介紹
- 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。

template<size_t N>
class fixed_size_pool
{};

? 此外，定長內存池也叫做對象池，在創建對象池時，對象池可以根據傳入的對象類型的大小來實現“定長”，因此我們可以通過使用模板參數來實現“定長”，比如創建定長內存池時傳入的對象類型是 int，那么該內存池就只支持 4 字節大小內存的申請和釋放。

template<class 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, kpage<<13, 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; // 空閑鏈表的頭指針
```
1. _left_size：
  - 表示定長內存池可用部分的剩余大小，因為我們需要向內存池申請空間，那么內存池的空間是不斷變小的，那么最后一次申請的時候，可能會出現越界的情況，所以我們可以使用一個整型變量來記錄當前內存池的大小。
2. _memory：
  - 表示定長內存池可用部分的起始指針，為什么是可用部分而不是整個內存池的起始位置呢，其實也是起始位置，但是這個起始位置是不斷在變化的，這和我們下面的實現有關系，我們需要挪動 _memory 來表示申請了空間！
3. _freelist：
- 表示空閑鏈表的頭指針，它用來鏈接未被使用的內存塊，以方便我們在申請空間的時候無需向內存池拿取，并且達到反復利用的效果，提高利用率和效率！
- 這里我們還要注意一個點，就是因為我們要使用模板，所以傳進來的類型是什么我們并不知道，而 _freelist 是一個指針，32 位為 4 個字節，64 位為 8 個字節，但是如果傳進來的類型是個結構體，大于我們指針可以指的范圍，此時就不對了，有人可能說那么就用一個 T* 指針來指向結構體不就好了，但是我們要明白的是我們以后申請內存塊，可能是不同大小的內存塊，所以不一定是 T 大小結構的內存塊，所以在鏈接自由鏈表的時候，我們統一規則，將內存塊的開頭，大小為一個指針的空間作為鏈接部分，所以要保證這個內存塊的大小要超過 4/8 個字節，否則會出現越界，一般我們都會采取內存對其來防止這種小于 4/8 個字節的情況！連接方式如上圖中所連接的方式是一樣的，下面我們在講成員函數的時候會說到！
成員函數：
- apply()
  1. 這個函數負責申請內存塊，但是首先要判斷一下自由鏈表是否有未使用的內存塊，有的話直接拿來用即可；沒有的話我們需要就得從內存池中拿，注意也是要先判斷，判斷申請的內存塊是否超過了內存池的大小，當大塊內存已經不足以切分出一個對象時，我們就應該調用我們封裝的 SystemAlloc 函數，再次向堆申請一塊內存空間，此時也要注意及時更新 _memory 指針的指向，以及 _leftbytes 的值。
  2. 若成功申請到了內存塊，則使用 定位new 進行初始化，因為我們是先分配了堆空間，所以初始化一般都使用 定位new，以便將內存分配交給內存池管理器來管理。
  3. 而具體在實現如何從空閑鏈表中拿取這個內存塊并不難，就是一個**頭刪操作**！而對于從內存池中拿取就需要配合 _memory 來移動，具體可以看下圖：
  4. 另外還有一個就是當自由鏈表中拿取內存塊的時候，我們之前規定了讓內存塊的前 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()
  1. 釋放已經不想使用的內存塊空間，防止內存塊中一些數據的內存泄漏！
  2. 對于還回來的定長內存塊，我們可以用空閑鏈表將其鏈接起來，但我們并不需要為其專門定義鏈式結構，我們可以讓內存塊的前 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::vector<TreeNode*> 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::vector<TreeNode*> v2;v2.reserve(N);fixed_size_pool<TreeNode> 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 是一個通用的內存池，而定長內存池是專門針對申請定長對象而設計的，因此在這種特殊場景下定長內存池的效率更高，正所謂 “尺有所短，寸有所長”。

在這里插入圖片描述