Reland "[vm] Only call `.hashCode` once when adding to `Map` and `Set`"
Relanding after https://dart-review.googlesource.com/c/sdk/+/244200.
Original change's description:
> [vm] Only call `.hashCode` once when adding to `Map` and `Set`
>
> The methods to add to hash maps and hash sets are recursive: if the
> index needs to be rehashed then the same method is called again
> after rehashing.
>
> This CL nests the actual implementation in a private method that takes
> the full hashCode as an extra argument.
>
> No significant code size or run time changes are reported on our
> benchmarks. (Our benchmarks do not contain purposefully slow hashCodes.)
>
> Note that hashCode can be called again later if rehashing of the index
> is required on adding subsequent elements.
>
> Bug: https://github.com/dart-lang/sdk/issues/48948
> Change-Id: Ia3ccff9e592d675b4922ac78c4aa7ee0287ecb50
> Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/243623
> Reviewed-by: Martin Kustermann <kustermann@google.com>
> Commit-Queue: Daco Harkes <dacoharkes@google.com>
Change-Id: I033bd7cc29fc812dccb6dccf0c3dca6e22cae2ca
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/248802
Commit-Queue: Tess Strickland <sstrickl@google.com>
Auto-Submit: Daco Harkes <dacoharkes@google.com>
Reviewed-by: Tess Strickland <sstrickl@google.com>
diff --git a/runtime/tests/vm/dart/regress_48948_test.dart b/runtime/tests/vm/dart/regress_48948_test.dart
new file mode 100644
index 0000000..2a334b3
--- /dev/null
+++ b/runtime/tests/vm/dart/regress_48948_test.dart
@@ -0,0 +1,34 @@
+// Copyright (c) 2022, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+// Regression test for https://github.com/dart-lang/sdk/issues/48948.
+
+import 'package:expect/expect.dart';
+
+class Foo {
+ const Foo(this.x, this.y);
+
+ final int x;
+ final int y;
+
+ static int hashCodeCounter = 0;
+
+ @override
+ int get hashCode {
+ hashCodeCounter++;
+ return x.hashCode ^ y.hashCode;
+ }
+}
+
+void main() {
+ final Map<Foo, int> someMap = {};
+ final Set<Foo> someSet = {};
+ Expect.equals(0, Foo.hashCodeCounter);
+
+ someMap[Foo(1, 100)] = 2;
+ Expect.equals(1, Foo.hashCodeCounter);
+
+ someSet.add(Foo(1, 100));
+ Expect.equals(2, Foo.hashCodeCounter);
+}
diff --git a/runtime/tests/vm/dart_2/regress_48948_test.dart b/runtime/tests/vm/dart_2/regress_48948_test.dart
new file mode 100644
index 0000000..0e71942
--- /dev/null
+++ b/runtime/tests/vm/dart_2/regress_48948_test.dart
@@ -0,0 +1,36 @@
+// Copyright (c) 2022, the Dart project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+// Regression test for https://github.com/dart-lang/sdk/issues/48948.
+
+// @dart = 2.9
+
+import 'package:expect/expect.dart';
+
+class Foo {
+ const Foo(this.x, this.y);
+
+ final int x;
+ final int y;
+
+ static int hashCodeCounter = 0;
+
+ @override
+ int get hashCode {
+ hashCodeCounter++;
+ return x.hashCode ^ y.hashCode;
+ }
+}
+
+void main() {
+ final Map<Foo, int> someMap = {};
+ final Set<Foo> someSet = {};
+ Expect.equals(0, Foo.hashCodeCounter);
+
+ someMap[Foo(1, 100)] = 2;
+ Expect.equals(1, Foo.hashCodeCounter);
+
+ someSet.add(Foo(1, 100));
+ Expect.equals(2, Foo.hashCodeCounter);
+}
diff --git a/sdk/lib/_internal/vm/lib/compact_hash.dart b/sdk/lib/_internal/vm/lib/compact_hash.dart
index 8a179fb6..16d85b2 100644
--- a/sdk/lib/_internal/vm/lib/compact_hash.dart
+++ b/sdk/lib/_internal/vm/lib/compact_hash.dart
@@ -345,7 +345,6 @@
for (int j = 0; j < _usedData; j += 2) {
final key = _data[j];
- final value = _data[j + 1];
final fullHash = _hashCode(key);
final hashPattern = _HashBase._hashPattern(fullHash, hashMask, size);
@@ -452,10 +451,10 @@
}
}
- void _insert(K key, V value, int hashPattern, int i) {
+ void _insert(K key, V value, int fullHash, int hashPattern, int i) {
if (_usedData == _data.length) {
_rehash();
- this[key] = value;
+ _set(key, value, fullHash);
} else {
assert(1 <= hashPattern && hashPattern < (1 << 32));
final int index = _usedData >> 1;
@@ -496,8 +495,12 @@
}
void operator []=(K key, V value) {
- final int size = _index.length;
final int fullHash = _hashCode(key);
+ _set(key, value, fullHash);
+ }
+
+ void _set(K key, V value, int fullHash) {
+ final int size = _index.length;
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
final int d =
_findValueOrInsertPoint(key, fullHash, hashPattern, size, _index);
@@ -505,7 +508,7 @@
_data[d] = value;
} else {
final int i = -d;
- _insert(key, value, hashPattern, i);
+ _insert(key, value, fullHash, hashPattern, i);
}
}
@@ -526,7 +529,7 @@
this[key] = value;
} else {
final int i = -d;
- _insert(key, value, hashPattern, i);
+ _insert(key, value, fullHash, hashPattern, i);
}
return value;
}
@@ -832,10 +835,14 @@
}
bool add(E key) {
+ final int fullHash = _hashCode(key);
+ return _add(key, fullHash);
+ }
+
+ bool _add(E key, int fullHash) {
final int size = _index.length;
final int sizeMask = size - 1;
final int maxEntries = size >> 1;
- final int fullHash = _hashCode(key);
final int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size);
int i = _HashBase._firstProbe(fullHash, sizeMask);
int firstDeleted = -1;
@@ -856,7 +863,7 @@
}
if (_usedData == _data.length) {
_rehash();
- add(key);
+ _add(key, fullHash);
} else {
final int insertionPoint = (firstDeleted >= 0) ? firstDeleted : i;
assert(1 <= hashPattern && hashPattern < (1 << 32));
