锐客网

  1. 首页 > it技术 > >

函数调用的代价与优化

译者注：本文原始链接为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 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_class 和child_class1、child_class2和child_class3 ，应当使用std::vector 、std::vector和std::vector 而不是std::vector 。这涉及到更多的设计上的问题，但实际上程序要快得多。
上述两种方法都会使函数调用可内联。
内联实践
在某些情况下，内联是有用的，而在某些情况下却没用。是否应该进行内联的第一个指标是函数大小：函数越小，内联就越有意义。如果调用一个函数需要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] 里的语句封装成为函数调用。另外两个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

    推荐阅读


    上一篇：算法|算法 | Java 常见排序算法（纯代码）

    下一篇：安卓开源框架学习|OKHttp原理讲解之RetryAndFollowUpInterceptor