目录

项⽬介绍

小知识点补充 

定位new

英语单词：

什么是内存池

1.池化技术

2.内存池

3.内存池主要解决的问题

3.1 效率问题

3.2 碎片化 

3.2.1 外碎片 

4.了解一下malloc

先设计⼀个定⻓的内存池

New的实现

Delete的实现

性能测试

脱离malloc直接在堆中

ObjectPool.h

Test.cpp

⾼并发内存池整体框架设计

⾼并发内存池--thread cache

申请内存：

释放内存：

计算对象大小的对齐映射规则

Common.h

ThreadCache.h

解决thread cache的锁问题​编辑

⾼并发内存池--central cache

申请内存：

释放内存：

⾼并发内存池--page cache

申请内存：

释放内存：

从堆中申请内存，页号和地址的关系

内存回收

测试

高并发内存池-使用定长内存池配合脱离使用new

释放对象时优化为不传对象大小

测试+改错

性能优化

项⽬介绍

1.这个项⽬做的是什么？

当前项⽬是实现⼀个⾼并发的内存池，他的原型是google的⼀个开源项⽬tcmalloc，tcmalloc全称 Thread-Caching Malloc，即线程缓存的malloc，实现了⾼效的多线程内存管理，⽤于替代系统的内存分配相关的函数（malloc、free）。

2.用到的知识

这个项⽬会⽤到C/C++、数据结构（链表、哈希桶）、操作系统内存管理、单例模式、多线程、互斥锁等等⽅⾯的知识。

小知识点补充 

定位new

new(obj) T; 这一行代码是 placement new（定位 new）的使用，它是 C++ 中的一种特殊的内存分配方式。下面我将详细解释它的含义和工作原理，以及如何使用。

什么是 Placement New？

在 C++ 中，new 通常用于动态分配内存并构造对象，例如：

T* obj = new T();  // 这会分配内存并调用T的构造函数

然而，new(obj) T; 则是定位 new（Placement New）的用法。它并不分配内存，而是在指定的内存位置（由 obj 指向的地址）上构造对象。也就是说，obj 必须是一个指向已经分配内存的指针，这块内存已经存在并且足够大来容纳一个 T 类型的对象。

语法结构

new (pointer) T(args);

• pointer：指向已分配内存的位置。这块内存已经预先分配好，通常由 malloc、内存池（如你的代码中所示）或者其他方式分配。

• T：对象的类型。你希望在 pointer 指向的内存位置构造一个类型为 T 的对象。

• args：传递给 T 类型构造函数的参数（如果有的话）。

为什么需要 Placement New？

在常规的 new 操作中，new 关键字不仅分配内存，还会调用构造函数来初始化对象。这样会额外的进行一次内存分配。然而，在很多情况下，你可能已经分配了内存，并且只想在这些内存位置上创建对象。这时，placement new 就非常有用了。

在你的代码中，new(obj) T; 是用来在已经分配好的内存（由 obj 指向）上构造一个类型为 T 的对象。

示例说明

假设你有一个类 MyClass，并且已经预先分配了一块足够大的内存，我们希望在这块内存上构造一个 MyClass 对象。以下是一个简单示例：

1. 传统 new 示例：

class MyClass {
public:
    MyClass() {
        std::cout << "MyClass Constructor Called!" << std::endl;
    }
};

int main() {
    MyClass* obj = new MyClass();  // 分配内存并构造对象
    delete obj;  // 释放内存
    return 0;
}

• new MyClass() 会分配内存并构造一个 MyClass 对象。

• 使用 delete 释放内存。

2. Placement new 示例：

class MyClass {
public:
    MyClass() {
        std::cout << "MyClass Constructor Called!" << std::endl;
    }
};

int main() {
    char buffer[sizeof(MyClass)];  // 分配足够大的内存，存放 MyClass 对象
    MyClass* obj = new (buffer) MyClass();  // 在 buffer 上构造 MyClass 对象
    // 在这里，我们并没有调用 `new MyClass()`，而是直接在 buffer 上构造了对象
    return 0;
}

• buffer 是一个已分配的内存块（大小足够存放一个 MyClass 对象）。

• new (buffer) MyClass(); 在 buffer 上直接调用 MyClass 的构造函数，而不需要重新分配内存。

3. 在内存池中使用 Placement New：

