经过前面的测试可以看到，我们的代码此时与 malloc 之间还是有差距的，此时我们就应该分析分析我们当前项目的瓶颈在哪里，但这不能简单的凭感觉，我们应该用性能分析的工具来进行分析。
VS 编译器中就带有性能分析的工具的，我们可以依次点击 “调试→性能和诊断” 进行性能分析，注意该操作要在 Debug 模式下进行。
然后会弹出一个选项框，这里我们选择的是第二个，因为我们要分析的是各个函数的用时时间，然后点击下一步。
通过分析结果可以看到，光是 deallocate 和 get_span_from_pageID 这两个函数就占用了一半多的时间。
而在 deallocate 函数中，调用 get_span_from_pageID 函数时消耗的时间是最多的。
因此当前项目的瓶颈点就在锁竞争上面，需要解决调用 get_span_from_pageID 函数访问映射关系时的加锁问题。而 tcmalloc 当中针对这一点使用了基数树进行优化，使得在读取这个映射关系时可以做到不加锁。
Ⅱ. 引入基数树
基数树实际上就是一个分层的哈希表，根据所分层数不同可分为单层基数树、二层基数树、三层基数树等。
1、单层基数树
单层基数树实际采用的就是直接定址法，每一个页号对应 span 的地址就存储数组中在以该页号为下标的位置。
最坏的情况下我们需要建立所有页号与其 span 之间的映射关系，因此这个数组中元素个数应该与页号的数目相同，数组中每个位置存储的就是对应 span 的指针。
// 单层基数树
template <int BITS>
class TCMalloc_PageMap1
{
private:
void** array_; // 存储映射关系的数组
static const int LENGTH = 1 << BITS; // 页的数目
public:
typedef uintptr_t Number;
explicit TCMalloc_PageMap1()
{
size_t size = sizeof(void*) << BITS; // 需要开辟数组的大小
size_t alignSize = AlignClass::align(size, 1 << PAGE_SHIFT); // 按页对齐后的大小
array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT); // 向堆申请空间
memset(array_, 0, size); // 对申请到的内存进行清理
}
void* get(Number k) const
{
if ((k >> BITS) > 0) // k的范围不在[0, 2^BITS-1]则直接返回
return nullptr;
return array_[k]; // 返回该页号对应的span
}
void set(Number k, void* v)
{
assert((k >> BITS) == 0); // k的范围必须在[0, 2^BITS-1]
array_[k] = v; // 建立映射
}
}; 此时当我们需要建立映射时就调用 set 函数，需要读取映射关系时，就调用 get 函数就行了。
代码中的非类型模板参数 BITS 表示存储页号最多需要比特位的个数。在 32 位下我们传入的是 32 - PAGE_SHIFT，在 64 位下传入的是 64 - PAGE_SHIFT，而其中的 LENGTH 成员代表的就是页号的数目，即 2^BITS。
比如 32 位平台下，以一页大小为 8K 为例，此时页的数目就是 2^32 / 2^13 = 2^19，因此存储页号最多需要 19 个比特位，此时传入非类型模板参数的值就是 32 − 13 = 19。由于 32 位平台下指针的大小是 4 字节，因此该数组的大小就是 2^19 * 4 = 2^21 = 2M，内存消耗不大，是可行的。
但如果是在 64 位平台下，此时该数组的大小是 2^51 * 8 = 2^54，这显然是不可行的，实际上对于 64 位的平台，我们需要使用三层基数树。
2、二层基数树
这里还是以 32 位平台下，一页的大小为 8K 为例来说明，此时存储页号最多需要 19 个比特位。而二层基数树实际上就是把这 19 个比特位分为两次进行映射：用前 5 个比特位在基数树的第一层进行映射，映射后得到对应的第二层，然后用剩下的 14 个比特位在基数树的第二层进行映射，映射后最终得到该页号对应的 span 指针。
在二层基数树中，第一层的数组占用 32 * 4 = 128B 空间，第二层的数组最多占用 128 * 2^14 = 2^21 = 2MB，二层基数树相比一层基数树的好处就是一层基数树必须一开始就把 2M 的数组开辟出来，而二层基数树一开始时只需将第一层的数组开辟出来，当需要进行某一页号映射时再开辟对应的第二层的数组就行了（就类似文件系统那种多级索引方式）。
// 二层基数树
template <int BITS>
class TCMalloc_PageMap2
{
private:
static const int ROOT_BITS = 5; // 第一层对应页号的前5个比特位
static const int ROOT_LENGTH = 1 << ROOT_BITS; // 第一层存储元素的个数
static const int LEAF_BITS = BITS - ROOT_BITS; // 第二层对应页号的其余比特位
static const int LEAF_LENGTH = 1 << LEAF_BITS; // 第二层存储元素的个数
// 第一层数组中存储的元素类型
struct Leaf
{
void* values[LEAF_LENGTH];
};
Leaf* root_[ROOT_LENGTH]; //第一层数组
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; // 第一层对应的下标
const Number i2 = k & (LEAF_LENGTH - 1); // 第二层对应的下标
if ((k >> BITS) > 0 || root_[i1] == nullptr) // 页号值不在范围或没有建立过映射
return nullptr;
return root_[i1]->values[i2]; // 返回该页号对应span的指针
}
void set(Number k, void* v)
{
const Number i1 = k >> LEAF_BITS; // 第一层对应的下标
const Number i2 = k & (LEAF_LENGTH - 1); // 第二层对应的下标
assert(i1 < ROOT_LENGTH);
root_[i1]->values[i2] = v; // 建立该页号与对应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] == nullptr) // 第一层i1下标指向的空间未开辟
{
//开辟对应空间
static fixed_size_pool<Leaf> leafPool;
Leaf* leaf = (Leaf*)leafPool.apply();
memset(leaf, 0, sizeof(*leaf));
root_[i1] = leaf;
}
key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; // 继续后续的检查
}
return true;
}
void PreallocateMoreMemory()
{
Ensure(0, 1 << BITS); // 将第二层的空间全部开辟好
}
}; 因此在二层基数树中有一个 Ensure 函数，当需要建立某一页号与其 span 之间的映射关系时，需要先调用该 Ensure 函数确保用于映射该页号的空间是开辟了的，如果没有开辟则会立即开辟。
而在 32 位平台下，就算将二层基数树第二层的数组全部开辟出来也就消耗了 2M 的空间，内存消耗也不算太多，因此我们可以在构造二层基数树时就把第二层的数组全部开辟出来。
3、三层基数树
上面一层基数树和二层基数树都适用于 32 位平台，而对于 64 位的平台就需要用三层基数树了。三层基数树与二层基数树类似，三层基数树实际上就是把存储页号的若干比特位分为三次进行映射。
此时只有当要建立某一页号的映射关系时，再开辟对应的数组空间，而没有建立映射的页号就可以不用开辟其对应的数组空间，此时就能在一定程度上节省内存空间。
// 三层基数树
template <int BITS>
class TCMalloc_PageMap3
{
private:
static const int INTERIOR_BITS = (BITS + 2) / 3; // 第一、二层对应页号的比特位个数
static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS; // 第一、二层存储元素的个数
static const int LEAF_BITS = BITS - 2 * INTERIOR_BITS; // 第三层对应页号的比特位个数
static const int LEAF_LENGTH = 1 << LEAF_BITS; // 第三层存储元素的个数
struct Node
{
Node* ptrs[INTERIOR_LENGTH];
};
struct Leaf
{
void* values[LEAF_LENGTH];
};
Node* NewNode()
{
static fixed_size_pool<Node> nodePool;
Node* result = nodePool.apply();
if (result != nullptr)
{
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); // 第一层对应的下标
const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1); // 第二层对应的下标
const Number i3 = k & (LEAF_LENGTH - 1); // 第三层对应的下标
// 页号超出范围，或映射该页号的空间未开辟
if ((k >> BITS) > 0 || root_->ptrs[i1] == nullptr || root_->ptrs[i1]->ptrs[i2] == nullptr)
{
return nullptr;
}
return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3]; //返回该页号对应span的指针
}
void set(Number k, void* v)
{
assert(k >> BITS == 0);
const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); // 第一层对应的下标
const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH - 1); // 第二层对应的下标
const Number i3 = k & (LEAF_LENGTH - 1); // 第三层对应的下标
Ensure(k, 1); // 确保映射第k页页号的空间是开辟好了的
reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v; // 建立该页号与对应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); // 第一层对应的下标
const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH - 1); // 第二层对应的下标
if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH) // 下标值超出范围
return false;
if (root_->ptrs[i1] == nullptr) // 第一层i1下标指向的空间未开辟
{
// 开辟对应空间
Node* n = NewNode();
if (n == nullptr) return false;
root_->ptrs[i1] = n;
}
if (root_->ptrs[i1]->ptrs[i2] == nullptr) // 第二层i2下标指向的空间未开辟
{
// 开辟对应空间
static fixed_size_pool<Leaf> leafPool;
Leaf* leaf = leafPool.apply();
if (leaf == nullptr) return false;
memset(leaf, 0, sizeof(*leaf));
root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
}
key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; // 继续后续检查
}
return true;
}
void PreallocateMoreMemory()
{}
}; 因此当我们要建立某一页号的映射关系时，需要先确保存储该页映射的数组空间是开辟好了的，也就是调用代码中的 Ensure 函数，如果对应数组空间未开辟则会立马开辟对应的空间。
Ⅲ. 使用基数树进行优化代码实现
现在我们用基数树对代码进行优化，此时将 PageCache 类当中的 unorder_map 用基数树进行替换即可，由于当前是 32 位平台，因此这里随便用几层基数树都可以，这里就以一层基数树为例！
// PageCache.h
#pragma once
#include "Common.h"
#include "FixedLenMemPool.hpp"
#include "PageMap.h"
// 单例模式：饿汉方式
class PageCache
{
private:
//std::unordered_map<page_t, Span*> _tables; // 存放页号与对应span对象的映射关系
TCMalloc_PageMap1<32 - PAGE_SHIFT> _tables; // 基数树结构的哈希表
//...
public:
//...
}; 此时当我们需要修改一下源代码中建立页号与 span 的映射的操作，改成调用基数树当中的 set 函数，如下所示：
_tables[span->_pid] = span;
// 改成这样子:
_tables.set(span->_pid, span); 而当我们需要读取某一页号对应的 span 时，就调用基数树当中的 get 函数，如下所示：
auto it = _tables.find(pid);
// 改成这样子:
auto it = (Span*)_tables.get(pid); 并且现在 PageCache 类向外提供的用于读取映射关系的 get_span_from_pageID 函数内部就不需要加锁了：
// 根据传入的内存块地址返回对应的span对象的指针
Span* PageCache::get_span_from_pageID(void* ptr)
{
// 1. 先根据地址求出其所属的页号
page_t pid = ((page_t)ptr >> PAGE_SHIFT);
// 2. 找到对应的页号对应的span指针进行返回
auto it = (Span*)_tables.get(pid);
assert(it != nullptr);
return it;
}为什么读取基数树映射关系时不需要加锁？
当某个线程在读取映射关系时，可能另外一个线程正在建立其他页号的映射关系，而此时无论我们用的是 C++ 当中的 map 还是 unordered_map，在读取映射关系时都是需要加锁的！
因为 C++ 中 map 的底层数据结构是红黑树，unordered_map 的底层数据结构是哈希表，而无论是红黑树还是哈希表，当我们在插入数据时其底层的结构都有可能会发生变化。比如红黑树在插入数据时可能会引起树的旋转，而哈希表在插入数据时可能会引起哈希表扩容。此时要避免出现数据不一致的问题，就不能让插入操作和读取操作同时进行，因此我们在读取映射关系的时候是需要加锁的。
而对于基数树来说就不一样了，基数树的空间一旦开辟好了就不会发生变化，因此无论什么时候去读取某个页的映射，都是对应在一个固定的位置进行读取的，它的结构不会发生变化。
并且线程之间不会同时对同一个页进行读取映射和建立映射的操作，因为只有在释放对象时才需要读取映射，而建立映射的操作都是在 page cache 中进行的，这个过程是加锁的。也就是说，读取映射时读取的都是对应 span 的 _useCount 不等于 0 的页，而建立映射时建立的都是对应 span 的 _useCount 等于 0 的页，所以说我们不会同时对同一个页进行读取映射和建立映射的操作。
性能测试
还是同样的代码，只不过我们用基数树对代码进行了优化，这时测试固定大小内存的申请和释放的结果如下：
当固定大小内存的申请和释放时：
debug 环境下：
release 环境下：
当不同大小内存的申请和释放时：
debug 环境下：
release 环境下：
