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

Question

更新： 这应该算是flutter channel stable v1.9.1+hotfix.4的bug。当切换到主通道时，这是固定的，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 非常慢。下面class如果不重写hashCode方法，比Object.hashCode方法耗时要长20倍，甚至慢。否则它比一个 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 比保留对象默认实现慢三倍（这比 int 慢 10 倍以上）。

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

更新 3： 在 dart SDK 存储库中有关于此的 open issue。它已经存在 4 年多了。

Answer 1

我已经用不同的 class 实现进行了测试，可以看到等待时间是针对 hashCode 的。这是有道理的，因为整数的 hashCode 与它所代表的整数相同（如果你考虑一下就有意义）。

Object()的hashCode比较复杂，需要外部调用一些我不知道的代码。

如果我创建自己的 class 并用 "always return 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

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

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

"Proposing a workaround to this issue"

更新

这在 flutter channel stable v1.9.1+hotfix.4 中发生，但在 master 中已修复。应该没有必要在下一个 Flutter 版本中实现。

如果你现在不能接受标准 hashCode 方法的性能，我认为唯一的另一种方法是像这样手动缓存它：

class ObjectWithCachedHash {
  int _hashCodeCache;

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

仅当 hashCode 不依赖于对象内的任何值时才应执行此操作（例如，纯粹基于实例的标准 hashCode 实现）。

更新 link 发布

缓慢的 hashCode 问题是一个已知问题（感谢 Ignacio Catalan 指出）：

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

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

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

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

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

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

Primitive type HashSet or HashMap 10 times faster than Object?

performance

dart

hashmap

hashset

primitive