c++ - 对稀疏数组的高效多线程写访问？

Question

我有一个大数组double*，多个线程向它写入。

我用 boost::mutex 保护每次写入，但这会引入争用并使一切变得非常缓慢，几乎是非并行的。

是否有更好的方法来控制对我的数组的多线程写访问？

具体来说，我该如何利用它，在我的例子中，数组是稀疏的，每个线程通常写入数组的不同部分；对同一索引的并发写入应该很少见，并且主要发生在少数数组索引上。

编辑:准确地说，每个线程在多个数组索引上使用 += 增加值。

Answer 1

使用消息队列。使入队方法自动更新(即单指针交换)，您应该能够恢复并发性。然后有一个单独的(单个)线程从队列中读取并写入数组。

我可以对此进行扩展，因为我提供了更多关于正在执行的更新类型的信息。但总的来说，您可以找到许多应该可以帮助您做到这一点的无锁队列实现(例如 here )。

编辑以回答 OP 编辑​​:您需要构建一个类来存储索引对列表和更新值(或更新函数)。

class UpdateMessage {
    public:
    vector<Pair<int, int>> updates;   
}

或者类似的东西。然后，读者可以获取更新消息并迭代该 vector ，为给定消息执行所有更新。

---

使用 MoodyCamel 队列

假设可以在不锁定数组的情况下计算更新，这里有一个快速而肮脏的实现应该可以满足您的要求。

using namespace moodycamel;

typedef Updates vector<Pair<int, double>>;

ReaderWriterQueue<Updates> queue(100);
double array[] = initialize_array();
int sleep_interval = 10; // in microseconds, you'll probably want to do something smarter than a
                         // fixed interval here.

void read(ReaderWriterQueue queue) {
    Updates updates;
    bool succeeded = queue.try_dequeue(updates);
    if(succeeded) {
        for(auto it = updates.begin(); it != updates.end(); it = updates.next()) {
            array[it.x] = it.y;
        }
    }
}

void write(ReaderWriterQueue queue, Updates ups) {
    bool succeeded;
    do {
        succeeded = queue.try_enqueue(ups);
        usleep(sleep_interval);
    } while(!succeeded);
}

当然，如果插入失败，这会旋转写入线程。如果这 Not Acceptable ，您可以直接使用 try_enqueue 并在 enqueue 失败的情况下执行任何您想做的事情。