对稀疏数组的高效多线程写访问？ [英] Efficient multi-threaded write access to sparse array?

问题描述

我有一个大型数组 double * ，并且有多个线程写入该数组。

I have a large array double*, and multiple threads write to it.

我使用 boost :: mutex 保护每次写操作，但这会引起争用并使所有操作变慢，几乎

I protect each write with a boost::mutex, but that introduces contention and makes everything very slow, almost non-parallel.

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

Is there a better way to control multi-threaded write access to my array?

具体来说，在我的情况下，如何利用该数组是稀疏的，并且每个线程通常都写入该数组的不同部分。并发写入同一索引应该很少，并且大多数情况下会发生在少数数组索引中。

Specifically, how can I exploit that, in my case, the array is sparse, and each thread typically writes to different parts of the array; concurrent writing to the same index should be rare and happen mostly to a handful of array indices.

编辑：确切地说，每个线程使用<$ c $来增加值c> + = 在多个数组索引上。

To be precise, each thread increases the value using += on multiple array indices.

推荐答案

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

Use a message queue. Make the enqueue method update atomically (i.e. a single pointer swap) and you should be able to recover your concurrency. Then have a separate (single) thread read from the queue and write to the array.

我可以对此进行详细说明，以获取更多有关正在执行哪种更新的信息。但总的来说，您会发现许多无锁队列实现都可以帮助您实现这一目标（例如此处）。

I can expand on this given a little more info on precisely what kind of updates are being performed. But in general, you can find many lock-free queue implementations that should help you do this (e.g. here).

编辑以回答OP编辑：您将要构造一个存储对列表的类。索引和更新值（或更新函数）。

Edit to answer OPs edit: You'll want to construct a class that stores the list of pairs of indices and the update values (or update functions).

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

或类似的东西。然后，读者可以获取一条更新消息，并对该向量进行迭代，以对给定消息执行所有更新。

Or something like it. The reader can then grab an update message and iterate over that vector performing all the updates for a given message.

假设无需锁定数组就可以计算更新，这是一种快速而肮脏的实现，应该可以满足您的要求。

Assuming updates can be computed without locking the array, here's a fast and dirty implementation that should satisfy your requirements.

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);
}

当然，如果插入失败，这会使写入线程旋转。如果不可接受，您可以直接使用 try_enqueue 并在入队失败。

Of course, this spins the writing thread if the insertion fails. If that's not acceptable, you can simply use try_enqueue directly and do whatever you'd like to do in the case that the enqueue fails.

这篇关于对稀疏数组的高效多线程写访问？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！