我已经有了一个实现它的实现,但是在整个数组上完全迭代,对于大型(1M元素)数组来说非常慢.
给出以下示例数组,
0 0 1 0 0 2 0 0 0 3 0 4 1 1 0 0 1 0 4 1
变
0 0 1 1 1 2 2 2 2 5 0 4 5 6 6 0 1 1 5 6
等等,直到有问题的尺寸(1024×1024)
数组需要更新(理想情况下),但如果需要可以使用另一个数组.内存占用空间不是问题,但性能至关重要,因为这些阵列具有数百万个元素,每秒必须处理数百次.
单个单元格计算似乎不可并行化,因为它们依赖于从左侧开始的值,因此GPU加速似乎是不可能的.我已经研究过PLINQ,但索引的必要条件使得它很难实现.
是否有另一种方法来构建数据以使其更快地处理？
如果使用创新的技术可以实现高效的GPU处理,那么这将是非常优选的,因为这是当前必须从视频卡中拉出并推回到视频卡的纹理数据.
解决方法
在这种情况下适用的一些经验法则：
>如果您可以提示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.没有太多的努力,这可能会给你带来很好的性能提升.
