基于一个简单定长内存池的实现方法详解
主要分为 3 个部分,memoryPool 是管理内存池类,block 表示内存块,chunk 表示每个存储小块。它们之间的关系为,memoryPool 中有一个指针指向某一起始 block,block 之前通过 next 指针构成链表结构的连接,每个 block 包含指定数量的 chunk。每次分配内存的时候,分配 chunk 中的数据地址。
主要数据结构设计:
Block:
struct block {
block * next;//指向下一个block指针
unsigned int numofChunks;
unsigned int numofFreeChunks;//剩余free的chunk数量
unsigned int blockNum;//该block的编号
char * data;
queue<int> freepos; //记录可用chunk序号
};
MemoryPool:
class memoryPool {
unsigned int initNumofChunks; //每个block的chunk数量
unsigned int chunkSize;//每个chunk的数据大小
unsigned int steps;//每次扩展的chunk数量
unsigned int numofBlocks;//当前管理多少个blocks
block * blocksPtr;//指向起始block
block * blocksPtrTail;//指向末尾block
block * firstHasFreeChunksBlock;//指向第一个不为空的block
};
Chunk:
ChunkNum:该 chunk 所在 block 里的编号
blockAddress: 该 chunk 所对应的 block,主要用于 free 这个 chunk 的时候,能够快速找到所属 block,并进行相应更新
data:实际供使用的数据起始位置
关键操作说明:
内存分配:
从 firstHasFreeChunksBlock 开始查找第一个有 free 位置的 block,如果找到,则则获取该 block 的 freepos 的队首元素,返回该元素序号对应的 chunk 的数据地址,并将 freepos 的队首元素弹出,其他相关属性更新。如果找不到,则新增 steps 个 chunk,再重复上面的过程。
内存释放:
传入待释放的地址指针p,通过对p的地址移动可以找到chunk中的 ChunkNum 和 blockAddress 两个数据,通过 blockAddress 可以找到该 chunk 所属的 block,然后将ChunkNum 添加到该 block 的 freepos 中,其他相应属性更新。
使用方法:
memoryPool * mp = new memoryPool (256);
char * s = (char *)mp->allocate();
// 一些操作
mp->freeMemory(s);
delete mp;
不足:
没考虑线程安全问题,该实现方案在单线程下可以正常运行。
程序源代码:
#include <iostream>
#include <queue>
#include <string.h>
#include <ctime>
using namespace std;
struct block {
block * next;
unsigned int numofChunks;//指向下一个block指针
unsigned int numofFreeChunks;//剩余free的chunk数量
unsigned int blockNum;//该block的编号
char * data;
//记录可用chunk序号
queue<int> freepos;
block(unsigned int _numofChunks ,unsigned int _chunkSize, unsigned int _blockNum){
numofChunks = _numofChunks;
numofFreeChunks = _numofChunks;
blockNum = _blockNum;
next = NULL;
data = new char [numofChunks * (sizeof(unsigned int) + sizeof(void *) + _chunkSize)];
char * p = data;
//每个chunk的结构:4byte的chunk序号 + 4byte的所属block地址 + 真正的数据
for(int i=0;i<numofChunks;i++){
char * ptr = p + i * (_chunkSize + sizeof(unsigned int) + sizeof(void *));
unsigned int * num = (unsigned int *)(ptr);
*num = i;
ptr += sizeof(void *);
int * blockpos = (int *) ptr;
*blockpos = (int)this;
freepos.push(i);
}
}
~block(){
delete [] data;
}
};
class memoryPool {
public :
memoryPool(unsigned int _chunkSize = 256, unsigned int _initNumofChunks = 4096, unsigned int _steps = 64){
initNumofChunks = _initNumofChunks;
chunkSize = _chunkSize;
steps = _steps;
numofBlocks = steps;
//创建内存池时,初始化一定数量的内存空间
block * p = new block(initNumofChunks, chunkSize, 0);
blocksPtr = p;
for(int i=1;i<steps;i++){
p->next = new block(initNumofChunks, chunkSize, i);
p = p->next;
blocksPtrTail = p;
}
firstHasFreeChunksBlock = blocksPtr;
}
~memoryPool(){
block * p = blocksPtr;
while(blocksPtr!=NULL){
p = blocksPtr->next;
delete blocksPtr;
blocksPtr = p;
}
}
/*
从firstHasFreeChunksBlock开始查找第一个有free位置的block,
如果找到,则则获取该block的freepos的对首元素,
返回该元素序号对应的chunk的数据地址,并将freepos的队首元素弹出,
其他相关属性更新。如果找不到,则新增steps个chunk,再重复上面的过程。
*/
void * allocate(){
block * p = firstHasFreeChunksBlock;
while(p != NULL && p->numofFreeChunks <= 0) p = p->next;
if(p == NULL){
p = blocksPtrTail;
increaseBlocks();
p = p->next;
firstHasFreeChunksBlock = p;
}
unsigned int pos = p->freepos.front();
void * chunkStart = (void *)(p->data + pos * (chunkSize + sizeof(unsigned int) + sizeof(void *)));
void * res = chunkStart + sizeof(unsigned int) + sizeof(void *);
p->freepos.pop();
p->numofFreeChunks --;
return res;
}
void increaseBlocks(){
block * p = blocksPtrTail;
for(int i=0; i<steps; i++){
p->next = new block(initNumofChunks, chunkSize, numofBlocks);
numofBlocks++;
p = p->next;
blocksPtrTail = p;
}
}
/*
传入待释放的地址指针_data,
通过对_data的地址移动可以找到chunk中的ChunkNum和blockAddress两个数据,
通过blockAddress可以找到该chunk所属的block,
然后将ChunkNum添加到该block的freepos中,其他相应属性更新。
*/
void freeMemory(void * _data){
void * p = _data;
p -= sizeof(void *);
int * blockpos = (int *) p;
block * b = (block *) (*blockpos);
p -= sizeof(unsigned int);
int * num = (int *) p;
b->freepos.push(*num);
b->numofFreeChunks ++;
if (b->numofFreeChunks > 0 && b->blockNum < firstHasFreeChunksBlock->blockNum)
firstHasFreeChunksBlock = b;
}
private :
unsigned int initNumofChunks; //每个block的chunk数量
unsigned int chunkSize;//每个chunk的数据大小
unsigned int steps;//每次扩展的chunk数量
unsigned int numofBlocks;//当前管理多少个blocks
block * blocksPtr;//指向起始block
block * blocksPtrTail;//指向末尾block
block * firstHasFreeChunksBlock;//指向第一个不为空的block
};
//test
void echoPositionNum(char * p){
p -= (sizeof(void *) + sizeof(unsigned int));
int * num = (int *) p;
cout<<*num<<endl;
}
//测试
void test0(){
memoryPool mp;
char * s1 = (char *)mp.allocate();
char * s2 = (char *)mp.allocate();
char str [256];
char str2 [256];
char str3 [256];
for(int i=0; i<255; i++) {
str[i] = 'a';str2[i] = 'b';str3[i] = 'c';
}
str[255] = '\0';
str2[255] = '\0';
strcpy(s1,str);
strcpy(s2,str2);
str3[255] = '\0';
echoPositionNum(s1);
cout<<s1<<endl;
mp.freeMemory(s1);
echoPositionNum(s2);
cout<<s2<<endl;
char * s3 = (char *)mp.allocate();
strcpy(s3,str3);
echoPositionNum(s3);
cout<<s3<<endl;
}
void test1(){
clock_t clock_begin = clock();
const int N = 50000;
char * s[N];
int round = 100;
while(round>=0){
round --;
for(int i=0;i<N;i++){
s[i] = new char[256];
}
for(int i=0;i<N;i++){
delete [] s[i];
}
}
clock_t clock_end = clock();
cout<<"Time cost\t"<<clock_end - clock_begin<<endl;
}
void test2(){
memoryPool mp(256);
clock_t clock_begin = clock();
const int N = 50000;
char * s[N];
int round = 100;
while(round>=0){
round --;
for(int i=0;i<N;i++){
s[i] = (char *)mp.allocate();
}
for(int i=0;i<N;i++){
mp.freeMemory(s[i]);
}
}
clock_t clock_end = clock();
cout<<"Time cost\t"<<clock_end - clock_begin<<endl;
}
int main()
{
test0();
test1();
test2();
return 0;
}
运行结果:
相关文章
- php如何实现抓取网页图片,相较于手动的粘贴复制,使用小程序要方便快捷多了,喜欢编程的人总会喜欢制作一些简单有用的小软件,最近就参考了网上一个php抓取图片代码,封装了一个php远程抓取图片的类,测试了一下,效果还不错分享...2015-10-30
- 批量更新mysql更新语句很简单,更新一条数据的某个字段,一般这样写:复制代码 代码如下:UPDATE mytable SET myfield = 'value' WHERE other_field = 'other_value';如果更新同一字段为同一个值,mysql也很简单,修改下where即...2013-10-04
- EXCEL数据上传到SQL SERVER中的方法需要注意到三点!注意点一:要把EXCEL数据上传到SQL SERVER中必须提前把EXCEL传到服务器上.做法: 在ASP.NET环境中,添加一个FileUpload上传控件后台代码的E.X: 复制代码 代码如下: if...2013-09-23
- 我们都知道用php+mysql在web 页实现数据库资料全部显示是非常简单而有趣的,数据库资料很少的情况下页面显示还是让人满意的,但是当数据库资料非常多的情况下,页面的显示情况将会变的非常糟糕,下面就来介绍一下如何实现当...2015-11-08
- 由于国内好几个浏览器都是双核浏览器(蛋痛,做一个浏览器壳就说国产,而且使用率高),有时打开网页会出现不兼容模式,在极速模式下是好的,现在我们来用代码实现网页自动调用国内...2016-09-20
- 小编推荐的这篇文章介绍了PHP中对汉字进行unicode编码和解码的实现方法,非常实用,有兴趣的同学可以参考一下。 代码如下复制代码 //将内容进行UNICODE编码fu...2017-07-06
- 微信扫码网站自动登录的原是还是比较简单的,只要各位知道相互的原理就可以实现了,下面我们来看两个例子,我相信各位看了这两个例子肯定知道怎么来做了。 magento 微...2016-11-25
- 在php程序中有事会需要用到C代码,这篇文章着重介绍一下用C写php扩展的方法,而且不需要重新编译php。有需要的同学可以参考一下。 在php程序中需要用到C代码,应该是下...2017-07-06
- 本文介绍了php使用PDO事务配合表格读取大量数据插入操作实现方法,非常实用,有兴趣的同学快来看看吧。 在处理大量数据的时候,或者同时对几个表操作,而这几个表的操作...2017-07-06
php mysql_insert_id()返回数据库最新id实现方法
php mysql_insert_id()返回数据库最新id实现方法 有需要同学可参考一下。 代码如下 复制代码 mysql_insert_id() mysql_insert_id() 函数...2016-11-25- 小编推荐的这篇文章介绍了用PHP将Unicode 转化为UTF-8的实现方法,非常实用,有兴趣的同学快来看看吧。 代码如下复制代码 functionunescape($str) { $str= ra...2017-07-06
- 从异步JS的重要性开始说起,再引入异步js框架,一步步的深入了解异步JS。1.异步JS的重要性 随着Web平台地位的提升,霸占着浏览器的JavaScript语言也成为了世界上最流行的语言之一,甚至通过Node.js进入了服务器编程领域。Jav...2015-10-30
- 表四:Socket函数 函数名 描述 socket_accept() 接受一个Socket连接 socket_bind() 把socket绑定在一个IP地址和端口上 socket_clear_error() 清除socket...2016-11-25
- 在php页面缓存主要用到的是ob系列函数,如ob_start(),ob_end_flush(),ob_get_contents(),但是更高级的缓存是不使用这些函数的,本文章最后一个实现就有讲到,大家可参考一...2016-11-25
- 我们知道 Zend 有免费的优化引擎针对 PHP 而作,但是 FreeLAMP 这次采用的是一个叫做 PHP Accelerator 的缓冲产品。 我们在 “LAMP 加速” 这篇文章中阐述过加速的...2016-11-25
- php定时跳转我们需要利用header函数输入html或js代码来实现定时跳转了,下面我来介绍一个简单的例子 php代码 代码如下 复制代码 header("ref...2016-11-25
- 今天我们来讲述一下简单的方法就是android开发之应用程序全屏实现方法,有需要的同学可以参考一下本文章。 一般Android的应用启动时都有欢迎界面,类似QQHD启动那样...2016-09-20
- 本文章介绍了关于现在浏行的安卓手机软件中如何加入广告哦,下面我们来看看关于android软件中加入广告实现方法吧。 经过了一番折腾,忙忙碌碌了一下午,终于搞明白了An...2016-09-20
- php教程 用户注册并且设置为己登录状态实现方法,下面实例讲述了如何把表单提交的数据保存到mysql教程数据库教程,而没有实现用户注册后自动登录的功能,而实例二就实现了...2016-11-25
- 文章利用了一个简单的实例来实现php从数据库中读取数据详细讲解,有需要的朋友可以看看,这里同时还简单的讲到了安全问题。 先看段代码 代码如下 复制代码...2016-11-25