performance - 原始类型 HashSet 或 HashMap 比 Object 快 10 倍？

Question

更新:这应该被认为是flutter channel stable v1.9.1+hotfix.4中的一个bug。当切换到 channel 主机时，这是固定的，int 和 Object Sets 具有相同数量级的性能。

基准测试抛出 HashSet<int>平均比 HashSet<Object> 快 10 倍.
这种行为的原因是什么？

当我以一种我期望更高效的方式更改库的内部结构时，我的性能大幅下降(超过一个数量级)。

问题从 HashSet<int>到 HashSet<MyClass> ，我在 HashSet 中运行简单的基准测试时证实了这一点，它添加了 1000 次相同的值。结果是 HashSet<int>平均比 HashSet<Object> 快 10 倍.

从代码设计的角度有什么建议吗？使用 HashSet<MyClass> 时，代码看起来更干净。而不是具有将实例与 int 相关联的其他数据结构。这种性能下降很重要，因为它是库的核心。我发现保持程序高效的唯一方法是使用标识 MyClass 的整数来操作所有内容。

可以在此处找到基准:
https://gist.github.com/icatalud/dc28bd3bdd7c13b39c308b7abb9a9d8c

添加到 Set 的函数如下:

plainAddSet<T>(T obj, [int n = 1000]) {
  var s = Set<T>();
  for (var i = 0; i < n; i++) {
    s.add(obj);
  }
}

更新:运行更多测试让我找到了性能下降的根本原因。 hashCode getter 非常慢。在下面的类中如果hashCode方法没有被覆盖的话，耗时20倍，甚至比Object还要慢。否则它需要比 int Set 多一点。

class Identifiable {
  static int lastId = 0;
  int id;
  Identifiable() : id = lastId++;

  // Not overriding this getter, causes the benchmark to take 20 times longer.
  int get hashCode => id;

  bool operator ==(other) =>
      other.runtimeType == runtimeType &&
      hashCode == other.hashCode;
}

更新 2:尽管如此，理解为什么重写 == 运算符并从那里访问 hashCode 比保留 Object 默认实现(比 int 慢 10 倍以上)慢三倍还是很有趣的。

class Identifiable {
  bool operator ==(other) =>
      other.runtimeType == runtimeType &&
      other.hashCode == hashCode;
}

更新 3:有一个 open issue关于这个在 dart SDK 存储库中。它已经存在了4年多。

Answer 1

我已经测试了不同的类实现，可以看到 hashCode 的等待时间。这是有道理的，因为整数的 hashCode 与它所代表的整数完全相同(如果您考虑一下，这是有道理的)。

Object() 的 hashCode 更复杂，需要对一些我不知道的代码进行外部调用。

如果我创建自己的类并使用“始终返回 5”之类的内容覆盖 hashCode 属性，那么我将获得与整数相同的速度。

由于每次向 Map 或 Set 添加内容时都会使用 hashCode(和 ==)，因此保持这两个函数尽可能高效非常重要。

对更新 2 的回答

Object() hashCode 属性较慢的原因是它比整数 hashCode 做了很多事情。我检查了源代码，这是它执行的步骤:

hashCode 的实现在这里打了补丁:https://github.com/dart-lang/sdk/blob/e88057fe04deccb9468d93785f3fd43523c2f91f/sdk_nnbd/lib/_internal/vm/lib/object_patch.dart#L41

最终调用了一个名为 _objectHashCode 的静态方法:https://github.com/dart-lang/sdk/blob/7c1821c4aae86db4febf3c0656985e23df31be0f/sdk/lib/_internal/vm/lib/object_patch.dart#L25

_objectHashCode 做的第一件事就是通过调用 _setHash 来调用外部方法。可以在这里找到它的实现:https://github.com/dart-lang/sdk/blob/84db16381d8efbb4fdbcfa79ef411a5ec8809bc7/runtime/lib/object.cc#L34

如您所见，这比仅获取整数本身的值并将其用作哈希要复杂得多。正如您在代码中看到的那样，甚至还使用了随机生成器。

我应该补充一点，哈希是缓存的，所以这只是第一次调用 hashCode 它真的很慢。但是正如您所看到的，缓存版本仍然是一个外部调用，它比获取一个整数变量更昂贵。

“提出解决此问题的方法”的更新

这发生在 Flutter Channel stable v1.9.1+hotfix.4 中，但在 master 中已修复。不需要在下一个 Flutter 版本中实现。

如果您现在不能接受标准 hashCode 方法的性能，我认为唯一的另一种方法是手动缓存它，例如:

class ObjectWithCachedHash {
  int _hashCodeCache;

  @override
  int get hashCode => _hashCodeCache ??= super.hashCode;
}

仅当 hashCode 不依赖于对象内部的任何值时才应该这样做(例如，纯粹基于实例的标准 hashCode 实现)。

更新了问题链接

hashCode 缓慢的问题是一个已知问题(感谢 Ignacio Catalan 指出这一点):

https://github.com/dart-lang/sdk/issues/24206

应该注意的是，在这个 stackoverflow 问题中发现的性能问题更可能与最近在 master 上修复的回归有关:

https://github.com/dart-lang/sdk/issues/24206#issuecomment-539448012

但是这个回归的修复只会修复 x64 的问题，所以 32 位架构(以及所有 ARM 架构)仍然会受到性能问题的影响(这是另一个与回归无关的问题)。

因此，对于 32 位和 ARM 用户的建议是在本地缓存 hashCode 值，如果您的代码依赖于 Object.hashCode 并且要进行大量比较(例如，使用带有大量对象的 Map 或 Set)。