在你提供的 ObjectPool 示例中，new(obj) T; 是在已经分配好的内存上构造 T 类型的对象。例如，内存池可能已经为多个对象分配了一大块内存（比如128KB），然后通过 new(obj) T; 在这些内存区域上逐个构造对象。

工作原理

1. 不进行内存分配

placement new 不会调用 operator new（即不会分配内存）。它假定内存已经由你提供，且这块内存足够大。因此，你必须确保传递给 new 的地址指向的内存足够存放一个 T 类型的对象。

2. 调用构造函数

placement new 只是用来调用指定内存位置的构造函数。它实际上是在指定的内存地址上调用了 T 类型的构造函数。

3. 返回对象的指针

new(obj) T; 会返回指向 obj 的指针，指向已经初始化的对象。

为什么不直接使用 new？

通常使用 new 会执行内存分配和对象构造，但是有时你已经有一块内存（例如通过 malloc 或内存池）并且不需要重新分配内存。此时，placement new 就非常有用。

内存池场景中的应用

在内存池的实现中，常常会通过一次性分配大块内存，并在这块内存上“定位”地创建多个对象。例如，你可能为内存池分配了128KB的内存，然后在这个内存块中管理多个对象。当你需要一个新的对象时，你只需在这块内存上调用 placement new 来构造对象。

销毁对象有序列表

使用 placement new 构造的对象并不使用普通的 delete 来销毁。普通 delete 会调用析构函数并释放内存，而 placement new 并不负责释放内存。因此，如果你通过 placement new 构造了对象，你需要显式调用对象的析构函数，并确保内存不会泄漏：

obj->~T();  // 显式调用析构函数

总结

• new (obj) T; 是 placement new，用于在已分配的内存上构造对象。

• 它不会分配内存，而是直接在指定的内存位置上调用构造函数。

• 适用于内存池、缓存池等需要手动管理内存的场景。

• 使用时需要保证内存已经分配且足够容纳对象，并且在不再需要时显式销毁对象，释放资源。

这种方法常用于需要精细控制内存和对象生命周期的场合，特别是在内存池管理中，能有效提高性能和内存利用率。

英语单词：

cache:高速缓冲储存器

Align:对齐

concurrent:并发

batch:批量

fetch:拿来

actual:实际

range:范围

benchmark:基准；标准；基准测试

什么是内存池

1.池化技术

所谓 “池化技术”，就是程序先向系统申请过量的资源，然后自己管理，以备不时之需。之所以要请过量的资源，是因为每次申请该资源都有较大的开销，不如提前申请好了，这样使用时就会变得非常快捷，大大提高程序运行效率。
在计算机中，有很多使用  “池” 这种技术的地方，除了内存池，还有连接池、 线程池、对象池等。以服务器上的线程池为例，它的主要思想是：先启动若干数量的线程，让它们处于睡眠状态，当接收到客户端的请求时，唤醒池中某个睡眠的线程，让它来处理客户端的请求，当处理完这个请求，线程又进入睡眠状态。

2.内存池

内存池是指程序预先从操作系统申请一块足够大内存，此后，当程序中需要申请内存的时候，不是直接向操作系统申请，而是直接从内存池中获取；同理，当程序释放内存的时候，并不真正将内存返回给操作系统，而是返回内存池。 当程序退出（或者特定时间）时，内存池才将之前申请的内存真正释放。

3.内存池主要解决的问题

内存池主要解决的当然是效率的问题，其次如果作为系统的内存分配器的⻆度，还需要解决⼀下内存碎⽚的问题。那么什么是内存碎⽚呢？

3.1 效率问题

打个通俗的比方就是：问爸爸妈妈要钱买东西，一次次的要效率太低，如果估算好一个月要用到生活费，直接给一个月的，就不用一次一次的要，可以提交很多的效率。

3.2 碎片化 

再需要补充说明的是内存碎片分为外碎片和内碎片，上面我们讲的外碎片问题。外部碎片是一些空的连续内存区域太小，这些内存空间不连续，以至于合计的内存足够，但是不能满足一些的内存分配请需求。内部碎片是由于一些对齐的需求 ，导致分配出去的空间中一些内存无法被利用。内碎片问题，我们后面项目就会看到，那会再进行更准确的理解。（创建时申请空间连续，释放时不按申请的顺序释放，会导致这些内存空间不连续）

3.2.1 外碎片 

