TBB: concurrent_queue 高性能的奥秘 – 英特尔? 软件网络博客 - 中文

TBB: concurrent_queue 高性能的奥秘
作者：softarts11 (3 篇文章)日期： 八月 13, 2009 在 11:49 上午
在如今的多线程开发的滚滚浪潮中，线程安全会是一个充满正面色彩的广告语，还是一个隐含性能低下令人不安的信息？众所周知，STL库所提供的容器均不能保证线程安全，所有的工作都要需要开发者来承担。最简单的实现线程安全的手段便是使用锁来同步对容器的访问，只需要lock和unlock两行语句，容器就变成线程安全了，很简单，不是吗？不过，这时候"线程安全"就成了性能低下的同名词，期望的并发操作成了对容器的串行访问，我们不仅仅需要安全，还需要高性能。
TBB::concurrent_queue令人惊异地同时做到了这两点，在让开发者放心地得到线程安全的同时，还可以心安理得的享受高性能的并发访问。这其中会有什么奥秘？作为普通的开发者，我们可以从中学到什么东西？
Herb Sutter在DDJ 一文中抛出并行编程的三个简单论点，一是分离任务，使用更细粒度的锁或者无锁编程；二是尽量通过并行任务使用CPU资源，以提高系统吞吐量及扩展性；三是保证对共享资源访问的一致性。
传统的STL:queue 加锁的方案，Intel Thread Profilec测量，图的上半部分 fully utilized 只有9%（绿色部分），下半部分有大段时间处于串行执行状态（黄色），并行运算度很低
这三个论点各有侧重，我们看看concurrent_queue是怎么做的。
所谓分解任务，以尽可能细的粒度执行，这样就可以让每个任务运行而不互相干扰。并行编程中有一个对应的重要概念，就是尽量使用thread的private/local数据，例如ptmalloc中采用了好几个private heap，以降低多个线程同时请求分配内存，造成访问globalheap时的contend。
针对一个concurrent_queue，内部预先分配了8个micro_queue，并保存在名为array数组中，然后通过concurrent_queue_rep::choose函数来选择其中一个队列，这样做的好处是能把MultiThread对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]；而threadB同时在进行第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]被threadA占用时，该标记会阻止thread B更新array[0](此时tail_counter!=k)，程序会在do{}while循环里反复测试等式是否成立，不然去执行backoff.pause()以进入睡眠状态。
MorganStanley的Petru marginean在DDJ上的文章上曾经提出过几种阻塞的同步方法，分别是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(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，多核编程饶有兴趣。
分类：博客征文专栏
如需了解英特尔软件产品相关的性能和优化选项，请参阅优化注意事项.
评论 (3)
2009年08月21日 11:20

zxeoc 实际上就是用多个micro_queue代替原本的单个queue，是并行和串行的一个折中。
2009年08月24日 04:45

朱慧春 能支持intel的CPU吗
2009年08月25日 07:36

flygun "STL库" 不提供线程安全吗？ stlport提供的兼容的SGI stl是线程安全的。
硬件非常快了，软件的速度确实还有很大优化空间。