C++ exp LUT（查找表）

Question

在我编写的一个C++ CPU密集型模拟中，通过valgrind在我的程序中追踪到一个瓶颈是cmath::exp。它目前占用了超过40%的模拟时间。我可以将输入限制在相对较小的值域内，但我想控制精度。我考虑使用LUT（查找表）来替换exp，但我不太确定如何以“正确的方式”（商标）做到这一点。我关心以下问题：

1. 大的查找表会不适合缓存，因此会减慢访问速度
2. 将双精度输入转换为整数以便访问查找表的最佳方法
3. 答案对（2）的斜率有依赖吗？
4. 我是在重新发明轮子吗——这已经被别人做过了吗？

实现/（从库）包含exp的LUT的最佳方法是什么？

- Hooked

---

你需要处理的领域是什么？ - Alan Stokes

@AlanStokes exp(x) 其中 x = [-k ... -1]，k>1，且 k 仅在运行时已知（因此可能需要每次运行程序重新构建 LUT（这是可以接受的，因为模拟时间可能需要数天））。 - Hooked

你的计算代码中可能有一小部分对我们有用。它是一种“主循环”还是真的非常复杂，不容易适应单个SO帖子？ - Viktor Latypov

答案在这里(http://codereview.stackexchange.com/a/111531/84610)，展示了如何在与您类似的整体计算目标的上下文中实现`exp`的查找表。 - abcd

@dbliss：实现的函数是exp的严重剪裁和量化版本。它不会尝试估计任何未预先计算的点。这对您来说很好。但不要将其与快速估计整个范围内函数的方法混淆。 - Ben Voigt

@BenVoigt 完全正确。后面的问题（获取整个范围的快速方法）是我现在正在解决的。在SO上有很多关于这个问题的混乱文本（其中一些与我的问题相关，大多数不相关），但我还没有找到一个简单有效的解决方案。 - abcd

Answer 1

我曾经遇到过这个问题，所以我采取了一些堆栈样本来诊断它。这样可以告诉我们调用来自哪里以及参数值是什么。我发现当exp从特定位置调用时，参数值非常重复。这表明需要采用记忆化方法，这将产生巨大的差异。它需要一个简单的“包装”函数：

double exp_cached(double arg, double* old_arg, double* old_result){
  if (arg== *old_arg) return *old_result;
  *old_arg = arg;
  *old_result = exp(arg);
  return *old_result;
}

无论何处调用exp(foo)，请执行以下操作：

static double old_arg = -999999999, old_result;
...
... exp_cached(foo, &old_arg, &old_result)...

那样，如果在调用处的参数与之前相同，则不会调用exp。

- Mike Dunlavey

Answer 2

1. 最佳查找表大小是由您在性能、准确性和实现复杂度之间权衡所做出的决定。您需要进行分析，我们无法告诉您答案（因为我们不知道答案）。

2. 使用 <math.h> 中的 lrint 将 double 转换为 long int。我不确定它是否在 <cmath> 中。

3. 我不确定斜率与将浮点数转换为整数有什么关系。您能详细说明一下您担心的问题吗？

4. 是的，您正在重新发明轮子。任何曾经实现过数学库的人都已经反复地完成了您所做的工作。这方面有很多文献资料。

一个简单的查找表远非最佳选择。您将需要使用某种多项式逼近方法，可以考虑使用具有从查找表中选择系数的分段函数逼近。对于像 exp 这样平滑且可预测的函数，使用多项式将为您提供更高的精度，而计算代价相同。所需的多项式将取决于复杂度和准确度之间的权衡，以及您是想最小化期望误差、最小化最大误差，还是使用其他损失函数。

限制 exp 的定义域并没有实际帮助太多，因为它很容易扩展到整个定义域。

// only works for x in [0, 1]
double exp2_limited(double x);

// works for all x, but doesn't handle overflow properly
double exp2(double x)
{
    return scalbn(exp2_limited(fmod(x, 1.0)), (long) floor(x));
}

摘要：

• 在设计这样的函数之前，您必须知道所需的准确度。

• 您还必须知道损失函数（即选择损失函数）。

• 在了解速度有多快之前，您必须进行分析。

• 使用多项式。

- Dietrich Epp

Answer 3

之前有一个非常类似的问题被问过。这是我的答案：

• 快速计算指数：是否可能在不失去太多性能的情况下提高准确性？

这种方法是由那个问题的作者建议的，我能够有效地实现它（小查找表和最小额外工作）。它是用C#编写的，但转换为C++应该很简单，如果你遇到麻烦，我可以帮忙。

- Ben Voigt

---

问题所询问的是如何在不失太多准确性的情况下提高性能。而你的答案声称做到了相反的事情：在不失太多性能的情况下提高准确性。请扩展你的答案，告诉我们为什么你发布的链接对于问题的提出者仍然具有参考价值。 - abcd

@dbliss：两者并不不同。如果你在（1,0）和（0,1）之间画一条线，那么点（0.8，0.8）同时在线的右侧和上方。两个问题措辞的区别在于另一个问题已经从（高准确性低性能）转向（低准确性高性能），而这个问题则从（高准确性低性能）开始。但两者都试图达到（良好准确性良好性能），而传统的权衡只提供（中等准确性良好性能）或（良好准确性中等性能）。 - Ben Voigt

@dbliss：具有讽刺意味的是，另一个问题恰好是在神经网络的背景下进行的，就像您的代码审查帖子一样。那么，为什么您要说这些问题完全不相关呢？ - Ben Voigt

@dbliss：所以你的意思是如果链接被截断为“快速Exp计算”，你更有可能访问它？现在它是整个问题标题，由SO引擎自动拉入，因为它看到了一个站内链接。 - Ben Voigt

由于某种原因，我现在才注意到你的第一条评论。我认为这澄清了一切。那个评论中的解释正是我在第一条评论中所询问的。 - abcd