3

我正在编写一个算法来找到一个 nxn 矩阵的逆。让我们以 3x3 矩阵的具体情况为例。

当您手动反转矩阵时，您通常会查找包含一个或多个零的行/列，以使行列式计算更快，因为它消除了您需要计算的项。

按照 C/C++ 中的这个逻辑，如果你用一个或多个零来识别一行/列，你最终会得到以下代码：

float term1 = currentElement * DetOf2x2(...);
//           ^
//           This is equal to 0.
//
// float term2 = ... and so on.

由于编译器无法知道currentElement在编译时将为零，因此无法将其优化为类似float term = 0;的东西，因此浮点乘法将在运行时执行。

我的问题是，这些零值会使浮点乘法更快，还是无论 的值如何，乘法都会花费相同的时间currentElement？如果在运行时无法优化乘法，那么我可以删除搜索包含零的行/列的逻辑。

4

5 回答 5

10

除非计算很简单（例如所有常量），否则不允许编译器对此进行优化。

原因是，DetOf2x2 可能返回一个 NAN 浮点值。将 NAN 与零相乘不会返回零，而是再次返回 NAN。

您可以在这里使用这个小测试自己尝试：

int main (int argc, char **args)
{
  // generate a NAN
  float a = sqrt (-1);

  // Multiply NAN with zero..
  float b = 0*a;

  // this should *not* output zero
  printf ("%f\n", b);
}

如果你想优化你的代码，你必须自己测试为零。编译器不会为您执行此操作。

于 2013-03-05T02:32:41.710 回答
7 
float term1 = currentElement * DetOf2x2(...);

DetOf2x2(...)即使 currentElement 为 0，编译器也会调用：这肯定比最终乘法的成本要高得多，无论是否乘以 0。有多种原因：

  • DetOf2x2(...)即使在currentElementis0和
  • DetOf2x2(...)可能会返回像 Not-a-Number / NaN sentinel 这样应该传播到的值term1（正如 Nils Pipenbrinck 首先指出的那样）

GivenDetOf2x2(...)几乎肯定正在处理只能在运行时确定的值，后一种可能性不能在编译时排除。

如果您想避免调用Detof2x2(...)，请尝试：

float term1 = (currentElement != 0) ? currentElement * DetOf2x2(...) : 0;
于 2013-03-05T02:34:58.453 回答
3

现代 CPU 实际上会非常快速地处理乘以零，比一般乘法更快，并且比分支快得多。除非该零将通过至少几十条指令传播，否则甚至不要费心尝试优化它。

于 2013-03-05T02:21:16.507 回答
0

在运行时执行的优化称为 JIT（即时）优化。在翻译（编译）时执行的优化称为 AOT（提前）优化。您指的是 JIT 优化。编译器可能会在您的机器代码中引入 JIT 优化，但与常见的 AOT 优化相比，它的实现肯定要复杂得多。优化通常是根据重要性实现的，这种“优化”可能会被视为对其他算法产生负面影响。C 实现不需要执行任何这些优化。

您可以手动提供优化，这将是“搜索包含零的行/列的逻辑”，或者类似这样：float term1 = currentElement != 0 ? currentElement * DetOf2x2(...) : 0;

于 2013-03-05T02:32:50.780 回答
0

当编译器可以猜测“currentElement”的值时，以下构造在编译时有效。

浮动术语 1 = 当前元素？currentElement * DetOf2x2(...) : 0;

如果在编译时无法猜到，则会在运行时进行检查，性能取决于处理器架构：分支之间的权衡（包括分支延迟和重建指令流水线的延迟可高达 10 或20 个周期）和平面代码（一些处理器每个周期运行 3 条指令）和硬件分支预测（当硬件支持分支预测时）。

由于 x86_64 处理器上的乘法吞吐量接近 1 个周期，因此没有性能差异取决于 0.0、1.0、2.0 或 12345678.99 等操作数值。如果存在这种差异，那将被视为加密风格软件中的隐蔽通道。

GCC 允许在编译时检查函数参数

内联浮点 myFn（浮点 currentElement，myMatrix M）

{

#if __builtin_constant_p(currentElement) && currentElement == 0.0

返回 0.0；

＃别的

返回当前元素 * det(M);

＃万一

}

您需要在编译器中启用内联和过程间优化。

于 2015-01-06T03:37:23.247 回答