4.了解一下malloc

C/C++中我们要动态申请内存都是通过malloc去申请内存，但是我们要知道，实际我们不是直接去堆获取内存的。

而malloc就是一个内存池。 mallocO相当于向操作系统 “批发”了一块较大的内存空间，然后“零售” 给程序用。当全部 “售完” 或程序有大量的内存需求时，再根据实际需求向操作系统“进货”malloc的实现方式有很多种，一般不同编译器平台用的都是不同的。比如windows的vs系列用的微软自己写的一套，linux gcc用的glibc中的ptmalloc。

一文了解，Linux内存管理，malloc、free 实现原理

malloc背后的实现原理----内存池

malloc的底层实现（ptmalloc）

先设计⼀个定⻓的内存池

作为程序员（C/C++）我们知道申请内存使用的是malloc， malloc其实就是一个通用的大众货，什么场景下都可以用，但是什么场景下都可以用就意味着什么场景下都不会有很高的性能，下面我们就先来设计一个定长内存池做个开胃菜，当然这个定长内存池在我们后面的高并发内存池中也是有价值的，所以学习他目的有两层，先熟悉一下简单内存池是如何控制的，第二他会作为我们后面内存池的一个基础组件。

创建一个并发内存池(ConcurrentMemoryPool)项目

New的实现

Delete的实现

如果申请的大块内存空间没有用完，freeList又不为空，，可以先将还回来的内存块对象，再次重复利用

处理一下不足

性能测试

脱离malloc直接在堆中

VirtualAlloc:VirtualAlloc_百度百科

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

ObjectPool.h

#pragma once

#include<iostream>
#include<vector>
#include <new>
#include <time.h>
using std::cout;
using std::endl;

#ifdef _WIN32
#include <Windows.h>
#else
// linux下brk mmap等 linux中的头文件
#endif

// 直接去堆上按页申请空间 
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
		// linux下brk mmap等 
#endif
		if (ptr == nullptr)
			throw std::bad_alloc();
	return ptr;
}


定长内存池
//template<size_t N>
//class ObjectPool
//{};

//用T也可以使定长内存池，因为T也是固定的
template<class T>
class ObjectPool
{
public:
	T* New()
	{
		T* obj = nullptr;
		//优先把还回来内存块对象，再次重复利用
		if (_freeList)
		{
			void* next = *((void**)_freeList);
			obj = (T*)_freeList;
			_freeList = next;
		}
		else
		{
			//剩余内存不够一个对象大小时，则重新开大块空间
			if (_remainByrtes < sizeof(T))
			{
				_remainByrtes = 128 * 1024;
				//_memory = (char*)malloc(_remainByrtes);//128k的空间
				_memory = (char*)SystemAlloc(_remainByrtes >> 13);//128k的空间

				//记得检查一下
				if (_memory == nullptr)
				{
					throw std::bad_alloc();
				}
			}
			obj = (T*)_memory;
			size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
			_memory += objSize;
			_remainByrtes -= objSize;
		}

		//对已经有的空间进行初始化
		//定位new，显示调用T的构造对象初始化
		//new(obj) T; 是一种在已分配内存中直接构造对象的方法，
		//它不会重新分配内存，而是将对象的数据构造到指定的内存位置上。
		new(obj)T;
		return obj;
	}

	void Delete(T* obj)
	{
		//显示调用析构函数清理对象
		obj->~T();
		
		//头插
		*(void**)obj = _freeList;
		_freeList = obj;	
	} 

private:
	//用char*更方便因为一个一个字节的加更方便，1字节好控制
	//void* _memory;
	char* _memory = nullptr;//指向大块内存的指针
	void* _freeList = nullptr;//还回来过程链接的自由链表的头指针
	size_t _remainByrtes = 0;//大块内存在切分过程中剩余字节空间大小
};
 

//测试性能
struct TreeNode
{
	int _val;
	TreeNode* _left;
	TreeNode* _right;
	TreeNode()
		:_val(0)
		, _left(nullptr)
		, _right(nullptr)
	{}
};
void TestObjectPool()
{
	// 申请释放的轮次 
	const size_t Rounds = 3;

	// 每轮申请释放多少次 
	const size_t N = 100000;

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

	ObjectPool<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.New());
		}
		for (int i = 0; i < N; ++i)
		{
			TNPool.Delete(v2[i]);
		}
		v2.clear();
	}
	size_t end2 = clock();
	cout << "new cost time:" << end1 - begin1 << endl;
	cout << "object pool cost time:" << end2 - begin2 << endl;
}

