如何删除嵌套的 foreach 循环以提高性能

Question

我有一个基于表现的问题。有没有办法删除嵌套的 foreach 循环，用性能更高的东西替换它们？这是一个例子：

List<foo> foos = SelectAllfoos();

foreach(foo f in foos){
    //dosomething

    foreach(foo2 f2 in foo.GetFoos2()){
        //dosomething
    }

    foreach(foo3 f3 in foo.GetFoos3()){
        //dosomething
    }

    foreach(foo4 f4 in foo.GetFoos4()){
        //dosomething

        foreach(foo4_1 f4_1 in f4.GetFoos4_1()){
            //dosomething
        }
    }
}

显然这是我为这个例子发明的假代码。但是想象一下你有这样的东西。您应该如何改进此方法的性能？

PS：我已经尝试使用 System.Threading.Task.Parallel.ForEach 并且它提高了性能，但我的意思是编写此代码的更好方法。

PPS：这是用 C# 编写的，但我的问题涉及更广泛的范围，对所有语言都有用。

Answer 1

由于这个问题比较笼统，而且只关注没有提供有关正在完成的实际工作信息的循环，所以我只能提供一个笼统的答案。

您通常最不想关注的是循环机制本身。这些通常产生的影响很小（如果有的话）。

通常情况下，如果您遇到这种算法改进失败的情况（例如：顺序循环不能比线性时间复杂度做得更好，因为它们无论如何都需要遍历并对每个元素做一些事情），那么两个最大的改进通常来自并行化和内存优化。

不幸的是，后者很少被讨论，尤其是在高级语言中，但通常具有同样多或更多的影响。它可以将执行时间缩短几个数量级，并且适用于任何语言。像缓存效率这样的概念不是语言相关的概念，因为无论我们使用什么编程语言，硬件都保持不变（尽管我们实现它的方式在语言之间可能有很大差异）。

内存访问模式

以图像处理算法为例。在那种情况下，给定两条在其他方面相同的机器指令（除了它们被交换的事实），在外循环中一次访问一个水平扫描线像素的内存访问模式可以显着优于访问一个垂直列像素的内存访问模式一次像素数。即使具有相同总指令级成本（尽管指令成本是可变的）但仅以交换顺序访问内存的其他相同机器指令也是如此。

这是因为，粗略地说，计算机以连续块（页面、高速缓存行）的形式从较慢形式的内存中获取数据到较快形式的内存中。当您水平访问图像的像素时，相邻的水平像素块可能会从较慢形式的内存中获取到更快的形式，并且您最终会在继续访问之前从较快形式的内存中访问所有相邻像素下一个系列的像素。当您以垂直方式访问图像的像素时，您最终会将水平相邻像素加载到更快形式的内存中，而只使用该列中的一个像素。由于缓存未命中，结果可能会显着减慢生成的图像算法，因为我们无法使用所有可用数据，因为在它被驱逐之前加载到更小但更快的内存中（我们基本上是在浪费更小但更快的内存的很多好处）。

所以通常情况下，如果你想让循环运行得更快，并且算法改进已经结束，你会想要分析访问内存的方式，甚至可能改变所涉及数据结构的内存布局。当您访问内存中靠近在一起的连续数据时，计算机会喜欢它，而当您以混乱的方式访问内存时，计算机会非常不喜欢它。他们更喜欢将内存内容紧密打包在一起的数组，而不是将内存分散到各处的链接结构（除非链接结构或其内存分配器经过精心设计，不会这样做）。快速循环不是来自对循环机制的改变，而是来自于循环正在做的事情，但比算法改进甚至并行化更深入的是那些来自面向数据的设计思维的内存相关优化。在像 C# 这样的语言中，从数据结构中获得更好的引用局部性的技术之一是对象池。

循环Tiling/Blocking

有时，您可以通过简单地更改循环访问数据的方式而不实际更改数据的表示方式来改进内存访问模式。一个这样的例子是循环平铺（又名循环阻塞）：https://software.intel.com/en-us/articles/how-to-use-loop-blocking-to-optimize-memory-use-on-32-bit-intel-architecture。但同样，这里的加速不是来自优化您编写循环的方式本身，而是优化您以利用引用局部性的方式遍历数据的方式。它仍然完全是关于内存访问的。

分析

所有这些微观层面的优化技术都有使您的代码更难维护的趋势，因此它们几乎总是最好在事后应用，并且您手头有大量的分析测量。一般来说，了解优化的第一件事是如何衡量，根据硬数据而不是直觉来衡量。初学者往往希望优化更多，而不是更少，因为他们这样做是基于对可能效率低下的猜测，而不是硬数据和适当的测量。对于明显的算法瓶颈很容易做到这一点，但其他任何事情通常都需要您手中的分析器。一个好的优化器是一个狙击手调度热点，而不是一个盲目地向任何可能减慢速度的东西投掷手榴弹的手榴弹。事实上，了解如何正确确定优化的优先级并进行适当的测量可能比了解机器的内部工作原理更重要。所以可能除了所有这些东西之外，如果你想让你的循环运行得更快，首先抓住一个分析器并学习如何正确地衡量低效率。首先要问的不是如何让事情变得更快，而是实际上需要更快的东西（同样重要的是，如果不是更多，什么不是）。

如何删除嵌套的 foreach 循环以提高性能

how to remove nested foreach loops for performance emprovement

performance

foreach

nested-loops