欢迎您来到芯片的主页!

Welcome to Chipset's homepage!

boost下circular_buffer的速度问题

 

boost::circular_buffer is on the way…
很多时候我们会用到缓冲区或者类似缓冲区的数据结构,如果能事先估计出数据量多大,并尽可能的节约内存,可以使用环形(逻辑上)结构的缓冲区。boost已经有了一个这样的缓冲区,circular_buffer,由Jan Gaspar设计实现,它的数据结构跟传统的静态环形双端队列(很多数据结构书上有相关介绍)一样,速度比传统的静态环形双端队列快得多。只不过我对它的表现还是不太满意,觉得它还不够快。为此,我设计了一个简单的静态环形双端队列,它的数据结构与circular_buffer没什么两样,没有编写迭代器,也没有给出太多公有成员函数,只不过它的速度要快一些。下面先来看看它的逻辑结构和物理结构图。

图(a)是静态环形双端队列的逻辑结构图,图(b)是对应的物理结构图。静态环形双端队列有四个指针,指针start指向分配内存块的起始地址处,finish指向该快内存的末尾,first和last是两个自由指针,可以在[start, finish)区间自由移动,在队头添加一个元素时,first就向左移动一个元素的位置,在队头删除一个元素时,first就向右移动一个元素的位置,在队尾添加一个元素时,last向右移动一个元素的位置,在队尾删除一个元素时,last向左移动一个元素的位置。
开始时,指针first和last都指向同一个位置(我们的设计是指向[start, finish)区间的正中间),当环形双端队列满时last和first之间还剩一个元素的空位(如果不留空位怎么区分队满还是队空?)。比较难处理的问题是指针first和last移动到队头和队尾怎么办,因为在物理上(在内存中存放元素时)一块存储空间的始末永远都不会构成一个环,环行结构只能在逻辑上出现。
解决此问题的一种方法是取模,例如:first向左移动一个元素的位置:first = (first - 1 + cap) % cap; last向右移动一个元素的位置:last = (last + 1) % cap;其中first和last都是整形变量,cap是所开辟空间的大小,这就能很好的解决了环形移动指针的问题。这种传统的算法形式上虽然比较简洁,但是速度慢,因为取模需要做除法运算,以现在的CPU架构,做一次除法相当于做多次加法。
另外一种解决方案更容易理解,例如:当指针first移动到最左端时就让它指向右端,移动到最右端时就让它指向左端,当指针last移动到最右端时就让它指向左端,移动到最左端时就让它指向右端,这种算法速度快,因为做一次判断需要的指令数跟做一次加法需要的指令数相差不多。
为了能够区分何时队满何时队空,环形队列应该至少富裕一个元素的空间,也就是说我们将用last + 1 == first表示队满,用last == first表示队空。
为了看看环形缓冲区的性能怎样,做了一个简单的测试,测试用系统配置如下。
操作系统: Windows XP Professional(内核版本5.1.2600), 英文版
CPU: Intel(R) PIII 1.13MHz, Moblie
编译器: Code::Blocks(svn5616) + MinGW(g++4.4.0)
测试用数据: 32位的随机数(由boost::mt19937产生)
测试数据量: 1千万,测试时间单位: 毫秒
测试方法: 生成Release版(-O3),运行5次取平均值,分别测试成员函数push_back+pop_front,push_back+pop_back,push_front+pop_back,push_front+pop_front耗费的时间。
    测试结果见下图。


    由上图(a)、(b)、(c)、(d)容易看出,boost::circular_buffer比普通的静态双端环形队列快得多,但比静态双端环形队列circular_deque慢很多。
传统的环形队列速度慢的主要原因是移动指针时需要取模,这很糟糕,因为取模需要做除法,计算机做一次乘法或除法运算比做一次加法耗费的CPU周期多很多,由于每移动一次指针都需要做一次取模运算,从而导致整体运行速度大大下降。
boost 1.42中的circular_buffer中成员函数push_front, push_back, pop_front, pop_back不够快的主要原因是有太多的琐碎操作,这些琐碎的操作会消耗很多CPU周期,作者Jan Gaspar为何要这样实现,本人不理解,我觉得没有必要那样做(请参考boost::circular_buffer的源代码)。
如果您想看看各自的实现,circular_deque和circular_deque_traditional的源代码可以从下面地址下载
http://www.cppblog.com/Files/Chipset/circular_deque.zip

posted on 2010-07-14 14:24 Chipset 阅读(2881) 评论(0)  编辑 收藏 引用 所属分类: 算法和数据结构


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理