🎇C++學(xué)習(xí)歷程：入門

---

• 博客主頁：一起去看日落嗎
• 持續(xù)分享博主的C++學(xué)習(xí)歷程
• 博主的能力有限，出現(xiàn)錯誤希望大家不吝賜教
• 分享給大家一句我很喜歡的話： 也許你現(xiàn)在做的事情，暫時看不到成果，但不要忘記，樹🌿成長之前也要扎根，也要在漫長的時光🌞中沉淀養(yǎng)分。靜下來想一想，哪有這么多的天賦異稟，那些讓你羨慕的優(yōu)秀的人也都曾默默地翻山越嶺🐾。

---

🍁 🍃 🍂 🌿

---

🌿1. 性能瓶頸分析

經(jīng)過前面的測試可以看到，我們的代碼此時與malloc之間還是有差距的，此時我們就應(yīng)該分析分析我們當(dāng)前項目的瓶頸在哪里，但這不能簡單的憑感覺，我們應(yīng)該用性能分析的工具來進行分析。

• VS編譯器下性能分析的操作步驟

VS編譯器中就帶有性能分析的工具的，我們可以依次點擊“調(diào)試→性能和診斷”進行性能分析，注意該操作要在Debug模式下進行。

同時我們將代碼中n的值由10000調(diào)成了1000，否則該分析過程可能會花費較多時間，并且將malloc的測試代碼進行了屏蔽，因為我們要分析的是我們實現(xiàn)的高并發(fā)內(nèi)存池。

在點擊了“調(diào)試→性能和診斷”后會彈出一個提示框，我們直接點擊“開始”進行了。

然后會彈出一個選項框，這里我們選擇的是第二個，因為我們要分析的是各個函數(shù)的用時時間，然后點擊下一步。

出現(xiàn)以下選項框繼續(xù)點擊下一步。

最后點擊完成，就可以等待分析結(jié)果了。

• 分析性能瓶頸

通過分析結(jié)果可以看到，光是Deallocate和MapObjectToSpan這兩個函數(shù)就占用了一半多的時間。

而在Deallocate函數(shù)中，調(diào)用ListTooLong函數(shù)時消耗的時間是最多的。

在ListTooLong函數(shù)中，調(diào)用ReleaseListToSpans函數(shù)時消耗的時間是最多的。

在ReleaseListToSpans函數(shù)中，調(diào)用MapObjectToSpan函數(shù)時消耗的時間是最多的。

也就是說，最終消耗時間最多的實際就是MapObjectToSpan函數(shù)，我們這時再來看看為什么調(diào)用MapObjectToSpan函數(shù)會消耗這么多時間。通過觀察我們最終發(fā)現(xiàn)，調(diào)用該函數(shù)時會消耗這么多時間就是因為鎖的原因。

因此當(dāng)前項目的瓶頸點就在鎖競爭上面，需要解決調(diào)用MapObjectToSpan函數(shù)訪問映射關(guān)系時的加鎖問題。tcmalloc當(dāng)中針對這一點使用了基數(shù)樹進行優(yōu)化，使得在讀取這個映射關(guān)系時可以做到不加鎖。

---

🌿2. 針對性能瓶頸使用基數(shù)樹進行優(yōu)化

基數(shù)樹實際上就是一個分層的哈希表，根據(jù)所分層數(shù)不同可分為單層基數(shù)樹、二層基數(shù)樹、三層基數(shù)樹等。

• 單層基數(shù)樹

單層基數(shù)樹實際采用的就是直接定址法，每一個頁號對應(yīng)span的地址就存儲數(shù)組中在以該頁號為下標的位置。

最壞的情況下我們需要建立所有頁號與其span之間的映射關(guān)系，因此這個數(shù)組中元素個數(shù)應(yīng)該與頁號的數(shù)目相同，數(shù)組中每個位置存儲的就是對應(yīng)span的指針。

