优化条件"if (m == 0 || n == 0)"的方法

Question

我正在写一个函数，这是我目前所拥有的:

template <typename T> 
M2SA(T* A, size_t m, T* B, size_t n)
{
    /* Require both arrays be nonempty */
    if (m == 0 || n == 0)
    {
        throw ("Cannot find median of 2 sorted arrays if either is empty!";)
    }
}

是否有任何方法可以使用位比较操作优化条件if (m == 0 || n == 0) ??

Answer 1

是否有任何方法可以优化条件if (m == 0 || n == 0)(使用位操作)??

对于几乎所有平台，答案都是响亮的否，除非m或n极有可能为0，并且参数没有在寄存器中传递:
如果你要求优化，编译器会生成最优的代码，很可能是这样的:

(load first argument into register)
(load second argument into register)
logical-and both arguments (not bitwise-and)
jump to throw statement if the zero-flag set

两个测试都有两个说明!我敢说，没有哪个平台不是最佳的。还有一种情况，编译器可以进一步优化:如果它内联函数，它可以传播常量，这可能使条件不变。

无论如何，代码中的异常消息表明您正在测试错误的条件，您想要!m && !n。

Answer 2

在更改一行代码之前，将编译器的优化设置设置为高并查看汇编语言。

我不知道如何优化表达式:((m == 0) || (n == 0))并从中挤出可忽略不计的时间。数据缓存丢失或指令缓存重新加载与执行两个子表达式的性能相同或更慢。

这是扩展的意思(不一定是最佳的):

if (m == 0)
{
  throw (/*...*/);
}
else  // m != 0
{
  if (n == 0)
  {
    throw (/*...*/);
  }
}

最好的解决方案是具有最少分支指令的解决方案。

扩展版本的汇编语言为:

; optional:  move m into register 0
  compare register 0 to zero.
  branch, if equal, to Throw.
; optional:  move n into register 1
  compare register 1 to zero.
  branch if not equal to Continue
Throw:
  call throw_mechanism;
Continue:

为指令计数构建真值表:

  m   |  n    |  instructions processed
------+-------+-------------------
  0   |  N/A  |  2
 !0   |  0    |  4
 !0   |  != 0 |  4

m的前两个指令总是被处理:获取和求值。m != 0导致4条指令被取出并求值的情况。

所以平均和最坏的情况是2个额外的指令被执行。

假设每条指令的处理速率为50纳秒，那么在最好的情况下可以节省100纳秒，在最坏的情况下可以节省200纳秒。

如前所述，数据缓存命中或指令管道(缓存)的重新加载可能需要超过200纳秒(最坏的情况)。

因为给定表达式的优化产生的结果可以忽略不计，并且应用于非常小的代码段，所以它被称为微优化。如果m或n不在数据缓存中，或者必须从内存中加载，那么从内存中获取这两个值所需的时间可能等于或大于处理额外指令所需的时间，从而耗尽优化表达式所获得的时间。类似地，如果指令管道或缓存需要重新加载。优化该表达式所节省的时间浪费在研究优化或等待外部实体(如鼠标单击或硬盘驱动器I/O)的其他代码上。

换句话说，您和您的程序将从使您的代码更健壮和更正确地工作中获益，而不是担心像这样的琐碎优化。

Answer 3

改正错误。

降低分支和指令计数的一种方法是使用按位与运算:

if ( 0 == n * m )
{
    ...
}

乘法是快速的，如果放在一个简单的循环中，编译器可以很容易地向量化。生成的程序集由3条指令组成，其中包括跳转。

MUL a,b // assume a and b are registers
TEST a
JNZ after_the_if_scope
//throw code
after_the_if_scope:
...

话虽如此，结果的统计信息(真或假)将更大程度地影响性能，因为在许多情况下，分支错误预测的成本高于实际计算的成本。

还要注意，如果m和m不是普通整数，而是代价高昂的函数调用，则应该使用逻辑函数或避免计算第二个函数。