优化条件的方法"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

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

无论如何,代码中的异常消息表明您正在测试您想要的错误条件!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纳秒(最差时间情况).

摘要
因为给定表达式的优化产生微不足道的结果,并适用于代码一个非常小的部分,它被称为microoptimization.如果m或n不在数据高速缓存中或必须从内存加载,从内存中获取这两个值所需的时间可能等于或大于处理额外指令所需的时间,耗尽通过优化表达式获得的任何时间.类似地,如果需要重新加载指令管道或缓存.通过优化此表达式节省的时间在研究优化或等待外部实体的其他代码(例如鼠标单击或硬盘驱动器I/O)时被浪费.

换句话说,您和您的程序将从使代码更加健壮和正常工作中受益更多,而不是担心像这样的琐碎优化.