Advanced Idiom: Waiting on an Element

Sometimes a thread must wait for an element v[i] that is being asynchronously added by another thread. The following idiom can be used for the wait:

  1. Wait until i<v.size(). Afterwards, v[i] is known to be allocated, but perhaps not constructed.

  2. Wait for v[i] to be constructed.

A good way to do step 2 is to wait for an atomic flag in the element to become non-zero. Sometimes the entire element is the flag. To ensure that the flag is zero until the element is constructed, do the following:

  • Instantiate concurrent_vector with an allocator that allocates zeroed memory, such as tbb::zero_allocator.

  • Making the element constructor set the flag to non-zero as its last action.

Below is an example where the vector elements are atomic pointers. It assumes that pointers added to the vector are non-NULL, hence the flag is the pointer itself.

#include ″tbb/compat/thread″
#include ″tbb/tbb_allocator.h″ // zero_allocator defined here
#include ″tbb/atomic.h″
#include ″tbb/concurrent_vector.h″
 
using namespace tbb;
typedef concurrent_vector<atomic<Foo*>, zero_allocator<atomic<Foo*> > > FooVector;
 
Foo* FetchElement( const FooVector& v, size_t i ) {
    // Wait for ith element to be allocated
    while( i>=v.size() )
        std::this_thread::yield();
    // Wait for ith element to be constructed
    while( v[i]==NULL )
        std::this_thread::yield();
    return v[i];
}

In general, the flag must be an atomic type to ensure proper memory consistency.

For more complete information about compiler optimizations, see our Optimization Notice.