c++ - 同步push_back和std::thread

Question

我的密码

void build(std::vector<RKD <DivisionSpace> >& roots, ...) {
  try {
    // using a local lock_guard to lock mtx guarantees unlocking on destruction / exception:
    std::lock_guard<std::mutex> lck (mtx);
    roots.push_back(RKD<DivisionSpace>(...));
  }
  catch (const std::bad_alloc&) {
    std::cout << "[exception caught when constructing tree]\n";
    return;
  }
}

现在，实际工作应该串行而不是并行进行。
RKD的构造函数可以与 RKD的其他构造函数并行运行。但是，将对象推回 std::Vector是关键部分，对吧？

我将要构建的对象数量是已知的。实际上，它将在[2，16]范围内。从理论上讲，它可以是任何正数。

另外，对于将它们插入容器的顺序，我并不感兴趣。

所以我可以做类似的事情:

RKD tree = RKD(...);
mutex_lock(...);
roots.push_back(tree);

但是，这意味着要复制，不是吗？

我应该怎么做才能使我的代码并行？

由于 this的答案，我决定使用一个锁(而不只是一个互斥锁)。

Answer 1

Tomasz Lewowski在其评论中提出的建议，我已经扩展了，这一建议非常简单，并基于以下观察:push_back上的std::vector可能需要重新分配后备存储并复制(或最好移动)元素。这构成了需要同步的关键部分。

对于下一个示例，假设我们希望有一个用前12个素数填充的 vector ，但是我们不关心它们的顺序。 (我在这里只是对数字进行了硬编码，但假设它们是通过一些有意义的并行并行计算获得的。)在以下情况下，存在危险的竞争状况。

std::vector<int> numbers {};  // an empty vector

// thread A             // thread B             // thread C

numbers.push_back( 2);  numbers.push_back(11);  numbers.push_back(23);
numbers.push_back( 3);  numbers.push_back(13);  numbers.push_back(27);
numbers.push_back( 5);  numbers.push_back(17);  numbers.push_back(29);
numbers.push_back( 7);  numbers.push_back(19);  numbers.push_back(31);

push_back还有另一个问题。如果两个线程同时调用它，它们都将尝试以相同的索引构造对象，从而可能造成灾难性的后果。因此，在 fork 线程之前，无法使用 reserve(n)解决问题。

但是，由于您事先知道了元素的数量，因此您可以简单地将它们分配给 std::vector内的特定位置，而无需更改其大小。如果您不更改大小，则没有关键部分。因此，在以下情况下，没有种族。

std::vector<int> numbers(12);  // 12 elements initialized with 0

// thread A          // thread B          // thread C

numbers[ 0] =  2;    numbers[ 1] =  3;    numbers[ 2] =  5;
numbers[ 3] =  7;    numbers[ 4] = 11;    numbers[ 5] = 13;
numbers[ 6] = 17;    numbers[ 7] = 19;    numbers[ 8] = 23;
numbers[ 9] = 29;    numbers[10] = 31;    numbers[11] = 37;

当然，如果两个线程都尝试写入相同的索引，则竞争将再次出现。幸运的是，在实践中保护这一点并不困难。如果 vector 有n个元素，并且有p个线程，则线程i仅写入元素[i n/p，(i + 1)n/p)。注意，这比让线程i仅在j mod p = i时将索引i写入索引j的元素更好，因为它导致较少的缓存失效。因此，以上示例中的访问模式不是最佳的，最好是这样。

std::vector<int> numbers(12);  // 12 elements initialized with 0

// thread A          // thread B          // thread C

numbers[ 0] =  2;    numbers[ 4] = 11;    numbers[ 8] = 23;
numbers[ 1] =  3;    numbers[ 5] = 13;    numbers[ 9] = 29;
numbers[ 2] =  5;    numbers[ 6] = 17;    numbers[10] = 31;
numbers[ 3] =  7;    numbers[ 7] = 19;    numbers[11] = 37;

到目前为止，一切都很好。但是，如果您没有 std::vector<int>而是 std::vector<Foo>怎么办？如果 Foo没有默认的构造函数，则

std::vector<Foo> numbers(10);

