函数调用的代价与优化

译者注:本文原始链接为https://johnysswlab.com/make-your-programs-run-faster-avoid-function-calls/,翻译获得作者同意。

这是程序底层优化的第二篇文章,第一篇文章缓存友好程序设计指南

现代软件设计像层(layer),抽象(abstractions)和接口(interfaces)。 这些概念被引入到编程中的初衷是好的,因为它们允许开发者编写更容易理解和维护的软件。 在编译器的世界里,所有这些结构都转化为对函数的调用:许多小函数相互调用,而数据逐渐从一层移动到另一层。

这个概念的问题是,原则上函数调用代价是昂贵的。为了进行调用,程序需要把调用参数放在程序栈上或放到寄存器中。它还需要保存自己的一些寄存器,因为它们可能被调用的函数覆盖。被调用的函数不一定在指令缓存中,这可能导致执行延迟和性能降低。当被调用的函数执行完毕时,返回到原函数也会有性能上的损失。

一方面,函数作为一个概念是很好的,它使软件更可读,更容易维护。另一方面,过多地调用微小的函数,肯定会使程序变慢。

避免函数调用的一些技巧

让我们来看看避免函数调用的一些技巧。

内联

内联是编译器用来避免函数调用和节省时间的一种技术。简单地说,内联一个函数意味着把被调用的函数主体放在调用的地方。一个例子:

void sort(int* a, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            swap_if_less(&a[i], &a[j]);
        }
    }
}
template <typename T>
void swap_if_less(T* x, T* y) {
    if (*x < *y) {
        std::swap(*x, *y);
    }
}

函数 sort 正在进行排序,而函数 swap_if_less 是 sort 使用的一个辅助函数。函数 swap_if_less 是一个小函数,并被 sort 多次调用,所以避免这种情况的最好办法是将 swap_if_less 的主体复制到函数 sort 中,并避免所有与函数调用有关的开销。内联通常是由编译器完成的,但你也可以手动完成。我们已经介绍了手动内联,现在我们来介绍一下由编译器进行的内联。所有的编译器都会默认对小函数进行内联调用,但有些问题:

  • 如果一个被调用的函数被定义在另一个 .C 或 .CPP 文件中,它不能被自动内联,除非启用了链接优化。
  • 在C++中,如果类方法是在类声明中定义的,那么它将被内联,除非它太大。
  • 标记为静态的函数可能会被自动内联。
  • C++的虚方法不会被自动内联(但也有例外)。
  • 如果一个函数是用函数指针调用的,它就不能被内联。另一方面,如果一个函数是作为一个lambda表达式被调用的,那么它很可能可以被内联。
  • 如果一个函数太长,编译器可能不会内联它。这个决定是出于性能考虑,长函数不值得内联,因为函数本身需要很长的时间,而调用开销很小。

内联会增加代码的大小,不小心的内联会带来代码大小的爆炸,实际上会降低性能。因此,最好让编译器来决定何时内联和内联什么。

在 C 和 C++ 中,有一个关键字 inline。如果函数声明中有这个前缀,就是建议编译器进行内联。在实践中,编译器使用启发式方法来决定哪些函数需要内联,并且经常不理会这个提示。

检查你的代码是否被内联的方法,你可以通过对目标代码反汇编(使用命令objdump -Dtx my_object_file.o)或以编程的方式(文章最后有介绍) 。GCC 和 CLANG 编译器提供了额外属性来实现内联:

  • __attribute__((always_inline))-强制编译器总是内联一个函数。如果不可能内联,它将产生一个编译警告。
  • __attribute__((flatten))– 如果这个关键字出现在一个函数的声明中,所有从该函数对其他函数的调用将尽可能被替换为内联版本。

内联和虚函数

正如上文所述,虚函数是不能够被内联的。并且,使用虚函数被其他函数代价更大。有一些解决方案可以缓解这个问题:

  • 如果一个虚拟函数只是简单地返回一个值,可以考虑把这个值作为基类的一个成员变量,并在类的构造中初始化它。之后,基类的非虚拟函数可以返回这个值。
  • 你可能正在将你的对象保存在一个容器中。与其将几种类型的对象放在同一个容器中,不如考虑为每种对象类型设置单独的容器。因此如果你有base_classchild_class1child_class2child_class3 ,应当使用std::vector<child_class1>std::vector<child_class2>std::vector<child_class3> 而不是std::vector<base_class> 。这涉及到更多的设计上的问题,但实际上程序要快得多。

上述两种方法都会使函数调用可内联。

内联实践

在某些情况下,内联是有用的,而在某些情况下却没用。是否应该进行内联的第一个指标是函数大小:函数越小,内联就越有意义。如果调用一个函数需要50个周期,而函数体需要20个周期来执行,那么内联是完全合理的。 另一方面,如果一个函数的执行需要5000个周期,对于每一个调用,你将节省1%的运行时间,这可能不值得。

内联的第二个标准是函数被调用的次数。 如果它被调用了几次,那么就没必要内联。 另一方面,如果它被多次调用,内联是合理的。然而,请记住,即使它被多次调用,你通过内联得到的性能提升可能也不值得。

