如何确定最快的链接顺序？

Question

我有大约50个不同的静态库链接到我的C++项目中，平均链接时间为70秒。

我发现改变库的链接顺序会改变这个时间。如果链接器不必在它建立的整个符号表中搜索一组符号，那么我想这是可以预料的。

我想我可以使用"nm"获取静态库之间的依赖关系图。然而，这只会给我一个"正确"的链接顺序。获取最快链接顺序所涉及的因素是什么？

我感觉这可能与上述的依赖关系图有关，通过获取尝试最小化某些数量的遍历路径，但我真的不确定是哪种数量。

任何帮助都将不胜感激。

我主要使用英特尔编译器，偶尔也使用gcc编译器。当我用 top 检查时，它们似乎都在使用GNU ld 链接器。希望这有所帮助...

因此，为了更加明确我的问题，我已经知道如何从一组静态库获取1-pass顺序。我自己编写了这个脚本，但正如Olaf下面的答案所建议的那样，有已知的工具可以做到这一点。

我的问题是，我已经有了两个1-pass链接顺序，其中一个运行时间约为85秒，另一个运行时间约为70秒。因此，显然我们仍然可以在1-pass顺序中进行更多的优化。

- owagh

---

可能是符号/未解决符号列表，但这更像是一种猜测而不是知识。顺便提一下：您必须说明您感兴趣的链接器，因为不同的链接器具有完全不同的行为（例如，IBM会多次迭代库列表，直到解决所有问题或取得进展）。 - David Rodríguez - dribeas

只是一个大致的想法：编写一个脚本来对库的所有可能顺序进行排列，并在程序中以编程方式测量链接时间。 - πάντα ῥεῖ

@g-makulik，我有提到过我有大约50个库，链接时间为约70秒吗？ - owagh

@owagh 我需要更正一下：根据 lorder 手册所说，它应该给出最快的链接顺序。也许你可以在你的系统上找到这个工具的版本。 - πάντα ῥεῖ

完全没有关系的建议，假设你不仅是出于兴趣而且也是为了赚钱：将工作磁盘更换成固态硬盘。这应该比调整链接顺序花费的时间更能加速链接过程... - hyde

Answer 1

作为一种替代方案，不妨将您的库编译成共享库而不是静态库？

在我工作的地方，一个大型项目链接时间约为6分钟，这仅涉及5个库！

我的解决方案（针对调试版本）是按字母顺序创建.so文件（libA.so、libB.so等），以便每个单独的链接不会太长，并且最终链接要短得多，因为所有的(部分)链接都已经完成。发布版本是按照传统方式构建的，因为我的新方法存在所谓的“危险”。

使用这种方法，我成功将1个模块的编译/链接周期从6分钟缩短至10秒。

- Neil

Answer 2

过去，静态库中对象的顺序很重要。您可以使用以下命令按顺序排序对象：

$ lorder *.o | tsort

也许您可以对主要对象和库执行相同操作，例如 lorder main.o test.o libsome.a libthing.a | tsort.请参阅 lorder手册。

- Olaf Dietsche

---

那听起来像是一个有趣的工具，但我没有安装它。你能告诉我拥有它的软件包吗？ - owagh

谢谢！此外，似乎lorder只提供了部分有序图，所以我想它只相当于我自己编写的生成此信息的脚本。这只会给我们一个“正确”的总顺序，但不一定是最快的总顺序。 - owagh

@owagh 该手册表示它将库文件排序到最佳位置，以便在链接时可以一次性加载符号。 - πάντα ῥεῖ

正如man页面本身所建议的那样，可能会有多个这样的1-pass排序。我已经有了两个1-pass排序（这就是我所说的“正确”），其中一个链接在90年代，另一个链接在70年代。 - owagh

在Debian中删除的原因是：FreeBSD已经淘汰了lorder(1)：https://reviews.freebsd.org/D26044 - alx - recommends codidact

Answer 3

根据将ld与黄金比较的信息，符号表的大小会影响ld的速度。随着处理目标文件时符号表的增长，链接步骤会变得越来越慢。因此，如果您有两个不同的一遍链接顺序，将具有更多符号需要修正的库放在该顺序中后面的那个应该链接得更快。您应该能够修改拓扑排序以包括符号计数在排序标准中。

- MSN

Answer 4

你提到了一种基于对象和库的顺序的一次性排序，但是如果它在静态库中搜索，它不能保证静态库中的任何内容都会以特定的顺序出现，实际上你只能通过在ar时对静态库进行特定方式的排序来控制它。

此外，如果不了解链接器如何使用静态库，那么可以做出以下两个最佳假设：

1.它创建一个符号哈希表，引用提供或需要它们的对象；如果这是一个准确的假设，那么你可以得到关于静态库最优下限的最佳估计时间，即填充这样一个哈希表并从中读取所需的时间。

2.它根据存档索引中给定的顺序盲目读取存档。

为寻找最优链接时间的下限，你可以尝试将所有或部分存档文件中的对象连接成可重定位对象。对于这些子集，如果可能，应该识别实际链接的所有对象。 lorder的man页面指出你可以通过ar ts <archive>获得相同的结果...它将为你打印已排序的列表。 ar的man页面似乎表明，使用s标志运行ar将自动将最优顺序存储在存档索引中。

此外，请注意可能存在循环依赖，但如果你已经使用过tsort，那么应该已经意识到了这一点。

最后，我会留下最后一条信息。你想要的是可以解决NP完全问题的东西。祝你好运。

---

我最近为我的一个构建项目进行了一些时间测试; 我已经在我的ARFLAGS中添加了s标志，以查看它的影响。

总体而言，它似乎增加了我的构建时间，但我相信有一个逻辑上的解释：

大多数可执行文件/共享对象不使用静态链接

正在构建每个静态库的PIC和非PIC版本

如果我们更大量地使用静态库，我们可能会从中获益。

- Brian Vandenberg

---

我已经很久没有访问这个问题了... 无论如何，你所说的“大多数可执行文件不使用静态链接”是什么意思？你是指特定的可执行文件吗？ - owagh

是的，我们构建的大多数可执行文件都专门链接到动态库。 - Brian Vandenberg