Test.cpp

#include"ObjectPool.h"

int main()
{
	TestObjectPool();
	return 0;
}

⾼并发内存池整体框架设计

现代很多的开发环境都是多核多线程，在申请内存的场景下，必然存在激烈的锁竞争问题。malloc本身其实已经很优秀，那么我们项目的原型tcmalloc就是在多线程高并发的场景下更胜一筹，所以这次我们实现的内存池需要考虑以下几方面的问题

1. 性能问题。

2. 多线程环境下，锁竞争问题。

3. 内存碎⽚问题

concurrent memory pool主要由以下3个部分构成：
1. thread cache：线程缓存是每个线程独有的，⽤于⼩于256KB的内存的分配，线程从这里申请内存，不需要加锁，每个线程独享⼀个cache，这也就是这个并发线程池高效的地⽅。

2. central cache：中心缓存是所有线程所共享，thread cache是按需从central cache中获取的对
象。central cache合适的时机回收thread cache中的对象，避免⼀个线程占用了太多的内存，而其
他线程的内存吃紧，达到内存分配在多个线程中更均衡的按需调度的目的。central cache是存在竞
争的，所以从这⾥取内存对象是需要加锁，⾸先这⾥⽤的是桶锁，其次只有thread cache的没有内
存对象时才会找central cache，所以这⾥竞争不会很激烈。

3. page cache：页缓存是在central cache缓存上⾯的⼀层缓存，存储的内存是以页为单位存储及分
配的，central cache没有内存对象时，从page cache分配出⼀定数量的page，并切割成定长大小
的小块内存，分配给central cache。当⼀个span的几个跨度页的对象都回收以后，page cache会
回收central cache满⾜条件的span对象，并且合并相邻的页，组成更大的页，缓解内存碎片的问
题。

⾼并发内存池--thread cache

thread cache是哈希桶结构，每个桶是⼀个按桶位置映射⼤⼩的内存块对象的自由链表。每个线程都会有⼀个thread cache对象，这样每个线程在这⾥获取对象和释放对象时是无锁的。

申请内存：

1. 当内存申请size

2. 如果自由链表_freeLists[i]中有对象，则直接Pop⼀个内存对象返回。

3. 如果_freeLists[i]中没有对象时，则批量从central cache中获取⼀定数量的对象，插⼊到自由链表并返回⼀个对象。

释放内存：

1. 当释放内存⼩于256k时将内存释放回thread cache，计算size映射自由链表桶位置i，将对象Push 到_freeLists[i]。

2. 当链表的⻓度过⻓，则回收⼀部分内存对象到central cache。

计算对象大小的对齐映射规则

// 整体控制在最多10%左右的内碎⽚浪费 
// [1,128] 8byte对⻬                    freelist[0,16) 
// [128+1,1024] 16byte对⻬              freelist[16,72) 
// [1024+1,81024] 128byte对⻬           freelist[72,128) 
// [8*1024+1,641024] 1024byte对⻬       freelist[128,184) 
// [64*1024+1,256*1024] 8*1024byte对⻬  freelist[184,208) 

//计算对象大小的对齐映射规则
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费 
	// [1,128]						8byte对齐                                      freelist[0,16) 
	// [128+1,1024]				16byte对齐						freelist[16,72) 
	// [1024+1,81024]				128byte对齐						freelist[72,128) 
	// [8*1024+1,641024]			1024byte对齐						freelist[128,184) 
	// [64*1024+1,256*1024]		8*1024byte对齐					freelist[184,208) 

	//简单版本计算对齐数
	//size_t _RoundUp(size_t size, size_t alignNum)
	//{
	//	size_t alignSize;
	//	if (size % alignNum != 0)
	//	{
	//		alignSize = (size / alignNum + 1) * alignNum;
	//	}
	//	else
	//	{
	//		alignSize = size;
	//	}
	//	return alignSize;
	//}
	//复杂版本计算对齐数
	static inline size_t _RoundUp(size_t bytes, size_t AlignNum)
	{
		return (((bytes)+AlignNum - 1) & ~(AlignNum - 1));
	}

	//对齐大小计算
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);//8字节对齐
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);//16字节对齐

		}
		else if (size <= 8*1024)
		{
			return _RoundUp(size, 128);//128字节对齐

		}
		else if (size <= 64*1024)
		{
			return _RoundUp(size, 1024);//1024字节对齐

		}
		else if (size <= 256*1024)
		{
			return _RoundUp(size, 8*1024);//8字节对齐
		}
		else
		{
			assert(false);
			return -1;
		}
	}

};

