本文主要是介绍TBB:concurrent_queue 高性能的奥秘,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这里可以看到图,懒得上传到MSN了
http://ladefense.spaces.live.com/blog/cns!CB45984FA784EC2C!709.entry
/请转载者保留作者全部信息/
TBB:concurrent_queue 高性能的奥秘
在如今的多线程开发的滚滚浪潮中,线程安全会是一个充满正面色彩的广告语,还是一个隐含性能低下令人不安的信息?众所周知,STL库所提供的容器均不能保证线程安全,所有的工作都要需要开发者来承担。最简单的实现线程安全的手段便是使用锁来同步对容器的访问,只需要lock和unlock两行语句,容器就变成线程安全了,很简单,不是吗?不过,这时候"线程安全"就成了性能低下的同名词,期望的并发操作成了对容器的串行访问,我们不仅仅需要安全,还需要高性能。
TBB::concurrent_queue令人惊异地同时做到了这两点,在让开发者放心地得到线程安全的同时,还可以心安理得的享受高性能的并发访问。这其中会有什么奥秘?作为普通的开发者,我们可以从中学到什么东西?
Herb Sutter在DDJ <pillars of concurrency> 一文中抛出并行编程的三个简单论点,一是分离任务,使用更细粒度的锁或者无锁编程;二是尽量通过并行任务使用CPU资源,以提高系统吞吐量及扩展性;三是保证对共享资源访问的一致性。
<图>传统的STL:queue 加锁的方案,Intel Thread Profilec测量,图的上半部分 fully utilized 只有9%(绿色部分),下半部分有大段时间处于串行执行状态(黄色),并行运算度很低
这三个论点各有侧重,我们看看concurrent_queue是怎么做的。
所谓分解任务,以尽可能细的粒度执行,这样就可以让每个任务运行而不互相干扰。并行编程中有一个对应的重要概念,就是尽量使用thread的private/local数据,例如ptmalloc中采用了好几个private heap,以降低多个线程同时请求分配内存,造成访问global heap时的contend。
针对一个concurrent_queue,内部预先分配了8个micro_queue,并保存在名为array数组中,然后通过concurrent_queue_rep::choose函数来选择其中一个队列,这样做的好处是能把Multi Thread对1个queue的访问平均分布到多个内部的micro_queue上,从而尽可能避免冲突。
micro_queue& choose( ticket k ) {
// The formula here approximates LRU in a cache-oblivious way.
return array[index(k)];
}
static size_t index( ticket k ) {
return k*phi%n_queue;//phi=3,n_queue=8
}
具体选择哪个micro_queue,取决于一个为ticket类型的变量k,这个变量实质上是push操作次数的计数。
例如
k=0, 那么选择 array[0*3%8]=array[0]
k=1,array[1*3%8]=array[3]
...
k=7,array[5]
k=8,array[0] //又回到了与k=0时一样的结果。
无锁的push操作
即使能把queue分布到内部多个micro_queue上,那还是不可避免的会有冲突存在。例如,有可能2个不同的thread都是在访问同一个micro_queue。由上面结果可以看出,假设thread A在进行push操作时,k=0,那么使用的是array[0];而thread B同时在进行第8个push操作,k=8,使用的也是array[0],这种情况下怎么办?
concurrent_queue用这段代码来解决共享资源的访问冲突:
void micro_queue::push( const void* item, ticket k, concurrent_queue_base& base ) {
...
push_finalizer finalizer( *this, k+concurrent_queue_rep::n_queue );
if( tail_counter!=k ) {
ExponentialBackoff backoff;
do {
backoff.pause();
// no memory. throws an exception
if( tail_counter&0x1 ) throw bad_last_alloc();
} while( tail_counter!=k ) ;
}
...
}
对于每一次push操作,micro_queue使用了一个tail_counter来作为阻塞标记。例如,array[0]被thread A占用时,该标记会阻止thread B更新array[0] (此时tail_counter!=k),程序会在do{}while循环里反复测试等式是否成立,不然去执行backoff.pause()以进入睡眠状态。
MorganStanley的Petru marginean 在DDJ上的文章<Lock-Free Queues>上曾经提出过几种阻塞的同步方法,分别是NO_WAIT(循环查询),SLEEP(睡眠),TIMED_WAIT(超时等待)以及LOCK_NO_WAIT(锁),TBB使用的这种类似于TIMED_WAIT的方法,通过pause指令让线程暂停一会后,再重试。从网上得到的资料,pause指令在这种spin_lock模式的阻塞中,可以提高25倍效率。
保证共享资源访问的一致性,及使用new placement 改善内存分配的性能
通过以上两点,TBB::concurrent_queue已经基本解决并行处理数据的问题,然而还有些细节可以提高性能。有关内存的操作永远都是性能测试中的热点(hotspot),改善性能也可以从内存管理上入手
例如,每次push操作都需要为插入的元素分配内存,malloc是一个昂贵的操作,如果能够预先分配好一大段连续内存,或者是从内存池取得一段内存呢?
TBB中,首先分配一个可以容纳多个对象的page,然后在具体发生push操作时,使用C++的new placement语法,再从已分配的page上取得一个对象大小的内存。
/*overide*/ virtual page *allocate_page() {
size_t n = sizeof(page) + items_per_page*item_size;
page *p = reinterpret_cast<page*>(my_allocator.allocate( n ));
if( !p ) internal_throw_exception();
return p;
}
此外,concurrent_queue利用了TBB库的成果:atomic<>来声明一些原子变量,如tail_counter.
结论:
测试表明,并行度达到50%(图上半部分的蓝色柱),时间上也比STL:queue加锁的版本快了2-3倍。
concurrent_queue是一个典型的高性能并行容器实现,相信concurrent_haspmap和其它的容器,内存池及算法,都可以采用类似的方法去提高性能。只不过,仍然有些对concurrent_queue不解的地方:
为什么不采用Lock-Free的算法直接实现一个micro_queue?而是仍然使用一种类似spin_lock的做法去同步线程?
不过,目前的方案很有可能是Intel开发人员的折中选择,队列负载均衡,再加上预分配内存后,push入队操作应该很快,发生碰撞的机率并不大。毕竟Lock-Free还不够足够成熟。
关于作者:曾任职于Alcatel-Lucent,Nokia,从事高速数据处理,移动网络系统软件开发等。对Linux Kernel,多核编程饶有兴趣。
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/softarts/archive/2009/05/05/4152960.aspx
这篇关于TBB:concurrent_queue 高性能的奥秘的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!