C函数优化

Question

我有一个类似于这样的函数，常数a1-e8 (双精度浮点数)在代码中，比如说硬编码或定义的。该函数在-1.0到1.0的范围内接受双倍，并需要按季度分割，如图所示。

在汇编语言优化之前，还有其他代码优化可以提高运行时性能吗？我尝试制作一个x2来容纳x*x，并将e常量乘以x2*x2，但它实际上降低了性能。我还试着看看是否可以将x的副本转换为整数，并使用switch语句，但这也降低了性能。

double operation(double x) {
    if (x <= -0.75 && x >= -1.0) {
        return a1 + b1*x + c1*x*x + d1*x*x*x + e1*x*x*x*x;
    }
    else if (x <= -0.5) {
        return a2 + b2*x - c2*x*x - d2*x*x*x - e2*x*x*x*x;
    }
    else if (x <= -0.25) {
        return a3 - b3*x - c3*x*x - d3*x*x*x - e3*x*x*x*x;
    }
    else if (x <= 0.0) {
        return a4 - b4*x - c4*x*x - d4*x*x*x + e4*x*x*x*x;
    }
    else if (x <= 0.25) {
        return a5 + b5*x - c5*x*x + d5*x*x*x + e5*x*x*x*x;
    }
    else if (x <= 0.5) {
        return a6 + b6*x - c6*x*x + d6*x*x*x - e6*x*x*x*x;
    }
    else if (x <= 0.75) {
        return a7 - b7*x - c7*x*x + d7*x*x*x - e7*x*x*x*x;
    }
    else if (x <= 1.0) {
        return a8 - b8*x + c8*x*x - d8*x*x*x + f8*x*x*x*x;
    }
    return 0.0;
}

Answer 1

，在汇编语言优化之前，还有其他的代码优化可以提高运行时性能吗？

重新安排比较，这样您基本上是在对正确的大小写进行二进制搜索，而不是线性搜索，从而大大加快了速度：

double op2(double x) {
    if (x <= 0) {
        if (x <= -0.5) {
            if (x <= -0.75 && x >= -1.0) {
                return a1 + b1*x + c1*x*x + d1*x*x*x + e1*x*x*x*x;
            }
            return a2 + b2*x - c2*x*x - d2*x*x*x - e2*x*x*x*x;
        }
        else {
            if (x <= -0.25) {
                return a3 - b3*x - c3*x*x - d3*x*x*x - e3*x*x*x*x;
            }
            return a4 - b4*x - c4*x*x - d4*x*x*x + e4*x*x*x*x;
        }
    }
    else {
        if (x <= 0.5) {
            if (x <= 0.25) {
                return a5 + b5*x - c5*x*x + d5*x*x*x + e5*x*x*x*x;
            }
            return a6 + b6*x - c6*x*x + d6*x*x*x - e6*x*x*x*x;
        }
        else {
            if (x <= 0.75) {
                return a7 - b7*x - c7*x*x + d7*x*x*x - e7*x*x*x*x;
            }
            else if (x <= 1.0) {
                return a8 - b8*x + c8*x*x - d8*x*x*x + e8*x*x*x*x;
            }
        }
    }
    return 0.0;
}

我在同一个循环中调用原始版本(op1)和我的版本(op2)，并在1.0、1.0之间使用相同的随机输入来测试这一点。这两个函数返回相同的值。通过对超过1亿次循环迭代的代码进行分析，我得到了以下结果：

​

​

因此，op2版本的速度比原始版本快不到两倍。

更新：

我还测试了一个版本，它将输入映射到一个整数，然后打开它。这只是因为间隔大小是相同的，所以op2中的方法可以适用于任意间隔，而这个方法不能。为了完成映射，我将1添加到输入，将输入范围移到0，2.0，然后乘以4，将范围扩大到0，8.0。然后我把它转换成int，这样我们就可以打开它了。具有多个连续值的switch语句的好处是编译器可以将其实现为跳转表，这使得它非常快速。代价是额外的浮点乘法。以下是功能：

