一般的malloc实现，对一块已分配的内存，都有两个机器字的簿记，甚至更多。如果不需要排错，理论上讲，只需要一个字长的额外开销，用来记录这块内存的尺寸（放在intptr[-1]处是个好主意）。

为什么需要这个开销呢？因为free传入的只是个指针，它不知道要释放多大的内存，因此free内部必须通过某种方式来获得这块内存的尺寸。

可以想象，如果用 malloc/free 来作为一个关联数组（map）的分配器，要浪费不少内存。不过好在实际数据的尺寸往往比额外消耗要大很多，相比起来，浪费的比例不算很大，况且现在内存还很便宜。

其实，打造一个高效的分配器并不难，难的是它的适用范围（多线程？cell尺寸，chunk尺寸，对齐，排错…），如果可以忍受这些缺陷，或者说是限制，还是比较值得的。下一步就是它的灵活性——让它可以更加容易集成进其它系统。

对于C标准库，如果能增加一个/一族这样的分配器，还是很有价值的。从理论上讲，只要free时多传一个size参数，就可以完全去掉额外的开销。这样两个函数就可以做到：

这样做还有一个额外的好处，就是可以更好地对齐，假定程序需要按32字节对齐，malloc/free 就至少需要32字节做簿记，如果再加上内存越界检测，就需要64字节。salloc/sfree则只需要将分配的内存对齐到32字节边界即可。

 

但是这对程序的正确性要求很高，malloc/free中，内存越界检测可以很容易实现，而salloc/sfree就完全做不到（除非增加额外簿记）。一个好主意是可以在debug版中加入这些差错功能，而在release版中去掉。

 

更好（确切地讲应该是更灵活）的方案是，实现一个

 

而让 salloc/sfree简单地作为 mpool 的包装。

 

gcc的std::allocator基本上是按这样的方式实现的，只不过，它的size参数，大多数时刻是自动传递的（知道具体的class/struct，也就知道它的尺寸）。实现方式上，使用 size_aligned/align 作为索引去访问特定尺寸的mempool，一个 mempool 是多个链表串起来的大chunk，每个chunk内部是链表穿起来的cell。这也许是最好的实现方式了，除了节省的额外空间开销，时间开销上，如果不考虑加锁，一次alloc平均可以在10时钟周期内完成，dealloc用的时间更短。相比之下malloc/free耗的时间也要多得多。

固定长度的数据结构很简单，大家每天都在用。

可变长度数据结构，都可以通过内嵌对象的形式，转化成固定长度的数据结构，大家每天也都在用，例如：

 

每个 person 对象的长度是固定的，但是，其内嵌的 name 和 address 是变长的。从而，整个对象占据的总空间也是变长的。

 

但是，将这样的的对象平坦化，使之只占据一块连续空间，使用的人很少，因为在绝大多数情况下，很少有人思考这个问题，并且，大多数问题已经使用内嵌数据结构解决掉了。

 

然而，如果内存很紧张，或者需要处理得数据量非常大，这种方式浪费的内存就太多了。假定我们现在创建了一个 map<int, person> ，在gcc4.1 的 64位环境中，按8字节对齐，这个 map 总共会占用多少内存呢？

1. sizeof(map) = 48
2. sizeof(string) = 8
3. sizeof(person) = 24
4. sizeof(person_node) = alignto(24 + 32(rbtree node overhead), 8) = 56
5. sizeof(string_node) = 8*3(refcount, size_endptr, capacity_endptr)
6. memsizeof(string) = sizeof(string_node) + alignto(strlen + 1, 8)
7. memsizeof(person_node) = sizeof(person_node) + memsizeof(name) + memsizeof(address)

如果 avg(name) = 10, avg(address) = 20

实际占用的空间，大约还要再加上4：avg(name) = 14, avg(address) = 24

那么 memsizeof(person_node) = 56 + 24*2 + 14 + 24 = 142

那么该map 实际占用空间（gcc 的每个 map 还有一个虚结点:32个字节）：

48+32+n*142 = 80+n*142

 

如果使用一种理想的变长数据结构，再加上红黑树的优化(none virtual node, compressed color, no parentptr)，需要多少内存呢？

1. sizeof(map) = 16
2. memsizeof(person_node) = alignto(16(treenode) + 4(id) + 2*1(strlen) + 10(name) + 20(address) = 52, 8) = 56

memsizeof(map) = 16 + 56*n

 

内存一下节省了 60% 还多，也就是说，如果内存大小已经固定，可以装入 2.5 倍的数据。

1. 如果用来做集群缓存，可以节省50%的机器（系统也要占一些内存）。
2. 如果有5.6G的内存可用，就可以装入1亿条数据。
3. 并且，在节省了60%内存的同时，还有另外一种好处：提高cache命中率，如果3个字段访问的频率相同，cpu的 cache miss 会降低3倍。
4. 可以预见，因为cache miss降低，map.find 速度会大幅提高。

 

