C#中的并行数组处理

Question

我有一个包含921600个0到255之间数字的数组。

我需要检查每个数字是否超过了一个阈值。

能否同时检查数组的前半部分和后半部分，以减少运行时间?

我的意思是，以下两个for循环是否可以并行运行？

for(int i = 0; i < 921600 / 2; i++)
{
    if(arr[i] > 240) counter++;
}

for(int j = 921600 / 2; j < 921600; j++)
{
    if(arr[j] > 240) counter++;
}

提前感谢您！

- Mate Koroknai

---

你尝试使用过Parallel.For吗？它不一定会分成两部分，但我认为根据系统的不同，你会得到非常好的提升。 - Philippe Paré

我会跳过前一半/后一半的内容...那没有任何作用。请使用Parallel.For。 - Trey

如果你要从不同的线程中递增 counter，请确保使用类似 Interlocked.Increment() 的方法正确地执行它。 - itsme86

并行处理的问题在于，你应该批量处理而不是逐个元素处理。 - Jeroen van Langen

Answer 1

我建议在这种情况下使用Parallel Linq (PLinq)

int[] source = ...

int count = source
  .AsParallel()  // comment this out if you want sequential version
  .Count(item => item > 240);

- Dmitry Bychenko

---

这听起来不错，但与单线程版本相比，可能会非常慢。 "调用" 线程池线程的成本比比较本身更高。 - Jeroen van Langen

@Jeroen van Langen：这就是为什么我在.AsParallel()上放了一个注释的原因：简单的Count不适合并行执行。当我们需要决定是否应该并行计算时，PLinq非常方便 - 只需添加/注释掉一行即可。 - Dmitry Bychenko

Answer 2

您所询问的内容是完全可行的，具体如下。

int counter = 0;
var tasks = new List<Task>();
var arr = Enumerable.Range(0, 921600).ToArray();
tasks.Add(Task.Factory.StartNew(() =>
{
    for (int i = 0; i < 921600 / 2; i++)
    {
        if (arr[i] > 240) counter++;
    }
}));
tasks.Add(Task.Factory.StartNew(() =>
{
    for (int j = 921600 / 2; j < 921600; j++)
    {
        if (arr[j] > 240) counter++;
    }
}));
Task.WaitAll(tasks.ToArray());

不要使用此代码！您将遇到竞争条件，其中一个线程的增量由于“读取，读取，写入，写入”情况而丢失。在LinqPad中运行此代码，我最终得到的计数器值在600,000和800,000之间。显然，这个范围远不及实际值。

解决此竞争条件的方法是引入锁定，这意味着只有一个线程可以同时触摸变量。这消除了分配为多线程的能力，但允许我们获得正确的答案。（参考我的机器需要0.042秒）

int counter = 0;
var tasks = new List<Task>();
var arr = Enumerable.Range(0, 921600).ToArray();
var locker = new Object();
tasks.Add(Task.Factory.StartNew(() =>
{
    for (int i = 0; i < 921600 / 2; i++)
    {
        if (arr[i] > 240)
            lock (locker)
                counter++;
    }
}));
tasks.Add(Task.Factory.StartNew(() =>
{
    for (int j = 921600 / 2; j < 921600; j++)
    {
        if (arr[j] > 240)
            lock (locker)
                counter++;
    }
}));
Task.WaitAll(tasks.ToArray());

解决方案确实是使用Dmitry建议的并行Linq：

Enumerable.Range(0, 921600).AsParallel().Count(x=>x>240);

这需要0.031秒，比我们的锁定代码更快，仍然返回正确的答案，但是去掉 AsParallel 调用后，它可以在 0.024 秒内运行。并行运行一段代码会引入管理线程的开销。有时性能提升超过了这个开销，但是很多时候却没有。

故事的寓意是，始终针对你预期的数据运行一些度量/时间测量，并检查是否实际上存在性能优势。

- Daniel Gee

Answer 3

在搜索并行概念时，发现了你的问题。也许下面的小技巧可以帮助你。

int n=921600/2;
for(int i=0; i<n; i++)
{
 if(arr[i]>240) counter ++;
 if(arr[n + i] > 240) counter ++;
}

- bala prathap

---

这被称为循环展开，它可能会提高性能，因为对编译器来说更容易。但只适用于偶数计数。 - Kari