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

Question

我的代码需要从以下函数不断计算一个值:

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

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

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

使用查找表会比计算更快吗？此外，使用 N 维矩阵会比一维 std::vector 更好吗？不应该超过表的大小的阈值(如果有的话)是多少？

Answer 1

I'm writing a code that continuously requires to compute a value from a particular function. After some profiling, I discovered that this part of my program is where most of the time is spent.

So far, I'm not allowed to use less than 100 MB, and I can use up to 2GB. A linear interpolation will be used for points between to points in the matrix.

如果您有巨大的查找表(如您所说的数百 MB)，它不适合缓存 - 很可能内存查找时间会比计算本身长得多。 RAM“非常慢”，尤其是从巨大数组的随机位置获取时。

这是综合测试:

live demo

#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