代码实现：

Common.h

#pragma once

#include<iostream>
#include<vector>
#include <new>
#include <time.h>
#include <assert.h>
using std::cout;
using std::endl;

void*& NextObj(void* obj)
{
	return *(void**)obj;
}
//管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);
		//头插
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;
	}
	void* Pop()
	{
		assert(_freeList);
		//头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
	}

private:
	void* _freeList;
};

ThreadCache.h

#pragma once
#include"Common.h"
class ThreadCache
{
public:
	// 申请和释放内存对象 
	void* Allocate(size_t size);
	void Deallocate(void* ptr, size_t size);

private:
	FreeList _freeLists[];
};

解决thread cache的锁问题

⾼并发内存池--central cache

central cache也是一个哈希桶结构，他的哈希桶的映射关系跟thread cache是一样的。不同的是他的每个哈希桶位置挂是SpanList链表结构，不过每个映射桶下面的span中的大内存块被按映射关系切成了一个个小内存块对象挂在span的自由链表中。

申请内存：

1. 当thread cache中没有内存时，就会批量向central cache申请⼀些内存对象，这⾥的批量获取对象 的数量使⽤了类似⽹络tcp协议拥塞控制的慢开始算法；central cache也有⼀个哈希映射的 spanlist，spanlist中挂着span，从span中取出对象给thread cache，这个过程是需要加锁的，不 过这⾥使⽤的是⼀个桶锁，尽可能提⾼效率。

2. central cache映射的spanlist中所有span的都没有内存以后，则需要向page cache申请⼀个新的 span对象，拿到span以后将span管理的内存按⼤⼩切好作为⾃由链表链接到⼀起。然后从span中 取对象给thread cache。

3. central cache的中挂的span中use_count记录分配了多少个对象出去，分配⼀个对象给thread  cache，就++use_count

释放内存：

1. 当thread_cache过⻓或者线程销毁，则会将内存释放回central cache中的，释放回来时-- use_count。当use_count减到0时则表⽰所有对象都回到了span，则将span释放回page cache， page cache中会对前后相邻的空闲⻚进⾏合并。

CentralCache.h

#pragma once
#include"Common.h"

//单例模式（饿汉）
class CentralCache
{
public:
	static CentralCache* GetInstance()
	{
		//饿汉模式在main函数之前就创建了，main函数之前不存在多线程，没有线程安全问题
		return &_sInst;
	}
	// 获取一个非空的span
	Span* GetOneSpan(SpanList& list, size_t byte_size);

	// 从中心缓存获取一定数量的对象给 thread cache
	size_t FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t byte_size);

private:
	//构造函数初始化，初始化列表阶段，
	// 不写构造函数，默认会对自定义类型成员进行初始化
	SpanList _spanLists[NFREELIST];

private:
	CentralCache() {}
	//防拷贝
	CentralCache(const CentralCache&) = delete;

	//只是声明，不是定义，因为是static
	static CentralCache _sInst;
};

Common.h

#pragma once

#include<iostream>
#include<thread>
#include<vector>
#include<algorithm>
#include <new>
#include <time.h>
#include <assert.h>
#include <mutex>
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256;//最大内存k
static const size_t NFREELIST = 256;//总的桶个数

#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef  size_t PAGE_ID;
#elif
	//Linux的
#endif 


static void*& NextObj(void* obj)
{
	return *(void**)obj;
}
//管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);
		//头插
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;
	}
	void PushRange(void* start, void* end)
	{
		NextObj(end) = _freeList;
		_freeList = start;
	}

	void* Pop()
	{
		assert(_freeList);
		//头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		return obj;
	}
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t& MaxSize()
	{
		return _maxSize;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
};

