a本篇指在记录博主学习、完成该项目时的笔记和感想，不适用于面面俱到的学习。

1.项目介绍

        本项目旨在实现一个高并发内存池，其原型参考了Google的开源项目tcmalloc。tcmalloc全称为Thread-Caching Malloc，通过线程缓存机制实现了高效的多线程内存管理，可替代系统的malloc、free等内存分配函数。

        本项目通过简化tcmalloc的核心框架，模拟实现了一个自主开发的高并发内存池。其主要目的是深入理解并掌握tcmalloc的设计精髓。

何为内存池

        所谓“池化技术”，就是程序先向系统申请过量的资源，然后⾃⼰管理，以备不时之需。之所以要申 请过量的资源，是因为每次申请该资源都有较⼤的开销，不如提前申请好了，这样使⽤时就会变得⾮ 常快捷，⼤⼤提⾼程序运⾏效率。

        比如之前学习的进程池、线程池，都是通过单例模式先把好几个进程或者线程开出来，降低使用时的时间成本

        

        内存池，就是指先写一个可以自主管理内存的程序，便于他人在生产中调用。

        比如C阶段的malloc（C++中的operator new就是复用的malloc）， malloc本质就是去获得 ⼀个内存池。malloc() 相当于向操作系统“批发”了⼀块较⼤的内存空间，然后“零

售”给程序⽤。当全部“售完”或程序有⼤量的内存需求时，再根据实际需求向操作系统“进货”。

malloc的实现⽅式有很多种，⼀般不同编译器平台⽤的都是不同的。⽐如windows的vs系列⽤的微软 ⾃⼰写的⼀套，linux gcc⽤的glibc中的ptmalloc

        本项目还有一个特殊的地方，就是vector list这些都尽量避免使用，因为这些东西的底层都是new

2. 开胃菜——设计一个定长的内存池

用一个自由链表把返回的块管理起来，由于这次的数据就是内存·本身，所以可以用内存直接存下一个块的地址，从而给他串起来。不过，这导致每个块至少得是4字节（64位下是8字节）；另外，我们还需要去了解下malloc的底层是什么系统调用，也就是如何直接拿到虚拟内存；

coding：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#define _WIN32
#include <iostream>
#include <string>
#include <vector>


template<typename T>
class ObjectPool
{
public:
	T* New()
	{
		if (_memory == nullptr)
		{
			_memory = std::malloc(1024 * 128);
			if (_memory == nullptr)
			{
				throw std::bad_alloc();
			}
		}

		T* obj = (T*)_memory;
		_memory += sizeof(T);
		return obj;
	}
private:
	char* _memory = nullptr;
	void* _freelist = nullptr;
};

memory使用char*是为了方便按照字节进行+-

现在的问题是，大块空间128*1024(128kb)用完了该怎么办？既不能让他越界，也不能判空，因为的确不是空，在进程地址空间上，除了我们Malloc的一块，这一整块的前后面都是紧挨着的其他内存

不能判空：不能用char* _memory==nullptr来确定是否已经把这个大

内存走完了，所以这个memory是否为空只能在第一次判断（初始化列表的参数是nullptr）

现在必须加一个变量，来描述还剩多少空间。

别忘了 objmalloc 前面要强转一下

现在处理一下返回的内存块挂进_freeList的问题，也就是一个delete模块

我们必须想办法让头上的4字节或者8字节存一个nullptr。

问题：不满4/8字节怎么办？如果有20/30/100字节一块（就是多于4字节或者8字节）该怎么处理？

整个内存块大小我们不清楚，只知道是一种已有类型：

强转成int*

32位可以处理如下：

直接解决不同位数的问题：一个二级指针就能解决问题

void**可以，int**可以，T**也可以

优先看其他用户返回的内存块，有没有能用的。

  