这个可变数据结构可以这样设计：

 

 

更复杂的情况：

1. 如果nName 和 nAddress 要大于 255 呢？——把 unsigned char 改成 unsigned short, 甚至 unsigned int
2. 如果person的字段很多，例如有20个字段：

 

这就不光是写代码的复杂了，运行时字段访问的性能也成问题！性能问题可以用另外一种方式——使用直接定位——来解决。

 

 

如果需要变长数据的数组，怎么办？简单，offset array + data byte array，具体实现方式与 person4 类似，只不过 offset array 元素需要使用更宽的整数。

 

 

一直希望有个可以像 FILE* 一样使用的 memory file，正好，今天，在linux的stdio.h中找到了这个东西。

 

#define _GNU_SOURCE
#include <stdio.h>

FILE *fmemopen(void *buf, size_t size, const char *mode);

FILE *open_memstream(char ** ptr, size_t *sizeloc) ;

 

详细说明：http://linux.die.net/man/3/open_memstream

 

fmemopen 有用之处主要在于从内存中读取，使用 fscanf。当然也可以写，如果是为了写，并且随后再读，可以将 buf 和 size指定为 NULL，0，这样写时会自动增加内存。

 

open_memstream 就主要用于写了，比如生成sql语句：

 

在至强服务器上，使用 febird/vcproj/test_trb 测试 trb。结果发现使用compare函数指针的find仅比直接比较快17%！我原本以为至少要快一倍，因为在Windows（PentiumM Dual Core）上，直接比较的版本要快80%左右。

经过测试，发现：现代Cpu的流水线真强！

 

运行时间显示（单位是纳秒）：

服务器（至强四核 2.29G）： [doit=4971:  3.952, null=1648:  1.310, pse=4327:  3.440]

台式机（奔腾双核 2.49G）： [doit=6585:  5.301, null=1679:  1.352, pse=2246:  1.808]

 

doit表示pf_compare的那个循环

null表示那个啥也没干（volatile 用来禁止编译器优化）

pse表示那个累加循环

 

虽然主频低，但是服务器明显要快得多（不然至强怎么比奔腾贵那么多？）。

 

我看过pc下vc 2008 生成的代码，累加的那个循环，其中循环体26条指令（包含跳转指令）。平均每次循环仅消耗约4.5个时钟周期！流水线、分支预测这么强，在包含跳转的情况下，每个时钟周期还能执行3~4条指令！

更可怕的，在服务器上，一个包含函数调用的循环，仅需要9个时钟周期（2.29*3.95=9.05）！这完全颠覆了我对现代CPU的世界观。

 

这个简单的测试也说明，为什么find函数的compare_fun_ptr版本这么快（比较两个整数的函数是非常trivial的）。

完整的测试代码在：http://code.google.com/p/febird

在其中：$febird_home/vcproj/test_trb

 

因为某种原因（Threaded Red black tree C++ warpper），需要比较两个函数指针是否相等。但是，这么貌似很简单的需求却得不到满足。

下表，是在Visual C++ 2008 中，同一个函数通过不同途径得到的指针

key_comp	0x0041158c _febird_trb_compare_less
febird::G_relocate_febird_trb_compare_less	0x101cb4a4 _febird_trb_compare_less
febird_trb_compare_less	0x1051af60 febird_trb_compare_less(const trb_vtab *, const void *, const void *)

 

函数 febird_trb_compare_less 在 febird.dll 动态库中，并且导出。

febird::G_relocate_febird_trb_compare_less 是在 febird.dll 中定义了一个全局函数指针变量，并初始化为 &febird_trb_compare_less 。

key_comp 是使用 febird.dll 并将 &febird_trb_compare_less 传递给febird.dll中的另一个函数（假设函数名为foo）。以上三个不同的指针值就是在foo中查看到的。

 

在网上搜索了很多关于函数指针比较的东西，最终得出的结论是：跨越dll的函数指针比较是未定义的，除非是其中一个是NULL指针。不光vc，很多其他编译器也做不到跨dll的已定义的函数指针比较。

原本以为是dll重定位的问题，但是将函数指针放到 febird::G_relocate_febird_trb_compare_less 中也无济于事，反而更多出了一个指针值（0x101cb4a4 ）。

 

最终我的问题也解决了，就是在把这个比较放在头文件中，并且，key_comp作为一个模板参数来直接和&febird_trb_compare_less比较。

 

另外，函数指针作为模板参数时，不能将NULL之类的东西作为该模板参数传递。因为这个时候模板参数必须是一个const extern变量。如果试图传递NULL，在不同的编译器下会得到不同的错误信息（这样做在GCC4.1下编译过了，但连接错误）。

 

