C代码循环优化(没有编译器优化)

Question

在不需要编译器优化(使用-o标志编译)的环境中，可以对此代码应用什么手动代码优化以使其运行得更快？数组大小为512x512。

for(iy=0;iy<Ny;iy++) {
for(ix=0;ix<Nx;ix++) {

if (ix==0) {
  pudx = (u[1][iy] + u[Nx-1][iy] - 2.0*u[0][iy])/(calc1);   
} else if (ix==Nx-1) {
  pudx = (u[0][iy] + u[Nx-2][iy] - 2.0*u[Nx-1][iy])/(calc1);  
} else {
  pudx = (u[ix+1][iy] + u[ix-1][iy] - 2.0*u[ix][iy])/(calc1);
}

if (iy==0) {
  pudy = (u[ix][1] + u[ix][Ny-1] - 2.0*u[ix][0])/(calc2);    
} else if (iy==Ny-1) {
  pudy = (u[ix][0] + u[ix][Ny-2] - 2.0*u[ix][Ny-1])/(calc2);   
} else {
  pudy = (u[ix][iy+1] + u[ix][iy-1] - 2.0*u[ix][iy])/(calc2);
}


u_new[ix][iy] = 2.0*u[ix][iy] - u_old[ix][iy] + calc*(pudx+pudy);

  }
}

到目前为止，我可以考虑把calc1和calc2的反义词放在循环之外。

我现在正试图找到一种在循环之外编写if语句的方法，但无法找到一种方法。有什么建议吗？

Answer 1

你想要尽可能多地从内部循环中移动。这似乎很容易。另外，空格是免费的，根本不让程序慢下来(长变量名称会减慢代码的速度，但空格不会)！

你的内环是ix。您有一系列的if/elsif/else来检查ix的值，但是有趣的情况是该循环的第一次和最后一次迭代！因此，缩短循环，并将例外情况移出它。当然，您也可以对以if/elsif/else变量为中心的iy做同样的事情，将这些语句移出外部循环。但是这会复制两次内部循环，这可能是你不想做的。因此，也许可以少做一点，把计算移到外部循环：

for (prev_iy = Ny - 1, iy = 0, next_iy = 1; 
     iy < Ny; 
     prev_iy = iy, ++iy, ++next_iy) 
{
    if (iy == Ny - 1) 
        next_iy = 0;

    /* if (ix == 0) {  -- moved out of inner loop */
    ix = 0; 

    pudx = (u[ix+1][iy] + u[Nx-1][iy] - 2.0*u[ix][iy])/(calc1);   
    pudy = (u[ix][next_iy] + u[ix][prev_iy] - 2.0*u[ix][iy])/(calc2);
    u_new[ix][iy] = 2.0 * u[ix][iy] - u_old[ix][iy] + calc * (pudx + pudy);

    for (ix = 1; ix < Nx - 1; ++ix) {
        pudx = (u[ix+1][iy] + u[ix-1][iy] - 2.0 * u[ix][iy])/(calc1);
        pudy = (u[ix][next_iy] + u[ix][prev_iy] - 2.0 * u[ix][iy])/(calc2);
        u_new[ix][iy] = 2.0*u[ix][iy] - u_old[ix][iy] + calc*(pudx+pudy);
    }

    /* if (ix == Nx - 1) { -- moved out of inner loop */
    pudx = (u[0][iy] + u[ix-1][iy] - 2.0*u[ix][iy])/(calc1);  
    pudy = (u[ix][next_iy] + u[ix][prev_iy] - 2.0*u[ix][iy])/(calc2);
    u_new[ix][iy] = 2.0*u[ix][iy] - u_old[ix][iy] + calc*(pudx+pudy);
}

接下来，我建议反转循环( ix上的循环，然后是iy)。或者交换x/y变量的名称。我不知道您的目标体系结构是什么，但是一般来说，C编译器将数据存储在行主订单中，如果您遵循这种顺序，它会对性能产生巨大的影响。显然，您将访问所有的单元，但是您确实希望尽可能多地访问从低到高的内存地址。

