在并行循环中，对于惰性向量的访问
在并行循环中，对于惰性向量的访问
在一个性能关键的、并行的代码中，我有一个向量，其元素为：\n
- \n
- 计算非常昂贵，并且结果是确定性的（给定位置上的元素值仅取决于位置）
- 随机访问（通常访问次数大于或远远大于向量的大小）
- 聚集访问（许多访问请求相同的值）
- 该向量被不同的线程共享（竞争条件？）
- 为了避免堆碎片化，对象不应该被重新创建，但在可能的情况下被重置和回收利用
- 要放入向量中的值将由多态对象提供
\n
\n
\n
\n
\n
\n
\n目前，我预计算出向量的所有可能值，所以竞争条件不应该是一个问题。\n为了提高性能，我考虑创建一个延迟向量，这样代码只在请求向量元素时执行计算。\n在并行区域中，可能会有多个线程同时请求并且计算相同的元素。\n如何处理这种可能的竞争条件？\n下面是我想要实现的一个示例。它在Windows 10、Visual Studio 17下可以正确编译和运行。我使用的是C++17。\n// Lazy.cpp : 定义控制台应用程序的入口点。\n#include \"stdafx.h\"\n#include
懒惰的向量访问在并行循环中是一个常见的问题。这个问题的主要原因是因为使用std::vector<bool>非常糟糕，同时缺乏原子性和内存一致性。下面给出了一个完全基于OpenMP的解决方案的概要。建议使用特殊的标记来表示缺失的条目，而不是单独使用vector<bool>，这样会使一切变得更容易。
class LazyVectorTest //vector that contains N possible results
{
public:
LazyVectorTest(int N,const Evaluator & eval) : N(N), innerContainer(N, invalid), eval_ptr(&eval)
{};
~LazyVectorTest() {};
//reset, to generate a new table of values
//the size of the vector stays constant
void reset(const Evaluator & eval) {
this->eval_ptr = &eval;
for (int i = 0; i<N; i++) {
// Use atomic if that could possible be done in parallel
// omit that for performance if you doun't ever run it in parallel
#pragma omp atomic write
innerContainer[i] = invalid;
}
// Flush to make sure invalidation is visible to all threads
#pragma omp flush
}
int size() { return N; }
// Don't return a reference here
double operator[] (int pos) {
double value;
#pragma omp atomic read
value = innerContainer[pos];
if (value == invalid) {
value = eval_ptr->expensiveFunction(pos);
#pragma omp atomic write
innerContainer[pos] = value;
}
return value;
}
private:
// Use nan, inf or some random number - doesn't really matter
static constexpr double invalid = std::nan("");
const int N;
const Evaluator* eval_ptr;
std::vector<double> innerContainer;
};
在发生冲突的情况下，其他线程将会冗余计算该值，利用确定性的特性。通过对元素的读写都使用omp atomic，可以确保不会读取到不一致的“半写”值。
这种解决方案可能会在极少数情况下增加一些额外的延迟。与此同时，好的情况下是最佳的，只需要进行一次原子读取。甚至不需要任何内存flush/ seq_cst，最坏的情况下是冗余计算。如果将标志和值分开写入，以确保更改的可见性顺序正确，则需要这些（顺序一致性）。
对于自定义类的情况，可以使用{ std::lock_guard<std::mutex> lock(mutex[pos]); if (!innerContainer[pos]) { innerContainer[pos] = std::make_unique<...>(...) } return innerContainer[pos]; }。如果这成为性能瓶颈，还可以使用DCLP（Double-Checked Locking Pattern），但这很难正确实现。可以使用C++11的互斥锁或OpenMP的互斥锁...后者在OpenMP上下文中更好定义，但使用起来不太方便。
实际上，在实际代码中我们使用了一个定制的线程池，因为测试表明它在这个特定函数中的性能优于OpenMP（这个事实我还没有解释）。所以互斥锁是可行的方法。这很有启发性。谢谢！
懒惰向量访问在并行循环中的问题是由于多线程访问同一位置的元素时可能产生的竞争条件。为了解决这个问题，可以使用std::call_once函数来保证每个位置的元素只被计算一次，并且所有线程在访问该位置之前都会等待计算完成。以下是解决方法的示例代码：
class LazyVectorTest //包含N个可能结果的向量
{
//具有确定性输出的函数，取决于位置
void expensiveFunction(int pos) {
double t = 0;
for (int j = START_SUM; j++ < END_SUM; j++)
t += log(exp(log(exp(log(j+pos)))));
values[pos] = t;
}
public:
LazyVectorTest(int N) : values(N), flags(N)
{};
int size() { return values.size(); }
//访问相同位置应该产生相同的结果
double operator[](int pos) {
std::call_once(flags[pos], &LazyVectorTest::expensiveFunction, this, pos);
return values[pos];
}
private:
std::vector values;
std::vector flags;
};
std::call_once函数的作用是确保只有一个线程能够完整地执行一个函数。这种方法的潜在缺点是，它会阻塞第二个线程，等待可能出现的异常，而不是立即执行其他操作。在这种情况下，这是可取的，因为我们希望修改values[pos]的操作在读取return values[pos]之前被顺序执行。
然而，使用std::call_once函数在并行化这个示例代码时并没有带来很大的速度提升。这可能是因为该示例代码的计算量较小，无法充分利用多线程的优势。对于这个问题，我们无法重置flags，因为once_flag结构体的拷贝构造函数被删除了。因此，每次需要一个新的对象时，lazy对象都必须被销毁和重建。在示例代码中，这种做法可能不可行，因为对象可能需要创建数百万次，我们需要尽量避免重新分配内存。
另外，需要注意的是，在OpenMP线程/内存模型和C++11线程之间的交互是未指定的，无法保证所有线程在通过call_once之后都能看到更新后的values[pos]。
为了解决std::call_once函数不可移动插入的问题，可以选择使用std::deque
使用std::call_once函数可以解决懒惰向量访问在并行循环中可能产生的竞争条件问题。然而，在具体的应用中，需要注意std::call_once函数的潜在缺点和与其他线程库的交互问题。