concurrentdvector用于2d数组

Question

我目前正在尝试使用表示2D数组tbb::concurrent_vector<T>.这个2d数组将被许多不同的线程访问,这就是为什么我希望它能够最有效地处理并行访问.

我想出了两个解决方案:

• 用a tbb::concurrent_vector<tbb::concurrent_vector<T> >来存储它.

• 将所有内容存储在一个tbb::concurrent_vector<T>和访问元素中x * width + y

我偏爱第二个,因为我不想锁定整行来访问一个元素(因为我假设要访问该元素array[x][y],tbb实现将锁定第xth行然后锁定第th y个元素).

我想知道哪种解决方案对你来说更好.

Answer 1

首先,我认为可能会有一些混乱tbb::concurrent_vector.此容器类似于std::vector但具有线程安全的大小调整,但由于内部存储布局而导致元素访问速度较慢.

你可以在这里阅读更多相关信息.

在你的情况下,由于你提出的第二个解决方案(带x * width + y索引的1D数组),我假设你的算法不涉及数组的密集多线程大小调整.因此,tbb::concurrent_vector与单个螺纹容器相比,您不会受益std::vector.

我猜你假设有tbb::concurrent_vector保证的线程安全元素访问,但它没有 - 引用doc:tbb::concurrent_vector::operator[]

获取给定索引处元素的引用.

只要调用线程检查了该索引,此方法对于并发读取以及生长向量时都是线程安全的

如果您没有调整数组的大小,那么您只对第一部分感兴趣:线程安全的并发读取.但是std :: vector甚至原始C数组给你的相同.另一方面,它们都不提供线程安全的任意访问(读/写元素).

您必须使用锁来实现它,或者找到另一个为您执行此操作的库(可能std::vector来自STLPort,但我不确定).虽然这样效率很低,但是因为每次从2D数组访问元素都会涉及线程同步开销.虽然我不知道你究竟想要实现什么,但很可能同步需要比实际计算更长的时间.

现在回答你的问题,即使在单线程设置中,最好使用一维数组来表示ND数组,因为计算索引(x*width + y)比真正的ND数组所需的额外内存访问要快.对于并发向量,这更加正确,因为在最佳情况下(没有冲突的行访问),您将拥有两倍的锁定开销,并且在存在冲突的情况下会更多.

因此,在您提出的两个解决方案中,我会毫不犹豫地选择第二个解决方案:一维数组(不是必需的tbb::concurrent_vector),具有足够的元素访问锁定功能.

根据您的算法和不同线程的访问模式,另一种方法 - 用于图像编辑软件(gimp,photoshop ...) - 基于区块:

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

哪里Not_ThreadSafe_Vector可以是没有锁定元件访问的任何容器,例如std::vector; 并且ThreadSafe_Vector是一个具有线程安全读/写元素访问权限的容器(不是tbb::concurrent_vector!).这样,如果您的访问模式中有一些位置(一个线程更可能访问其先前访问的元素而不是远处),那么可以使每个线程处理来自单个区块的数据.时间,切换到另一个磁贴时只有同步开销.