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.

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.