c++ - C++中的引用速度

Question

我一直在从事一个项目，并试图找到执行时间大幅下降的原因，并将其缩小到我设法从逻辑中优化的单一方法。问题是我的解决方案涉及使用引用，这使得代码的另一部分运行得非常缓慢......我想回答的问题是为什么当地图是引用而不是引用时，内部循环需要更长的时间来评估局部变量？

这是优化之前的旧方法：

// old method: create an empty map, populate it
// and then assign it back to the path object later
map<int,float> screenline_usage; 

for (int i=0; i<numCandidates; ++i)
{
  // timing starts here. 
  map<int, float>& my_screenline_usage =
    path->get_combined_screenline_usage(legnr, stop_id);
  map<int, float>::iterator it = my_screenline_usage.begin(); 
  for (; it != my_screenline_usage.end(); ++it) 
    screenline_usage[it->first] += usage * it->second; 
  // timing ends here, this block evaluated 4 million times for overall execution time of ~12 seconds
}

// This function call is evaluated 400k times for an overall execution time of ~126 seconds
path->set_zone_screenline_usage(access_mode, zone_id, screenline_usage); 

// TOTAL EXECUTION TIME: 138 seconds.

优化后的新方式：

// new method: get a reference to internal path mapping and populate it
map<int, float>& screenline_usage =
  path->get_zone_screenline_usage(access_mode, zone_id);
screenline_usage.clear();

for (int i=0; i<numCandidates; ++i)
{
  // timing starts here
  map<int, float>& my_screenline_usage =
    path->get_combined_screenline_usage(legnr, stop_id);
  map<int, float>::iterator it = my_screenline_usage.begin(); 
  for (; it != my_screenline_usage.end(); ++it) 
    screenline_usage[it->first] += usage * it->second; 
  // timing ends here, this block evaluated 4 million times for overall execution time of ~76 seconds
}

// New method... no need to assign back to path object (0 seconds execution :)
// TOTAL EXECUTION TIME: 76 seconds (62 second time saving) ... but should be able to do it in just 12 seconds if the use of reference didn't add so much time :(

以下是从该代码调用的相关子例程：

// This is the really slow routine, due to the copy assignment used. 
void set_zone_screenline_usage(int access_mode, int zone_id,
  map<int,float>& screenline_usage)
{
  m_container[access_mode][zone_id] = screenline_usage; 
}

map<int,float>& get_zone_screenline_usage(int access_mode, int zone_id)
{
  return m_container[access_mode][zone_id]; 
}

注意：时间信息是针对单次运行的，其中上述代码被评估了大约 400k 次。计时是使用我为访问 RDTSC 时间戳计数器而构建的一些类完成的（是的，我知道 TSC 表示时间戳计数器），numCandidates 的平均值为 10，放入 screenline_usage 映射的平均元素数为 25。

更新：首先感谢所有参与其中的人。我认为最终这与 c++ 引用完全无关，更多的是与缓存一致性有关。我已将上面的优化代码替换为 vector& 和实现为成员变量映射的哈希函数

// newest method: get a reference to internal path mapping (as vector) and populate it 
// map<int,int> m_linkNum_to_SlNum declared in header and populated in constructor. 
vector<float>& screenline_usage = path->get_zone_screenline_usage(access_mode, zone_id);

for (int i=0; i<numCandidates; ++i)
{
  // timing starts here
  map<int, float>& my_screenline_usage =
    path->get_combined_screenline_usage(legnr, stop_id);
  map<int, float>::iterator it = my_screenline_usage.begin(); 
  for (; it != my_screenline_usage.end(); ++it) 
    screenline_usage[m_linkNum_to_SlNum[it->first]] += usage * it->second; 
  // timing ends here, this block evaluated 4 million times for overall execution time of ~9 seconds
}

// Newest method... again no need to assign back to path object (0 seconds execution :)
// TOTAL EXECUTION TIME: just 9 seconds (129 second time saving) ... this is even better than using a locally constructed map which took 12 seconds in the inner loop :)

在我看来，鉴于向量不是本地的，而是一个连续的内存块，并且散列函数 (m_linkNum_to_SlNum) 是本地成员变量，这种方法导致代码/数据能够放入缓存中无需去主存储器获取数据，从而显着提高速度。非常感谢根据这些发现得出的其他结论。

