TBB Study Notes (2)

tbb::concurrent_vector

stl::vector相比,tbb::concurrent_vector不支持inserterase操作,且不保证内存是连续的。因为不支持insert操作,故而无法实现由一个线程进行插入排序,并同时由另一个线程去遍历的场景。TBB中也没有平衡树的支持,估计是因为,插入/删除时的节点移动操作很多,细粒度锁不容易带来更佳性能的原因。

template<typename T, class A>
class concurrent_vector: protected internal::allocator_base<T, A>,
                         private internal::concurrent_vector_base;

typedef concurrent_vector_base_v3 concurrent_vector_base;
// VC10 defines its own v4 template

struct concurrent_vector_base_v3::segment_t {
void* array;
};

atomic<segment_t*> my_segment;
segment_t my_storage[pointers_per_short_table]; 
// pointers_per_short_table = 3

concurrent_vector_base_v3::concurrent_vector_base_v3():

将指针数组my_storage的元素赋值为NULL, 然后将my_storage赋值给my_segment。

concurrent_vector_base_v3::segment_index_of(index):

即 log2(index|1)

concurrent_vector_base_v3::segment_base (k):

(1 << k & ~1),和2**k(即1<<k)不同,当k为0时,结果为0而不是1

concurrent_vector_base_v3::segment_base_index_of(index):

将index调整为segment内的索引,并返回是第几个segment。

concurrent_vector_base_v3::segment_size(k):

返回第k个segment的大小。1 << k,k==0时应该返回2才对呀

从逻辑上看,concurrent_vector内部的segments布局如下,总会是2,2,4,8,16,32...

但是实际分配的空间,则可能是16,16,32,64,取决于第一次的reservation, growth 或 assignment操作。如果第一次要求分配10个元素,那么heap上分配的空间是,比10大的最小的2的幂数,即16。

(插图来自http://blogs.msdn.com/b/nativeconcurrency,VC10中的concurrent_vector和TBB中的是同出一脉的。)

concurrent_vector::push_back (item)

调用internal_push_back(sizeof(T), k)去分配一段空间,然后调用internal_loop_guide(ntrails为1)将item拷贝到分配的空间上,最后返回iterator

concurrent_vector_base_v3::internal_push_back(element_size, &index)

使用__TBB_FetchAndIncrementWacquire将m_early_size加1,并将原来的size赋值给tmp和index。调用helper::extend_table_if_necessary(*this, k_old, tmp),在必要时扩展segment table,调用helper::acquire_segment获取一个segment的基地址,计算偏移并返回对应的地址。

libittnotify是一些profiling的函数,在编译时可以打开或关闭。ITT=>Intel Threading Tools。

TBB Study Notes (1)

因为工作的关系,现在对C++的并发编程十分有兴趣,TBB无疑是这一领域的佼佼者。我主要对并发容器、scalable allocator比较有兴趣。现在刚刚开始读TBB的代码,这里是一些粗浅的笔记,欢迎大家多指正 ...

tbb::machine

tbb_machine.h中引入了所有支持平台的头文件,如果对应平台没有定义__TBB_CompareAndSwap4,__TBB_CompareAndSwap8,__TBB_Yield,或__TBB_release_consistency_helpler,就会报错,无法支持。如果没有定义__TBB_load_with_acquire或__TBB_store_with_release,就会通过__TBB_release_consistency_helpler来实现它们;如果没有实现__TBB_Pause,就通过__TBB_Yield来实现。

__TBB_rel_acq_fence和__TBB_release_consistency_helper不同,前者是一个真正的硬件的fence,后者只是为了告诉编译器不要进行重排。Intel的编译器就将__TBB_release_consistency_helper定义为空了,但是GCC需要特殊的定义。但是奇怪的是,MSDN上说_ReadWriteBarrier是包括硬件fence的。

内存语义(memory semantics):

load_with_acquire: 栅栏之后的内存操作不能移动到load之前;
store_with_release: 栅栏之前的内存操作不能移动到store之后;

__TBB_machine_fetchadd1等方法,通常定义在src/<arch>/atomic_support.asm中的,ibm_aix51中是一个C文件。

某些term和Windows API的对应关系:

fetch-and-add => InterlockedExchangeAdd
fetch-and-store => InterlockedExchange
compare-and-swap => InterlockedCompareExchange

atomic_backoff: pause()方法,在前5以内,是指数级的backoff,之后调用__TBB_Yield()来交出CPU。bounded_pause()会在5次尝试之后,返回false。

还定义了原子的OR和AND操作,以及__TBB_TryLockByte,__TBB_LockByte等辅助函数(都是基于CAS来实现的)。

tbb::atomic

enum memory_semantics: {__TBB_full_fence, acquire, release};

后面两个应该只是为支持IA64的,只有在linux_ia64.h中定义了__TBB_DECL_FENCED_ATOMICS这个宏,并实现了型如__TBB_CompareAndSwap##S##M(其中S是size,M是memory_semantic,例如__TBB_CompareAndSwap4acquire)等方法。如果这些方法没有被定义的话,tbb_machine.h中会用__TBB_full_fence语义的版本重定义之。

atomic_rep: 对长度为[2, 4, 8]字节的类型,都要求对齐;即加入了一些编译器属性。

template struct atomic_traits;
包括compare_and_swap, fetch_and_add, fetch_and_store等几个基本的方法。

atomic_impl实际上是对atomic_rep和atomic_traits的一个包装。而atomic模板从atomic_impl中派生得到的,对指针类型来说,是从atomic_impl_with_arithmetic中派生的(void *除外),以对指针的移动操作(例如++, --)进行memory barrier的保护。而atomic_impl_with_arithmetic也是从atomic_impl中派生的。相比atomic_impl,atomic对赋值操作operator=加入了fence的保护。

tbb::blocked_range

包括1维、2维、3维的实现。模板参数是iterator类型。表示一个半闭半开的区间,[my_begin, my_end)。当区间的size<=my_grainsize时,区间就不可再分了。其中一个构造函数,可以将当前的range(*this)分为两半,新构造的range是后一半,旧的range被修改为前一半。