2014年（6）
分类： C/C++
2014-08-28 18:12:52
当程序运行时，她会持续不断地分配和释放存储对象（尤其是oo模型比较常见，ADT模型可能比较
少）的内存块，由于各种对象的生存周期存在差异，而且通常无法预测，因此就会出现大块内存
碎片分裂成小碎片的现象，显而易见，程序运行时间越长，碎片现象就会越严重。内存碎片可能使
程序执行越来越慢，严重时有可能导致程序停止执行。
内存碎片比较常见的定义是指一大块没有使用的内存（空闲内存）中散布着许多小块正在使用的
内存，严格来说内存碎片总是存在的，但是只有当内存碎片的数量很大的时候，内存碎片才会成为
一个问题，动态地为程序分配和释放内存，重新释放的内存很难再形成连续的大块的内存，出现这
种情况的原因不仅仅在于一个程序使用内存的方式，而且还在于同时有不同的程序使用同一内存资源。
碎片有两种：一种是数据结构未用完“她所分配的全部内存”而产生的所谓的“内部碎片”；另一种
是两个已分配物之间的内存由于太小而无法存储任何东西，所产生的“外部碎片”，如果你删除某个
对象，而她占用的恰好是另外两个对象之间的空间，那么被删除对象的一部分空间会浪费掉。除非：
(1).上述的另外两个对象也被删除了，从而留出了一块连续的内存空间；
(2).你可以将对象在内存中移来移去，从而挤出对象之间的未用空间；
(3).你鸿运当头，另一个对象所需的内存恰好扣合这个未用空间。
碎片很难消除，因为用以减少内部碎片的模式（例如令分配的内存大小全部不偏不倚于真实需求）通常
会增加外部碎片，这是因为所有奇特（怪异）大小的内存分配区块之间空间都被浪费掉了。同样道理，
用以减少外部碎片的模式（例如分配尺寸相同的区块）会增加内部碎片，因为各区块内有一部分内存被
浪费掉了。因此有多种多样的思想应运而生：与其建立新对象，不如重用旧货色亦或可以在程序开始运
行时将所有对象统统建立起来等等。
其次从设计上来说，默认的内存管理器是通用的，也就是说全局new/delete/malloc/free等等是不做
任何简化假设的，线程安全以及所需内存大小的各不相同她们必须全权考虑到。可想而知她们的灵活性
是以牺牲速度为代价的。有的代码可能需要特定大小的内存块或者有的代码只需要在单线程中执行等等，
默认的内存管理器所提供的各种保护机制或灵活性并不被真正的需要，或者说使用这些功能强大的默认
内存管理器根本就是对CPU时钟周期的一种浪费。因此为了效率，特定的内存分配管理迫在眉睫。
另外再引用写侯捷先生的《池内春秋》一文中的部分内容：malloc/new/::operator new(STL内存分配子
不在内)都会在空间和速度上带来额外的开销，空间上额外的开销称为cookie（小甜饼），主要用来标识
所得区块的大小（楼主个人感觉应该还有在所得区块的地址吧！），设想如果没有cookie的存在，一旦你
想释放先前所得的内存块，释放式就无法从指针身上看出区块的大小，也就无法做出正确的回收动作。侯先生
给出了空间和速度上额外开销的明证，有兴趣的同学可自行下载《池内春秋》。个人感觉速度额外开销明证
不是很强有力。于是想出如下方法：
printLocalTime();
for(int i=0; i<20000; ++i)
new char[100];//malloc(100);
printLocalTime();
printLocalTime();
for(int i=0; i<20000; ++i)
new char[i+1];//malloc(i+1);其实写成new char[i]也行。 new/malloc均可申请0字节
printLocalTime();
printLocalTime();
for(int i=0; i<20000; ++i)
{
char* p = new char[i+1];//malloc(i+1);
delete p;
}
printLocalTime();
对比各个时间差，会发现new[100]和new[i+1]相差很远。假设new[100]是定值的话，new[i]则或大于或
小于new[100]，个中细节在此不多说。其实好想和侯先生沟通下这个问题，不知我的想法正确与否。
最后就是个人项目上问题的思考了,接收到外系统发来的报文（注：和大并发，epoll，reactor pattern无关），
然后放到sharing queue中，多线程争相抢食，利用oo面向对象模型不断new+多态+delete工作，当然其他处也少
不了new/malloc/calloc等.....想在项目中（再）添加点实务性前卫的东西或者是从效率的调度考虑优化，
期间参考了各种书目和文献，找到了一个比较不错的想法：找出自己代码的特有点，从这个特有点出发，试着
（并不是一定）去优化，于是乎直接排除对不同大小内存需求做“嘿咻”的想法，锁定在了Fixed Allocation上面。
首先个人感觉代码中的业务类大小总不会无限大，即有个最大的。再加上线程的个数必为定值，也不会无限大
（一般和cpu数目一致较好，可能以后的博文中会探讨到这方面）。这不正好符合Fixed Allocation固定式分配
的需求吗？通过预先分配的结构来满足你的需求，正常处理期间避免动态分配内存（与其建立新对象，不如重用
旧货色），假定我们的程序运行在4核unix上，我们建立四个线程，也就是同时存在同时工作的最多四个业务类，
为了每个业务都能正常工作，我们以sizeof最大的为基准...new char[4*sizeof(max class)]。前提条件你必须
拥有足够的内存可用，也就是说这个最大真的不能很大啊，到底多大合适而且如何在代码中控制这些业务类不能
无限大下去，一致困扰着我，直到在《imperfect c++》中了解到编译期约束才算完美解决，现在我在代码中是硬性
规定业务类不能超过512字节（本来我想让它更小），否则编译期约束会在编译期报错。
在列出Fixed Allocation内存池之前，我们有几点知识必须先了解：
(1)编译期约束
//编译期约束 测试__T1是否是__T2的基类
template
class must_be_the_base
{
public:
~must_be_the_base()
{
void(*fun)(__T1*, __T2*) = constraints;
}
private:
static void constraints(__T1* pFather, __T2* pSon)
{
pFather = pSon;
}
};
工作原理：constraints()是一个静态函数，并且为private所修饰，确保不会被外部调用，析构函数中则声明了一个
指向constraints()的指针，从而强迫编译期至少要去评估该函数以及其语句是否有效，同时这个方案没有任何运行期
的负担。
(/******************************************************************************************/
上述约束存在两个问题：假如传入的是同一种类型则无法作出正确的判断，更甚者假如__T1是void同也无法作出
正确的判断，采用模板局部特化，在此进行修正：
template
class must_be_the_base
{
public:
~must_be_the_base()
{
void (*fun) () = constrains;
}
private:
static void constrains()
{
struct be_the_base
{
char be_the_base_:(0 > 1 ? 1 : 0);
};
}
};
template
class must_be_the_base
{
public:
~must_be_the_base()
{
void(*fun)() = constrains;
}
private:
static void constrains()
{
struct be_the_base
{
struct be_the_base_:(0 > 1 ? 1 : 0);
};
}
};
上述两个问题解决了，但是还有另一个问题，假如两个__T1和__T2都是void类型呢？
上述两个局部特化就存在二义性。我们会很自然的想到利用模板全特化进行处理，然而编译器会在
编译期编译模板全特化的。我们现在写的编译期约束本质就是利用了模板实例化时才会被编译的特性的。
我们的目的是在我们写出must_be_the_base
must_be_the_base
muse_be_the_base
其实我们就此可以打住。让二义性存在着，反正这个时候只要程序员写出
must_be_the_base
然而......我们是否可以从模板类里面的成员函数写成模板的形式下手呢？
我们需要做进一步的处理，
template<>
class must_be_the_base
{
public:
/*注：此处为构造函数，之前均为析构函数，因析构函数无法模板化，之前都是采用析构函数是有原因的，
因为类的析构函数只能有一个，不像构造函数可能有多种重载的形式。
*/
template
must_be_the_base() {}
};
当我们写出 must_be_the_base
然而写出must_be_the_bse
template<>
class must_be_the_base
{
public:
template
must_be_the_base(---) //故意在此写出一些乱起八糟不正确的东西
{}
};
当我们再次写出must_be_the_bae
现的很好，HP UNIX上的aCC却没有报任何错误，这使我很困惑！！！
希望能在《c++ templates》一书中找到解决方案。因楼主对template涉猎尚不是很深，只能继续努力研读。
博文原是在2014.08.28写的，现在今天2014.9.22对此进行了修正。
/****************************************************************************************/)
//编译期约束 测试小于512个长度
template
class size_of
{
public:
enum{value = sizeof(__T)};
};
template<>
class size_of
{
public:
enum{value = 0};
};
template
class test_less_512
{
public:
~test_less_512()
{
void(*fun)(void) = constraints;
}
private:
static void constraints()
{
struct test_less_512_
{
int less_512:(size_of<__T>::value < 512 ? 1:0);
};
}
};
注：imperfact c++中介绍的是约束两个类的大小相等，采用的是判断一维数组的维数是否为0，然貌似近年来的柔性数组出现
带来不好的局面，先采用了位域方式，已命名域不能使0宽度。
只需在各个业务类的析构函数中添加一句test_less_512
(2)new运算符的重载
void* operator new(std::size_t size) throw(std::bad_alloc);
void operator delete(void* doom, std::size_t size) throw(std::bad_alloc);
另外楼主在《STL源码剖析》中遇到这样一段：
template
inline void construct(T1* p, const T2& value)
{
new (p)T1(value);
}
起初以为T1前面的(p)是强制转换，然后就这样下去了，随后在《内存受限系统》中也偶遇类似情况，还以为是强制转换。
直到最后的最后晓得那是给new传参，是所谓的placement new。惭愧之至！
template
void* XXX::operator new(std::size_t size, __T* memory) throw(std::bad_alloc)
{
void* ptr = memory->pop();
return ptr;
}
(3).若不想使用编译器自动生成的函数，就明确拒绝。简单实现Boost库中的noncopyable类。
class entity
{
protected:
entity(void){}
~entity(void){}
/*
下面是个很神奇的地方，使用private而不是public能将连接期错误提前到编译期
*/
private:
//明确拒绝了copy构造函数和copy赋值操作符
entity(const entity&); //仅提供声明式，不提供定义式
entity& operator=(const entity&);//仅提供声明式，不提供定义式
};
凡是想明确拒绝编译器生成copy构造和copy赋值操作符的类私有继承这个类即可。
(4).使用explicit制止单一参数constructor被当做conversion运算符。
(5).类似下面C语言形式的一种简易变形的单件模式。
在C语言中假如想要获取链表或者stack的大小时，常见的做法往往是从头到尾遍历计数。然在给我老弟成彬
介绍栈这种数据结构种种时，突发想到下述用空间换时间的方式，进栈set_size(1)，出栈set_size(-1),
获取大小直接调用get_size();
static int set_size(int inc)
{
static int nStackNum = 0;
nStackNum += inc;
return nStackNum;
}
int get_size()
{
return set_size(0);
}
(6).充分利用内存空间，避免不必要的大型数据结构。
typedef unsigned char uchar;
class large
{
uchar v1; //在32位机上sizeof(large):20字节
int v2;
uchar v3;
int v4;
uchar v5;
};
class small
{
uchar v1; //在32位机上sizeof(small):12字节
uchar v3;
uchar v5;
int v2;
int v4;
};
Fixed Allocation内存池实现：
.h文件
/********************************************************************************/
#define _USE_CONTINUATION_MEMORY_
class CMemoryMng : private entity
{
public:
CMemoryMng(int capacity = 4, std::size_t size = 512);
void* pop();
void push(void* doom);
void create(int capacity, std::size_t size);
void destroy();
static CMemoryMng& GetObjectMemory();
private:
typedef struct info
{
char* data;
bool used;
struct info* next;
}INFO;
class mutexGuard //锁守卫，完美锁 参考自muduo源码
{
public:
explicit mutexGuard(rm_mutex& doom)
:__mutex(doom)
{
__mutex.lock();
}
~mutexGuard()
{
__mutex.unlock();
}
private:
rm_mutex& __mutex;
};
//禁止在栈或者堆上建立对象，只允许在全局区建立对象
void* operator new(std::size_t) throw();
void operator delete(void* doom, std::size_t) throw();
~CMemoryMng();
INFO* __freeList;//链表头
rm_mutex __mutex;//锁
};
/********************************************************************************/
.cpp文件
/********************************************************************************/
CMemoryMng::CMemoryMng(int capacity, std::size_t size)
: __freeList(NULL),
__mutex()
{
create(capacity, size);
}
CMemoryMng::~CMemoryMng()
{
destroy();
}
/*
拿走
*/
void* CMemoryMng::pop()
{
mutexGuard mutex(__mutex);
INFO* it = __freeList;
while(it != NULL)
{
if(false == it->used)
{
it->used = true;
break;
}
it = it->next;
}
return it->data;
}
/*
放回
*/
void CMemoryMng::push(void* doom)
{
mutexGuard mutex(__mutex);
INFO* it = __freeList;
while(it != NULL)
{
if(true == it->used && it->data == (char*)doom)
{
it->used = false;
break;
}
it = it->next;
}
}
/*
创建
*/
void CMemoryMng::create(int capacity, std::size_t size)
{
INFO* ptr = NULL;
#ifdef _USE_CONTINUATION_MEMORY_
char* data = (char*)calloc(capacity, sizeof(char)*size);
assert(data);
#endif
for(int i=0; i
ptr = (INFO*)calloc(1, sizeof(INFO));
assert(ptr);
#ifdef _USE_CONTINUATION_MEMORY_
ptr->data = data + (capacity - i - 1)*sizeof(char)*size;
#else
ptr->data = (char*)calloc(1, size*sizeof(char));
assert(ptr->data);
#endif
ptr->used = false;
ptr->next = NULL;
ptr->next = __freeList;
__freeList = ptr;
}
}
/*
销毁
*/
void CMemoryMng::destroy()
{
INFO* it = __freeList;
INFO* ptr = it;
while(it != NULL)
{
ptr = ptr->next;
#ifdef _USE_CONTINUATION_MEMORY_
if(it == __freeList)
#endif
free(it->data);
free(it);
it = ptr;
}
}
/*
一种简单的单件模式实现
*/
CMemoryMng& CMemoryMng::GetObjectMemory()
{
static CMemoryMng objectMemory;
return objectMemory;
}
/********************************************************************************/
_USE_CONTINUATION_MEMORY_看个人喜好选择使用与否！
不使用_USE_CONTINUATION_MEMORY_内存可能的情形
|----------| |----------| |----------| |----------|
...| A |...| B |...| C |...| D | ...
|----------| |----------| |----------| |----------|
使用_USE_CONTINUATION_MEMORY_内存可能的情形
|----------|----------|----------|----------|
...| A | B | C | D |...
|----------|----------|----------|----------|
具体业务的直属基类：
.h文件
为了限定只准在工厂方法（可能以后会在博文中聊到工厂模式）中生产产品，在此用private和friend结合的方式达到要求。
/********************************************************************************/
class CDutyMngTask : public base
{
public:
CDutyMngTask(){}
virtual ~CDutyMngTask(){}
virtual int Run(void* ptr);
...
void operator delete(void* doom, std::size_t size) throw();//放弃抛异常
private:
friend int CFactory::work_impl(......);
void* operator new(std::size_t size) throw();
template
void* operator new(std::size_t size, __T* memory) throw();
};
/********************************************************************************/
.cpp文件
/********************************************************************************/
int CDutyMngTask::Run(void* ptr)
{
return 0;
}
void CDutyMngTask::operator delete(void* doom, std::size_t size) throw()
{
CMemoryMng::GetObjectMemory().push(doom);
}
void* CDutyMngTask::operator new(std::size_t size) throw()
{
void* ptr = CMemoryMng::GetObjectMemory().pop();
return ptr;
}
template
void* CDutyMngTask::operator new(std::size_t size, __T* memory) throw()
{
void* ptr = memory->pop();
return ptr;
}
/********************************************************************************/
自己在项目中写的简易的Fixed Allocation内存池介绍完毕，欢迎大家浏览、评价、纠错和捧场。
