【项目日记】高并发内存池---细节优化及性能测试

static void* ConcurrentAlloc(size_t size)
{
	//如果size的空间大于的32页，就不能在线程缓存里进行取了
	//因为线程缓存中最大的内存块是256KB 
	//超过32页就需要取页缓存中去进行取了
	if (size > MAX_BYTES)
	{
		//计算对齐空间
		size_t alignsize = SizeClass::RoundUp(size);
		//计算页数
		size_t num = alignsize >> PAGE_SHIFT;
		//根据页数开辟span
		PageCache::GetInstance()->GetMutex().lock();
		Span * span = PageCache::GetInstance()->NewSpan(num);
		PageCache::GetInstance()->GetMutex().unlock();
		span->_objsize = alignsize;
		//根据span中的_pageid计算地址
		void* ptr = (void*)(span->_pageid << PAGE_SHIFT);
		//进行返回即可
		return ptr;
	}
	//在该线程中进行内存的申请
	if (pThreadCache == nullptr)
	{
		static ObjectPool<ThreadCache> tcpool;
		//pThreadCache = new ThreadCache;
		pThreadCache = tcpool.New();
	}
	//进行开辟空间
	void * obj = pThreadCache->Allocate(size);
	//cout << std::this_thread::get_id() << " : " << pThreadCache << endl;
	return obj;
}

static void  ConcurrentFree(void* ptr)
{
	assert(ptr);
	//找到ptr对应的span即可找到字节数
	//在span创建完之后传回给中心缓存挂载起来时就已经确定了其内存块的大小！！！
	Span* span = PageCache::GetInstance()->MapObjectToSpan(ptr);
	size_t size = span->_objsize;
	//如果size大于256KB就要跳过线程缓存和中心缓存
	if (size > MAX_BYTES)
	{
		//直接回收该空间到页缓存中
		PageCache::GetInstance()->GetMutex().lock();
		PageCache::GetInstance()->ReleaseSpanToPageCache(span);
		PageCache::GetInstance()->GetMutex().unlock();
		return;
	}
	//回收空间
	pThreadCache->Deallocate(ptr, size);
}

Span* PageCache::NewSpan(size_t num)
{
	// 如果开辟的页数大于 128 页 内存池就不能发挥作用了
	// 需要直接去堆上申请
	if (num >= PAGENUM)
	{
		//开辟对应的大空间
		void* ptr = SystemAlloc(num);
		//创建span
		//Span* newspan = new Span;
		//使用定长池 跳过new(malloc)
		Span* newspan = _spanpool.New();
		newspan->_pageid = (PAGE_ID)ptr >> PAGE_SHIFT;//页号
		newspan->_n = num;//页数
		//建立哈希映射
		_SpanMap[newspan->_pageid] = newspan;
		//进行返回

		return newspan;
	}
	// 1 - 128
	//...省略...
	//.........
}
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	//如果页数大于128 不能进行合并 直接返回给系统
	if (span->_n > PAGENUM - 1)
	{
		void* ptr = (void*)(span->_pageid << PAGE_SHIFT);
		//解除映射
		_SpanMap.erase(span->_pageid);

		_spanpool.Delete(span);

		SystemFree(ptr);
		

		return;
	}
	//1 -128
	//......
	//......
}

class PageCache
{
public:
	Span* NewSpan(size_t num);
	std::mutex& GetMutex();
	void ReleaseSpanToPageCache(Span* span);
	Span* MapObjectToSpan(void* start);
private:
	//...
	//对象池 方便进行取出span
	ObjectPool<Span> _spanpool;
	//...
	//...
}

static void  ConcurrentFree(void* ptr)
{
	assert(ptr);
	//找到ptr对应的span即可找到字节数
	//在span创建完之后传回给中心缓存挂载起来时就已经确定了其内存块的大小！！！
	Span* span = PageCache::GetInstance()->MapObjectToSpan(ptr);
	size_t size = span->_objsize;
	//如果size大于256KB就要跳过线程缓存和中心缓存
	if (size > MAX_BYTES)
	{
		//直接回收该空间到页缓存中
		PageCache::GetInstance()->GetMutex().lock();
		PageCache::GetInstance()->ReleaseSpanToPageCache(span);
		PageCache::GetInstance()->GetMutex().unlock();
		return;
	}
	//回收空间
	pThreadCache->Deallocate(ptr, size);
}

if()
{
	int x = 0 ;//打上断点
}

#include"Common.h"

// --- 参考tc-malloc源码的基数树优化 ---
//可以实现无锁操作 --- 大大提升性能
//基数树的本质也是哈希表
// 1. 1层的结构就是通过一个大的指针数组来指向span
// 2. 2层的结构就是通过二维数组来实现 比如32位下 8KB页，会有2^19个页号
//	  前5位确认在哪个指针数组 后13位确定具体指针
// 3 3层的同理使用三维数组

// 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)) {
	explicit TCMalloc_PageMap1() {
		//array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
		size_t size = sizeof(void*) << BITS;
		size_t alignSize = SizeClass::_RoundUp(size, 1 << PAGE_SHIFT);
		array_ = (void**)SystemAlloc(alignSize >> PAGE_SHIFT);
		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)) {
	explicit TCMalloc_PageMap2() {
		//allocator_ = allocator;
		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] == 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;
				static ObjectPool<Leaf>	leafPool;
				Leaf* leaf = (Leaf*)leafPool.New();

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

// Three-level radix tree
template <int BITS>
class TCMalloc_PageMap3 {
private:
	// How many bits should we consume at each interior level
	static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up
	static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;

	// How many bits should we consume at leaf level
	static const int LEAF_BITS = BITS - 2 * INTERIOR_BITS;
	static const int LEAF_LENGTH = 1 << LEAF_BITS;

	// Interior node
	struct Node {
		Node* ptrs[INTERIOR_LENGTH];
	};

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

	Node* root_;                          // Root of radix tree
	void* (*allocator_)(size_t);          // Memory allocator

	Node* NewNode() {
		Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
		if (result != NULL) {
			memset(result, 0, sizeof(*result));
		}
		return result;
	}

public:
	typedef uintptr_t Number;

	explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) {
		allocator_ = allocator;
		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] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) {
			return NULL;
		}
		return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
	}

	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);
		reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
	}

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

			// Check for overflow
			if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)
				return false;

			// Make 2nd level node if necessary
			if (root_->ptrs[i1] == NULL) {
				Node* n = NewNode();
				if (n == NULL) return false;
				root_->ptrs[i1] = n;
			}

			// Make leaf node if necessary
			if (root_->ptrs[i1]->ptrs[i2] == NULL) {
				Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
				if (leaf == NULL) return false;
				memset(leaf, 0, sizeof(*leaf));
				root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
			}

			// Advance key past whatever is covered by this leaf node
			key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
		}
		return true;
	}

	void PreallocateMoreMemory() {
	}
};