这是因为两次查找而不是一次而变慢了吗？

Question

当我想确保我想要使用的条目存在时,我通常会这样做.

#include <unordered_map>

struct type { int member; };
std::unordered_map<type> map;

if (map.find(key) != map.end())
    map[key].member = 42;

但是,我认为它key在哈希映射中执行两次查找.这会缓存查找.

#include <unordered_map>

struct type { int member; };
std::unordered_map<type> map;

auto find = map.find(key);
if (find != map.end())
    find->second.member = 42;

第一种选择感觉更具表现力.它真的慢吗？

Answer 1

它可能更慢,它可能不会(你现在正在"加速"中进行额外的写入)但是在编写代码时真的不应该担心这种小的优化.写清楚的表达代码.然后,如果您的程序确实太慢,请在其上运行分析工具并找到您的瓶颈.如果这个代码是实际上是一个真正的问题,然后才把试试你的"加快",看看它是否重要.

Answer 2

是的,因为你搜索了两次密钥:map[key]搜索完全相同的密钥map.find,你扔掉了结果.

这就像打开一个抽屉,看看是否有一个给定的物体,说"啊是的!" 并关闭抽屉,然后再次打开它并研究对象进行更改.

第二个代码打开抽屉,搜索对象并进行更改.

可以存在允许避免双重搜索的编译器优化,或者可以在恒定时间内减少搜索的编译器优化,并且可以存在允许避免auto find变量存储在存储器上的编译器优化(它可以是CPU寄存器,因为它用法非常本地化).

整个问题实际上会减少两次哈希计算两次的时间(并且在哈希冲突的情况下遍历最终的映射槽)以及访问额外变量的时间:

2*H < H+M

这意味着H < M.如果M是一个寄存器而H不是微不足道的,那么很难H小于M.

Answer 3

是的,它可能会比较慢,但可能不是可测量慢.还有一些额外的工作:

1. 散列可能会被计算两次,除非你有足够的智能编译器,使用像pure或const这样的供应商扩展或使用类似的方法.请注意,如果散列是微不足道的,并且编译器知道它的代码,那么大多数编译器现在可能都足够聪明.
2. 需要第二次找到存储桶的位置(除非编译器会注意到这是相同的哈希值,因此不需要重新计算)
3. 需要执行碰撞列表的遍历(或者根据冲突解决方案的类似方法).再次 - 足够聪明的编译器可能会注意到我们正在做两次,我们实际上并没有修改任何东西等等.我们现在可能有这样的编译器但是我不能100%确定我们是否在那里.即使它们不是,它们也是高速缓存的读取,并且它们可能不会施加任何显着的成本(例如,与哈希或错过读取相比).没有详细讨论处理器架构L1 $读取命中在i7上需要大约4个周期的延迟(来自内存的数据,可能是错误的),处理器在等待它时可能会做其他工作.

总结如果:

• 您的哈希函数很昂贵(例如,它需要获取字符串的哈希值).
• 编译器不够智能推断出哈希函数不会修改对象并确实返回相同的值.
• 它是内循环中的代码.

然后你可能会看到差异.

最后一句话 - 它可能无关紧要,它不是很大的架构差异,而是5s优化.因此,当分析器显示此功能导致速度减慢时,请编写更容易维护的内容并重新查看问题.