30

我需要在我的一些代码中使用对数函数，但底数并不重要。因此，如果我发现任何显着差异，我开始在 、 和 性能log()之间log2()进行选择。log10()（我将把所说的函数分别称为ln、lb和lg）。

我为什么要为此大惊小怪？因为我将在优化算法的每次迭代中调用该函数多达 400,000,000 次。这既不是可选的，也不是我问题的主题。

我设置了一些非常基本的测试，如下所示：

timespec start, end;
double sum = 0, m;

clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
for (int n = 1; n < INT_MAX; ++n)
{
    m = n * 10.1;
    sum += log(m);
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

cout << "ln=";
cout << diff(start, end).tv_sec << ":" << diff(start, end).tv_nsec << endl;

... // likewise for log2 and log10

（timespec diff(timespec start, timespec end)如果您愿意的话....）

获得了以下结果：

GCC v4.6.3

-O0
ln=140:516853107
lb=155:878100147
lg=173:534086352

-O1
ln=133:948317112
lb=144:78885393
lg=163:870021712

-O2
ln=9:108117039
lb=9:134447209
lg=4:87951676

-O3
ln=9:102016996
lb=9:204672042
lg=4:153153558

我已经查看了 compile 的输出-S，但我对汇编程序的掌握还不够好，无法完全理解这些差异。-S输出：-O0 -S , -O3 -S

为什么lg使用 O2/O3 可以更好地优化？

编辑：源代码，注意第三个循环中的错字，这是 log10 看起来更快的原因（多。得到优化）。我已经接受了我认为最接近的答案，因为这个问题现在已经结束，尽管我从 drhirsch 和 janneb 的答案中学到了很多东西。

4

4 回答 4

6

这将取决于 C 库中 log() 函数的实现、编译器版本、硬件架构等。无论如何，下面我在 x86-64 上使用 GCC 4.4 和 glibc 2.11。

更改示例以便我添加一行

cout << "sum=" << sum << endl;

这会阻止编译器优化 log() 调用，正如我在评论中提到的，我得到以下时间（仅整秒，-O2）：

  • 日志：98s
  • 日志2：105s
  • log10：120s

这些时间似乎与原帖中的 -O0 和 -O1 时间大致一致；在更高的优化级别，日志评估被优化掉，因此 -O2 和 -O3 结果是如此不同。

此外，查看带有“perf”分析器的日志示例，报告中排名前 5 的违规者是


# Samples: 3259205
#
# Overhead         Command              Shared Object  Symbol
# ........  ..............  .........................  ......
#
    87.96%             log  /lib/libm-2.11.1.so        [.] __ieee754_log
     5.51%             log  /lib/libm-2.11.1.so        [.] __log
     2.88%             log  ./log                      [.] main
     2.84%             log  /lib/libm-2.11.1.so        [.] __isnan
     0.69%             log  ./log                      [.] log@plt

除 main 之外，所有其他符号都与 log() 调用有关。总结这些，我们可以得出结论，这个例子总运行时间的 97% 都花在了 log() 中。

__ieee754_log 的实现可以在 glibc git repo中找到。相应地，其他实现是：log2，log10。请注意，之前的链接指向 HEAD 版本，对于已发布的版本，请参阅其相应的分支

于 2012-05-30T08:09:39.237 回答
5

不幸的是，OP 未能向我们展示原始代码，他选择将代码稍微混淆，将其转换为汇编。

在汇编代码中，OP 链接（我的注释）：

.L10:
    cvtsi2sd %ebx, %xmm0         // convert i to double
    xorpd    %xmm1, %xmm1        // zero 
    mulsd    .LC0(%rip), %xmm0   // multiply i with 10.1
    ucomisd   %xmm0, %xmm1       // compare with zero
    jae       .L31               // always below, never jump

    addl    $1, %ebx             // i++
    cmpl    $2147483647, %ebx    // end of for loop
    jne     .L10
    ...
.L31:
    call    log10, log2, whatever...  // this point is never reached

可以看到调用log永远不会被执行，特别是如果你使用 gdb 单步执行它。所有代码都是 2 31次乘法和双精度比较。

这也解释了使用 编译时 log 函数的执行速度惊人地提高了 30 倍-O2，以防有人也发现这很奇怪。

编辑：

for (int n = 1; n < INT_MAX; ++n)
{
    m = n * 10.1;
    sum += log(m);
}

编译器无法完全优化循环，因为她无法证明调用log将始终成功 - 如果参数为负，它会产生副作用。因此，她通过与零的比较来替换循环 -log只有在乘法的结果小于或小于零时才执行。这意味着它永远不会被执行:-)