template<typename T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		//如果freelist中存在，可以先用已经存在的内存块
		if (_freelist)
		{
			obj = _freelist;
			_freelist = *(void**)_freelist;
			return obj;
		}

		if (_remainBytes<sizeof(T))
		{
			_remainBytes = SIZE;
			_memory = (char*)std::malloc(_remainBytes);
			if (_memory == nullptr)
			{
				throw std::bad_alloc();
			}
		}

		obj = (T*)_memory;
		_memory += sizeof(T);
		_remainBetys -= sizeof(T);
		return _memory;
	}

	void Delete(T* obj)
	{
		obj->~T();
		//处理自由链表接受返回的内存块的问题

		//1.解决前四个字节（或者八个）指向下一个的问题,并且每次delete的内容采用头插
		*(int**)obj = _freelist;
		_freelist = obj;
	}
private:
	char* _memory = nullptr;
	size_t _remainBytes = 0;
	void* _freelist = nullptr;
};

---

现在处理如果内存空间没有指针那么大该怎么办：如果没有那么大，将内存块补成至少一个指针的大小

malloc函数 除了开空间，还要调用对应的构造函数 

定位new？

定位new则直接在已经分配好的内存中构造对象，而不进行内存分配，

template<typename T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		//如果freelist中存在，可以先用已经存在的内存块
		if (_freelist)
		{
			obj = _freelist;
			_freelist = *(int**)_freelist;
			return obj;
		}

		if (_remainBytes<sizeof(T))
		{
			_remainBytes = SIZE;
			_memory = (char*)std::malloc(_remainBytes);
			if (_memory == nullptr)
			{
				throw std::bad_alloc();
			}
		}

		obj = (T*)_memory;

		//如果每一个obj的内存大小都不到一个指针大小，就补成一个指针。并且这样做还不用考虑是64位还是32位
		size_t obj_size = sizeof(T) > sizeof(void*) ? sizeof(T) : sizeof(void*);

		_memory += sizeof(T);
		_remainBetys -= sizeof(T);


		//C++中，除了开辟空间，还要初始化对象
		//采用定位new
		new(obj)T();

		return _obj;
	}

	void Delete(T* obj)
	{
		obj->~T();
		//处理自由链表接受返回的内存块的问题

		//1.解决前四个字节（或者八个）指向下一个的问题,并且每次delete的内容采用头插
		*(int**)obj = _freelist;
		_freelist = obj;
	}
private:
	char* _memory = nullptr;
	size_t _remainBytes = 0;
	void* _freelist = nullptr;
};

话说回来，如果一直使用的是malloc，其实依然没有不是我们自己去向内存申请空间，在此分别了解一下win环境下的VS和LINUX中是如何系统调用来申请空间的。

Linux进程分配内存的两种方式--brk() 和mmap() - VinoZhu - 博客园

VirtualAlloc 函数 （memoryapi.h） - Win32 apps | Microsoft Learn

MEM_RESERVE | MEM_COMMIT相当于让当前的虚拟内存被保存并提交，可以观察到这两个选项的本质是位图的计算方法，1和2（包括后面的8），分别表示不同的位，|在一起就是让两个比特位都变成1

static避免命名冲突

inline static void* SystemAlloc(int kpage)
{
#ifdef _WIN32
	//VirtualAlloc分配的内存大小是以字节为单位的
	void* ptr =  VirtualAlloc(0, kpage * (1 << 13), MEM_RESERVE | MEM_COMMIT, PAGE_READWRITE);
#endif _WIN32

#ifdef _linux_

#endif

	if (ptr == nullptr)
	{
		throw std::bad_alloc();
	}

	return ptr;

}

---

简单写一个测试函数，x86和x64都可以运行。

以下是简单的测试：

struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;

	TreeNode()
		:_val(0)
		, _left(nullptr)
		, _right(nullptr)
	{
	}
};