double op3(double x) {
    int c = (int)((x + 1) * 4);    // mapping from double to int
    switch (c) {
        case 0: {
            return a1 + b1*x + c1*x*x + d1*x*x*x + e1*x*x*x*x;
        }
        case 1: {
            return a2 + b2*x - c2*x*x - d2*x*x*x - e2*x*x*x*x;
        }
        case 2: {
            return a3 - b3*x - c3*x*x - d3*x*x*x - e3*x*x*x*x;
        }
        case 3: {
            return a4 - b4*x - c4*x*x - d4*x*x*x + e4*x*x*x*x;
        }
        case 4: {
            return a5 + b5*x - c5*x*x + d5*x*x*x + e5*x*x*x*x;
        }
        case 5: {
            return a6 + b6*x - c6*x*x + d6*x*x*x - e6*x*x*x*x;
        }
        case 6: {
            return a7 - b7*x - c7*x*x + d7*x*x*x - e7*x*x*x*x;
        }
        case 7: {
            return a8 - b8*x + c8*x*x - d8*x*x*x + e8*x*x*x*x;
         }
        default: {
            return 0.0;
        }
    }
}

其结果是：

​

​

因此，op3比最初的op1快得多，但op2在这种情况下仍然是赢家。但是，如果您有更多的例子，我认为您最终会达到这样一个点:将输入映射到整数的成本低于op2中的比较成本。

查看这三个函数，您可以看到op1方法的复杂性是O(n)，其中n是间隔的数目。op2方法是O(log )，因为有n个间隔所需的log级别的比较。op3方法是O(1)：一旦将输入映射到间隔，开关语句就可以使用跳转表在恒定时间内找到正确的情况。

Answer 2

除了使用编译标志(Linux/Mint19 19上的-Ofast)将使性能提高大约2.5 (100,000,000个呼叫，大部分在此范围内)之外，几乎没有什么小的调整可以帮助：

• 用查找替换if。见下文。减少浪费时间，以找到正确的情况。系数已根据公式的加/减调整为+/-。

这将提供+25%的速度。

原始代码:未优化: 2.154用-Ofast: 0.678修改代码优化，-Ofast: 0.581

double operation(double x) {
    static double aa[] = { a1, a2, a3, a4, a5, a6, a7, a8 } ;
    static double bb[] = { b1, b2, -b3, -b4, b5, b6, -b7, -b8 } ;
    static double cc[] = { c1, -c2, -c3, -c4, -c5, -c6, -c7, c8 } ;
    static double dd[] = { d1, -d2, -d3, -d4, d5, d6, d7, -d8 } ;
    static double ee[] = { e1, -e2, -e3, e4, e5, -e6, -e7, e8 } ;


    if (x < -1.0 || x > 1.0) {
        return 0 ;
    }
    int p = x*4 + 4 ;
//    if ( p < 0 ) p = 1;
    return aa[p] + bb[p]*x + cc[p]*x*x + dd[p]*x*x*x + ee[p]*x*x*x*x;
}

注:我相信原始代码有一个未成年人。它将对任何<-1的负值使用系数(x<-0.5)。我相信-1..+1以外的任何东西都应该返回0。

Answer 3

在香草mac上使用clang：

double dcos(double a, double b, double c, double d, double e, double x) {
        return a + b * x + c * x * x + d * x * x * x + e * x * x * x * x;
}

产生10个mulsd，4个addsd，而：

double dcos(double a, double b, double c, double d, double e, double x) {
        double x2 = x * x;
        return a + b * x + c * x2 + d * x * x2 + e * x2 * x2;
}

生成7个mulsd，3个addsd。它可能在数值上不太稳定，但这是一个区别。在一个快速和肮脏的测试中，它刮了大约16%的折扣。

bfm:tmp steve$ cc -O3 m.c m2.c -o m2
bfm:tmp steve$ cc -O3 m.c m1.c -o m1
bfm:tmp steve$ time ./m1
inf

real    0m4.136s
user    0m4.100s
sys 0m0.026s
bfm:tmp steve$ time ./m2
inf

real    0m3.501s
user    0m3.475s
sys 0m0.023s