//單層基數(shù)樹
template <int BITS>
class TCMalloc_PageMap1
{
public:typedef uintptr_t Number;explicit TCMalloc_PageMap1(){size_t size = sizeof(void*) << BITS; //需要開辟數(shù)組的大小size_t alignSize = SizeClass::_RoundUp(size, 1 << PAGE_SHIFT); //按頁對齊后的大小array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT); //向堆申請空間memset(array_, 0, size); //對申請到的內(nèi)存進行清理}void* get(Number k) const{if ((k >> BITS) > 0) //k的范圍不在[0, 2^BITS-1]{return NULL;}return array_[k]; //返回該頁號對應(yīng)的span}void set(Number k, void* v){assert((k >> BITS) == 0); //k的范圍必須在[0, 2^BITS-1]array_[k] = v; //建立映射}
private:void** array_; //存儲映射關(guān)系的數(shù)組static const int LENGTH = 1 << BITS; //頁的數(shù)目
};

此時當(dāng)我們需要建立映射時就調(diào)用set函數(shù)，需要讀取映射關(guān)系時，就調(diào)用get函數(shù)就行了。

代碼中的非類型模板參數(shù)BITS表示存儲頁號最多需要比特位的個數(shù)。在32位下我們傳入的是32-PAGE_SHIFT，在64位下傳入的是64-PAGE_SHIFT。而其中的LENGTH成員代表的就是頁號的數(shù)目，即 22^BITS

比如32位平臺下，以一頁大小為8K為例，此時頁的數(shù)目就是2³² / 2¹³ = 2 ¹⁹ , 因此存儲頁號最多需要19個比特位，此時傳入非類型模板參數(shù)的值就是 32 ? 13 = 19。由于32位平臺下指針的大小是4字節(jié)，因此該數(shù)組的大小就是2¹⁹ x 4 = 2M ,內(nèi)存消耗不大，是可行的。但如果是在64位平臺下，此時該數(shù)組的大小是2⁵¹ x 8 = 2²⁴G,這顯然是不可行的，實際上對于64位的平臺，我們需要使用三層基數(shù)樹。

• 二層基數(shù)樹

這里還是以32位平臺下，一頁的大小為8K為例來說明，此時存儲頁號最多需要19個比特位。而二層基數(shù)樹實際上就是把這19個比特位分為兩次進行映射。

比如用前5個比特位在基數(shù)樹的第一層進行映射，映射后得到對應(yīng)的第二層，然后用剩下的比特位在基數(shù)樹的第二層進行映射，映射后最終得到該頁號對應(yīng)的span指針。

在二層基數(shù)樹中，第一層的數(shù)組占用2⁵ x = 2⁷ Byte 空間，第二層的數(shù)組最多占用2⁵ x 2¹⁴ x 4 = 2²¹ = 2M。二層基數(shù)樹相比一層基數(shù)樹的好處就是，一層基數(shù)樹必須一開始就把 2M 的數(shù)組開辟出來，而二層基數(shù)樹一開始時只需將第一層的數(shù)組開辟出來，當(dāng)需要進行某一頁號映射時再開辟對應(yīng)的第二層的數(shù)組就行了。

//二層基數(shù)樹
template <int BITS>
class TCMalloc_PageMap2
{
private:static const int ROOT_BITS = 5;                //第一層對應(yīng)頁號的前5個比特位static const int ROOT_LENGTH = 1 << ROOT_BITS; //第一層存儲元素的個數(shù)static const int LEAF_BITS = BITS - ROOT_BITS; //第二層對應(yīng)頁號的其余比特位static const int LEAF_LENGTH = 1 << LEAF_BITS; //第二層存儲元素的個數(shù)//第一層數(shù)組中存儲的元素類型struct Leaf{void* values[LEAF_LENGTH];};Leaf* root_[ROOT_LENGTH]; //第一層數(shù)組
public:typedef uintptr_t Number;explicit TCMalloc_PageMap2(){memset(root_, 0, sizeof(root_)); //將第一層的空間進行清理PreallocateMoreMemory(); //直接將第二層全部開辟}void* get(Number k) const{const Number i1 = k >> LEAF_BITS;        //第一層對應(yīng)的下標const Number i2 = k & (LEAF_LENGTH - 1); //第二層對應(yīng)的下標if ((k >> BITS) > 0 || root_[i1] == NULL) //頁號值不在范圍或沒有建立過映射{return NULL;}return root_[i1]->values[i2]; //返回該頁號對應(yīng)span的指針}void set(Number k, void* v){const Number i1 = k >> LEAF_BITS;        //第一層對應(yīng)的下標const Number i2 = k & (LEAF_LENGTH - 1); //第二層對應(yīng)的下標assert(i1 < ROOT_LENGTH);root_[i1]->values[i2] = v; //建立該頁號與對應(yīng)span的映射}//確保映射[start,start_n-1]頁號的空間是開辟好了的bool Ensure(Number start, size_t n){for (Number key = start; key <= start + n - 1;){const Number i1 = key >> LEAF_BITS;if (i1 >= ROOT_LENGTH) //頁號超出范圍return false;if (root_[i1] == NULL) //第一層i1下標指向的空間未開辟{//開辟對應(yīng)空間static ObjectPool<Leaf> leafPool;Leaf* leaf = (Leaf*)leafPool.New();memset(leaf, 0, sizeof(*leaf));root_[i1] = leaf;}key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; //繼續(xù)后續(xù)檢查}return true;}void PreallocateMoreMemory(){Ensure(0, 1 << BITS); //將第二層的空間全部開辟好}
};

因此在二層基數(shù)樹中有一個Ensure函數(shù)，當(dāng)需要建立某一頁號與其span之間的映射關(guān)系時，需要先調(diào)用該Ensure函數(shù)確保用于映射該頁號的空間是開辟了的，如果沒有開辟則會立即開辟。

而在32位平臺下，就算將二層基數(shù)樹第二層的數(shù)組全部開辟出來也就消耗了 2 M 2M 2M的空間，內(nèi)存消耗也不算太多，因此我們可以在構(gòu)造二層基數(shù)樹時就把第二層的數(shù)組全部開辟出來。

• 三層基數(shù)樹

上面一層基數(shù)樹和二層基數(shù)樹都適用于32位平臺，而對于64位的平臺就需要用三層基數(shù)樹了。三層基數(shù)樹與二層基數(shù)樹類似，三層基數(shù)樹實際上就是把存儲頁號的若干比特位分為三次進行映射。

此時只有當(dāng)要建立某一頁號的映射關(guān)系時，再開辟對應(yīng)的數(shù)組空間，而沒有建立映射的頁號就可以不用開辟其對應(yīng)的數(shù)組空間，此時就能在一定程度上節(jié)省內(nèi)存空間。

//三層基數(shù)樹
template <int BITS>
class TCMalloc_PageMap3
{
private:static const int INTERIOR_BITS = (BITS + 2) / 3;       //第一、二層對應(yīng)頁號的比特位個數(shù)static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS; //第一、二層存儲元素的個數(shù)static const int LEAF_BITS = BITS - 2 * INTERIOR_BITS; //第三層對應(yīng)頁號的比特位個數(shù)static const int LEAF_LENGTH = 1 << LEAF_BITS;         //第三層存儲元素的個數(shù)struct Node{Node* ptrs[INTERIOR_LENGTH];};struct Leaf{void* values[LEAF_LENGTH];};Node* NewNode(){static ObjectPool<Node> nodePool;Node* result = nodePool.New();if (result != NULL){memset(result, 0, sizeof(*result));}return result;}Node* root_;
public:typedef uintptr_t Number;explicit TCMalloc_PageMap3(){root_ = NewNode();}void* get(Number k) const{const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);         //第一層對應(yīng)的下標const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1); //第二層對應(yīng)的下標const Number i3 = k & (LEAF_LENGTH - 1);                    //第三層對應(yīng)的下標//頁號超出范圍，或映射該頁號的空間未開辟if ((k >> BITS) > 0 || root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL){return NULL;}return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3]; //返回該頁號對應(yīng)span的指針}void set(Number k, void* v){assert(k >> BITS == 0);const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);         //第一層對應(yīng)的下標const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1); //第二層對應(yīng)的下標const Number i3 = k & (LEAF_LENGTH - 1);                    //第三層對應(yīng)的下標Ensure(k, 1); //確保映射第k頁頁號的空間是開辟好了的reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v; //建立該頁號與對應(yīng)span的映射}//確保映射[start,start+n-1]頁號的空間是開辟好了的bool Ensure(Number start, size_t n){for (Number key = start; key <= start + n - 1;){const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);         //第一層對應(yīng)的下標const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1); //第二層對應(yīng)的下標if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH) //下標值超出范圍return false;if (root_->ptrs[i1] == NULL) //第一層i1下標指向的空間未開辟{//開辟對應(yīng)空間Node* n = NewNode();if (n == NULL) return false;root_->ptrs[i1] = n;}if (root_->ptrs[i1]->ptrs[i2] == NULL) //第二層i2下標指向的空間未開辟{//開辟對應(yīng)空間static ObjectPool<Leaf> leafPool;Leaf* leaf = leafPool.New();if (leaf == NULL) return false;memset(leaf, 0, sizeof(*leaf));root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);}key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; //繼續(xù)后續(xù)檢查}return true;}void PreallocateMoreMemory(){}
};

因此當(dāng)我們要建立某一頁號的映射關(guān)系時，需要先確保存儲該頁映射的數(shù)組空間是開辟好了的，也就是調(diào)用代碼中的Ensure函數(shù)，如果對應(yīng)數(shù)組空間未開辟則會立馬開辟對應(yīng)的空間。

---

🌿3. 使用基數(shù)樹進行優(yōu)化代碼實現(xiàn)

• 代碼更改

現(xiàn)在我們用基數(shù)樹對代碼進行優(yōu)化，此時將PageCache類當(dāng)中的unorder_map用基數(shù)樹進行替換即可，由于當(dāng)前是32位平臺，因此這里隨便用幾層基數(shù)樹都可以。

//單例模式
class PageCache
{
public://...
private://std::unordered_map<PAGE_ID, Span*> _idSpanMap;TCMalloc_PageMap1<32 - PAGE_SHIFT> _idSpanMap;
};

此時當(dāng)我們需要建立頁號與span的映射時，就調(diào)用基數(shù)樹當(dāng)中的set函數(shù)。

_idSpanMap.set(span->_pageId, span);

而當(dāng)我們需要讀取某一頁號對應(yīng)的span時，就調(diào)用基數(shù)樹當(dāng)中的get函數(shù)。

Span* ret = (Span*)_idSpanMap.get(id);

并且現(xiàn)在PageCache類向外提供的，用于讀取映射關(guān)系的MapObjectToSpan函數(shù)內(nèi)部就不需要加鎖了。

//獲取從對象到span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT; //頁號Span* ret = (Span*)_idSpanMap.get(id);assert(ret != nullptr);return ret;
}

• 為什么讀取基數(shù)樹映射關(guān)系時不需要加鎖？

當(dāng)某個線程在讀取映射關(guān)系時，可能另外一個線程正在建立其他頁號的映射關(guān)系，而此時無論我們用的是C++當(dāng)中的map還是unordered_map，在讀取映射關(guān)系時都是需要加鎖的。

因為C++中map的底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹，unordered_map的底層數(shù)據(jù)結(jié)構(gòu)是哈希表，而無論是紅黑樹還是哈希表，當(dāng)我們在插入數(shù)據(jù)時其底層的結(jié)構(gòu)都有可能會發(fā)生變化。比如紅黑樹在插入數(shù)據(jù)時可能會引起樹的旋轉(zhuǎn)，而哈希表在插入數(shù)據(jù)時可能會引起哈希表擴容。此時要避免出現(xiàn)數(shù)據(jù)不一致的問題，就不能讓插入操作和讀取操作同時進行，因此我們在讀取映射關(guān)系的時候是需要加鎖的。

而對于基數(shù)樹來說就不一樣了，基數(shù)樹的空間一旦開辟好了就不會發(fā)生變化，因此無論什么時候去讀取某個頁的映射，都是對應(yīng)在一個固定的位置進行讀取的。并且我們不會同時對同一個頁進行讀取映射和建立映射的操作，因為我們只有在釋放對象時才需要讀取映射，而建立映射的操作都是在page cache進行的。也就是說，讀取映射時讀取的都是對應(yīng)span的_useCount不等于0的頁，而建立映射時建立的都是對應(yīng)span的_useCount等于0的頁，所以說我們不會同時對同一個頁進行讀取映射和建立映射的操作。

• 再次對比malloc進行測試

還是同樣的代碼，只不過我們用基數(shù)樹對代碼進行了優(yōu)化，這時測試固定大小內(nèi)存的申請和釋放的結(jié)果如下：

可以看到，這時就算申請釋放的是固定大小的對象，其效率都是malloc的兩倍。下面在申請釋放不同大小的對象時，由于central cache的桶鎖起作用了，其效率更是變成了malloc的好幾倍。

---