void TestObjectPool()
{
	size_t Rounds = 5;//增删轮次
	size_t num = 100000;//每轮次数

	std::vector<TreeNode*> v1;
	v1.reserve(100000);

	size_t begin1 = clock();
	for (int i = 0; i < Rounds; i++)
	{
		for (int j = 0; j < num; j++)
		{
			v1.push_back(new TreeNode());
		}
		for (int j = 0; j < num; j++)
		{
			delete v1[j];
		}
		v1.clear();
	}
	size_t end1 = clock();


	//测试我们自己的
	std::vector<TreeNode*> v2;
	v2.reserve(100000);

	ObjectPool<TreeNode> _obj_pool;

	size_t begin2 = clock();
	for (int i = 0; i < Rounds; i++)
	{
		for (int j = 0; j < num; j++)
		{
			v2.push_back(_obj_pool.New());
		}
		for (int j = 0; j < num; j++)
		{
			_obj_pool.Delete(v2[j]);
		}
		v2.clear();
	}
	size_t end2 = clock();

	std::cout << "new cost : " << end1 - begin1 << std::endl;
	std::cout << "ObjectPool cost : " << end2 - begin2 << std::endl;
}

---

3. 项目框架设计

thread-cache 

        第一层缓存，每个线程拥有自己的thread-cache，不需要加锁都可以获得内存。

central-cache

        哈西桶，桶锁；所以不会有特别激烈的锁竞争

可以宏观的认为，page cache是管理一个大的，切碎了给central，central再切碎点给thread cache。

而之前的freelist，管理的其实就是切好的小块内存，而且一直在头插和头删。

这样暂时只能处理一种定长的内存块。我们希望的是处理不同大小的内存块

---

        freelist作为在刚刚的开胃菜中，首先用于分配内存的模块，therad-list可以模仿这个思路，所以thread-cache也采用这样的链表结构，但是之前的freelist挂的都是同样的大小，现在需要处理不同的大小。

        可以考虑多个自由链表，如果使用1-256*1024种（因为我们分配的大小可能是1-256kb）链表，那也太多了。

舍弃一点灵活性，生成一点内碎片，增加一点灵活性。

所以，其实thread-cache就是按照上图这样的哈希桶来处理的。

搭建thread-cache的第一层

freelist可能需要多个，我们实现一个freelist的类，然后之后用vector<freelist>或者 freelist _list[size]管理即可，但是可能不会考虑

想想为什么不用vector？因为vector本身就是用new形成的！

来研究一下这个桶。

首先allocate 不能超过256*1024，也就是256kb

命名一个control来管理这个类。

 同理，为了至少能存的下64位的指针，就需要一个至少8字节的。

tcmalloc更复杂，  

利用率几乎控制在百分之九十

32对齐的桶控制1025的话，颗粒度有点太高了，所以直接往上加，只要浪费不超过百分之十即可。

浪费率有点太低了：

这下也能算出一共有多少个_freelist，freelists数组的大小就也能开出来了

这里的ClassControl中想设计成static，是为了全局都好调用。

 

可以数学算出到底亏了多少 a

但是为了提效率，需要非常厉害的位运算来控制这个问题

又写经典bug了：

align——对齐

   >>align_shift，相当于是除以当前的AlignNum，算清楚当前是第几个块，-1是因为下标是从0开始的 

用位运算可以增加性能，本来就是追求性能的项目。

inline static int _Index(size_t size, size_t AlignShift)
{
	return ((size + ((1 << AlignShift) - 1)) >> AlignShift) - 1;
}
inline static int Index(size_t size)
{
	//根据对齐度的不同，需要分区间计算Index
	//并且桶的总数是写好了的
	std::vector<int> DifNum = { 16,56,56,56,24 };
	if (size <= 128)
	{
		return _Index(size,3);
	}
	else if (size <= 1024)
	{
		return _Index(size - 128,4) + 
			DifNum[0];
	}
	else if (size <= 1024)
	{
		return _Index(size - 8*1024,7) + 
			DifNum[0] + DifNum[1];
	}
	else if (size <= 64 * 1024)
	{
		return _Index(size - 8 * 1024,10) + 
			DifNum[0] + DifNum[1] + DifNum[2];
	}
	else if (size <= 256 * 1024)
	{
		return _Index(size - 64 * 1024,13) + 
			DifNum[0] + DifNum[1] + DifNum[2] + DifNum[3];
	}
}

---

现在的问题是如何去让每个线程都调用ThreadCache

*TLS：

        

怎么把各个线程和thread-cache对应起来。

线程本地存储（Thread Local Storage） - 坦坦荡荡 - 博客园

