Threaded Red-Black Tree 线索红黑树

项目地址: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%)。

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

 

全部的代码在这里

 

作者:
该日志由 rockeet 于2009年05月26日发表在C++, 算法分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
转载请注明: Threaded Red-Black Tree 线索红黑树
标签:
【上一篇】
【下一篇】

您可能感兴趣的文章:

发表评论

您必须 登录 后才能发表评论。