c++ - 二维数组的 concurrent_vector

Question

我目前正在尝试使用 tbb::concurrent_vector<T> 表示二维数组.这个二维数组将被许多不同的线程访问，这就是为什么我希望它尽可能高效地处理并行访问。

我想出了两个解决方案:

• 使用 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，但具有线程安全的大小调整功能，但由于内部存储布局，元素访问速度较慢。

您可以阅读更多相关信息 here .

在您的情况下，由于您提出的第二个解决方案(具有 x * width + y 索引的一维数组)，我假设您的算法不涉及密集的多线程调整大小大批。因此，与 std::vector 这样的单线程容器相比，您不会从 tbb::concurrent_vector 中受益。

我猜你假设 tbb::concurrent_vector 保证线程安全的元素访问，但事实并非如此 - 引自 tbb::concurrent_vector ::operator[] 文档:

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

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

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

现在回答你的问题，即使在单线程设置中，最好使用一维数组来表示 ND 数组，因为计算索引 (x * width + y) 比真正的 ND 阵列。 对于并发 vector ，情况更是如此，因为在最佳情况下(没有冲突的行访问)，锁定开销会增加一倍，而在有冲突的情况下会更多。

因此，在您提出的两个解决方案中，我会毫不犹豫地选择第二个:一维数组(不需要 tbb::concurrent_vector)，并为元素访问提供足够的锁定。

根据您的算法和不同线程的访问模式，图像编辑软件(gimp、photoshop...)中使用的另一种方法是基于图 block 的:

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!)。 这样，如果您在访问模式中有一些局部性(一个线程更有可能访问靠近其先前访问的元素而不是很远的元素)，那么每个线程都可以处理来自单个图 block 的数据时间，并且只有在切换到另一个图 block 时才会有同步开销。