• 与线程栈的区别：线程栈是线程私有的，用于存储局部变量和函数调用信息，而 thread_local 变量存储在全局数据区中，每个线程有自己的副本。

• 存储位置：这些副本存储在全局数据区中，通过线程局部存储（TLS）机制管理。

• 

关于是否需要static，所有的全局函数，都可能被多个cpp包含，如果没有static修饰，很可能会在链接的时候出问题。

当前这么报错就对了，因为我们从FetchFromCentralCache中也拿的是nullptr

借助spdlog，我们完成了第一步的单元测试。

再次好好了解了一下static的问题。

• 在头文件中声明 static 变量并不是一个好习惯，因为它可能会导致头文件被包含多次时出现重复定义错误。

• extern 关键字在 C++ 中用于声明一个变量或函数，它告诉编译器该变量或函数的定义在别处。对于全局变量和静态全局变量，extern 可以用来在一个文件中声明变量，而在另一个文件中定义它，从而避免变量被重复定义。

• 

extern的正确玩法：

每个cpp文件中的static对象都是新的，都会进行各自的构造

只声明，不去调用extern修饰的函数，是不会编译报错的，只是依然会调用两遍构造函数

也就是说现在有三个文件，一个head.hpp y一个head.cc 一个main.cc 在head.hpp中static一个变量，不管在head.cc或者main.cc中是否使用extern声明，依然会在每个cpp文件中有一个该对象。

因为extern只是一个声明

Central Cache

核心依然是按照大小对齐规则的哈希桶

不同的是，central是需要加锁的，

thread2在thread cache 中没有找到对应的内存块，只能加锁的去central找——因为central和thread的对齐规则是一样的

但是使用的是桶锁，每一个桶一个锁

thread1获取8b的锁 thread2获取16b的锁，互不影响

当然，肯定不可能一次给一个，否则就失去了“池”的意义，span是以多个页为单位的更大快的内存

每个span 可能一样大吗？ 8B可能 一两页就够了，256kb的内存可能就需要更大的页

thread cache内挂的内存太多了，是可以丢回给central cache的

_usecount归零，表示当前span的每一个小块都回来了，一旦回来了，就i可以整体合并这几个页，继续向上回收

central cache是起到居中调度的作用。

start coding：

未来的span中，可能会涵盖几个page，需要结合虚拟内存大小给page编号

遇到的第一个问题，32位下，4GB=2^32 假设一个page是8kb，则：2^32/2^13 = 2^19

一个size_t或者Int都表示的下这个数；但在64位下 有2^51个page，需要用longlong才能满足编号

解决办法：

再一次减少编译警告：

然后完善central cache对应的两个结构，一个span和一个spanlist

//每个span里有若干个page
struct Span
{
	PAGEID _page_num; //大块内存起始页的ID
	size_t _num;      //当前span 的 page 数量

	//span将在每一个桶中被链表管理起来
	
	Span* _next;
	Span* _prev;

	size_t _unused = 0; //当前span里未被使用的小内存,此数为0表示所有的内存块都归还了
	void* _freelist = nullptr;//存放已经切好了的小内存的自由链表

};

//每个central的桶里有若干个span，用链表管理
//链表设计成双向带头循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span();//必须的时候还是要用一下
		_head->_next = _head;
		_head->_prev = _head;
	}

	void Insert(Span* obj,Span* pos)
	{
		assert(obj && pos);

		Span* temp_prev = pos->_prev;

		//temp_prev obj pos
		obj->_next = pos;
		obj->_prev = temp_prev;
		temp_prev->_next = obj;
		pos->_prev = obj;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		/*
		这个地方的erase注意，
		erase主要是为了把数据还给page cache，所以只需要解除连接
		而不是真的删除
		*/
		pos->_prev->_next = pos->_next;
		pos->_next->_prev = pos->_prev;

	}
private:
	Span* _head;
public:
	//不想再封装一个调用mutex的函数...
	std::mutex mtx;//桶锁
};

为了便于thread来centralcache中取

thread有多少个桶，就有多少个Spanlist

