博客新地址:https://github.com/AngryHacker/articles/blob/master/src/code_reading/memorypool.md
什么是内存池?什么是 C++ 的 allocator?
内存池简单说,是为了减少频繁使用 malloc/free new/delete 等系统调用而造成的性能损耗而设计的。当我们的程序需要频繁地申请和释放内存时,频繁地使用内存管理的系统调用可能会造成性能的瓶颈,嗯,是可能,毕竟操作系统的设计也不是盖的(麻麻说把话说太满会被打脸的(⊙v⊙))。内存池的思想是申请较大的一块内存(不够时继续申请),之后把内存管理放在应用层执行,减少系统调用的开销。
那么,allocator 呢?它默默的工作在 C++ 所有容器的内存分配上。默默贴几个链接吧:
http://www.cnblogs.com/wpcockroach/archive/2012/05/10/2493564.html
http://blog.csdn.net/justaipanda/article/details/7790355
http://www.cplusplus.com/reference/memory/allocator/
http://www.cplusplus.com/reference/memory/allocator_traits/
当你对 allocator 有基本的了解之后,再看这个项目应该会有恍然大悟的感觉,因为这个内存池是以一个 allocator 的标准来实现的。一开始不明白项目里很多函数的定义是为了什么,结果初步了解了 allocator 后才知道大部分是标准接口。这样一个 memory pool allocator 可以与大多数 STL 容器兼容,也可以应用于你自定义的类。像作者给出的例子 —— test.cpp, 是用一个基于自己写的 stack 来做 memory pool allocator 和 std::allocator 性能的对比 —— 最后当然是 memory pool allocator 更优。
项目:
Github:MemoryPool
基本使用:
因为这是一个 allocator 类,所以所有使用 std::allocator 的地方都可以使用这个 MemoryPool。在项目的 test.cpp 中,MemoryPool 作为 allocator 用于 StackAlloc(作者实现的 demo 类) 的内存管理类。定义如下:
StackAlloc<int, MemoryPool<int> > stackPool;
其次,你也可以将其直接作为任一类型的内存池,用 newElement 创建新元素,deleteElement 释放元素,就像 new/delete 一样。用下面的例子和 new/delete 做对比:
#include <iostream>
#include <cassert>
#include <time.h>
#include <vector>
#include <stack>
#include "MemoryPool.h"
using namespace std;
/* Adjust these values depending on how much you trust your computer */
#define ELEMS 1000000
#define REPS 50
int main()
{
clock_t start;
MemoryPool<size_t> pool;
start = clock();
for(int i = 0;i < REPS;++i)
{
for(int j = 0;j< ELEMS;++j)
{
// 创建元素
size_t* x = pool.newElement();
// 释放元素
pool.deleteElement(x);
}
}
std::cout << "MemoryPool Time: ";
std::cout << (((double)clock() - start) / CLOCKS_PER_SEC) << "\n\n";
start = clock();
for(int i = 0;i < REPS;++i)
{
for(int j = 0;j< ELEMS;++j)
{
size_t* x = new size_t;
delete x;
}
}
std::cout << "new/delete Time: ";
std::cout << (((double)clock() - start) / CLOCKS_PER_SEC) << "\n\n";
return 0;
}
运行的结果是:
MemoryPool Time: 1.93389
new/delete Time: 4.64903
嗯,内存池快了一倍多。如果是自定义的类的话这个差距应该还会更大一点。
代码分析:
项目的实现有 C++11 和 C++98 两个版本,C++11 版本似乎更加高效,不过个人 C++11 了解不多,就以 C++98 版本来分析吧。
主要函数:
allocate 分配一个对象所需的内存空间
deallocate 释放一个对象的内存(归还给内存池,不是给操作系统)
construct 在已申请的内存空间上构造对象
destroy 析构对象
newElement 从内存池申请一个对象所需空间,并调用对象的构造函数
deleteElement 析构对象,将内存空间归还给内存池
allocateBlock 从操作系统申请一整块内存放入内存池
关键知识点:
理解项目的关键在于理解 placement new 和 union 的用法.
placement new: http://blog.csdn.net/zhangxinrun/article/details/5940019
union:http://www.cnblogs.com/BeyondTechnology/archive/2010/09/19/1831293.html
关于 union 的使用觉得好巧妙,这是相应的定义:
union Slot_ {
value_type element;
Slot_* next;
};
Slot_ 在创建对象的时候存放对象的值,当这个对象被释放时这块内存作为一个 Slot_* 指针放入 free 的链表。所以 Slot_ 既可以用来存放对象,又可以用来构造链表。
工作原理:
内存池是一个一个的 block 以链表的形式连接起来,每一个 block 是一块大的内存,当内存池的内存不足的时候,就会向操作系统申请新的 block 加入链表。还有一个 freeSlots_ 的链表,链表里面的每一项都是对象被释放后归还给内存池的空间,内存池刚创建时 freeSlots_ 是空的,之后随着用户创建对象,再将对象释放掉,这时候要把内存归还给内存池,怎么归还呢?就是把指向这个对象的内存的指针加到 freeSlots_ 链表的前面(前插)。
用户在创建对象的时候,先检查 freeSlots_ 是否为空,不为空的时候直接取出一项作为分配出的空间。否则就在当前 block 内取出一个 Slot_ 大小的内存分配出去,如果 block 里面的内存已经使用完了呢?就向操作系统申请一个新的 block。
内存池工作期间的内存只会增长,不释放给操作系统。直到内存池销毁的时候,才把所有的 block delete 掉。
注释源码:
头文件:
/*-
* Copyright (c) 2013 Cosku Acay, http://www.coskuacay.com
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
* IN THE SOFTWARE.
*/
#ifndef MEMORY_POOL_H
#define MEMORY_POOL_H
#include <limits.h>
#include <stddef.h>
template <typename T, size_t BlockSize = 4096>
class MemoryPool
{
public:
/* Member types */
typedef T value_type; // T 的 value 类型
typedef T* pointer; // T 的 指针类型
typedef T& reference; // T 的引用类型
typedef const T* const_pointer; // T 的 const 指针类型
typedef const T& const_reference; // T 的 const 引用类型
typedef size_t size_type; // size_t 类型
typedef ptrdiff_t difference_type; // 指针减法结果类型
template <typename U> struct rebind {
typedef MemoryPool<U> other;
};
/* Member functions */
/* 构造函数 */
MemoryPool() throw();
MemoryPool(const MemoryPool& memoryPool) throw();
template <class U> MemoryPool(const MemoryPool<U>& memoryPool) throw();
/* 析构函数 */
~MemoryPool() throw();
/* 元素取址 */
pointer address(reference x) const throw();
const_pointer address(const_reference x) const throw();
// Can only allocate one object at a time. n and hint are ignored
// 分配和收回一个元素的内存空间
pointer allocate(size_type n = 1, const_pointer hint = 0);
void deallocate(pointer p, size_type n = 1);
// 可达到的最多元素数
size_type max_size() const throw();
// 基于内存池的元素构造和析构
void construct(pointer p, const_reference val);
void destroy(pointer p);
// 自带申请内存和释放内存的构造和析构
pointer newElement(const_reference val);
void deleteElement(pointer p);
private:
// union 结构体,用于存放元素或 next 指针
union Slot_ {
value_type element;
Slot_* next;
};
typedef char* data_pointer_; // char* 指针,主要用于指向内存首地址
typedef Slot_ slot_type_; // Slot_ 值类型
typedef Slot_* slot_pointer_; // Slot_* 指针类型
slot_pointer_ currentBlock_; // 内存块链表的头指针
slot_pointer_ currentSlot_; // 元素链表的头指针
slot_pointer_ lastSlot_; // 可存放元素的最后指针
slot_pointer_ freeSlots_; // 元素构造后释放掉的内存链表头指针
size_type padPointer(data_pointer_ p, size_type align) const throw(); // 计算对齐所需空间
void allocateBlock(); // 申请内存块放进内存池
/*
static_assert(BlockSize >= 2 * sizeof(slot_type_), "BlockSize too small.");
*/
};
#include "MemoryPool.tcc"
#endif // MEMORY_POOL_H
实现文件:
/*-
* Copyright (c) 2013 Cosku Acay, http://www.coskuacay.com
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
* IN THE SOFTWARE.
*/
#ifndef MEMORY_BLOCK_TCC
#define MEMORY_BLOCK_TCC
// 计算对齐所需补的空间
template <typename T, size_t BlockSize>
inline typename MemoryPool<T, BlockSize>::size_type
MemoryPool<T, BlockSize>::padPointer(data_pointer_ p, size_type align)
const throw()
{
size_t result = reinterpret_cast<size_t>(p);
return ((align - result) % align);
}
/* 构造函数,所有成员初始化 */
template <typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::MemoryPool()
throw()
{
currentBlock_ = 0;
currentSlot_ = 0;
lastSlot_ = 0;
freeSlots_ = 0;
}
/* 复制构造函数,调用 MemoryPool 初始化*/
template <typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::MemoryPool(const MemoryPool& memoryPool)
throw()
{
MemoryPool();
}
/* 复制构造函数,调用 MemoryPool 初始化*/
template <typename T, size_t BlockSize>
template<class U>
MemoryPool<T, BlockSize>::MemoryPool(const MemoryPool<U>& memoryPool)
throw()
{
MemoryPool();
}
/* 析构函数,把内存池中所有 block delete 掉 */
template <typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::~MemoryPool()
throw()
{
slot_pointer_ curr = currentBlock_;
while (curr != 0) {
slot_pointer_ prev = curr->next;
// 转化为 void 指针,是因为 void 类型不需要调用析构函数,只释放空间
operator delete(reinterpret_cast<void*>(curr));
curr = prev;
}
}
/* 返回地址 */
template <typename T, size_t BlockSize>
inline typename MemoryPool<T, BlockSize>::pointer
MemoryPool<T, BlockSize>::address(reference x)
const throw()
{
return &x;
}
/* 返回地址的 const 重载*/
template <typename T, size_t BlockSize>
inline typename MemoryPool<T, BlockSize>::const_pointer
MemoryPool<T, BlockSize>::address(const_reference x)
const throw()
{
return &x;
}
// 申请一块空闲的 block 放进内存池
template <typename T, size_t BlockSize>
void
MemoryPool<T, BlockSize>::allocateBlock()
{
// Allocate space for the new block and store a pointer to the previous one
// operator new 申请对应大小内存,返回 void* 指针
data_pointer_ newBlock = reinterpret_cast<data_pointer_>
(operator new(BlockSize));
// 原来的 block 链头接到 newblock
reinterpret_cast<slot_pointer_>(newBlock)->next = currentBlock_;
// 新的 currentblock_
currentBlock_ = reinterpret_cast<slot_pointer_>(newBlock);
// Pad block body to staisfy the alignment requirements for elements
data_pointer_ body = newBlock + sizeof(slot_pointer_);
// 计算为了对齐应该空出多少位置
size_type bodyPadding = padPointer(body, sizeof(slot_type_));
// currentslot_ 为该 block 开始的地方加上 bodypadding 个 char* 空间
currentSlot_ = reinterpret_cast<slot_pointer_>(body + bodyPadding);
// 计算最后一个能放置 slot_type_ 的位置
lastSlot_ = reinterpret_cast<slot_pointer_>
(newBlock + BlockSize - sizeof(slot_type_) + 1);
}
// 返回指向分配新元素所需内存的指针
template <typename T, size_t BlockSize>
inline typename MemoryPool<T, BlockSize>::pointer
MemoryPool<T, BlockSize>::allocate(size_type, const_pointer)
{
// 如果 freeSlots_ 非空,就在 freeSlots_ 中取内存
if (freeSlots_ != 0) {
pointer result = reinterpret_cast<pointer>(freeSlots_);
// 更新 freeSlots_
freeSlots_ = freeSlots_->next;
return result;
}
else {
if (currentSlot_ >= lastSlot_)
// 之前申请的内存用完了,分配新的 block
allocateBlock();
// 从分配的 block 中划分出去
return reinterpret_cast<pointer>(currentSlot_++);
}
}
// 将元素内存归还给 free 内存链表
template <typename T, size_t BlockSize>
inline void
MemoryPool<T, BlockSize>::deallocate(pointer p, size_type)
{
if (p != 0) {
// 转换成 slot_pointer_ 指针,next 指向 freeSlots_ 链表
reinterpret_cast<slot_pointer_>(p)->next = freeSlots_;
// 新的 freeSlots_ 头为 p
freeSlots_ = reinterpret_cast<slot_pointer_>(p);
}
}
// 计算可达到的最大元素上限数
template <typename T, size_t BlockSize>
inline typename MemoryPool<T, BlockSize>::size_type
MemoryPool<T, BlockSize>::max_size()
const throw()
{
size_type maxBlocks = -1 / BlockSize;
return (BlockSize - sizeof(data_pointer_)) / sizeof(slot_type_) * maxBlocks;
}
// 在已分配内存上构造对象
template <typename T, size_t BlockSize>
inline void
MemoryPool<T, BlockSize>::construct(pointer p, const_reference val)
{
// placement new 用法,在已有内存上构造对象,调用 T 的复制构造函数,
new (p) value_type (val);
}
// 销毁对象
template <typename T, size_t BlockSize>
inline void
MemoryPool<T, BlockSize>::destroy(pointer p)
{
// placement new 中需要手动调用元素 T 的析构函数
p->~value_type();
}
// 创建新元素
template <typename T, size_t BlockSize>
inline typename MemoryPool<T, BlockSize>::pointer
MemoryPool<T, BlockSize>::newElement(const_reference val)
{
// 申请内存
pointer result = allocate();
// 在内存上构造对象
construct(result, val);
return result;
}
// 删除元素
template <typename T, size_t BlockSize>
inline void
MemoryPool<T, BlockSize>::deleteElement(pointer p)
{
if (p != 0) {
// placement new 中需要手动调用元素 T 的析构函数
p->~value_type();
// 归还内存
deallocate(p);
}
}
#endif // MEMORY_BLOCK_TCC
今天的文章【源码剖析】MemoryPool —— 简单高效的内存池 allocator 实现分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/32339.html