查找表与运行时计算效率 - C++

Question

我的代码需要从以下函数连续计算一个值：

inline double f (double x) {
    return ( tanh( 3*(5-x)  ) *0.5 + 0.5);
}

分析表明程序的这一部分是花费大部分时间的地方。由于该程序将运行数周甚至数月，我想优化此操作并正在考虑使用查找表。

我知道查找表的效率取决于表本身的大小以及它的设计方式。目前我不能使用少于 100 MB，最多可以使用 2GB。矩阵中两点之间的值将被线性插值。

使用查找表会比进行计算更快吗？此外，使用 N 维矩阵是否会比一维 std::vector 更好，并且不应跨越的表大小的阈值（如果有）是多少？

Answer 1

我正在编写一个不断需要从特定函数计算值的代码。经过一些分析，我发现我的程序的这部分是花费大部分时间的地方。

到目前为止，我不允许使用少于 100 MB，我最多可以使用 2GB。线性插值将用于矩阵中点之间的点。

如果您有巨大的查找表（如您所说的数百 MB），它不适合缓存 - 很可能内存查找时间将远高于计算本身。RAM“非常慢”，尤其是从巨大数组的随机位置获取时。

这是合成测试：

现场演示

#include <boost/progress.hpp>
#include <iostream>
#include <ostream>
#include <vector>
#include <cmath>

using namespace boost;
using namespace std;

inline double calc(double x)
{
    return ( tanh( 3*(5-x)  ) *0.5 + 0.5);
}

template<typename F>
void test(F &&f)
{
   progress_timer t;
   volatile double res;
   for(unsigned i=0;i!=1<<26;++i)
      res = f(i);
   (void)res;
}

int main()
{
   const unsigned size = (1 << 26) + 1;
   vector<double> table(size);
   cout << "table size is " << 1.0*sizeof(double)*size/(1 << 20) << "MiB" << endl;
   cout << "calc ";
   test(calc);
   cout << "dummy lookup ";
   test([&](unsigned i){return table[(i << 12)%size];}); // dummy lookup, not real values
}

我机器上的输出是：

table size is 512MiB
calc 0.52 s

dummy lookup 0.92 s