地图访问和迭代所用的 C++ 时间

Question

我正在使用 gprof 分析代码，我观察到 -> 运算符消耗了大量时间。

这是地图的示例定义。

map<int, vector<int> > myMap;

我有一个迭代器，

map<int, vector<int> >::iterator it;

我经常运行循环，例如：

for(it = myMap.begin(), it != myMap.end(); it++) {
   //Do stuff
}

这是分析得到的数据

Function:
std::_Rb_tree_iterator<std::pair<int const, std::vector<ClassType*, std::allocator<ClassType*> > > >::operator->() const
Time Consumed:
20.18%
Number of Times function is called:
15285739415

Function:
std::_Rb_tree_iterator<std::pair<int const, std::vector<ClassType*, std::allocator<ClassType*> > > >::operator++(int)
Time Consumed:
2.90%
Number of Times function is called:
3825378111

根据我的理解，++ 运算符计算下一个元素，它花费了 O(log(n)) 并且 -> 给出了应该花费 O(1) 时间的元素。尽管 -> 运算符比 ++ 运算符被调用得更多，但我认为它不应该消耗那么多时间。 ++ 不应该比 -> 运算符消耗更多时间吗？

Answer 1

内存访问（-> 运算符）通常比算术运算（++ 运算符）慢得多。

这是因为搜索数据需要时间，从最低级别（最接近寄存器）的缓存开始一直搜索到硬盘驱动器中的可能页面。如您所料，离寄存器越远，这将花费相当多的时间。

然而，算术运算可能不需要涉及内存访问。如果算术运算中涉及的数据能装进寄存器，那么就连最底层的缓存都不需要访问了。

这里有一个 good article 关于缓存 coherence/spatial 位置如何影响应用程序速度的 good article。

地图访问和迭代所用的 C++ 时间

C++ Time Taken in Map Access and Iteration

c++

dictionary

operators

c++11