c++ - 缓存还是不缓存(生成)，这是个问题

Question

我有一个集合，例如 100 个 double 值，这些值必须除以一个固定的 int 变量很多次:

unsigned int current_interval = double_value / int_value;

我需要知道下面的简单缓存是否是一个更便宜的计算(为什么？):

std::map<double_value,current_interval> cache;
//...
unsigned int get_interval(double_value / int_value){
    if((it = cache.find(double_value)) != cache.end()
    {
     return it->second;
    }
    unsigned int current_interval = double_value / int_value;
    cache[double_value] = current_interval;
    return current_interval;
}

谢谢

Answer 1

总结:重复除法可能比在 map 中查找值更快

详细信息:

我认为这是一个有趣的问题。至少从 map 查找与浮点除法相比的执行时间的角度来看。在解决这个问题之前，我想重申其中两条评论:

1) 如果您真的只有 100 个 double 除以一个固定值然后多次使用，我希望您应该能够转换您的算法以直接使用这个结果。我希望这会比提议的缓存算法更有效。

2) 不要使用double 作为映射中的键。

现在进入主要问题。为了回答这个问题，我写了两个小程序。第一个简单地在大小为 100 的映射中查找值。第二个执行浮点除法。我已经包含了完整的源代码，以防有人想复制我的结果。同样对于第二个程序，我包含了一些额外的代码，只是为了保持相同的结构，但重要的是在第二个循环中。

---

map .cpp

#include <map>
#include <stdlib.h>

std::map<int,int> testmap;

int main(int argc, char **argv) {
  int count = atoi(argv[1]);
  int val   = atoi(argv[2]);
  int total = 0;

  for(int i = 0; i < 100; i++) {
    testmap[i] = val + i;
  }

  for(int i = 0; i < count; i++) {
    for(int j = 0; j < 100; j++) {
      total += testmap[j];
    }
  }

  return total;
}

---

双.cpp

#include <map>
#include <stdlib.h>

std::map<int,int> testmap;

int main(int argc, char **argv) {
  int count = atoi(argv[1]);
  double val   = atof(argv[2]);
  double total = 0;

  for(int i = 0; i < 100; i++) {
    testmap[i] = val + i;
  }

  for(int i = 0; i < count; i++) {
    for(int j = 0; j < 100; j++) {
      total += val / j;
    }
  }

  return total;
}

---

我用 O1 和 O3 编译以确保编译器没有优化掉循环。我还测试了几种不同的迭代大小，以确保执行时间与迭代次数成比例。

我在 Intel(R) Xeon(R) CPU E3-1275 v3 @ 3.50GHz 系统上运行了我的测试，该系统使用 g++ (GCC) 4.9.2

对于 O1，我运行 10000000 次迭代的结果是:

map: 7.1 seconds 
double: 3.6 seconds

对于 O3，我的结果是:

map: 5.3 seconds
double: 3.5 seconds

所以区别不是那么大，但显然在我在这里写的小型微基准中除法实现更快。而且它更容易实现。所以我认为尝试记住除法的结果，然后在 map 中查找它们，比在需要时简单地计算值要快的可能性很小。为了使内存有用，基本操作需要比在现代 CPU 中高度优化的浮点除法更昂贵。