优化嵌套循环

Question

我们有一个任务，需要优化一段非常低效的程序，使其运行更快。我已经优化了大部分代码，除了这两个简单的函数，它们让我感到困扰，因为它们非常简单。其中一个函数将二维数组中的所有值设置为相同的值，另一个函数交换两个二维数组的值。这就是问题所在。尽管这两个函数很简单，但它们占用了最多的时间，我无法找出如何简化它们而不破坏函数。我知道可以使它们运行得更快，因为班里其他学生已经取得了惊人的加速效果。这两个函数分别是：

fSetArray(int rows, int cols, float val)
{
    int i, j;
    F2D *out;
    out = fMallocHandle(rows, cols);

    for(i=0; i<rows; i++)
    for(j=0; j<cols; j++)
        subsref(out,i,j) = val;

    return out;

}

这段代码中最重要的部分是两个循环。基本上，我们有一个二维数组，它有一定的宽度（行）和一定的高度（列），我们将所有值都设置为val。但是我没有看到任何可以消除其中一个循环（这将是加速的最佳方法）的方法，除非我漏看了什么明显的东西。如果cols和rows是相同的数字，那么这会变得容易得多。

另一个函数是：

fDeepCopy(F2D* in)
{
    int i, j;
    F2D* out;
    int rows, cols;

    rows = in->height;
    cols = in->width;

    out = fMallocHandle(rows, cols);

    for(i=0; i<rows; i++)
    for(j=0; j<cols; j++)
        subsref(out,i,j) = subsref(in,i,j);

    return out;
}

输出数组始终大于输入数组，因此我们不必担心溢出等问题。这个函数基本上只是交换了两个数组的值，但由于它非常简单，我无法进一步减少它。

在有人提到并行化之前，由于样本大小和服务器，创建线程所需的开销实际上会减慢程序的速度。我已经尝试过了。因为这两个函数太短了，不值得创建线程，只是为了在一个并行循环后杀死它们。

但是作为参考，技术上说这是一个OpenMP项目，我们应该使用并行化，但对于这两个函数来说，这样做实际上会降低整个程序的速度。我已经用并行循环计时过了。

编辑：感谢所有给我提建议的人！现在我已经让它完全运行，并且速度非常快！

- T T

---

尝试交换循环的顺序 - 这可能会影响缓存命中率。 - Sergey Kalinichenko

subsref 是如何定义的？它很可能是一个宏，但如果它是一个函数，请确保它被内联。或者将其重写为宏。 - Greg Inozemtsev

你需要包含更多细节，特别是关于F2D结构和subsref函数。 - betabandido

你能调用一个类似于memcpy / memset的函数吗？ - Michael Dorgan

我在考虑这个问题。我假设所有这些元素都是连续存储在内存中的，如果是这样的话，我可以直接调用memcpy，因为浮点数具有固定的字节大小。 - T T

你做了哪些改变，使得速度有所提升？ - steveha

Answer 1

一种优化的方法是循环展开。有时，由于在获取索引、更新它并将其存回内存时存在大量活动，流水线需要停顿。这可能是您的多线程实现表现不佳的主要原因，所有线程可能都在争夺对索引的访问。

如果您想重新尝试多线程实现，请让每个线程根据线程计数知道它的“偏移量”，并让每个线程处理通过模除发现的不同余数。

thread 0 works on i*rows+j % (thread count) = 0
thread 1 works on i*rows+j % (thread count) = 1
(and so on)

如果您不想重新尝试多线程实现，仍然有一些技术可以提高性能。有时，即使是单个线程也可能会在索引变量上无谓地停顿（因为它导致处理器流水线的低效使用）。为了解决这种问题，可以通过按特定数量递增索引并在循环内调用该方法来尝试修复。

fDeepCopy(F2D* in)
{
    int i, j;
    F2D* out;
    int rows, cols;

    rows = in->height;
    cols = in->width;

    out = fMallocHandle(rows, cols);

    for(i=0; i<rows; i++) {
      // rewrite to ensure we don't walk off "4 long" pads
      int j = 0;
      int pads = (cols / 4)*4;
      for(; j < pads; j = j + 4) {
        subsref(out,i,j) = subsref(in,i,j);
        subsref(out,i,j+1) = subsref(in,i,j+1);
        subsref(out,i,j+2) = subsref(in,i,j+2);
        subsref(out,i,j+3) = subsref(in,i,j+3);
      }
      // process the remainders
      for(; j < pads; j++) {
        subsref(out,i,j) = subsref(in,i,j);
      }
    }
    return out;
}

现在CPU设计师越来越优秀，因此实际上对您的运行进行分析以确定CPU是否已经为您执行了这样的优化，或者这样的技术实际上可能会减慢您的代码速度是至关重要的。

最后，您还可以利用SSE扩展（链接），在正确的条件下可以对存储在MMX寄存器中的多个值执行相同的操作。例如，您可以使用内联汇编将两组四个32位单精度浮点数打包到MMX寄存器中，然后一次性执行四个浮点数的加法。

因此，看起来像是：

vec_res.x = v1.x + v2.x;
vec_res.y = v1.y + v2.y;
vec_res.z = v1.z + v2.z;
vec_res.w = v1.w + v2.w;

需要进行八次内存查找、四次加法和四次存储（未经优化的16个操作）的操作，可以被替换为

movaps xmm0, [v1]          ;xmm0 = v1.w | v1.z | v1.y | v1.x 
addps xmm0, [v2]           ;xmm0 = v1.w+v2.w | v1.z+v2.z | v1.y+v2.y | v1.x+v2.x               
movaps [vec_res], xmm0

只需要三个未经优化的操作。

关键在于分析性能，以便检测瓶颈并调整代码，使其达到最小可接受性能。

- Edwin Buck

Answer 2

memset 对于第一个函数应该很有帮助。

- Charles