计算距离平方的最快方法

Question

我的代码在很大程度上依赖于计算3D空间中两点之间的距离.为了避免昂贵的平方根,我使用整个平方距离.但它仍然占用了计算时间的很大一部分,我想用更快的东西替换我的简单函数.我现在有:

double distance_squared(double *a, double *b)
{
  double dx = a[0] - b[0];
  double dy = a[1] - b[1];
  double dz = a[2] - b[2];

  return dx*dx + dy*dy + dz*dz;
}

我也尝试使用宏来避免函数调用,但它没有多大帮助.

#define DISTANCE_SQUARED(a, b) ((a)[0]-(b)[0])*((a)[0]-(b)[0]) + ((a)[1]-(b)[1])*((a)[1]-(b)[1]) + ((a)[2]-(b)[2])*((a)[2]-(b)[2])

我想过使用SIMD指令但是找不到一个好的例子或完整的指令列表(理想情况下是一些乘法+加两个向量).

GPU不是一个选项,因为每个函数调用只知道一组点.

计算距离平方的最快方法是什么？

Answer 1

一个好的编译器将优化你所能管理的那个.如果一个好的编译器认为它们将是有益的,它将使用SIMD指令.确保为编译器打开所有这些可能的优化.不幸的是,尺寸为3的向量与SIMD单元不相容.

我怀疑你只需要接受编译器生成的代码可能非常接近最优并且不能获得显着的增益.

Answer 2

第一个显而易见的事情是使用restrict关键字.

就像现在一样,a并且b是可混淆的(因此,从编译器的角度来看,假设最坏的情况是别名).没有编译器会自动向量化这个,因为这样做是错误的.

更糟的是,不仅可以在编译器无法矢量化这样一个循环,如果你也(不幸运的是,在你的例子)存储,它也必须每次都重新加载值.始终要清楚别名,因为它会极大地影响编译器.

接下来,如果你能忍受的,用float的,而不是double和垫,以4个浮点即使一个未使用,这是一个更"自然"的数据,为广大CPU的布局(这多少有些特定的平台,但4辆彩车是一个很好的猜测大多数平台 - 3个双打,即"典型"CPU上的1.5个SIMD寄存器,在任何地方都不是最佳的.

(对于手写的SIMD执行(这是很难比你想象的),第一和之前的所有一定要有一致的数据.接下来,看看什么延迟你的instrucitons在目标计算机上,首先做的最长的人.例如在预普雷斯科特英特尔是有意义的每个组件第一洗牌到寄存器中,然后用自身相乘,即使使用3次乘法,而不是一个,因为洗牌有很长的等待时间.在以后的型号,一个洗牌接受一个周期,这将是一个完全的反优化.
这再次表明,将它留给编译器并不是一个坏主意.)