如果您的Nx和Ny值确实是常量--表明矩阵为512 x 512 --您可以通过使用511按位执行&来获得很多好处。例如，"-1“将变为511,512将变为0。只要您的数组大小总是2的幂，按位计算，而且很便宜，并且可以将所有的情况折叠成一行代码。

有几个“重复”的值。您可能会对这些值进行有益的缓存。(例如，u[ix][iy]经常被使用。)

更好的是，请记住，上一次通过循环时，u[ix-1][iy]与u[ix][iy]是相同的。因此，您可以将这些值从一个循环循环“保存”到下一个循环，并在不同的地方使用它们。类似地，在一个循环中，当ix得到一个更高的值时，u[ix+1][iy]将是u[ix][iy]，因此您也可以保存该值。

对于内环，实际上在管道中有三个值，将它们称为“最后”、“curr”和“下一步”。next值为u[ix+1][iy]。last和curr值只是next的旧副本：

last = curr;
curr = next;
next = u[ix + 1][iy];
pudx = (-2.0 * curr + last + next) / calc1;

类似地，管道中有3个值处于perpindicular状态：伊-1、iy和iy+1。显然，curr对两者都是一样的，但我认为您不能有效地缓存之前的512个值。( CPU缓存可能会存储它们，但不应该尝试在程序中缓存它们。)

指针？

因为您的计算相当简单，所以您可能考虑做的一件事是使用指针而不是数组访问。同样，这假设您重构您的循环以保持正确的顺序。例如，您可以尝试这样的方法：

prev_row = u[511];
this_row = u[0] + 1;
next_row = u[1];
new = u_new;
old = u_old;

for (i = 0; i < 511 * 512; ++i) {
    last = curr;
    curr = next;
    curr2 = 2.0 * curr;
    next = *this_row++;
    pudy = (*prev_row++ + *next_row++ - curr2) / calc1;
    pudx = (last + next - curr2) / calc2;

    *new++ = curr2 - *old++ + calc * (pudx + pudy);
}

/* Now handle last row, after fixing next_row pointer */

next_row = u[0];
for (i = 0; i < 512; ++i ) {
    ... as above ...
}

值得指出的是，现在您的代码非常脆弱。你有很多数组索引，任何小错误(比如加号而不是减号，或者x代替y)都会给你一个可能有效的结果--看起来不太正确。

您将需要一组强大的测试用例来捕获这类事情。但我也建议您使用变量或预处理宏来拼写事物，而不是象征性地表达它们。

例如：

#define ABOVE(m,row,col)  (m[(row)-1][col])
#define BELOW(m,row,col)  (m[(row)+1][col])
#define LEFT(m,row,col)   (m[row][(col)-1])
#define RIGHT(m,row,col)  (m[row][(col)+1])
#define CENTER(m,row,col) (m[row][col])

然后你可以说：

pudx = (BELOW(u,ix,iy) + ABOVE(u,ix,iy) - 2.0 * CENTER(u,ix,iy)) / (calc1);  

你可以走得更远，但想法是产生一个单一的真理来源，你可以盯着它很难确认它是正确的，然后让其他一切看起来基本相同。

这显然不适用于指针场景。但是在这种情况下，您可能需要为循环体定义一个宏，这样就可以很容易地重复它。

程序集

编译器有一个命令行开关，它将生成程序集代码作为输出。它可能是-S (gcc)或/FAs (msvc)，但它在那里。用它！如果您不打算启用优化，那么您将不得不自己测量效果。这样做的一个好方法是查看生成的程序集，并查看特定更改所产生的结果。

老实说，这很难。但是，如果您专注于代码的一小部分--最内部的循环--您通常可以知道发生了什么。而在大多数情况下，更短的是更好。

Optimization

您没有说明为什么您无法使用优化选项。除非这是为某些类分配，我鼓励您尝试启用优化无论如何。你可以做的一件事就是分裂你的代码。将这一个函数移动到一个单独的.c源文件中，并使其编译和运行正常。然后，无论您通常做什么，都可以开始构建您的项目，但是请将这个单独的.c文件配置为使用更高的优化级别。这可能会让你避开你遇到的任何障碍(技术或政治)。

当然，良好的单元测试是必不可少的。