项目地址：http://code.google.com/p/febird

 

使用 libavl 中的 trb ，经过修改，实现了一个更高效更友好易用的版本，并且也支持范围查询，提供完备的std::map/set接口。

1. 对基本类型的key，实现高效search
2. 支持 lower_bound/upper_bound/equal_range
3. 结点采用压缩方式，将colorbit(1bit)和tagbit(2bit)压缩到指针中
   1. 从而每个结点的overhead是2ptr(32位环境下8byte，64位环境下16bits)
   2. stl::map/stl::set 的节点overhead 一般是 4ptr
4. 遍历tree的速度比stl::map/set快一倍
   1. 线索树的线索(thread)可以直接访问next/prev，而不需要回溯到祖先结点再访问其最左/右叶子
   2. 通过线索(thread)直接访问到next/prev的概率大约有50%
5. key的访问使用fieldoffset，C标准中有 offsetof(T,f) 宏来计算字段偏移
6. 因为使用C模拟template，从而没有C++的代码膨胀问题
7. C接口需要手工打造vtable
8. vtable指针通过参数传递，而不是将它作为trb_tree的一部分，更节约内存
   1. 也许仅仅一个vtable指针用不了多少内存
   2. 但是当有若干个【在我的应用中，大约2M个】trb_tree时，节省的内存相当可观
9. 使用C实现核心功能，同时提供更易用的C++接口（trbset/trbmap/trbtab）
   1. 类似stl中的相应东西
   2. trbset相当于stl::set
   3. trbmap相当于stl::map
   4. trbtab提供更多的控制
10. C++接口只是一个语法糖wrapper，将调用转发到C，但是使用C++可以避免几乎一切误用
    1. C++将vtable作为模板的static成员，非常合理，非常恰到好处

以前我写过两篇文章：

在 C 语言中实现模板函数的方法

在 C 语言中实现模板函数的方法（续）

 

对基本类型的key，实现高效search，其核心思想就来源于这两篇文章，但是有许多精化。其间使用了更之前的一些东西：

1. 基本类型enum
2. 类型迭代（使用preprocessor）

基本类型enum，使用enum的目的在于：使用这个enum，查找到相应的处理函数。

 

类型迭代：p_field_type_loop.h

 

在包含该文件之前，需要定义 FIELD_TYPE_FILE ，从而p_field_type_loop.h可以作为一个通用的代码生成器。在FIELD_TYPE_FILE中，实现具体的代码，在需要参数化类型的地方，使用FIELD_TYPE_TYPE来代替。FIELD_TYPE_PROMOTED用来提升相应的FIELD_TYPE_TYPE，例如 signed char 被提升到 int，float 被提升到double，这一点，在使用C的vararg时是绝对必要的。

 

另外，在包含该文件之前，还要将FIELD_TYPE_FILE中实现的函数名定义成宏，如：

 

以trb_find_xx为例，当trb_find_xx被展开后，变成trb_find_tev_double等等。

为什么要搞这么多呢？因为在这些函数中，对key值的大小比较实际上是个trivial操作，而一般传统的方法是传递一个compare函数指针，通过该指针调用compare函数，来实现灵活性（对任意类型的key）。

但是，通过函数指针调用一个非常trivial的操作，有很多不必要的性能损失（经过测试，对int的key，trb_find_xx会慢约20%~80%，服务器GCC+至强2.29G中慢20%，台式机VC+奔腾2.49G中慢80%）。

使用这种编程范式，可以在不必造成冗余代码的情况下，大幅提升性能。

 

全部的代码在这里

 

使用操作符重载时，出现模板匹配错误，bug 的出现很简单，下面是代码：

项目地址：http://code.google.com/p/febird

 

用gcc4.3重新编译了一下febird，出现了很多错误，仔细观察，这些错误都是因为不符合C++标准，重新改成符合标准的，比想象的改动量要大。
又测试了一下纯 C 实现的 algorithm: febird.c，是从VC2008的stl代码改过来的，在VC2008中测试比std::sort快20%，但是一到gcc中，却比std::sort慢了一倍还不止！不知到dinkware怎么写的。他有没有和sgi的比较过。重新研读了一下 gcc4.3 的 algorithm代码，gcc.stl.sort把insertion_sort放到sort的最后一个阶段，而ms.stl.sort把insertion_sort放到小区间内，就仅从这点上讲，gcc.stl.sort就少了很多函数调用的开销，ms又做了一些看似聪明的优化，比如递归层次按log(1.5,n)来计算，partition时又“跳过”连续相等的一段序列，等等，它的这些“优化”的结果就是速度只有gcc的1/3。