concurrent_vector for 2d array

Question

I am currently trying to represent a 2D array using tbb::concurrent_vector<T>. This 2d array will be accessed by a lot of different threads and thats why I want it to handle parallel accesses the most efficiently possible.

I came up with 2 solutions:

• Use a tbb::concurrent_vector<tbb::concurrent_vector<T> > to store it.

• Store everything in a tbb::concurrent_vector<T> and access elements w/ x * width + y

I had a preference for the second one because I dont want to lock an entire row to access one element (since I assume that to access the element array[x][y], the tbb implementation will lock the xth row and then the yth element).

I would like to know which solution seems better to you.

Aindrea

What about std::vector<tbb::concurrent_vector> ? I don't know enough TBB to answer, but this looks fine to me. – Cretan

Well, if the std::vector holds the rows (tbb::concurrent_vector), I would be in trouble if I for example try to add a new row in one thread and delete one in another. – Aindrea

it may depend on what concurrent operations you expect the container to handle. – Whenas

Answer 1

First, I think there might be some confusion concerning tbb::concurrent_vector. This container is similar to std::vector but with thread-safe resizing but slower element access due to the internal storage layout.

You can read more about it here.

In your case, because of the second solution you proposed (1D array with x * width + y indexing), I'm assuming your algorithm doesn't involves intensive multi-threaded resizing of the array. Therefore, you wouldn't benefit from tbb::concurrent_vector compared to a single threaded container like std::vector.

I guess you were assuming that tbb::concurrent_vector guaranteed thread-safe element access, but it does not - quote from tbb::concurrent_vector::operator[] doc:

Get reference to element at given index.

This method is thread-safe for concurrent reads, and also while growing the vector, as long as the calling thread has checked that index

If you are not resizing the array, you are only interested in the first part: thread-safe concurrent reads. But std::vector or even raw C array gives you the same. On the other hand, neither offers thread-safe arbitrary access (read/write elements).

You would have to implement it using locks, or find another library that does this for you (maybe std::vector from STLPort but I'm not sure). Although this would be quite inefficient, since each access of an element from your 2D array would involve a thread synchronization overhead. While I don't know what exactly you are trying to implement, It's quite possible that the synchronization would take longer than your actual computations.

Now to answer your question, even in a single threaded setting, it is always better to use 1D array for representing ND arrays, because computing the index (x * width + y) is faster than an additional memory accesses needed by the true ND array. For concurrent vectors, this is even more true because you would have twice the lock overhead in a best-case scenario (no conflicting row access), and a lot more in case there are conflicts.

So out of the two solutions you proposed, I wouldn't hesitate and go for the second one: a 1D array (not necessary tbb::concurrent_vector) with adequate locking for element access.

Depending on your algorithm and the access pattern by the different threads, another approach - used in image editing software (gimp, photoshop...) - is tile based:

template<typename T> struct Tile {
    int offsetX, int offsetY;
    int width, height;
    Not_ThreadSafe_Vector<T> data;
};
ThreadSafe_Vector< Tile<T> > data

Where Not_ThreadSafe_Vector could be any container without locking on element access, e.g. std::vector ; and ThreadSafe_Vector is a container with thread safe read/write element access (not tbb::concurrent_vector!). This way, if you have some locality in your access pattern (a thread is more likely to access an element near to its previous access than far away), then each thread can be made to work on the data from a single tile most of the time, and you only have synchronization overhead when switching to another tile.

Kalikalian

Answer 2

I checked that tbb::concurrent_vector or std::vector does not allow creation of a vector of atomic types. This is because atomic types are not copyable.

Nostril

This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review – Beeler

Answer 3

tbb::concurrent_vector is completely thread safe for accessing elements (read, write, take the address) and growing the vector. Check response from Intel employee Arch D. Robison here.

However, operations for clearing or destroying a vector are not thread safe (refer to $6.2.1 Intel TBB Tutorial pdf document). That is, don't invoke clear() if there are other operations underway on the tbb::concurrent_vector.

As Antoine mentioned, handling the ND array as a 1D array is always to be preferred due to efficiency & performance.

Kristine

tbb::concurrent_vector is NOT completely thread safe for accessing elements. Arch's phrase "concurrent_vector allows multiple threads to access (read, write, take the address) of the same element. It does not serialize the accesses, so whether those accesses are safe depends upon the data type." means that you can access elements simultaneously but the safety depends on the particular element type. – Wadsworth

@Wadsworth Not sure I understand. Do you have an example of a potential difference between 2 data types and what would it cause? If tbb::concurrent_vector isn't thread safe, then why make it? Serializing access isn't thread-safety. That is another matter entirely (although it is good that you underlined it). Again, it is thread-safe, unless there's something else I don't understand. – Kristine

tbb::concurrent_vector provides container wide thread-safe operations, e.g. push_back, grow_by and so on. While item access functions are also safe, the items cannot be modified concurrently in some cases. Consider tbb::concurrent_vector<std::vector<int>> cv. It is safe to cv.push_back(std::vector<int>{}) concurrently, but it is not safe to cv[0].push_back(0) concurrently because std::vector<int> is not thread safe. However, it is safe with tbb::concurrent_vector<std::atomic<int>> cv to modify elements concurrently, e.g. cv[0]++. – Wadsworth