一个span的小块对象不会一次性给完一个thread， 所以，我们现在去CentralCache中完善

类里面声明，类外外面还要实现一次，不要在hpp中使用static

---

联动之前的Fetchfromcc：

关于这个FetchFromCC，每次该拿多少，也是有学问的，不能一次性给太多，给太多thread用不完是浪费；不能给太少，给太少还需要重复来拿。由此联想到TCP协议中的慢启动算法，我们可以逐个增加分发给该线程的内存数量

类似于TCP中的慢启动算法，第一次给1个对应size的小内存块（去对应下标的centralcache的桶里，找到有资源的span就取这个span的资源）

站在线程角度，我们要给每个ThreadCache（这是TLS的）的freelists里的不同的链表设置一个计数器，这个计数器记录了目前位置最高一次性拿多少个大小匹配freelist的内存块，如果再次申请该大小，理应增加返回的块数

 

真正的单例模式：

getinstance 要设计成static

现在都有了central cache，来完善一下之前遗留的“枢纽”问题：如何fetch from central cache ，每次fetch 多少呢？

maxsize是在freelist定义的变量，初始化为1  

batchNum表示的是我们按照慢启动算法计算得出的本次应该获得的内存块数目，但是当前的span中不一定能给出这么多，我们设计一个FetchRangeObjNum来返回获得的实际数量，并且设计一个输出型参数start和end，来维护fetch出来的这段范围

去获取span，如何判断是否获取成功？

span一定不为空 span的freelist一定页不为空，因为freelist管理的是当前span中已经被切好的小块的、可以被直接使用的内存；为什么不能用usecount？因为usecount在面对不同的“小块内存”时，大小可能会不一样 