//计算对象大小的对齐映射规则
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费 
	// [1,128]						8byte对齐                                      freelist[0,16) 
	// [128+1,1024]				16byte对齐						freelist[16,72) 
	// [1024+1,81024]				128byte对齐						freelist[72,128) 
	// [8*1024+1,641024]			1024byte对齐						freelist[128,184) 
	// [64*1024+1,256*1024]		8*1024byte对齐					freelist[184,208) 

	//简单版本计算对齐数
	//size_t _RoundUp(size_t size, size_t alignNum)
	//{
	//	size_t alignSize;
	//	if (size % alignNum != 0)
	//	{
	//		alignSize = (size / alignNum + 1) * alignNum;
	//	}
	//	else
	//	{
	//		alignSize = size;
	//	}
	//	return alignSize;
	//}
	//复杂版本计算对齐数
	static inline size_t _RoundUp(size_t bytes, size_t AlignNum)
	{
		return (((bytes)+AlignNum - 1) & ~(AlignNum - 1));
	}

	//对齐大小计算
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);//8字节对齐
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);//16字节对齐

		}
		else if (size <= 8*1024)
		{
			return _RoundUp(size, 128);//128字节对齐

		}
		else if (size <= 64*1024)
		{
			return _RoundUp(size, 1024);//1024字节对齐

		}
		else if (size <= 256*1024)
		{
			return _RoundUp(size, 8*1024);//8字节对齐
		}
		else
		{
			assert(false);
			return -1;
		}
	}

	//简单计算桶的下标
	//size_t _Index(size_t bytes, size_t alignNum)
	//{
	//	if (bytes % alignNum == 0)
	//	{
	//		return bytes / alignNum - 1;
	//	}
	//	else
	//	{
	//		return bytes / alignNum;
	//	}
	//}
	//复杂计算桶的下标
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	// 计算映射的哪⼀个自由链表桶 
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链 
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 81024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] +
				group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

	// 一次thread cache从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0); 

		// [2, 512], 一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

};

// 管理多个连续页大块内存跨度结构  
struct Span {
	PAGE_ID _pageId = 0; // 大块内存起始页的页号  
	size_t _n = 0;       // 页的数量  

	Span* _next = nullptr; // 双向链表的结构  
	Span* _prev = nullptr;

	size_t _useCount = 0; // 切好小块内存，被分配给thread cache的计数  
	void* _freeList = nullptr; // 切好的小块内存的自由链表  
};

class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	void Insert(Span*pos,Span*newSpan)
	{
		assert(newSpan);
		assert(pos);

		Span* prev = pos->_prev;
		// prev newspan pos
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
private:
	Span* _head;
public:

	std::mutex _mtx;//桶锁
};

CentralCache.cpp

#include "CentralCache.h"

CentralCache CentralCache::_sInst;

// 获取一个非空的span
Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
{
	// ...
	return nullptr;
}

// 从中心缓存获取一定数量的对象给thread cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size)
{
	size_t index = SizeClass::Index(size);
	_spanLists[index]._mtx.lock();

	Span* span = GetOneSpan(_spanLists[index], size);
	assert(span);
	assert(span->_freeList);

	//从span中获取batchNum个对象
	//如果不够batchNum个，有多少拿多少
	start = span->_freeList;
	end = start;
	size_t i = 0;
	size_t actualNum = 1;
	while ((i < batchNum - 1 && NextObj(end) != nullptr))
	{
		end = NextObj(end);
		++i;
		++actualNum;
	}
	span->_freeList = NextObj(end);
	NextObj(end) = nullptr;
	_spanLists[index]._mtx.unlock();
	return actualNum;
}

ThreadCache.cpp

#include"ThreadCache.h"
#include"CentralCache.h"

void* ThreadCache::FetchFromCentralCache(size_t index, size_t size) {
	// 慢开始反馈调节算法
	// 1. 最开始不会一次向central cache一次批量要太多，因为要太多了可能用不完
	// 2. 如果你不断需要这个size大小内存需求，那么batchNum就会不断增长，直到上限
	// 3. size越大，一次向central cache要的batchNum就越小
	// 4. size越小，一次向central cache要的batchNum就越大
	size_t batchNum = std::min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));
	if (_freeLists[index].MaxSize() == batchNum)
	{
		_freeLists[index].MaxSize() += 1;
	}

	void* start = nullptr;
	void* end = nullptr;
	//实际多少个，因为可能存在供不应求，但至少有一个
	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);
	assert(actualNum > 1);
	if (actualNum == 1)
	{
		assert(start == end);
		return start;
	}
	else
	{
		_freeLists[index].PushRange(NextObj(start), end);
		return start;
	}
}


