C++ exp LUT（查找表）

在我正在写的一个C++ CPU绑定仿真中，我通过我的程序中的valgrind将瓶颈追溯到cmath::exp。目前它的仿真时间超过40％。我可以将输入绑定到一个相对较小的域，但我想控制精度。我正在考虑移动到LUT（查找表）来取代exp，但我不太清楚如何做到这一点“正确的方式”（TM）。关注我：C++ exp LUT（查找表）

大型查找表将不适合在高速缓存从而减缓获得了双输入转换为整数接入到查找表中
最佳方式是否答案（2 ）取决于输入函数的斜率？
我重新发明了车轮 - 这已经做过吗？

实现/（包括从库中）LUT为exp的最佳方式是什么？

来源

2012-07-25 Hooked

什么是您需要处理的域？ – 2012-07-25 20:50:57

@AlanStokes'exp（x）'其中'x = [-k ... -1]'，'k> 1'和'k'只在运行时是已知的（因此推测每次都需要重建LUT该程序运行（这是好的，因为模拟时间可能需要几天））。 – Hooked 2012-07-25 20:56:35

您的计算代码的一小部分可能对我们有用。这是一种“主循环”，还是一种非常复杂且难以适应单个SO帖子的事情？ – 2012-07-25 21:12:06

以前有一个非常类似的问题。这里是我的答案：

Fast Exp calculation: possible to improve accuracy without losing too much performance?

的方法是由该问题笔者建议，我是能够有效地实现它（小查找表和查找后，最小的额外的工作）。它是用C＃编写的，但是转换到C++应该很简单，如果遇到麻烦，我可以提供帮助。

来源

2012-07-25 21:14:00

问题所要求的是一种提高性能而不会失去太多准确性的方法。你的答案声称做相反的事情：提高准确性而不会失去太多的表现。请扩大您的答案，以便它告诉我们为什么您发布的链接仍与OP相关。 – dbliss 2015-12-07 21:07:33

@dbliss：两者没有区别。如果您在（1,0）和（0,1）之间画一条线，则点（0.8，0.8）同时在线的右侧和线的上方。问题的措词之间的区别在于，另一个问题已经从（高精度低性能）转移到（低精度高性能），而这个问题从（高精度低性能）开始。但两者都试图达到（良好的准确性，良好的性能），而传统的权衡只能提供（平庸的准确性好的性能）或（良好的准确平庸的性能）。 – 2015-12-07 21:36:04

@dbliss：具有讽刺意味的是，另一个问题正是在神经网络的背景下进行的，就像你的代码评论文章一样。那么，你为什么试图说这些问题是完全不相关的？ – 2015-12-07 21:40:05

最佳查找表大小取决于您在性能，准确性和实现复杂性之间的权衡。你必须简介，我们不能告诉你答案（我们不知道答案）。
使用lrint从<math.h>将double转换为long int。我不确定它是否在<cmath>。
我不确定斜率与将浮点数转换为整数有什么关系。你能否详细说明你担心的是什么？
是的，你正在重新发明轮子。任何曾经实施过数学图书馆的人一直在做你正在做的事。关于这个问题有很多文献。

直观的查找表远非最佳。您将需要使用某种多项式近似，也许是从查找表中选择系数的分段逼近。对于像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)); 
}

摘要：

你必须知道所需要的精度，然后才能设计出这样的功能。
您还必须知道损失函数（即，选择的损失函数）。
你有个人主页，你知道它是多么快了。
使用多项式。

来源

2012-07-25 21:09:23

我有这个问题，我拿了几堆样本来诊断它。所做的是告诉来电的来源以及参数值是什么。我发现当exp被从特定的地方调用时，参数值是高度可重复的。

这提出了一个memoization方法，这造成了巨大的差异。

它需要一个简单的 “包装” 功能：

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不会被调用，如果它的参数在那个被调用的地方与之前有相同的参数值。

来源

2012-07-26 12:01:47

C++ exp LUT（查找表）

回答

相关问题