.net - 大数组和多线程 - 自旋锁或本地缓冲区还是其他什么？

Question

• 我有一个包含 250k 实体(大小为 20 字节)和 4 个线程的数组。
• 每个线程都会修改约 100k 个随机实体(这意味着您无法预测它将接触哪些实体)。它可以多次修改同一个实体。
• 每个实体最多可修改约 10 次。
• 修改大约需要 10^-6 秒。
• 每个实体都会被多个线程修改

最后一点是最重要的事实。第五点意味着我需要一种机制来保护我的实体不因并发访问/修改而损坏。第四点让我担心，考虑到获取锁的时间跨度很短，诸如互斥锁之类的经典锁定机制(会阻塞线程)是否会产生太多开销。

我想出了两个想法:

• 使用自旋锁来克服开销(假设我对开销的假设首先是正确的)。
• 为每个线程提供一个可以不间断修改的数组的本地副本。所有线程完成后，将所有数组合并为一个。这是可能的，因为如果一个实体有多个副本，我就可以选出获胜者。

你有什么推荐？您同意我的某个想法还是推荐其他想法？如果我将数字更改为，您的建议会改变吗？:

• 100 万个实体
• 8 个线程
• ~500k 随机访问
• 每个实体约 100 项修改

还请指出 C#/.Net 中的实现。提前致谢。

其他信息
实体是值类型(结构)。我无法为每个写入操作创建新对象 - 只能修改现有基元。

Answer 1

正如他们所说，剥猫皮的方法不止一种(尽管为什么有人想要剥猫皮是另一个问题):-)

对于 250K 对象和 4 个线程，您必须猜测冲突会(相对)罕见。这并不意味着我们可以忽略它们，但它可能会影响我们寻找它们的方式。测试关键部分非常快，除非确实存在冲突。这意味着检查每个事务的关键部分可能是可行的，因为我们知道相对较少的检查将花费更多的 CPU 时间。

创建 250K 个临界区是否可行？也许吧，我不确定。您可以使用以下命令创建一个非常轻量级的自旋锁:

while (0 != ::InterlockedExchange(&nFlag, 1)) {};
DoStuff();
nFlag = 0;

另一种方法可能是对数据集进行分区，并让每个线程处理一组唯一的对象。这使得冲突不可能发生，因此不需要锁定。根据问题的性质，您可以通过让每个线程操作一系列数据来实现这一点，或者可能通过为每个工作线程操作一个队列，并让一个或多个扫描线程识别需要处理的对象并将它们推送到适当的对象上来实现这一点。处理队列。