tbb::concurrent_vector

和stl::vector相比，tbb::concurrent_vector不支持insert和erase操作，且不保证内存是连续的。因为不支持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。

因为工作的关系，现在对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被修改为前一半。