Tomasz Lewowski在评论中提出的建议,我进行了扩展,这个建议非常简单,基于以下观察:对于
std::vector
的
push_back
可能需要重新分配后备存储器并复制(或者最好是移动)元素。这构成了一个需要同步的关键部分。
对于下面的示例,请假设我们想要一个填充有前12个质数的向量,但是我们不关心它们的顺序。(我在这里只是硬编码了数字,但是假设它们是通过某些昂贵的计算在并行环境下执行是有意义的。)下面的情况存在危险的竞争条件。
std::vector<int> numbers {}
// thread A // thread B // thread C
numbers.push_back( 2)
numbers.push_back( 3)
numbers.push_back( 5)
numbers.push_back( 7)
还有一个问题涉及到
push_back
。如果两个线程同时调用它,它们都会尝试在相同的索引处构造一个对象,可能会产生灾难性后果。因此,在分叉线程之前使用
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;
当然,如果两个线程都试图写入相同的索引,则竞争将再次出现。幸运的是,在实践中保护它并不困难。如果您的向量有n个元素,并且您有p个线程,则线程i仅写入元素[i n / p, (i + 1) n / p)。请注意,这比使线程i仅在索引j处写入元素更可取,仅当j mod p = i时,因为它会导致较少的缓存失效。因此,上面示例中的访问模式是次优的,最好像这样。
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)
最终会简化为a。
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 {...});
... ... ...
这可能比你想象中的不那么糟糕,因为虽然动态内存分配并非免费,但是
std :: unique_ptr
的
sizeof
非常小,所以如果
sizeof(Foo)
很大,则可以获得更紧凑且更快速迭代的向量奖励。 当然,这完全取决于你打算如何使用数据。
如果您不知道预先准确的元素数量或担心会弄乱索引,还有另一种方法:让每个线程填充自己的向量,然后在结尾合并它们。继续上面质数的例子,我们得到了以下结果。
std::vector<int> numbersA {};
std::vector<int> numbersB {};
std::vector<int> numbersC {};
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);
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());
(上述代码中使用的std::move
是来自算法库的移动语义。)
这种方法具有最理想的内存访问模式,因为numbersA
、numbersB
和numbersC
都写入完全独立分配的内存。当然,我们还需要做额外的顺序工作来连接中间结果。请注意,效率在很大程度上依赖于移动分配元素的成本与查找/创建元素的成本相比可以忽略不计。至少按照上述方式编写的代码还假定您的类型具有廉价的默认构造函数。当然,如果对于您的类型不是这种情况,您可以再次使用智能指针。
希望这些内容为您优化问题提供了足够的思路。
如果您以前从未使用过智能指针,请查看
“C++中的RAII和智能指针”并查看标准库的
动态内存管理库。当然,上面展示的技术也适用于
std::vector<Foo *>
,但是在现代C ++中,我们不再使用类似这样的资源拥有原始指针。
noexcept
),则可以避免复制构造函数的执行。 - WhozCraigstd::vector<std::unique_ptr<RKD>>
。但是,如果您是RKD
的作者,则最好给它移动语义。 - 5gon12eder