常写程序的人都很清楚，小对象放栈上，大对象放堆上。问题是有时候太多小对象迫不得已也得放堆上，例如链表节点、树节点等等，很多时候这些数据结构中每个节点存储的都是一个小对象。
以一个双链表为例(std::list)，假设用于存储32位整数大约1M(1048575)个，在32位系统上，这个链表用于存储这些整数将耗费24MB内存，而并不上理论上的12MB(每个节点有两个指针和一个32位整数，应该耗费12字节，因此1M个这样的节点大约耗费12MB内存)。真正的原因何在？
其实无论是new还是malloc每分配一块内存都要多分几个字节用于存储块大小信息、状态等，当创建小节点很多(分配的小块内存很多)时，这种开销就会相当可观。对于分配的小块内存一般会有8字节的开销，然后再圆整成8的倍数，分配大块内存则未必是这样，通常不是圆整成8的倍数，而是圆整成一个更大值的倍数，甚至圆整成2的指数个字节。
回到上面的双链表，对于每块12字节的内存，new至少分配20(12+8)字节，然后圆整成8的倍数，这样就成了24字节了。在32位系统上，其实没有必要用8字节存储那些额外信息(块大小、状态...)，4字节足矣，因为4的二进制为100，后面有两个0足可以存储状态了(一个0就够)，但是为了在64位系统上不出问题，通常用8字节。
在内存相对比较紧张的嵌入式应用中，过多的动态小块内存的总开销有时可能到了无法忍受的程度。此时，我们不得不自己设计一个小块内存管理器，下面将会讲述怎么用位图算法设计它。
每块内存用一个二进制位表示它的使用状态，如果该块内存被占用，则把对应位图中的对应位置0，如果空闲则置1，原理十分简单。
实现中，需要解决以下几个问题。
1) 如何快速找到某块内存的位图中的对应位？
这个问题涉及到位运算，见本主页的某个帖子"如何找到一个整数二进制的第一个1"。但是仅仅靠那么简单的位运算还解决不了问题。需要考虑一个位图多大，如果用64位整数表示一个位图的话，那么每块内存需要用1字节的开销记录在对应位图中的索引状态位，因为1字节有8位，最大能表示到256(0~255)，而一个64位整数仅仅64位，可见能表示的范围绰绰有余。
2) 一块内存回收怎么获得它的大小？
对于链表和树节点，每个这样的容器中各个节点的大小相同，因此没有必要存储这个大小，只有这样才可能节约每块内存的overhead开销。
3) 需要用多大的缓存呢？
向系统申请的每个chunk字节数是：8字节的位图 + 64 * (申请块大小+1字节的索引)。当一个chunk全部被使用时，可以不保留也没有必要保留它的信息。如果该chunk仅仅使用一部分，则缓存这个chunk，且仅仅缓存一个chunk，别的chunk即使仅仅使用一部分，也置之不理，只有某个非当前chunk全空时才会交给系统。这样既不至于缓存太多chunk导致其它进程动态申请内存成为问题，也能不至于分配和回收内存速度很慢。
但是这存在一点问题，尤其那些纯粹搞理论的人可能会提出，在极端情况下，如果每个chunk仅仅剩下一块内存使用，由于这些chunk均不能交给系统，理论上内存利用率极低。这种情况不予考虑，实际上任何一个内存管理器均存在这种极端情况下的隐患，包括new/malloc....，操作系统的堆内存管理器等等。
1 /// bitmap_fixed_size_allocator.hpp
2 #ifndef SINGLE_OBJECT_ALLOCATOR_HPP_
3 #define SINGLE_OBJECT_ALLOCATOR_HPP_
4
5 #include /// malloc, free
6 #include "mutex.hpp"
7 #include "guard.hpp"
8
10
11 /// It is specialy designed for small identical byte object memory management.
12
13 /// It is not the fastest and memory efficient small allocator, because for every
14 /// memory block there is a metadata field. To manage this data field, a lot of
15 /// bitwise operations are necessary although this will degrade performance. The
16 /// metadata field should not be removed to improve performance (like a freelist ),
17 /// because that design will cause memory blow up at some intensive situations.
18 /// Even though, it is still a bit faster and memory efficient than a general purpose
19 /// malloc/free function or new/delete operator built-in most C/C++ compilers.
20
21 /// SERIOUS WARNINGS:
22 /// Never try to use (directly or indirectly) more than one allocator object in
23 /// the same scope if you do not want to crash your program!!!
24 /// It is designed for internal use only. Do not use it in multi-processor
25 /// environment, because it can not prevent false sharing and blow up even you can
26 /// endure its snail speed!!!
27
28
29 class bitmap_fixed_size_allocator : public default_mutex
30 {
31 public:
32 #ifdef CXX0x
33 typedef uint64_t size_type;
34 typedef uint8_t index_type;
35 #else
36 typedef unsigned long long size_type;
37 typedef unsigned char index_type;
38 #endif
39
40 typedef bitmap_fixed_size_allocator alloc;
41 public:
42 bitmap_fixed_size_allocator(size_type, size_type = 256);
43 ~bitmap_fixed_size_allocator();
44
45 void* allocate(); /// allocate a block
46 void deallocate(void*); /// deallocate a block
47 void clear();