score 4 · Accepted Answer

也许您的 C++ 编译器能够为本地地图内联一些代码，但当地图是参考时则不行。

score 3 · Accepted Answer

你的问题不清楚。你的意思是问，为什么通过引用传递映射比通过值传递更快？如果是这样，答案很简单：按值返回地图意味着将其全部复制，而复制大地图是一项非常昂贵的操作。

另一方面，如果您的问题是：为什么获取对现有地图的引用并填充它比制作新地图更快，那么一个假设是它与

 screenline_usage[it->first] += usage * it->second;

由于 key [it->first] 已经存在于 path->get_zone_screenline_usage 内的 map 中，所以这只是一个简单的更新操作，不需要分配内存。但是，如果 screenline_usage 是一个空映射，那么每次访问一个新的 [it->first] 意味着它首先必须从堆中分配一个新的映射节点，这很昂贵。

score 2 · Accepted Answer

如果我正确理解您的问题，您暗示插入到本地堆栈分配的 map<> 比插入到您通过引用检索的现有堆分配的 map<> 快得多。

有几种可能会影响性能。不过，我怀疑它与 C++ 参考性能有什么关系。

第一种可能性是，通过更改screenline_usage为引用，您“本质上”是在检索指向现有对象的指针。对象的实际实例可能不是map<int,float>，它可以是从 map 继承的任何东西。例如，它可以是一个为其定义了自定义比较器函数的地图。或具有线程同步逻辑的子类。由于您不知道从对的调用中获得了什么类型m_container[access_mode][zone_id]，因此您很可能会得到一个在插入时表现不佳的子类。（顺便说一句，您可以在调试器中看到返回的类型。）然而，通过创建一个空map<int,float>，您可以保证该类型是实际的 map<>，而不是子类。

假设您正在获取一个实际的 map<> 实例。

第二种可能性是，在您使用的特定 STL 风格中，该map::clear()函数不能有效地清除用于维护关联索引的内部数据结构。我记得， stl::map<> 使用一些复杂的内部散列和桶结构来提供高效的插入和检索功能。但是，尚不清楚调用 clear() 时会发生什么。因此，screenline_usage.clear()与从空地图开始相比，插入地图的效率可能会更低。

最后，让我们假设我错了，这两种可能性都不是。有一种简单的方法可以确定差异是否是使用参考变量的结果。您可以尝试在堆上分配新映射并将其分配给代码中的引用，如下所示：

map<int, float>& screenline_usage = new map<int,float>();

这将帮助您确定插入现有地图和新地图是否存在一些差异，或者是否确实是 screenline_usage 是影响性能的参考。顺便说一句，不要忘记释放这个堆分配的映射，否则最终会导致内存泄漏。

score 1 · Accepted Answer

引用通常在幕后实现为指针。一个例外是，如果为它们分配了一个临时值，那么值的生命周期将延长到引用的生命周期；本质上，引用就是对象。所以，这取决于：

get_combined_screenline_usage

按引用或按值返回。如果是通过引用，引用方式可能会更快。如果是按值，那么旧方式和新方式本质上是做同样的事情，假设编译器做了返回值优化。

在这两种情况下，编译器所做的其他优化（例如内联）可能会掩盖这两种选择的影响；实际上，在不知道您的慢速部分是哪条确切线的情况下，这有点像猜谜游戏。

我建议尝试获取更细粒度的信息，并将其缩小到确切需要这么长时间的行，这会使优化变得容易得多。

（注：

map<int, float>::iterator it = my_screenline_usage.begin(); 
for (; it != my_screenline_usage.end(); ++it)

如果写成可能会更有效

for (map<int, float>::const_iterator it(my_screenline_usage.begin()), end(my_screenline_usage.begin()); it != end; ++it)

)

score 0 · Accepted Answer

我试图弄清楚的问题是为什么当地图是参考时，内部循环需要更长的时间来评估？

我猜想花费很长时间的是对get_zone_screenline_usage: 的调用，并且花费很长时间的原因是特定元素尚不存在，m_container因此必须在返回之前创建和插入。

score 0 · Accepted Answer

0

根据我的更新，我认为这很可能是缓存一致性问题，而不是 C++ 参考问题。

于 2010-12-16T00:48:12.127 回答

c++ - C++中的引用速度

6 回答 6

Related

Reference