109

我有大量的函数，总计大约 2.8 GB 的目标代码（不幸的是，没有办法，科学计算......）

当我尝试链接它们时，我得到（预期的）relocation truncated to fit: R_X86_64_32S错误，我希望通过指定编译器标志来规避这些错误-mcmodel=medium。除了我可以控制之外，所有链接的库都使用该-fpic标志编译。

尽管如此，错误仍然存​​在，我假设我链接到的一些库不是用 PIC 编译的。

这是错误：

/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/crt1.o: In function `_start':
(.text+0x12): relocation truncated to fit: R_X86_64_32S against symbol `__libc_csu_fini'     defined in .text section in /usr/lib64/libc_nonshared.a(elf-init.oS)
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/crt1.o: In function `_start':
(.text+0x19): relocation truncated to fit: R_X86_64_32S against symbol `__libc_csu_init'    defined in .text section in /usr/lib64/libc_nonshared.a(elf-init.oS)
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/crt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/../../../../lib64/crti.o: In function    `call_gmon_start':
(.text+0x7): relocation truncated to fit: R_X86_64_GOTPCREL against undefined symbol      `__gmon_start__'
/usr/lib/gcc/x86_64-redhat-linux/4.1.2/crtbegin.o: In function `__do_global_dtors_aux':
crtstuff.c:(.text+0xb): relocation truncated to fit: R_X86_64_PC32 against `.bss' 
crtstuff.c:(.text+0x13): relocation truncated to fit: R_X86_64_32 against symbol `__DTOR_END__' defined in .dtors section in /usr/lib/gcc/x86_64-redhat-linux/4.1.2/crtend.o
crtstuff.c:(.text+0x19): relocation truncated to fit: R_X86_64_32S against `.dtors'
crtstuff.c:(.text+0x28): relocation truncated to fit: R_X86_64_PC32 against `.bss'
crtstuff.c:(.text+0x38): relocation truncated to fit: R_X86_64_PC32 against `.bss'
crtstuff.c:(.text+0x3f): relocation truncated to fit: R_X86_64_32S against `.dtors'
crtstuff.c:(.text+0x46): relocation truncated to fit: R_X86_64_PC32 against `.bss'
crtstuff.c:(.text+0x51): additional relocation overflows omitted from the output
collect2: ld returned 1 exit status
make: *** [testsme] Error 1

我链接的系统库：

-lgfortran -lm -lrt -lpthread

在哪里寻找问题的任何线索？

编辑：

首先谢谢大家的讨论。。。

为了澄清一点，我有数百个函数（在单独的目标文件中每个大小约为 1 MB），如下所示：

