更新:这应该被认为是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年多。
最佳答案
我已经测试了不同的类实现,可以看到 hashCode 的等待时间。这是有道理的,因为整数的 hashCode 与它所代表的整数完全相同(如果您考虑一下,这是有道理的)。
Object() 的 hashCode 更复杂,需要对一些我不知道的代码进行外部调用。
如果我创建自己的类并使用“始终返回 5”之类的内容覆盖 hashCode 属性,那么我将获得与整数相同的速度。
由于每次向 Map 或 Set 添加内容时都会使用 hashCode(和 ==),因此保持这两个函数尽可能高效非常重要。
对更新 2 的回答
Object() hashCode 属性较慢的原因是它比整数 hashCode 做了很多事情。我检查了源代码,这是它执行的步骤:
如您所见,这比仅获取整数本身的值并将其用作哈希要复杂得多。正如您在代码中看到的那样,甚至还使用了随机生成器。
我应该补充一点,哈希是缓存的,所以这只是第一次调用 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)。
关于performance - 原始类型 HashSet 或 HashMap 比 Object 快 10 倍?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58260908/