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。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

To submit your comment, click the image below where it asks you to...
Clickcha - The One-Click Captcha