编译器和链接器清楚地知道你的函数的大小,它们可以很好地决定是否内联。就调用频率这方面而言,编译器和链接器在这方面的知识也是有限的,但为了获得有关函数调用频率的信息,有必要在真实世界的例子上对程序进行剖析。但是,正如我所说的,大型函数很可能不是内联的好选择,即便它们被多次调用。

因此,在实践中,是否内联的决定权大部分交给编译器,你只要在影响性能关键函数明确其进行内联。

如果通过剖析你的程序,你发现了一个对性能至关重要的函数,首先你应该用__attribute__((flatten))来标记它,这样编译器就会内联该函数对其他函数的所有调用,其整个代码就变成了一个大函数。但即使你这样做了,也不能保证编译器真的会内联所有的东西。你必须确保内联没有障碍,正如已经讨论过的那样:

  • 打开链接时的优化,允许其他模块的代码被内联。
  • 不要使用函数指针来调用。在这种情况下,你会失去一些灵活性。
  • 不要使用C++的虚拟方法来调用。你失去了一些灵活性,但有一些方法可以解决已经提到的这个问题。

只有当编译器不能自动内联一个函数时,你才会想手动内联。如果自动内联失败,编译器会发出警告,从那时起,你应该分析是什么原因阻止了内联,并修复它,或者选择手动内联一个函数。

关于内联的最后一句话:有些函数你不希望内联。对于你的性能关键函数,有一些代码路径会经常被执行。但也有其他路径,如错误处理,很少被执行。你想把这些放在单独的函数中,以减少对指令缓存的压力。用__attribute__((cold))标记这些函数,让编译器知道它们很少执行,这样编译器就可以把它们从经常访问路径中移开。

避免递归函数

递归函数是可以调用自己的函数。虽然带有递归函数的解决方案通常更优雅,但从程序性能方面来看,非递归解决方案更有效率。因此,如果你需要优化带有递归函数的代码,有几件事你可以做:

  • 请确保你的递归函数是尾部递归。这将允许编译器对你的函数进行尾部递归优化,并将对函数的调用转换为跳跃。
  • 使用堆栈数据结构将你的递归函数转换成非递归。这将为你节省一些与函数调用有关的时间,但实现这个并不简单。
  • 在函数的每次迭代中做更多的事情。例如:
int factorial(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * (n - 1) * factorial(n - 2);
    }
}

上面的实现是在普通的代码基础上,做了更多的工作。

使用函数属性来给编译器提供优化提示

GCC 和 CLANG 提供了某些函数属性,启用后可以帮助编译器生成更好的代码。其中有两个与编译器相关的属性:const 属性和 pure 属性。

属性 pure 意味着函数的结果只取决于其输入参数和内存的状态。该函数不向内存写东西,也不调用任何其他有可能这样做的函数。

int __attribute__((pure)) sum_array(int* array, int n) {
     int res = 0;
    for (int i = 0; i < n; i++) {
        res += a[i];
    }
    return res;
}

pure 函数的好处是,编译器可以省略对具有相同参数的同一函数的调用,或者在参数未使用的情况下删除调用。

属性 const 意味着函数的结果只取决于其输入参数。例子:

