9

给定一个像 C-Stdlib 这样将 C-Functionpointer 作为回调的典型函数，qsort()任何编译器都可以使用内联优化代码吗？我认为不可能，这是正确的吗？

int cmp(void* pa, void* pb) { /*...*/ }
int func() {
  int vec[1000];
  qsort(vec, 1000, sizeof(int), &cmp);
}

好的，qsort()是来自外部库的函数，但我认为即使LTO也无济于事，对吧？

但是，如果我my_qsort()在同一个编译单元中定义，那么编译器是否可以内联？

int cmp(void* pa, void* pb) { /*...*/ }
void my_qsort(int* vec, int n, int sz, (void*)(void*,void*)) { /* ... */ }
int func() {
  int vec[1000];
  my_qsort(vec, 1000, sizeof(int), &cmp);
}

这有什么区别吗？我认为使用C 函数指针作为回调是阻止编译器内联的因素。正确的？

（我只是想确保我理解为什么我应该在 C++ 中使用Functor ）

4

3 回答 3

7

不，这是不可能的，至少按照传统工具链的工作方式是不可能的。传统的操作顺序是所有编译完成，然后链接完成。

要生成内联比较函数，编译器首先必须为qsort自己内联生成代码（因为每个实例qsort通常会使用不同的比较函数）。然而，在类似的情况下qsort，它通常在您开始考虑编写代码之前就已经编译并放置在标准库中。当你编译你的代码时，qsort它只能作为一个目标文件使用。

因此，为了有机会做这样的事情，您需要将内联功能构建到链接器而不是编译器中。至少在理论上这是可能的，但这绝对不是微不足道的——至少在我的估计中，它几乎肯定比使用源代码时更困难。它还需要在链接器中复制相当多的类似编译器的功能，并且可能需要将大量额外信息添加到目标文件中，以便为链接器提供足够的信息来处理它甚至可以尝试完成这项工作。

编辑：也许我应该更详细地说，以免评论链变成一个完全成熟的论点，而不仅仅是措辞。

传统上，链接器基本上是一种相当简单的野兽。它从一个可以分为四个主要内容的目标文件开始：

  1. 要从目标文件复制（不变，除非特别指示）到正在生成的可执行文件的位集合。
  2. 目标文件包含的符号列表。
  3. 对象文件未提供的符号列表。
  4. 需要写入地址的修正列表。

然后链接器开始匹配在一个文件中导出并在另一个文件中使用的符号。然后它在库（或库）中查找目标文件以解析更多符号。每当它添加到文件中时，它也会添加所需符号的列表，并递归搜索可以满足这些要求的其他目标文件。

当它找到提供所有符号的目标文件时，它将每个位的集合复制到输出文件中，并且在修复记录告诉它的地方，它写入分配给特定符号的相对地址（例如，你在哪里调用printf后，它会计算出它在可执行文件中复制组成的位的位置printf，并使用该地址填写您的调用）。在最近的案例中，它可以将共享对象/DLL的引用嵌入到可执行文件中，而不是从库中复制位，并将其留给加载器在运行时实际查找/加载该文件以提供实际代码一个符号。

然而，特别是，链接器传统上忽略了它正在复制的位块的实际内容。您可以（例如）相当合理地使用完全相同的链接器来处理许多不同处理器中的任何一个的代码。只要它们都使用相同的对象和可执行文件格式，就可以了。

链接时间优化确实在一定程度上改变了这一点。显然，为了优化代码，我们需要某种额外的智能，这种智能发生在传统上认为的链接时间。有（至少）两种方法可以做到这一点：

  1. 在链接器中构建了相当多的额外智能
  2. 将智能保留在编译器中，并让链接器调用它来进行优化。

两者都有例子——LLVM（一个明显的例子）几乎采用了前者。前端编译器发出 LLVM 代码，LLVM 将大量智能/工作用于将其转换为优化的可执行文件。带有 GIMPLE 的 gcc 采用后一种方法：GIMPLE 记录基本上为链接器提供了足够的信息，它可以将许多目标文件中的位反馈给编译器，让编译器对其进行优化，然后将结果反馈给链接器实际上复制到可执行文件中。

我想你可能会提出某种哲学观点，说这两者基本上是等价的——但我有点怀疑任何实现了这两者的人都会同意。

现在，确实（可能无论如何）其中任何一个都足以实现手头的优化。就个人而言，我怀疑是否有人为了自己的利益而实施这种优化。当您开始使用它时，它qsort几乎bsearch是它通常会/将适用的仅有的两个相当常见的功能。对于大多数实际目的，这意味着您将专门为了qsort.

另一方面，如果所涉及的工具包括生成内联函数和链接时间优化的能力，那么我认为至少有一个合理的机会，您最终可能会以或多或少的意外方式发生这种特定类型的优化 -两者结合在一起的效果。

至少在理论上，这意味着它可能发生。不过还有一个问题需要考虑：完全独立于手头的优化，许多编译器不会为递归函数生成内联代码。为了尝试这样做，编译器必须首先将递归函数转换为迭代形式。这在尾递归的情况下相当普遍——但快速排序不是尾递归。几乎唯一的选择是一qsort开始就不是递归的实现。这当然是可能的，但同样肯定是相当不寻常的。

因此，即使/如果工具链可以支持回调的内联生成，它也可能不会在这种情况下qsort（我承认，这是我个人测试过的唯一情况）。然而，无论好坏，qsort这几乎是这类函数中唯一一个足够常见的函数，它也很重要。

于 2011-03-13T17:13:35.553 回答
4

是的，有内联回调的编译器。GCC 绝对可以为在同一编译单元中定义的函数执行此操作，并且可能在使用 LTO 时执行此操作（我没有验证，但原则上没有什么可以阻止这种优化）。

但是，这是否可能qsort()是您的标准库的实现细节：任何标准库函数都可以作为inline函数提供——事实上，它们实际上可能被类似函数的宏所掩盖——因此编译器可以自由地如果是这种情况，则生成一个内联调用比较函数的专用版本。

于 2011-03-14T10:12:11.660 回答
1

您所说的情况是您应该在 C++ 中使用函子而不是函数指针的多个原因之一。

编译器是否能够内联带有回调的函数是相当复杂的，并且通常取决于各种情况。

在您的一些简单示例中，编译器肯定可以内联调用，因为它能够确定将调用哪个函数。在其他程序中，要调用的函数可能取决于某些运行时参数，可能存在编译器无法检测到的别名以及优化器使用的任何黑魔法。

于 2011-03-13T16:36:20.253 回答