将无效。即使有一个对象，创建许多昂贵的默认构造的对象只是在不获取值的情况下尽快对其进行重新分配也将是非常荒唐的。

当然，大多数设计良好的类都应具有非常便宜的默认构造函数。例如， std::string默认构造为不需要内存分配的空字符串。一个好的实现可以将默认构造字符串的成本降低到

std::memset(this, 0, sizeof(std::string));

而且，如果编译器足够聪明，可以弄清楚我们正在分配和初始化整个 std::vector<std::string>(n)，则它可以通过一次调用来进一步优化此格式

std::calloc(n, sizeof(std::string));

因此，如果有机会使 Foo廉价地默认可构造和可分配，就可以了。但是，如果发现这很困难，则可以通过将其移到堆上来避免此问题。智能指针可以廉价地默认构造，因此

std::vector<std::unique_ptr<Foo>> foos(n);

最终将减少到

std::calloc(n, sizeof(std::unique_ptr<Foo>));

无需对 Foo做任何事情。当然，这种便利是以每个元素的动态内存分配为代价的。

std::vector<std::unique_ptr<Foo>> foos(n);

// thread A                    // thread B                           // thread C

foos[0].reset(new Foo {...});  foos[n / 3 + 0].reset(new Foo {...});  foos[2 * n / 3 + 0].reset(new Foo {...});
foos[1].reset(new Foo {...});  foos[n / 3 + 1].reset(new Foo {...});  foos[2 * n / 3 + 1].reset(new Foo {...});
foos[2].reset(new Foo {...});  foos[n / 3 + 2].reset(new Foo {...});  foos[2 * n / 3 + 2].reset(new Foo {...});
...                            ...                                    ...

这可能没有您想像的那么糟糕，因为尽管动态内存分配不是免费的，但是 sizeof和 std::unique_ptr很小，因此，如果 sizeof(Foo)大，您将获得更紧凑的 vector 的好处，该 vector 可以更快地进行迭代。当然，这完全取决于您打算如何使用数据。

如果您事先不知道确切的元素数，或者担心弄乱索引，还有另一种方法可以做到:让每个线程填充自己的 vector 并在最后合并它们。继续素数示例，我们得到了这一点。

std::vector<int> numbersA {};  // private store for thread A
std::vector<int> numbersB {};  // private store for thread B
std::vector<int> numbersC {};  // private store for thread C

// thread A              // thread B              // thread C

numbersA.push_back( 2);  numbersB.push_back(11);  numbersC.push_back(23);
numbersA.push_back( 3);  numbersB.push_back(13);  numbersC.push_back(27);
numbersA.push_back( 5);  numbersB.push_back(17);  numbersC.push_back(29);
numbersA.push_back( 7);  numbersB.push_back(21);  numbersC.push_back(31);

// Back on the main thread after A, B and C are joined:

std::vector<int> numbers(
    numbersA.size() + numbersB.size() + numbersC.size());
auto pos = numbers.begin();
pos = std::move(numbersA.begin(), numbersA.end(), pos);
pos = std::move(numbersB.begin(), numbersB.end(), pos);
pos = std::move(numbersC.begin(), numbersC.end(), pos);
assert(pos == numbers.end());

// Now dispose of numbersA, numbersB and numbersC as soon as possible
// in order to release their no longer needed memory.

(以上代码中使用的 std::move是 the one from the algorithms library。)

由于 numbersA， numbersB和 numbersC正在写入完全独立分配的内存中，因此该方法具有最理想的内存访问模式。当然，我们必须做附加中间结果的附加顺序工作。请注意，效率很大程度上取决于以下事实:与查找/创建元素相比，移动分配元素的成本可忽略不计。至少如上所述，代码还假定您的类型具有便宜的默认构造函数。当然，如果您的类型不是这种情况，则可以再次使用智能指针。

我希望这为您提供了足够的想法来优化您的问题。

如果您以前从未使用过智能指针，请查看 “RAII and smart pointers in C++”并 checkout 标准库的 dynamic memory management library。上面显示的技术当然也可以与 std::vector<Foo *>一起使用，但是在现代C++中，我们不再使用像这样的拥有资源的原始指针。