c++ - 优化数学表达式

Question

我对 fitch 软件执行一些简单计算所花费的时间感到沮丧。我使用 Intel VTune 对其进行了分析，发现 52% 的 CPU 时间花在了 nudists() 函数上:

void nudists(node *x, node *y)
{
  /* compute distance between an interior node and tips */
  long nq=0, nr=0, nx=0, ny=0;
  double dil=0, djl=0, wil=0, wjl=0, vi=0, vj=0;
  node *qprime, *rprime;

  qprime = x->next;
  rprime = qprime->next->back;
  qprime = qprime->back;
  ny = y->index;
  dil = qprime->d[ny - 1];
  djl = rprime->d[ny - 1];
  wil = qprime->w[ny - 1];
  wjl = rprime->w[ny - 1];
  vi = qprime->v;
  vj = rprime->v;
  x->w[ny - 1] = wil + wjl;
  if (wil + wjl <= 0.0)
    x->d[ny - 1] = 0.0;
  else
    x->d[ny - 1] = ((dil - vi) * wil + (djl - vj) * wjl) / (wil + wjl);
  nx = x->index;
  nq = qprime->index;
  nr = rprime->index;
  dil = y->d[nq - 1];
  djl = y->d[nr - 1];
  wil = y->w[nq - 1];
  wjl = y->w[nr - 1];
  y->w[nx - 1] = wil + wjl;
  if (wil + wjl <= 0.0)
    y->d[nx - 1] = 0.0;
  else
    y->d[nx - 1] = ((dil - vi) * wil + (djl - vj) * wjl) / (wil + wjl);
}  /* nudists */

这两条长线占用了总 CPU 时间的 24%。有什么方法可以优化这段代码，尤其是那两条长线？另一个消耗大量CPU时间的函数是:

void secondtraverse(node *q, double y, long *nx, double *sum)
{
  /* from each of those places go back to all others */
   /* nx comes from firsttraverse */
   /* sum comes from evaluate via firsttraverse */
  double z=0.0, TEMP=0.0;

  z = y + q->v;
  if (q->tip) {
    TEMP = q->d[(*nx) - 1] - z;
    *sum += q->w[(*nx) - 1] * (TEMP * TEMP);
  } else {
    secondtraverse(q->next->back, z, nx, sum);
    secondtraverse(q->next->next->back, z, nx,sum);
  }
}  /* secondtraverse */

计算总和的代码占用了 18% 的 CPU 时间。有什么办法可以让它运行得更快吗？

完整的源代码可以在这里找到:http://evolution.genetics.washington.edu/phylip/getme.html

Answer 1

就优化大型方程组而言，您正在使用一些最耗时的运算:乘法和除法。

您必须在更大的框架、图片或范围中寻找优化。一些想法:

• 定点算术
• 消除每次迭代的除法。
• 线程化
• 多核
• 数组，非链表

定点算术

如果您可以将数字基数设置为 2 的幂，则许多除法将变为位移位。例如，除以16相当于右移4次。轮类通常比 split 更快。

消除每次迭代的除法

与其在每次迭代中执行除法，不如将其提取出来并减少执行频率，也许使用不同的值。

如果将除法视为分数，则可以在除以分母之前多次使用分子。

线程

您可能需要考虑多线程。根据代码效率创建线程。让一个线程作为在后台计算的工作线程。

多核(并行执行)

“x”和“y”变量似乎彼此独立。这些计算可以设置为并行编程。一个内核或处理器执行“x”计算，而另一个内核正在计算“y”变量。

考虑在更高级别上拆分它。一个核心(线程)处理所有“x”变量，而另一个核心处理“y”变量。结果独立保存。在计算完所有“x”和“y”变量后，让主核心处理所有结果。

数组，而不是列表

当所有数据都能放入处理器的数据缓存时，您的处理器将会最高兴。如果不能拟合所有的数据，那就尽可能的拟合。因此，与链表相比，数组最有可能适合数据缓存行。处理器将知道阵列地址是连续的并且可能不必重新加载数据缓存。