二维数组的并发向量

Question

我目前正在尝试使用

tbb::concurrent_vector<T>

表示 2D 数组。这个二维数组将被许多不同的线程访问，这就是为什么我希望它能够最有效地处理并行访问。

我想出了2个解决方案：

• 使用

  tbb::concurrent_vector<tbb::concurrent_vector<T> >

  来存储它。

• 将所有内容存储在

  tbb::concurrent_vector<T>

  中并使用

  x * width + y

访问元素

我更喜欢第二个，因为我不想锁定一整行来访问一个元素（因为我假设要访问元素

array[x][y]

，tbb 实现将锁定第

x

行，然后锁定

 y

第一个元素）。

我想知道哪种解决方案对您来说更好。

Answer 1

首先，我认为对于

tbb::concurrent_vector

可能存在一些困惑。该容器与

std::vector

类似，但具有线程安全的大小调整功能，但由于内部存储布局，元素访问速度较慢。

您可以在此处阅读更多相关信息。

在您的情况下，由于您提出的第二个解决方案（具有

x * width + y

索引的一维数组），我假设您的算法不涉及数组的密集多线程调整大小。因此，与像

tbb::concurrent_vector

这样的单线程容器相比，您不会从

std::vector

中受益。

我猜您假设

tbb::concurrent_vector

保证了线程安全的元素访问，但事实并非如此 - 引用自

tbb::concurrent_vector

::operator[]

文档：

获取对给定索引处元素的引用。

此方法对于并发读取是线程安全的，并且在增长向量时也是如此，只要调用线程已检查该索引

如果您不调整数组大小，则您只对第一部分感兴趣：线程安全并发读取。但是 std::vector 甚至原始 C 数组也可以给你同样的结果。另一方面，两者都不提供线程安全的任意访问（读/写元素）。

您必须使用锁来实现它，或者找到另一个为您执行此操作的库（可能来自 STLPort 的

std::vector

，但我不确定）。尽管这效率很低，因为每次访问 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

！）。 这样，如果您的访问模式具有某些局部性（线程更有可能访问靠近其先前访问的元素而不是远处的元素），则可以使每个线程处理来自单个图块的大部分数据。时间，并且只有在切换到另一个图块时才会有同步开销。

Answer 2

我检查了 tbb::concurrent_vector 或 std::vector 不允许创建原子类型的向量。这是因为原子类型不可复制。

Answer 3

tbb::concurrent_vector

对于访问元素（读、写、获取地址）和增长向量来说是完全线程安全的。请在此处查看英特尔员工 Arch D. Robison 的回复。

但是，清除或销毁向量的操作不是线程安全的（请参阅 $6.2.1 Intel TBB 教程 pdf 文档）。也就是说，如果

clear()

上正在进行其他操作，请勿调用

tbb::concurrent_vector

。

正如 Antoine 提到的，由于效率和性能的原因，将 ND 数组作为一维数组处理始终是首选。