相关疑难解决方法(0)

我正在阅读Agner Fog的优化手册，并且遇到了这个例子：

double data[LEN];

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] = A*i*i + B*i + C;
    }
}

Agner 指出，有一种方法可以优化此代码 - 通过认识到循环可以避免使用昂贵的乘法，而是使用每次迭代应用的“增量”。

我用一张纸来证实这个理论，首先......

...当然，他是对的 - 在每次循环迭代中，我们可以通过添加“增量”，基于旧结果计算新结果。该增量从值“A+B”开始，然后每一步增加“2*A”。

所以我们将代码更新为如下所示：

void compute()
{
    const double A = 1.1, B = 2.2, C = 3.3;
    const double A2 = A+A;
    double Z = A+B;
    double Y = C;

    int i;
    for(i=0; i<LEN; i++) {
        data[i] …

John Carmack在Quake III源代码中有一个特殊的功能,它计算浮点的平方根,比常规的快4倍(float)(1.0/sqrt(x)),包括一个奇怪的0x5f3759df常量.请参阅下面的代码.有人可以逐行解释这里究竟发生了什么以及为什么这比常规实现快得多？

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;
  i  = 0x5f3759df - ( i >> 1 );
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) );

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) );
  #endif
  #endif …

通过编码是否有任何(非微优化)性能增益

float f1 = 200f / 2

在比较中

float f2 = 200f * 0.5

几年前我的一位教授告诉我,浮点除法比浮点乘法慢,但没有详细说明原因.

这句话适用于现代PC架构吗？

UPDATE1

关于评论,请同时考虑这个案例:

float f1;
float f2 = 2
float f3 = 3;
for( i =0 ; i < 1e8; i++)
{
  f1 = (i * f2 + i / f3) * 0.5; //or divide by 2.0f, respectively
}

更新2 从评论中引用:

[我想]知道什么是算法/架构要求导致>除法在硬件上比复制要复杂得多

我正在谷歌搜索过去一小时的问题,但只有泰勒系列或一些示例代码的要点太慢或根本不编译.好吧,我发现谷歌的答案大多是"Google it,它已经被问到了",但遗憾的是它不是 ......

我在低端Pentium 4上分析我的游戏,发现大约85%的执行时间浪费在计算窦,cosinus和平方根(来自Visual Studio中的标准C++库)上,这似乎与CPU密切相关(在我的I7上,相同的功能只有5%的执行时间,并且游戏更快了waaaaaaaaaa).我不能优化这三个函数,也不能在一次传递中计算正弦和余弦(相互依赖),但我不需要太精确的模拟结果,所以我可以使用更快的逼近.

那么,问题是:在C++中计算float的正弦,余弦和平方根的最快方法是什么？

编辑 查找表更加痛苦,因为在现代CPU上产生的Cache Miss比Taylor系列更昂贵.这些天CPU很快,而缓存则不然.

我犯了一个错误,我虽然需要为Taylor系列计算几个阶乘,我现在看到它们可以实现为常量.

所以更新的问题是:对于平方根还有任何快速优化吗？

EDIT2

我使用平方根计算距离,而不是规范化 - 不能使用快速反平方根算法(如评论中所指出:http://en.wikipedia.org/wiki/Fast_inverse_square_root

EDIT3

我也无法在平方距离上操作,我需要精确的距离进行计算

假设有必要计算打包浮点数据的倒数或倒数平方根.两者都可以轻松完成:

__m128 recip_float4_ieee(__m128 x) { return _mm_div_ps(_mm_set1_ps(1.0f), x); }
__m128 rsqrt_float4_ieee(__m128 x) { return _mm_div_ps(_mm_set1_ps(1.0f), _mm_sqrt_ps(x)); }

这种方法效果很好但很慢:根据指南,它们在Sandy Bridge上进行了14次和28次循环(吞吐量).对应的AVX版本在Haswell上几乎占用相同的时间.

另一方面,可以使用以下版本:

__m128 recip_float4_half(__m128 x) { return _mm_rcp_ps(x); }
__m128 rsqrt_float4_half(__m128 x) { return _mm_rsqrt_ps(x); }

它们只需要一到两个时间周期(吞吐量),从而大大提升了性能.但是,它们非常接近:它们产生的结果相对误差小于1.5*2 ^ -12.鉴于单精度浮点数的机器epsilon是2 ^？24,我们可以说这种近似具有大约一半的精度.

似乎可以添加Newton-Raphson迭代以产生具有单精度的结果(可能不像IEEE标准所要求的那样精确),参见GCC,ICC,LLVM上的讨论.理论上,相同的方法可用于双精度值,产生半精度或单精度或双精度.

我有兴趣为float和double数据类型以及所有(half,single,double)精度实现此方法的实现.处理特殊情况(除以零,sqrt(-1),inf/nan等)不是必需的.此外,我不清楚这些例程中的哪一个比普通的IEEE编译解决方案更快,哪个更慢.

以下是对答案的一些小限制,请:

1. 在代码示例中使用内在函数.程序集依赖于编译器,因此不太有用.
2. 对函数使用类似的命名约定.
3. 实现例程,将单个SSE/AVX寄存器包含密集打包的float/double值作为输入.如果有相当大的性能提升,你也可以发布几个寄存器作为输入的例程(两个reg可能是可行的).
4. 如果两个SSE/AVX版本绝对等于将_mm更改为_mm256,则不要发布它们,反之亦然.

欢迎任何性能评估,测量和讨论.

摘要

以下是具有一次NR迭代的单精度浮点数的版本:

__m128 recip_float4_single(__m128 x) {
  __m128 res = _mm_rcp_ps(x);
  __m128 muls …

我正在尝试对快速反平方根进行基准测试。完整代码在这里：

#include <benchmark/benchmark.h>
#include <math.h>

float number = 30942;
    
static void BM_FastInverseSqrRoot(benchmark::State &state) {
    for (auto _ : state) {
        // from wikipedia:
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;
        i  = 0x5f3759df - ( i >> 1 );
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * …

我正在学习 SIMD 内在函数和并行计算。我不确定Intel对x86指令的定义sqrtpd是否 表示将同时计算传递给它的两个数字的平方根：

对源操作数（第二个操作数）中的两个、四个或八个压缩双精度浮点值的平方根执行 SIMD 计算，并将压缩双精度浮点结果存储在目标操作数（第二个操作数）中第一个操作数）。

我知道它明确表示SIMD 计算，但这是否意味着对于此操作，将同时计算两个数字的根？