优化头痛 - 从查找表中删除 if

Question

我正在尝试优化以下代码，这是我的应用程序中的瓶颈。 它的作用：它采用双精度值 value1 和 value2 并尝试找到包含校正因子的最大值。如果两个值之间的差异大于 5.0（LUT 按因子 10 缩放），我可以只取这两个值的最大值。如果差异小于 5.0，我可以使用 LUT 中的校正因子。

有谁知道这段代码的更好风格是什么？我不知道我在哪里浪费了时间——是大量的 if 还是乘以 10？

double value1, value2;
// Lookup Table scaled by 10 for (ln(1+exp(-abs(x)))), which is almost 0 for x > 5 and symmetrical around 0. LUT[0] is x=0.0, LUT[40] is x=4.0.
const logValue LUT[50] = { ... }

if (value1 > value2)
{
    if (value1 - value2 >= 5.0)
    {
        return value1;
    }
    else
    {
        return value1 + LUT[(uint8)((value1 - value2) * 10)];
    }
}
else
{
    if (value2 - value1 >= 5.0)
    {
        return value2;
    }
    else
    {
        return value2 + LUT[(uint8)((value2 - value1) * 10)];
    }
}

Answer 1

使用 Excel 几分钟即可生成一个近似方程，看起来它可能具有您所需的精度，因此您可以完全取消查找表。您仍然需要一个条件来确保方程的参数保持在优化的范围内。

double diff = abs(value1 - value2);
double dmax = (value1 + value2 + diff) * 0.5; // same as (min+max+(max-min))/2
if (diff > 5.0)
    return dmax;
return dmax + 4.473865638/(2.611112371+diff) + 0.088190879*diff + -1.015046114;

PS 我不能保证这会更快，只是这是一种足够不同的方法，值得进行基准测试。

PPS 可以改变约束来得出稍微不同的常数，有很多变化。这是我做的另一组，其中表格和公式之间的差异始终小于 0.008，而且每个值都将小于前面的值。

return dmax + 3.441318133/(2.296924445+diff) + 0.065529678*diff + -0.797081529;

编辑：我测试了此代码（第二个公式），针对 0 到 10 之间的一百万个随机数进行了 100 次传递，以及问题 MSalters 目前接受的答案，以及暴力实现max(value1,value2)+log(1.0+exp(-abs(value1-value2)))。我在双核 AMD Athlon 和 Intel 四核 i7 上进行了尝试，结果大致一致。这是一个典型的运行：

• 原始：1.32 秒。
• MSalters：1.13秒。
• 我的：0.67秒。
• 暴力破解：4.50 秒。

多年来，处理器的速度变得令人难以置信，现在它们执行几次浮点乘法和除法的速度比在内存中查找值的速度还要快。这种方法不仅在现代 x86 上更快，而且更准确；方程中的近似误差远小于截断查找输入引起的步长误差。

当然，结果仍然会根据您的处理器和编译器而有所不同；您自己的特定目标仍然需要进行基准测试。

Answer 2

它可能会同等地沿着两条路径走下去，以至于给处理器带来很多管道问题。

您尝试过分析吗？

我还建议尝试使用标准库，看看是否有帮助（例如，它是否能够使用特定于处理器的指令）：

double diff = std::fabs(value1 - value2);
double maxv = std::max(value1, value2);
return (diff >= 5.0) ? maxv : maxv + LUT[(uint8)((diff) * 10)];

Answer 3

我可能会编写稍微不同的代码来处理 value2 情况：

if (value2 < value1) std::swap(value1, value2);
assert(value1 <= value2); // Assertion corrected
int diff = int((value2 - value1) * 10.0);
if (diff >= 50) diff = 49; // Integer comparison iso floating point
return value2 + LUT[diff];

Answer 4

我假设当调用该函数时，您很可能会得到必须使用查找表的部分，而不是 >=5.0 部分。在这种情况下，最好引导编译器这样做。

double maxval = value1;
double difference_scaled = (value1-value2)*10;
if (difference < 0)
{
    difference = -difference;
    maxval = value2;
}
if (difference < 50)
    return maxval+LUT[(int)difference_scaled];
else
    return maxval;

尝试一下，让我知道这是否可以提高您的程序的性能。

Answer 5

该代码成为应用程序瓶颈的唯一原因是您多次调用它。您确定需要吗？也许可以更改代码中较高的算法以减少比较？

Answer 6

我已经做了一些非常快速的测试，但请自行分析代码以验证效果。

将 LUT[] 更改为静态变量使我的速度提高了 600%（从 3.5 秒到 0.6 秒）。这接近我使用的绝对最小值测试（0.4 秒）。看看是否有效并重新分析以确定是否需要进一步优化。

作为参考，我只是在 VC++ 2010 中对这个循环的执行（内部循环的 1 亿次迭代）进行计时：

int Counter = 0;

for (double j = 0; j < 10; j += 0.001)
    {
        for (double i = 0; i < 10; i += 0.001)
        {
            ++Counter;
            Value1 += TestFunc1(i, j);
        }
    }

Answer 7

您在函数中计算了多次 value1 - value2 。只需做一次。

转换为 uint8_t 也可能存在问题。就性能而言，用作从双精度到整数转换的最佳整数类型是 int，使用数组索引的最佳整数类型也是 int。代码>.

max_value = value1;
diff = value1 - value2;
if (diff < 0.0) {
  max_value = value2;
  diff = -diff;
}

if (diff >= 5.0) {
  return max_value;
}
else {
  return max_value + LUT[(int)(diff * 10.0)];
}

请注意，上述内容保证 LUT 索引介于 0（含）和 50（不含）之间。这里不需要 uint8_t。

编辑
经过一番尝试后，这是一个相当快的基于 LUT 的 log(exp(value1)+exp(value2)) 近似：

#include <stdint.h>

// intptr_t *happens* to be fastest on my machine. YMMV.
typedef intptr_t IndexType;

double log_sum_exp (double value1, double value2, double *LUT) {
  double diff = value1 - value2;
  if (diff < 0.0) {
    value1 = value2;
    diff = -diff;
  }   
  IndexType idx = diff * 10.0;
  if (idx < 50) {
    value1 += LUT[idx];
  }   
  return value1;
}   

整数类型 IndexType 是加快速度的关键之一。我使用 clang 和 g++ 进行了测试，两者都表明转换为 intptr_t （在我的计算机上为 long）并使用 intptr_t 作为索引LUT 比其他积分类型更快。它比某些类型要快得多。例如，unsigned long long 和 uint8_t 在我的计算机上是非常糟糕的选择。

类型不仅仅是一个提示，至少对于我使用的编译器来说是这样。这些编译器完全按照代码的指示执行从浮点类型到整型的转换，无论优化级别如何。

另一个减速带是由将整型类型与 50 进行比较而不是将浮点类型与 5.0 进行比较而产生的。

最后一个障碍：并非所有编译器都是一样的。 在我的计算机上 (YMMV)，g++ -O3 生成的代码比 clang -O3 慢得多（此问题慢 25%！），反过来，它生成的代码比 clang -O4 生成的代码要慢一些。

我还使用了有理函数近似方法（类似于 Mark Ransom 的答案），但上面显然没有使用这种方法。