int __attribute__((const)) factorial(int n) {
    if (n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

每个 const 函数也都是 pure 函数,所以关于pure 函数的一切说法也都适用于 const 函数。此外,对于 const 函数,编译器可以在编译过程中计算它们的值,并将其替换为常量,而不是实际调用该函数。

C++有成员函数的关键字 const ,但功能并不相同:如果一个方法被标记为 const,这意味着该方法不会改变对象的状态,但它可以修改其他内存(例如打印到屏幕上)。编译器使用这些信息来做一些优化; 如果该成员是常量,那么如果对象的状态已经被加载,就不需要再重新加载。例如:

class test_class {
    int my_value;
private:
    test_class(int val) : my_value(val) {}
    int get_value() const { return my_value; }
};

在这个例子中,方法 get_value 不会改变类的状态,可以被声明为 const。

如果你的函数要以库的形式提供给其他开发者,那么将函数标记为 const 和 pure 就特别重要。你不知道这些人是谁,也不知道他们的代码质量如何,这将确保编译器在编程马虎的情况下可以优化掉一些代码。请注意,标准库中的许多函数都有这些属性。

实验

ffmpeg – inline 与 no-inline

我们编译了两个版本的ffmpeg,一个是具有完全优化的默认版本,另一个是通过-fno-inline和-fno-inline-small-functions编译器关闭内联的削弱版本。我们用以下选项编译了ffmpeg:

./configure --disable-inline-asm --disable-x86asm --extra-cxxflags='-fno-inline -fno-inline-small-functions' --extra-cflags='-fno-inline -fno-inline-small-functions'

看来内联并不是ffmpeg性能大幅提升的根源。下面是结果:

Parameter Inlining disabled Inlining enabled
Runtime (s) 291.8s 285s

常规编译(带内联)只比禁用内联的版本快2.4%。让我们来讨论一下。正如我们以前所说的,为了从内联中获得真正的好处,你的函数尽可能短。否则的话,内联并不能带来性能的提升。

我们对 ffmpeg 进行了分析,ffmpeg 本身也使用了 av_flatten 和 av_inline 宏,它们与 GCC 中的 flatten 和 inline 属性相对应。当这些属性被明确设置时,-finline 和 fno-inline 开关没有任何作用。我想这就是我们看到性能差异如此之小的原因。

我们还尝试对一些函数使用 flatten 属性,以使转换更快,但没有任何函数会带来性能上的显著提高,因为没有真正的小函数会有这样的含义。

测试

我们使用 ffmpeg 结果并不好。因此为了明白 inline 是有效的,我们创建了一些测试用例。它们在我们的github仓库里 。运行它们只需要到路径 2020-06-functioncalls 下执行 make sorting_runtimes。

我们采用了一个常规的选择排序算法,并对其进行了一些内联处理,看看内联对排序的性能有何影响。

void sort_regular(int* a, int len) {
    for (int i = 0; i < len; i++) {
        int min = a[i];
        int min_index = i;
        for (int j = i+1; j < len; j++) {
            if (a[j] < min) {
                min = a[j];
                min_index = j;
            }
        }
        std::swap(a[i], a[min_index]);
    }
}

请注意,该算法由两个嵌套循环组成。循环内部有一个 if 语句,检查元素 a[j] 是否小于元素 min,如果是,则存储新的最小元素的值。

我们在这个实现的基础上创建了四个新函数。其中两个是调用内联版本的函数,另外两个是调用非内联版本的函数。我使用 GCC 的 __attribute__((always_inline)) 和 __attribute__((noinline)) 来确保当前状态正确的(不会被编译器自动内联)。其中两个叫sort_[no]inline_small 的函数将if(a[j]<min) 里的语句封装成为函数调用。另外两个sort_[no]inline_large 则将for (int j = i + 1; j < len; j++) { ... } 里面的语句全部封装成函数。下面是具体的算法实现:

void sort_[no]inline_small(int* a, int len) {
    for (int i = 0; i < len; i++) {
        int min = a[i];
        int min_index = i;
        for (int j = i+1; j < len; j++) {
            update_min_index_[no]inline(&a[j], j, &min, &min_index);
        }
        std::swap(a[i], a[min_index]);
    }
}
void sort_[no]inline_large(int* a, int len) {
    for (int i = 0; i < len; i++) {
        int smallest = find_min_element_[no]inline(a, i, len);
        std::swap(a[i], a[smallest]);
    }
}

我们执行上述的五个函数,并且输入的数组长度为 40000。下面是结果:

Regular Small inline Small Noinline Large Inline Large Noinline
Runtime 1829ms 1850ms 3667ms 1846ms 2294ms

正如你所看到的,普通、小内联和大内联之间的差异都在一定的测量范围内。在小内联函数的情况下,内循环被调用了4亿次,这在性能上的提升是可观的。小的不内联的实现比常规实现慢了2倍。在大型内联函数的情况下,我们也看到了不内联会导致性能下降,但这次的下降幅度较小约为20%。在这种情况下,内循环被调用了4万次,比第一个例子中的4亿次小得多。

总结

正如我们在上章节看到的那样,函数调用是昂贵的操作,但幸运的是,现代编译器在大多数时候都能很好地处理这个问题。开发者唯一需要确保的是,内联没有任何障碍,例如禁用的链接时间优化或对虚拟函数的调用。如果需要优化对性能敏感的代码,开发者可以通过编译器属性手动强制内联。

本文提到的其他方法可用性有限,因为一个函数必须有特殊的形式,以便编译器能够应用它们。尽管如此,它们也不应该被完全忽视。

如何检查函数在运行时是否被内联?

如果你想检查函数是否被内联,首先想到的是查看编译器产生的汇编代码。但你也可以以编程方式在程序执行过程中来确定。

假设你想检查一个特定的调用是否被内联。你可以这样做。每个函数都需要维护一个非内联可寻址的地址,方便外部调用。检查你的函数my_function是否被内联,你需要将my_function的函数指针(未被内联)与PC的当前值进行比较。根据比较的差异就可获得结论:

以下是我在我的环境中的做法(GCC 7,x86_64):

void * __attribute__((noinline)) get_pc () { return _builtin_return_address(0); }
    
void my_function() {
    void* pc = get_pc();
    asm volatile("": : :"memory");
    printf("Function pointer = %p, current pc = %p\n", &my_function, pc);
}
void main() {
    my_function();
}

如果一个函数没有被内联,那么PC的当前值和函数指针的值之间的差异应该很小,否则会更大。在我的系统中,当my_function没有被内联时,我得到了以下输出:

Function pointer = 0x55fc17902500, pc = 0x55fc1790257b

如果该函数被内联,我得到的是:

Function pointer = 0x55ddcffc6560, pc = 0x55ddcffc4c6a

对于非内联版本的差异是0x7b,对于内联版本的差异是0x181f。

扩展阅读

Smarter C/C++ inlining with __attribute__((flatten))

Agner.org: Software Optimization Resources

Implications of pure and constant functions

页面下部广告