double func1(std::tr1::unordered_map<int, double> & csc, 
             std::vector<EvaluationNode::Ptr> & ti, 
             ProcessVars & s)
{
    double sum, prefactor, expr;

    prefactor = +s.ds8*s.ds10*ti[0]->value();
    expr =       ( - 5/243.*(s.x14*s.x15*csc[49300] + 9/10.*s.x14*s.x15*csc[49301] +
           1/10.*s.x14*s.x15*csc[49302] - 3/5.*s.x14*s.x15*csc[49303] -
           27/10.*s.x14*s.x15*csc[49304] + 12/5.*s.x14*s.x15*csc[49305] -
           3/10.*s.x14*s.x15*csc[49306] - 4/5.*s.x14*s.x15*csc[49307] +
           21/10.*s.x14*s.x15*csc[49308] + 1/10.*s.x14*s.x15*csc[49309] -
           s.x14*s.x15*csc[51370] - 9/10.*s.x14*s.x15*csc[51371] -
           1/10.*s.x14*s.x15*csc[51372] + 3/5.*s.x14*s.x15*csc[51373] +
           27/10.*s.x14*s.x15*csc[51374] - 12/5.*s.x14*s.x15*csc[51375] +
           3/10.*s.x14*s.x15*csc[51376] + 4/5.*s.x14*s.x15*csc[51377] -
           21/10.*s.x14*s.x15*csc[51378] - 1/10.*s.x14*s.x15*csc[51379] -
           2*s.x14*s.x15*csc[55100] - 9/5.*s.x14*s.x15*csc[55101] -
           1/5.*s.x14*s.x15*csc[55102] + 6/5.*s.x14*s.x15*csc[55103] +
           27/5.*s.x14*s.x15*csc[55104] - 24/5.*s.x14*s.x15*csc[55105] +
           3/5.*s.x14*s.x15*csc[55106] + 8/5.*s.x14*s.x15*csc[55107] -
           21/5.*s.x14*s.x15*csc[55108] - 1/5.*s.x14*s.x15*csc[55109] -
           2*s.x14*s.x15*csc[55170] - 9/5.*s.x14*s.x15*csc[55171] -
           1/5.*s.x14*s.x15*csc[55172] + 6/5.*s.x14*s.x15*csc[55173] +
           27/5.*s.x14*s.x15*csc[55174] - 24/5.*s.x14*s.x15*csc[55175] +
           // ...
           ;

        sum += prefactor*expr;
    // ...
    return sum;
}

该对象s相对较小，并保留所需的常量 x14、x15、...、ds0、...等，同时ti仅从外部库返回一个 double。如您所见，csc[]它是一个预先计算的值映射，它也在以下形式的单独对象文件中进行评估（同样数百个，每个大约 1 MB 大小）：

void cscs132(std::tr1::unordered_map<int,double> & csc, ProcessVars & s)
{
    {
    double csc19295 =       + s.ds0*s.ds1*s.ds2 * ( -
           32*s.x12pow2*s.x15*s.x34*s.mbpow2*s.mWpowinv2 -
           32*s.x12pow2*s.x15*s.x35*s.mbpow2*s.mWpowinv2 -
           32*s.x12pow2*s.x15*s.x35*s.x45*s.mWpowinv2 -
           32*s.x12pow2*s.x25*s.x34*s.mbpow2*s.mWpowinv2 -
           32*s.x12pow2*s.x25*s.x35*s.mbpow2*s.mWpowinv2 -
           32*s.x12pow2*s.x25*s.x35*s.x45*s.mWpowinv2 +
           32*s.x12pow2*s.x34*s.mbpow4*s.mWpowinv2 +
           32*s.x12pow2*s.x34*s.x35*s.mbpow2*s.mWpowinv2 +
           32*s.x12pow2*s.x34*s.x45*s.mbpow2*s.mWpowinv2 +
           32*s.x12pow2*s.x35*s.mbpow4*s.mWpowinv2 +
           32*s.x12pow2*s.x35pow2*s.mbpow2*s.mWpowinv2 +
           32*s.x12pow2*s.x35pow2*s.x45*s.mWpowinv2 +
           64*s.x12pow2*s.x35*s.x45*s.mbpow2*s.mWpowinv2 +
           32*s.x12pow2*s.x35*s.x45pow2*s.mWpowinv2 -
           64*s.x12*s.p1p3*s.x15*s.mbpow4*s.mWpowinv2 +
           64*s.x12*s.p1p3*s.x15pow2*s.mbpow2*s.mWpowinv2 +
           96*s.x12*s.p1p3*s.x15*s.x25*s.mbpow2*s.mWpowinv2 -
           64*s.x12*s.p1p3*s.x15*s.x35*s.mbpow2*s.mWpowinv2 -
           64*s.x12*s.p1p3*s.x15*s.x45*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.p1p3*s.x25*s.mbpow4*s.mWpowinv2 +
           32*s.x12*s.p1p3*s.x25pow2*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.p1p3*s.x25*s.x35*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.p1p3*s.x25*s.x45*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.p1p3*s.x45*s.mbpow2 +
           64*s.x12*s.x14*s.x15pow2*s.x35*s.mWpowinv2 +
           96*s.x12*s.x14*s.x15*s.x25*s.x35*s.mWpowinv2 +
           32*s.x12*s.x14*s.x15*s.x34*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.x14*s.x15*s.x35*s.mbpow2*s.mWpowinv2 -
           64*s.x12*s.x14*s.x15*s.x35pow2*s.mWpowinv2 -
           32*s.x12*s.x14*s.x15*s.x35*s.x45*s.mWpowinv2 +
           32*s.x12*s.x14*s.x25pow2*s.x35*s.mWpowinv2 +
           32*s.x12*s.x14*s.x25*s.x34*s.mbpow2*s.mWpowinv2 -
           32*s.x12*s.x14*s.x25*s.x35pow2*s.mWpowinv2 -
           // ...
    
       csc.insert(cscMap::value_type(192953, csc19295));
    }

    {
       double csc19296 =      // ... ;

       csc.insert(cscMap::value_type(192956, csc19296));
    }

    // ...
}

就是这样。最后一步只是调用所有这些func[i]并总结结果。

关于这是一个相当特殊和不寻常的情况：是的。这是人们在尝试对粒子物理进行高精度计算时必须应对的问题。

编辑2：

我还应该补充一点，x12、x13 等并不是真正的常数。它们被设置为特定值，运行所有这些函数并返回结果，然后选择一组新的 x12、x13 等来生成下一个值。这必须做 10 5到 10 6次...

编辑3：

感谢您到目前为止的建议和讨论......我会尝试以某种方式在代码生成时滚动循环，说实话，不确定如何做到这一点，但这是最好的选择。

顺便说一句，我并没有试图隐藏“这是科学计算——无法优化”。
只是这段代码的基础是来自一个“黑匣子”的东西，我无法真正访问，而且，整个事情在简单的例子中效果很好，我主要对现实中发生的事情感到不知所措世界应用...

编辑4：

csc因此，通过简化计算机代数系统 ( Mathematica )中的表达式，我设法将定义的代码大小减少了大约四分之一。我现在还看到了一些方法，通过在生成代码之前应用一些其他技巧（这将使这部分减少到大约 100 MB），将它减少另一个数量级左右，我希望这个想法有效。

现在与您的答案有关：

我试图在 s 中再次将循环回滚func，CAS 不会有太大帮助，但我已经有了一些想法。例如，按变量对表达式进行排序，用 Pythonx12, x13,...解析cscs 并生成将它们相互关联的表。然后我至少可以将这些部分生成为循环。由于这似乎是迄今为止最好的解决方案，我将其标记为最佳答案。

但是，我也想感谢 VJo。GCC 4.6 确实工作得更好，生成的代码更小并且速度更快。使用大型模型按原样处理代码。所以从技术上讲，这是正确的答案，但改变整个概念是一种更好的方法。

谢谢大家的建议和帮助。如果有人感兴趣，我会在准备好后立即发布最终结果。

评论：

只是对其他一些答案的一些评论：我试图运行的代码并不是源于简单函数/算法的扩展和愚蠢的不必要的展开。实际发生的是，我们开始的东西是非常复杂的数学对象，将它们转化为可数值计算的形式会生成这些表达式。问题实际上在于潜在的物理理论。中间表达式的复杂性是众所周知的，但是当将所有这些东西组合成物理上可测量的东西——一个可观察的——时，它只是归结为只有少数非常小的函数构成了表达式的基础。（在这方面，通用且唯一可用的ansatz肯定存在“错误”这被称为“微扰理论”）我们试图将这个 ansatz 带到另一个层次，这在分析上不再可行，并且所需函数的基础是未知的。所以我们尝试像这样暴力破解它。不是最好的方法，但希望能帮助我们最终理解手头的物理学……

最后编辑：

感谢您的所有建议，我已经设法大大减少了代码大小，使用 Mathematica 并修改了funcs 的代码生成器，有点类似于最佳答案:)

我已经csc使用 Mathematica 简化了函数，将其缩小到 92 MB。这是不可约的部分。第一次尝试花了很长时间，但经过一些优化后，现在在单个 CPU 上运行大约 10 分钟。

对funcs 的影响是巨大的：它们的整个代码大小降低到大约 9 MB，因此现在代码总计在 100 MB 范围内。现在打开优化是有意义的，并且执行速度非常快。

再次感谢大家的建议，我学到了很多。

4

11 回答 11

53

因此，您已经有一个生成此文本的程序：

prefactor = +s.ds8*s.ds10*ti[0]->value();
expr = ( - 5/243.*(s.x14*s.x15*csc[49300] + 9/10.*s.x14*s.x15*csc[49301] +
       1/10.*s.x14*s.x15*csc[49302] - 3/5.*s.x14*s.x15*csc[49303] -...

和

double csc19295 =       + s.ds0*s.ds1*s.ds2 * ( -
       32*s.x12pow2*s.x15*s.x34*s.mbpow2*s.mWpowinv2 -
       32*s.x12pow2*s.x15*s.x35*s.mbpow2*s.mWpowinv2 -
       32*s.x12pow2*s.x15*s.x35*s.x45*s.mWpowinv2 -...

正确的？

如果您所有的函数都具有相似的“格式”（将 n 数字相乘 m 次并添加结果 - 或类似的东西），那么我认为您可以这样做：

  • 将生成器程序更改为输出偏移量而不是字符串（即，而不是字符串“s.ds0”，它将产生offsetof(ProcessVars, ds0)
  • 创建一个这样的偏移量数组
  • 编写一个求值器，它接受上面的数组和结构指针的基地址并产生结果

数组+求值器将表示与您的函数之一相同的逻辑，但只有求值器是代码。该数组是“数据”，可以在运行时生成或保存在磁盘上并读取 i 块或使用内存映射文件。

对于您在 func1 中的特定示例，想象一下，如果您可以访问 的基地址s和的基地址，以及csc您需要添加到基地址以达到的常量和偏移量的向量表示，您将如何通过评估器重写函数x14，ds8和csc[51370]

您需要创建一种新形式的“数据”来描述如何处理您传递给大量函数的实际数据。

于 2011-06-09T22:16:15.353 回答
46

Linux 使用的x86-64 ABI定义了一个“大型模型”，专门用于避免此类大小限制，其中包括 GOT 和 PLT 的 64 位重定位类型。（参见第 4.4.2 节中的表格，以及 3.5.5 中的指令序列，它们显示了它们是如何使用的。）

由于您的函数占用 2.8 GB，因此您很不走运，因为 gcc 不支持大型模型。您可以做的是以允许您将其拆分为您将动态链接的共享库的方式重新组织您的代码。

如果这不可能，正如有人建议的那样，不要将数据放入代码中（编译和链接它），因为它很大，你可以在运行时加载它（作为普通文件，或者你可以映射它）。

编辑

似乎 gcc 4.6 支持大型模型（请参阅此页面）。您可以尝试这样做，但上述内容仍然适用于重新组织您的代码。

于 2011-06-09T18:47:07.340 回答
37

对于这一方的程序，代码的缓存未命中很可能超过运行时循环的成本。我建议你回到你的代码生成器，让它为它想要评估的内容生成一些紧凑的表示（即，一个可能适合 D-cache 的表示），然后在你的程序中使用解释器执行它。您还可以查看是否可以分解出仍然具有大量操作的较小内核，然后将它们用作解释代码中的“指令”。

于 2011-06-09T22:06:46.277 回答
21

发生错误是因为您有太多的代码，而不是数据！这通过例如__libc_csu_fini（这是一个函数）被引用来表示_start，并且重定位被截断以适应。这意味着_start（程序的真正入口点）正试图通过一个 SIGNED 32 位偏移量调用该函数，该偏移量只有 2 GB 的范围。由于您的目标代码总量约为 2.8 GB，事实证明。

如果您可以重新设计数据结构，则可以通过将巨大的表达式重写为简单的循环来“压缩”您的大部分代码。

此外，您可以csc[]在不同的程序中计算，将结果存储在文件中，并在必要时加载它们。

于 2011-06-09T19:33:47.457 回答
15

我想每个人都同意应该有不同的方式来做你想做的事。编译数百兆字节（千兆字节？）的代码，将其链接成数千兆字节大小的可执行文件并运行它听起来效率非常低。

如果我正确理解您的问题，您可以使用某种代码生成器 G 来生成一堆函数func1...N，这些函数将一堆地图csc1...M作为输入。您要做的是计算csc1...M，并为不同的输入运行 1,000,000 次循环，每次 find s = func1 + func2 + ... + funcN。您没有指定如何fucn1...N相关csc1...M。

如果这一切都是真的，那么您似乎应该能够以不同的方式解决问题，这可能更易于管理，甚至可能更快（即让您的机器的缓存实际运行）。

除了目标文件大小的实际问题之外，您当前的程序效率不高，因为它没有本地化对数据的访问（太多巨大的地图）并且没有本地化代码执行（太多非常长的函数）。

如何将您的程序分成 3 个阶段：第 1 阶段构建csc1...M和存储它们。第 2 阶段一次构建一个func，对每个输入运行 1,000,000 次并存储结果。func1...N第 3 阶段求每次运行 1,000,000 次的存储结果的结果总和。这个解决方案的好处是它可以很容易地在多台独立的机器上并行。

编辑：@bbtrb，你可以让一个 func 和一个 csc 可用吗？它们似乎是高度规则和可压缩的。例如，func1 似乎只是表达式的总和，每个表达式由 1 个系数、2 个 s 中的变量索引和 1 个 csc 索引组成。所以它可以简化为一个很好的循环。如果您提供完整的示例，我相信可以找到将它们压缩成循环而不是长表达式的方法。

于 2011-06-10T02:04:07.033 回答
5

如果我正确阅读了您的错误，那么使您超出限制的是初始化的数据部分（如果是代码，恕我直言，您会有更多错误）。你有大量的全球数据吗？如果是这种情况，我会重组程序以便动态分配它们。如果数据已初始化，我会从配置文件中读取它。

顺便说一句，看到这个：

(.text+0x20): 未定义的对“main”的引用

我认为你还有另一个问题。

于 2011-06-09T18:47:51.670 回答
3

在我看来，代码正在使用某种自适应深度方法进行数值积分。不幸的是，代码生成器（或者更确切地说是代码生成器的作者）非常愚蠢，以至于每个补丁生成一个函数而不是每种类型的补丁一个函数。因此，它产生了太多需要编译的代码，即使它可以被编译，它的执行也会很痛苦，因为从来没有在任何地方共享过任何东西。（你能想象不得不从磁盘加载每一页目标代码所带来的痛苦吗，因为没有任何东西是共享的，所以它总是被操作系统驱逐的候选者。更不用说指令缓存了，这将是无用的。）

解决方法是停止展开所有内容；对于此类代码，您希望最大化共享，因为以更复杂的模式访问数据的额外指令的开销将被处理（可能）大型基础数据集的成本所吸收。也有可能代码生成器甚至会默认执行此操作，并且科学家看到了一些展开选项（注意这些有时会提高速度）并立即将它们全部打开，现在坚持接受由此产生的混乱通过计算机，而不是接受机器的实际限制并使用默认生成的数字正确版本。但是，如果代码生成器不这样做，那就找一个可以（或破解现有代码）的代码生成器。

底线：编译和链接 2.8GB 的​​代码不起作用，不应该被迫工作。寻找另一种方式。

于 2011-06-11T07:28:55.410 回答
3

一些建议： - 优化大小 (-Os)。进行内联函数调用，普通函数调用。启用字符串池。

尝试将内容拆分为不同的 DLL（共享对象，Linux 的 .so，Mac OS X 的 .dylib）。确保它们可以被卸载。然后实现一些东西来按需加载东西，并在不需要时释放它们。

如果没有，请将您的代码拆分为不同的可执行文件，并使用某些东西在它们之间进行通信（管道、套接字，甚至写入/读取文件）。笨拙，但你有什么选择？

完全替代： - 使用带有JIT的动态语言。就在我的头上 - 使用LuaJIT - 并在Lua或其他允许代码被垃圾收集的语言和运行时重写（重新生成？）很多这些表达式。

LuaJIT 非常高效，有时在某些方面优于 C/C++，但通常非常接近（有时由于垃圾收集不佳而速度很慢）。自己检查：

http://luajit.org/performance_x86.html

从那里下载scimark2.lua文件，并将其与“C”版本（google it）进行比较——结果通常非常接近。

于 2011-06-10T00:12:47.917 回答
2

链接器试图在已超出这些限制的二进制文件中生成 32 位重定位偏移量。尝试减少主程序的地址空间要求。

您能否将部分/大部分目标代码拆分为一个或多个库（也使用 -fpic / -fPIC 编译）？然后生成一个链接到这些库的非静态二进制文件。这些库将存在于离散的内存块中，并且您的重定位偏移量将是动态/绝对的（64 位）而不是相对的（32 位）。

于 2011-06-10T11:56:36.627 回答
2

这些表情在我看来很像一个交替的系列。我不知道其余代码是什么样子的，但似乎并不难推导出生成表达式。在执行时也可能是值得的，特别是如果您有 2.8 GB 的 2 KB 展开代码。

于 2011-06-10T01:52:18.023 回答
1

这看起来像是代码生成出错的结果，可能是符号代数和/或手动展开。众所周知，符号操作在表达式树或计算图的深度呈指数增长。很可能在这里可以使用自动微分，这将使代码大小非常小，并且还可以显着加快执行速度。

于 2011-06-10T10:10:51.157 回答