这里可以看到图,懒得上传到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

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