最新消息:

C-Buffered-tree 一个C实现的性能卓越的字典、集合类型库

c admin 3315浏览 0评论

介绍

众所周知,字典类型的实现不外乎哈希和平衡树,当然还有Google实现的B-tree版本。哈希实现是字典类型的主流,其随着键值膨胀的键冲突是这种实现的痛,目前解决的方法很多,如Redis的双哈希表然后迁移,还有BeansDB的哈希树等等。平衡树实现如C++标准库具有较好的收缩性但是其性能是个大问题,在大字典面前很乏力。Google的B-tree实现提供了传统C++ map类型的双倍性能并且减少了一半以上的内存利用。

C-Buffered-tree参考了CascaDB的思想和平衡操作,加强了No-Copy理念,实现了基本的字典类型的接口(Get,Put,Delete),并将继续实现set类型,sorted set类型。废话不多说,看性能检测。

性能

目前暂时只选择Redis的dict实现作为比较对象,据我了解,在C实现中,Redis的dict实现应该是其中翘楚,虽然其仍然有大量可以优化的地方。

虽然只检测了顺序插入的操作,但是无论是Redis的dict结构还是C-Buffered-tree,其对顺序插入和随机插入都没有特别的性能变化(C-Buffered-tree接下来会对顺序插入做优化)。以下都采用10个字节的键和值来进行。

QQ20130427-4

QQ20130427-5

很显然,三种操作C-Buffered-tree都具有明显的优势,在少量数据操作上优势较少(在这个时间上主要是其他误差在影响),在大量操作上基本都是双倍的速率。

内存利用

C-Buffered-tree具有高效的内存利用率,平均每个键值只有额外的32个字节的负载,空间利用与Redis-dict类似,但比平衡树实现至少节约5倍以上。

下一版本提供

  1. 性能翻番: 进一步强化No-Copy目标,调整内存布局和缓存优化,加入对顺序插入情景的优化,调整push操作的方式。
  2. 增加类型接口: 增加dictionary的迭代器,增加set和sorted set类型
  3. 采取措施加强Buffered-tree的收缩能力
  4. 增加不可变dictionary接口,将一个dictionary从mutable变为immutable,immutable dictionary具备更强劲的访问能力
  5. 加入线程安全版本

Github地址: https://github.com/yuyuyu101/C-Buffered-tree

转载请注明:爱开源 » C-Buffered-tree 一个C实现的性能卓越的字典、集合类型库

您必须 登录 才能发表评论!