是否有可能运行一个速度快得多的sqrt版本

Question

在我正在分析的一个应用程序中，我发现在某些情况下，这个函数能够占用总执行时间的10%以上。

多年来，我一直在讨论如何使用偷偷摸摸的浮点技巧来实现更快的sqrt，但我不知道这样的东西在现代CPU上是否已经过时了。

正在使用MSVC++ 2008编译器，仅供参考...尽管我假设sqrt不会增加太多开销。

有关modf函数的类似讨论，请参阅此处。

编辑:作为参考，this是一种广泛使用的方法，但它实际上要快得多吗？现在SQRT到底有多少个周期？

Answer 1

是的，即使没有诡计也是可能的：

1. 牺牲精度来换取速度: sqrt算法是迭代的，只需较少的迭代就可以重新实现。

1. 查找表:要么只是作为迭代的起始点，要么与插值相结合，让您一直到那里。

1. 缓存:您总是查询同一组有限的值吗？如果是这样的话，缓存可以很好地工作。我发现这在图形应用程序中很有用，在图形应用程序中，对许多相同大小的形状计算相同的内容，因此可以有效地缓存结果。

11年后的问候。

考虑到这仍然偶尔会得到投票，我想我应该添加一个关于性能的注释，现在更多的是内存访问的戏剧性限制。在优化这样的东西时，你绝对必须使用一个现实的基准测试(理想情况下，你的整个应用程序)--你的应用程序的内存访问模式会对像查找表和缓存这样的解决方案产生巨大的影响，仅仅比较你的优化版本的“周期”会让你误入歧途:将程序时间分配给单独的指令也是非常困难的，而且你的分析工具可能会在这里误导你。

1. 在相关的注释中，如果_mm512_sqrt_ps或类似指令适合您的用例，请考虑使用simd/向量化指令来计算平方根。

1. 看一看英特尔optimisation reference manual的15.12.3节，其中描述了近似方法，以及矢量化的指令，这可能也可以很好地翻译到其他架构。

Answer 2

这里有一个很好的对照表：http://assemblyrequired.crashworks.org/timing-square-root/

长话短说，SSE2的fsqrt大约比FPU fsqrt快2倍，近似+迭代比FPU fsqrt快4倍(总共8倍)。

此外，如果您尝试采用单精度sqrt，请确保这是您实际得到的结果。我听说过至少有一个编译器会将浮点型参数转换为双精度型，调用双精度sqrt，然后再转换回浮点型。

Answer 3

您很可能通过更改算法获得更多的速度改进，而不是通过更改它们的实现:尽量少调用sqrt()，而不是更快地调用。(如果您认为这是不可能的-您提到的对sqrt()的改进只是:对用于计算平方根的算法的改进。)

因为它经常被使用，所以很可能您的标准库的sqrt()实现对于一般情况来说几乎是最优的。除非你有一个受限制的域(例如，如果你需要更低的精度)，算法可以采取一些捷径，这是非常不可能有人提出一个更快的实现。

请注意，由于该函数占用了您执行时间的10%，即使您设法提出了一个仅占用std::sqrt()时间的75%的实现，这仍然只会使您的执行时间减少2.5%的。对于大多数应用程序，用户甚至不会注意到这一点，除非他们使用手表进行测量。