留在循环中的是乘法和测试，如果结果可能是否定的。

如果我添加-ffast-math到编译器选项，会产生一个有趣的结果，这使编译器从严格的 IEEE 合规性中解脱出来：

ln=0:000000944
lb=0:000000475
lg=0:000000357
于 2012-05-30T12:35:46.737 回答
4

我注意到了一些事情。如果我编译（GCC 4.5.3）你的汇编程序列表-O3 -S，g++ logflt.S -lrt我可以重现该行为。我的时间是：

ln=6:984160044
lb=6:950842852
lg=3:64288522

然后我用 . 检查了输出objdump -SC a.out。我更喜欢这个而不是查看.S文件，因为有些结构我（还）不理解。代码不是很容易阅读，但我发现以下内容：

在调用log或log2使用转换参数之前

400900:       f2 0f 2a c3             cvtsi2sd %ebx,%xmm0
400904:       66 0f 57 c9             xorpd  %xmm1,%xmm1
400908:       f2 0f 59 05 60 04 00    mulsd  0x460(%rip),%xmm0
40090f:       00 
400910:       66 0f 2e c8             ucomisd %xmm0,%xmm1

0x460(%rip)是一个指向 hex-value 的相对地址0000 00000000 33333333 33332440。这是一个 16 字节的 SSEdouble对，其中只有一个双精度是重要的（代码使用标量 SSE）。这双是10.1. mulsd因此在 C++ 行中执行乘法m = n * 10.1;。

log10是不同的：

400a40:       f2 0f 2a c3             cvtsi2sd %ebx,%xmm0
400a44:       66 0f 57 c9             xorpd  %xmm1,%xmm1
400a48:       66 0f 2e c8             ucomisd %xmm0,%xmm1

我认为对于log10您忘记执行乘法的情况！所以你只是log10一次又一次地用相同的值调用...如果cpu足够聪明来优化它，我不会感到惊讶。

编辑：我现在非常确定这是问题所在，因为在您的其他清单 ( -O0 -S) 中正确执行了乘法 - 所以请发布您的代码并让其他人证明我错了！

EDIT2：GCC可以摆脱这种乘法的一种方法是使用以下标识：

log(n * 10.1) = log(n) + log(10.1)

但在那种情况下log(10.1)，必须计算一次，我看不到这个代码。我也怀疑 GCC 是否会为and这样做，log10但不会这样做。loglog2

于 2012-05-30T08:20:08.600 回答
3

您正在错误地处理问题并且正在得出结论。

使用时钟不足以进行分析。使用体面的分析器而不是时钟（gprof 或 AQTime7）。Profiler 必须能够提供每行时间。您的问题是您假设瓶颈在于日志功能。然而，整数到浮点数的转换并不是很快，也可能是一个瓶颈。另一件事是 gcc 带有您可以阅读的源代码。

现在，假设瓶颈实际上存在于日志函数中：

正如您应该知道的那样，双打的精度有限——只有 15..17 位十进制数字。这意味着使用较大的对数基数，您将更快地达到精度限制时的情况。

即10^(log10(2^32) + 10^-15) - 2^32== 9.8895 * 10^-6，但是2^(log2(2^32) + 10^-15) - 2^32==2.977 * 10^-6和100^(log100(2^32) + 10^-15) - 2^32== 0.00001977，也log2(INT_MAX) > log10(INT_MAX)意味着对数基数较大，如果对数函数试图“搜索”正确的结果，它会很快遇到由于四舍五入而无法修改预测结果的情况关闭错误。然而，这仍然只是一个猜测。

还有其他计算对数的方法。例如，log10(x) == ln(x)/ln(10)如果对数函数以这种方式计算，您将得到几乎相似的时间。

我的建议是（停止浪费时间）用时钟功能以外的东西来分析你的程序（重新发明轮子是个坏主意，不使用现有的分析工具就是重新发明轮子，加上一个好的分析器将能够提供 per-日志函数中的行计时），读取日志函数的 gcc 源代码（毕竟它是可用的）和汇编输出。如果您不了解汇编输出，这将是学习如何阅读它的好机会。

如果拥有更快的对数函数真的很重要，并且算法优化真的是不可能的（如果对数真的是一个瓶颈，你可以缓存结果，例如）你可以尝试找到更快的算法实现，但如果我是你在这种情况下，我只是尝试将硬件放在问题上——例如，通过并行化任务。

于 2012-05-30T07:37:23.140 回答