c# – 数组中的分段聚合

在这种情况下适用的一些经验法则：

>如果您可以提示JIT索引将永远不会超出数组的范围,它将删除额外的分支.
>如果它真的很慢(f.ex.> 1秒),你应该只在多个线程中对它进行矢量化.否则任务切换,缓存刷新等可能只会消耗增加的速度,你最终会变得更糟.
>如果可能,使内存访问可预测,甚至是顺序的.如果你需要另一个阵列,那就这样吧 – 如果不是,那就更喜欢.
>如果您想要速度,请使用尽可能少的IL指令.通常这似乎有效.
>测试多次迭代.单次迭代可能不够好.

使用这些规则,您可以按如下方式创建一个小测试用例.请注意,我已将赌注提高到4Kx4K,因为1K速度太快你无法测量它:-)

public static void Main(string[] args)
{
    int width = 4096;
    int height = 4096;

    int[] ar = new int[width * height];
    Random rnd = new Random(213);
    for (int i = 0; i < ar.Length; ++i)
    {
        ar[i] = rnd.Next(0,120);
    }

    // (5)...
    for (int j = 0; j < 10; ++j)
    {
        Stopwatch sw = Stopwatch.StartNew();

        int sum = 0;
        for (int i = 0; i < ar.Length; ++i)  // (3) sequential access
        {
            if ((i % width) == 0)
            {
                sum = 0;
            }

            // (1) --> the JIT will notice this won't go out of bounds because [0<=i<ar.Length]
            // (5) --> '+=' is an expression generating a 'dup'; this creates less IL.
            ar[i] = (sum += ar[i]); 
        }

        Console.WriteLine("This took {0:0.0000}s",sw.Elapsed.TotalSeconds);
    }
    Console.ReadLine();
}

其中一次迭代在这里大约需要0.0174秒,因为这是你描述的最坏情况的16倍,我想你的性能问题已经解决了.

如果你真的想要平行它以使它更快,我认为这是可能的,即使你将松开JIT中的一些优化(具体来说：(1)).但是,如果您拥有像大多数人一样的多核系统,那么这些好处可能会超重：

for (int j = 0; j < 10; ++j)
{
    Stopwatch sw = Stopwatch.StartNew();
    Parallel.For(0,height,(a) =>
    {
        int sum = 0;
        for (var i = width * a + 1; i < width * (a + 1); i++)
        {
            ar[i] = (sum += ar[i]);
        }
    });
    Console.WriteLine("This took {0:0.0000}s",sw.Elapsed.TotalSeconds);
}

如果你确实需要性能,可以将其编译为C并使用P / Invoke.即使您不使用GPU,我认为SSE ??/ AVX指令可能已经为您提供了.NET / C#无法获得的显着性能提升.另外我想指出的是,英特尔C编译器可以自动对代码进行矢量化 – 甚至是Xeon PHI.没有太多的努力,这可能会给你带来很好的性能提升.