// 申请和释放内存对象 
void* ThreadCache::Allocate(size_t size)
{
	assert(size <= MAX_BYTES);
	//算一下对齐大小
	size_t alignSize = SizeClass::RoundUp(size);
	//哪一个桶里面 下标值index
	size_t index = SizeClass::Index(size);
	if (!_freeLists[index].Empty())
	{
		return _freeLists[index].Pop();
	}
	else
	{
		//else说明这一个桶对应的自由链表没有 就要去下一层去取了// 从中心缓存获取对象 
		// void* FetchFromCentralCache(size_t index, size_t size);
		return FetchFromCentralCache(index, alignSize);//对齐后的大小
	}
}

void ThreadCache::Deallocate(void* ptr, size_t size)
{
	assert(size <= MAX_BYTES);
	assert(ptr);

	//找对映射的自由链表桶，对象插入进去
	size_t index = SizeClass::Index(size);
	_freeLists[index].Push(ptr);
}

⾼并发内存池--page cache

申请内存：

1. 当central cache向page cache申请内存时，page cache先检查对应位置有没有span，如果没有则 向更⼤⻚寻找⼀个span，如果找到则分裂成两个。⽐如：申请的是4⻚page，4⻚page后⾯没有挂 span，则向后⾯寻找更⼤的span，假设在10⻚page位置找到⼀个span，则将10⻚page span分裂 为⼀个4⻚page span和⼀个6⻚page span。

2. 如果找到_spanList[128]都没有合适的span，则向系统使⽤mmap、brk或者是VirtualAlloc等⽅式 申请128⻚page span挂在⾃由链表中，再重复1中的过程。

3. 需要注意的是central cache和page cache 的核⼼结构都是spanlist的哈希桶，但是他们是有本质区别的，central cache中哈希桶，是按跟thread cache⼀样的⼤⼩对⻬关系映射的，他的spanlist中 挂的span中的内存都被按映射关系切好链接成⼩块内存的⾃由链表。⽽page cache 中的spanlist则 是按下标桶号映射的，也就是说第i号桶中挂的span都是i⻚内存。

释放内存：

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

从堆中申请内存，页号和地址的关系

在操作系统中，堆内存管理通常涉及将内存分为多个页面，每个页面通常是4KB大小（这个大小可能会根据不同的系统架构而有所不同）。页号和地址之间的关系是直接的，可以通过以下方式计算：

假设我们有以下定义：

• PAGE_SIZE 是每个页的大小，通常是4KB（即 4096字节）。
• page_number 是页号，一个非负整数。
• address 是内存中的某个地址。

页号和物理地址之间的关系可以通过以下公式计算：

复制

address = page_number * PAGE_SIZE

反过来，如果你有一个内存地址，你可以通过以下公式计算它所在的页号：

复制

page_number = address / PAGE_SIZE

这里的除法是整数除法，它会丢弃任何余数，只保留结果的整数部分。

以下是一个简单的示例，假设PAGE_SIZE是4096：

#include <iostream>

#define PAGE_SIZE 4096 // 4KB

// 函数：根据页号计算地址
uintptr_t getPageAddress(int page_number) {
    return static_cast<uintptr_t>(page_number) * PAGE_SIZE;
}

// 函数：根据地址计算页号
int getAddressPageNumber(uintptr_t address) {
    return static_cast<int>(address / PAGE_SIZE);
}

int main() {
    int page_number = 10; // 示例页号
    uintptr_t address = getPageAddress(page_number);
    std::cout << "Page " << page_number << " starts at address " << address << std::endl;

    // 反过来，根据地址计算页号
    int calculated_page_number = getAddressPageNumber(address);
    std::cout << "Address " << address << " is on page " << calculated_page_number << std::endl;

    return 0;
}

在这个例子中，如果你调用getPageAddress(10)，它将返回页号为10的起始地址，即10 * 4096。如果你有一个地址，比如0x10000（它是4096的十六进制表示），调用getAddressPageNumber(0x10000)将返回页号2，因为0x10000 / 4096 = 2。

内存回收

测试

高并发内存池-使用定长内存池配合脱离使用new

释放对象时优化为不传对象大小

测试+改错

性能优化