int CentralCache::FetchRangeObjNum(void*& start , void*& end,size_t batchNum,size_t index)
{
	assert(batchNum>=1);

	//end的移动次数
	int count = batchNum-1;

	//实际上fetch返回的小内存块数
	int actualNum = 1;

	Span* span = GetSpan(index);//TODO
	//假设现在已经获得了span

	//只要span存在，并且span管理分成小块的自由链表不为空即可
	assert(span && span->_freelist);

	//获取符合条件的小内存
	start = span->_freelist;
	end = start;
	while (NextObj(start) && count--)
	{
		end = NextObj(start);
		actualNum++;
	}

别忘了，这一步是到对应的centralCache的桶里面去拿资源，是需要桶锁的。

如果一个span中，小内存的个数已经够了，那没有问题

但是如果一个span剩下的小内存不够了呢？那就只能尽力而为，给actualNum个

为了挂到threadcache的freelists中去，需要进行push，但是此时可能是一个区间，所以可以再写一个PushRange

 

PageCache

首先明白，PageCache和CentralCache同样挂的都是span，但是page cache的映射关系不一样，有只包含1页的page。。。到包含128page的cache

映射规则不同于前两层，直接服务于centralcache，从而不需要切，并且映射是直接映射法，central需要多少page的span，就可以直接去pagecache中去取。

如果central cache释放回⼀个span，则依次寻找span的前后page id的没有在使⽤的空闲span， 看是否可以合并，如果合并继续向前寻找。这样就可以将切⼩的内存合并收缩成⼤的span，减少内存碎⽚。

并且，最大的一个span我们设计成128个page，即128*8=1024个kb。

相当于是1M，可以至少分出4个256kb，这与我们之前的NumofLimit是有联系的。当那种申请256Kb内存块的，第一次申请一个，第二次申请两个（batchNum是2）；那么这里至少是2*256kb=64page，每一个page算的是8kb。意思就是，最大的span对应的page数量就是64，而我们提供最大到128page的span，这是绝对足够的。所以，其实65——128page数量的span，都是用于在page cache层切割成更小的span的。

在设计page cache的核心数据结构时，依然是spanList，只是这次就需要128个。

page cache需要一个大锁，把整体锁起来

因为涉及合并的问题。2page的找不到，就需要找3page的。。。。，这一步导致不能用桶锁

桶锁有点麻烦。

加锁解锁消耗也很大。

GetSpan：

要遍历SpanList，就得有对应的接口。又是双向带头循环。

参数设计上要动点心思：对齐之后的size应该作为一个一直需要被传输的参数，不要过多纠结index的传递，一定意义上是冗余的

span永远都挂在central cache这一层中去管理，给thread cache返回的永远都是切好了的小内存

现在就要考虑分配多少个页的span了，需要一种算法去确定这个数值

一个内存池的首次使用，一定会先走下面的NewSpan逻辑，因为最开始的时候Central cache是没有Span挂在里面的。

NumMovePage

切分的逻辑：

 除了拿到一块内存，还需要把整个span给切分成小内存挂进freelist

该头插还是尾插呢？

头插能让用户层在预加载时的命中率提高

找page cache的时候，central cache的锁解不解？

解了好——之前被锁的那个桶，可能有1其他thread cache想释放内存对象回去，但是由于当前桶已经被锁死了

要去往下一层page cache要span的位置，一定已经没有可以用的span了。 

所以申请这个位置被堵住很正常；但是关于释放：释放肯定也需要在代码中去获取锁，可是现在锁一直在当前pagecache中申请内存的位置，相当于阻塞了thread_cache向central_cache的释放。

宏的问题

开发日志9.17——解决了大量warning的unicode问题，加上了page cache和central cache之间的锁

我草，幸亏我机制，提前准备了这个问题

---

释放：

tc malloc是两个机制一起去控制是否释放：链表长度和Thread Cache大小，今天稍微舍弃一点内容，只用链表长度来控制：

如果_freelists[index]太长了，需要向上回收

实现ListTooLong：

 拿一个批量的长度往回还。这里并没有把整个_freelist[index]里的内容都还回去。由于慢增长的特性，MaxSize是当前给过的最多的一次，假设是100，则几乎是已经给了1+2+3+。。。99个内存块

 为什么是几乎是？因为我们有一个actualNum和batchNum，从1加到99是batchNum的情况。

回到假设，所以释放的时候只是释放了一部分内容，会留一部分内容到thread cache中去 。当然，理论上来说我们已经给了1+。。。99个，其中肯定有很大一部分还在线程里

为了满足Size的设计，需要在push pop pushrange里都好好计算一下个数，然后在Freelist类中对应的Push PushRange Pop里增加对应的_size的变化。

有一个是需要返回的，所以Pushrange的时候实际只加了actualNum-1个。

Central Cache层释放：

spans的原因->不一定来自于一个span

 今天第一批申请。。。第二批申请。。。。可是线程中用完之后回收的顺序是不一定的

TC malloc中，是如何确定哪个内存属于哪个span的呢?

        我的想法：内存是用指针标识着的，指针的值去右移13位可以得到他所属的page id，根据page id-》每个span有记录自己的page id起始数和page数量

 

现在的问题变成了怎么把得到的page id和span相对应。可以直接暴力遍历，但是这样的话，如果有n个内存块需要我们换，复杂度就是n^2了

在pagecache里需要存pageid和Span的对应值，用一个unordered_map来存

因为Page Cache之后也需要这一层映射，所以我们把这个映射表

kspan就是我们当时在page cache中想返回的span，这个kspan中有_n个page,我们把这些kspan里的span，一个一个计数，并且放到Map里

如果当前span的小内存块都给出去了，就直接返回整个span。

可是span里的freelist挂的顺序都是乱的怎么办？完全不影响，直接把freelist清零，变成一个从来没有被切过的span。所有的管理，都是人为想象加上去的，内存其实一直都在原地没有变化过，物理空间永远、一定连续，只要整个span拿出去（被使用的小内存）都回来了，就可以直接

整个span被我们“初始化”好了，就把整个span还回去给page cache

锁的问题和之前是一样的，进入大锁之前先把桶锁放了

往前、往后探测，看看能不能合并。

这就是为什么我们需要在page cache层搞span到ID的映射。

直接通过usecount可不可以判断当前span能否合并呢？

对于已经挂在Central Cache中的span来说是没问题的， 但是对于刚刚从page cache拿到central cache中的那一块内存来说可就不一样了：我们正在central cache中对刚刚拿到的大内存进行一个切，他的usecount也是0，可是这个内存是不能拿给pagecache的，因为这个内存需要拿给thread cache去使用

所以还需要再增加一个参数：isuse

默认是false，并且要在pagemtx内解决这个问题，一拿到Span就要改，也就是在这块Span被central cache切好之前。

现在每一个被返回的span，自己的_isuse都会是true——也就是说，每一个正在处理、或者即将拿到pagecache锁然后再去处理的span，都不会被其他可能

收回来的page cache：

又有另外一个问题，只有要挂进central cache的部分被我们往unordered_map里映射了，现在是没法找到page cache中的其他的page

所以肯定要想办法映射一下刚刚的nSpan，也就是直接挂进page cache的部分：直接挂进page cache的部分不需要每一页都去映射，只需要把头和尾去映射即可，因为别人在page cache里找他，都是通过头和尾去找他

合成大内存一定是好事情，解决外碎片问题。

、

、

前面的后面的多大都不影响，只要找到了span，就能拿到他的头和尾

但是，又有可能合成一个比128还大的块，合成了更大的内存块。

while 1一直去合并更大的就可以了

前后都合并之后，就把总长度加起来，挂进对应的桶里，然后再把自己的isUse放成false，让别人恶意合并我，并且在unordered_map中记录自己的前后页号

---

联调释放：

首先，主函数中操作CourrentFree的时候，应该不加那个控制大小的

bug 1：多移动了一次：应该改成--length

注意length不能在最后被使用，要在一开始就在_size里减掉

返回来之后，span全部归零

找一个bug：

找两个Bug:

找三个Bug:

bug 4：next_span和span是一样的

---

大于256KB

替代MALLOC

新的问题，尽然和定长内存池的大小有关系。

非常奇怪，有几率触发 定位new的错误

以下是调试过程、

实验对比：

调用ObjPool，四次挂两次

调用new，一次都不挂，也从来没有挂过

注意：objpool是多线程共享的

找到问题了，定长内存池也应该加锁，要么就是各个线程独享！

当一个 线程把remainBytes变的大于0的时候，如果另一个线程还未判断remainBytes，这会导致后者线程不再判断remainBytes，直接跳到后面的obj = (T*)_memory,再跳到

---

怎么才能只放ptr就释放

解决办法1，pageid和size也做map映射

一个页里面的内存

Map加锁：

明显的死锁问题：

9.24开发日记：

发现昨天加的ObjPool会导致一开始使用的时候，两个线程不同步。

第一次尝试在ObjPool里加锁，发现有死锁问题，于是决定在外面使用一共thread_local。

但是每一个thread都拥有一个ObjPool的话，有点过大了，不过也不是不可以，是可以接受的大小，只能说最好不要。

之后再次研究为什么会死锁，发现是因为并非所有返回路径都有unlock

解决这个问题之后，就可以不使用thread_local修饰ThreadPool的工厂了

---

Benchmark

任何程序都有bug，一定情况下保证可靠性

C++中，保证运算是原子的类：

atomic

调试技巧1

调试技巧2：

调用堆栈

......

---

测试、优化

9.25

一包茶一根烟，一个代码调一天

能跑之后，需要关闭spdlog对应的打印信息，因为IO实在太花时间了

四个线程，每个线程10000轮，每轮10次，足足跑了11分钟

不断的加大数据量，发现在4线程，每个线程1000次的时候崩溃了

一点小Bug: 申请的数据比较大的时候的Bug

在release模式下，都测随机申请内存块大小，测试结果如下：

效率没有想象的那么高，和malloc差距不大

如果是申请同样大小的，那还远远干不过malloc

---

性能优化

分析性能瓶颈：

        使用VS下自带的分析工具，注意不是分析CPU资源，而是看函数的耗时

性能分析工具发现：

主要是ConcurrentFree中的锁耗时最多，但是锁是库中实现的，如果锁里面的内容再快点，也能提升效率（map越久，锁竞争越激烈）：

---

于是我们需要优化我们的map——基数树与减少锁

这是TC MALLOC官方的做法：先使用一个基数树

 整形对整形（ID-SPAN*），采用Radix Tree优化：

Trie(字典树) : 如何实现搜索引擎的关键词提示功能？_c# trie tree 实现搜索引擎提示功能-CSDN博客

高级数据结构与算法 | 基数树（Radix Tree）-CSDN博客

用页号作为搜索的线索，在每一个叶子节点上存下唯一的span*

#pragma once
// Single-level array
template <int BITS>
class TCMalloc_PageMap1 
{
private:
	static const int LENGTH = 1 << BITS;
	void** array_;
public:
	typedef uintptr_t Number;
	explicit TCMalloc_PageMap1(void* (allocator)(size_t)) 
	{
		*array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*)
			<< BITS));
		memset(array_, 0, sizeof(void*) << BITS);
	}
	// Return the current value for KEY. Returns NULL if not yet set,
	// or if k is out of range.
	void* get(Number k) const 
	{
		if ((k >> BITS) > 0) 
		{
			return NULL;
		}
		return array_[k];
	}
	// REQUIRES "k" is in range "[0,2^BITS-1]".
	// REQUIRES "k" has been ensured before.
	//
	// Sets the value 'v' for key 'k'.
	void set(Number k, void* v) 
	{
		array_[k] = v;
	}
};





