c - C代码的优化

Question

对于高性能计算类(class)的作业，我需要优化以下代码片段:

int foobar(int a, int b, int N)
{
    int i, j, k, x, y;
    x = 0;
    y = 0;
    k = 256;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*k);
            if (i > j){
               y = y + 8*(i-j);
            }else{
               y = y + 8*(j-i);
            }
        }
    }
    return x;
}

根据一些建议，我设法优化了代码(至少我是这么认为的)，例如:

1. 持续传播
2. 代数化简
3. 复制传播
4. 公共(public)子表达式消除
5. 消除死代码
6. 循环不变量移除
7. 位移位而不是乘法，因为它们的成本更低。

这是我的代码:

int foobar(int a, int b, int N) {

    int i, j, x, y, t;
    x = 0;
    y = 0;
    for (i = 0; i <= N; i++) {
        t = i + 512;
        for (j = i + 1; j <= N; j++) {
            x = x + ((i<<3) + (j<<2))*t;
        }
    }
    return x;
}

根据我的导师的说法，经过良好优化的代码指令应该在汇编语言级别具有更少或成本更低的指令。因此必须以比原始代码更短的时间运行指令，即使用以下方法进行计算::

execution time = instruction count * cycles per instruction

当我使用以下命令生成汇编代码时:gcc -o code_opt.s -S foobar.c,

尽管做了一些优化，但生成的代码比原始代码多了很多行，运行时间也更低，但没有原始代码那么多。我做错了什么？

不要粘贴汇编代码，因为两者都非常广泛。所以我在 main 中调用函数“foobar”，我在 linux 中使用 time 命令测量执行时间

int main () {
    int a,b,N;

    scanf ("%d %d %d",&a,&b,&N);
    printf ("%d\n",foobar (a,b,N));
    return 0;
}

Answer 1

最初:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
        if (i > j){
           y = y + 8*(i-j);
        }else{
           y = y + 8*(j-i);
        }
    }
}

删除 y 计算:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
    }
}

拆分i、j、k:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 8*i*i + 16*i*k ;                // multiple of  1  (no j)
        x = x + (4*i + 8*k)*j ;                 // multiple of  j
    }
}

在外部移动它们(并删除运行 N-i 次的循环):

for (i = 0; i <= N; i++) {
    x = x + (8*i*i + 16*i*k) * (N-i) ;
    x = x + (4*i + 8*k) * ((N*N+N)/2 - (i*i+i)/2) ;
}

重写:

for (i = 0; i <= N; i++) {
    x = x +         ( 8*k*(N*N+N)/2 ) ;
    x = x +   i   * ( 16*k*N + 4*(N*N+N)/2 + 8*k*(-1/2) ) ;
    x = x +  i*i  * ( 8*N + 16*k*(-1) + 4*(-1/2) + 8*k*(-1/2) );
    x = x + i*i*i * ( 8*(-1) + 4*(-1/2) ) ;
}

重写 - 重新计算:

for (i = 0; i <= N; i++) {
    x = x + 4*k*(N*N+N) ;                            // multiple of 1
    x = x +   i   * ( 16*k*N + 2*(N*N+N) - 4*k ) ;   // multiple of i
    x = x +  i*i  * ( 8*N - 20*k - 2 ) ;             // multiple of i^2
    x = x + i*i*i * ( -10 ) ;                        // multiple of i^3
}

另一个向外部移动(并删除 i 循环):

x = x + ( 4*k*(N*N+N) )              * (N+1) ;
x = x + ( 16*k*N + 2*(N*N+N) - 4*k ) * ((N*(N+1))/2) ;
x = x + ( 8*N - 20*k - 2 )           * ((N*(N+1)*(2*N+1))/6);
x = x + (-10)                        * ((N*N*(N+1)*(N+1))/4) ;

上述两个循环删除都使用了 summation 公式:

Sum(1, i = 0..n) = n+1
Sum(i¹, i = 0..n) = n(n + 1)/2
Sum(i², i = 0..n) = n(n + 1)(2n + 1)/6
Sum(i³, i = 0..n) = n²(n + 1)²/4