// Two-level radix tree
template <int BITS>
class TCMalloc_PageMap2 
{
private:
	// Put 32 entries in the root and (2^BITS)/32 entries in each leaf.
	static const int ROOT_BITS = 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;

	// Leaf node
	struct Leaf 
	{
		void* values[LEAF_LENGTH];
	};

	Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodes

	void* (*allocator_)(size_t); // Memory allocator


public:
	typedef uintptr_t Number;

	explicit TCMalloc_PageMap2(void* (*allocator)(size_t)) 
	{
		allocator_ = allocator;
		memset(root_, 0, sizeof(root_));
	}

	void* get(Number k) const 
	{
		const Number i1 = k >> LEAF_BITS;
		const Number i2 = k & (LEAF_LENGTH - 1);
		if ((k >> BITS) > 0 || root_[i1] == NULL) {
			return NULL;
		}
		return root_[i1]->values[i2];
	}

	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;
	}

	bool Ensure(Number start, size_t n) 
	{
		for (Number key = start; key <= start + n - 1;) 
		{
			const Number i1 = key >> LEAF_BITS;
			// Check for overflow
			if (i1 >= ROOT_LENGTH)
				return false;
			// Make 2nd level node if necessary
			if (root_[i1] == NULL) {
				Leaf* leaf = reinterpret_cast<Leaf*>
					((*allocator_)(sizeof(Leaf)));
				if (leaf == NULL) return false;
				memset(leaf, 0, sizeof(*leaf));
				root_[i1] = leaf;
			}
			// Advance key past whatever is covered by this leaf 
			node
				key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}


	void PreallocateMoreMemory() 
	{
		// Allocate enough to keep track of all possible pages
		Ensure(0, 1 << BITS);
	}
};

以上源码在被我们改造之后，就可以替代unordered_map了

在此，阅读了TC Malloc关于这方面优化的源码

第一层基数树非常简单，直接一字排开，一个页号对应一个Span*的地址。一共有32-13=19位，所以需要直接开一个2^19大小的数组。

在第二层 基数树中，分成两层，第一层取5位，所以第二层是19-5 = 14位

提前打开前32个（2^5）槽位，并且预先把这32个槽位的空间优化好（PreallocateMoreMemory+Ensure）

理解为什么更快：

unordered_map本质是哈希桶，我们存储的是ID号和SPAN*的映射，ID按照一定的算法确定的下标是会变化的，比如扩容什么的。或者map红黑树的扩容，访问的时候可能正在旋转或者扩容。

        1、然而基数树的结构是固定的，是更简单、确定的一种哈希映射，哈希结构确定。

        2、哈希结构确定的情况下，两个线程不可能读写同一个位置：

因此，可以在读这个哈希表时去掉锁，提升效率

使用基数树改造之后：

配置成可使用的库文件：