perf: improve equality comparison performance (#173)
Co-authored-by: Felix Angelov <felangelov@gmail.com>
diff --git a/benchmarks/README.md b/benchmarks/README.md
index 474db23..fe90cb0 100644
--- a/benchmarks/README.md
+++ b/benchmarks/README.md
@@ -11,82 +11,160 @@
## Results
+**JIT**
+
```
EmptyEquatable
- total runs: 2 064 037
+ total runs: 2 729 471
total time: 2.0000 s
average run: 0 μs
runs/second: Infinity
- units: 100
+ units: 100
units/second: Infinity
time per unit: 0.0000 μs
PrimitiveEquatable
- total runs: 729 555
+ total runs: 669 972
total time: 2.0000 s
average run: 2 μs
- runs/second: 500 000
- units: 100
- units/second: 50 000 000
+ runs/second: 500 000
+ units: 100
+ units/second: 50 000 000
time per unit: 0.0200 μs
CollectionEquatable (static, small)
- total runs: 51 944
+ total runs: 144 932
total time: 2.0000 s
- average run: 38 μs
- runs/second: 26 316
- units: 100
- units/second: 2 631 579
- time per unit: 0.3800 μs
+ average run: 13 μs
+ runs/second: 76 923
+ units: 100
+ units/second: 7 692 308
+ time per unit: 0.1300 μs
CollectionEquatable (static, medium)
- total runs: 44 572
+ total runs: 84 533
total time: 2.0000 s
- average run: 44 μs
- runs/second: 22 727
- units: 100
- units/second: 2 272 727
- time per unit: 0.4400 μs
+ average run: 23 μs
+ runs/second: 43 478
+ units: 100
+ units/second: 4 347 826
+ time per unit: 0.2300 μs
CollectionEquatable (static, large)
- total runs: 21 027
+ total runs: 16 457
total time: 2.0001 s
- average run: 95 μs
- runs/second: 10 526
- units: 100
- units/second: 1 052 632
- time per unit: 0.9500 μs
+ average run: 121 μs
+ runs/second: 8 264.5
+ units: 100
+ units/second: 826 446
+ time per unit: 1.2100 μs
CollectionEquatable (dynamic, small)
- total runs: 400 934
+ total runs: 388 236
+ total time: 2.0000 s
+ average run: 5 μs
+ runs/second: 200 000
+ units: 100
+ units/second: 20 000 000
+ time per unit: 0.0500 μs
+
+CollectionEquatable (dynamic, medium)
+ total runs: 382 155
+ total time: 2.0000 s
+ average run: 5 μs
+ runs/second: 200 000
+ units: 100
+ units/second: 20 000 000
+ time per unit: 0.0500 μs
+
+CollectionEquatable (dynamic, large)
+ total runs: 390 713
+ total time: 2.0000 s
+ average run: 5 μs
+ runs/second: 200 000
+ units: 100
+ units/second: 20 000 000
+ time per unit: 0.0500 μs
+```
+
+**AOT**
+
+```
+EmptyEquatable
+ total runs: 1 615 534
+ total time: 2.0000 s
+ average run: 1 μs
+ runs/second: 1 000 000
+ units: 100
+ units/second: 100 000 000
+ time per unit: 0.0100 μs
+
+PrimitiveEquatable
+ total runs: 928 013
+ total time: 2.0000 s
+ average run: 2 μs
+ runs/second: 500 000
+ units: 100
+ units/second: 50 000 000
+ time per unit: 0.0200 μs
+
+CollectionEquatable (static, small)
+ total runs: 128 224
+ total time: 2.0000 s
+ average run: 15 μs
+ runs/second: 66 667
+ units: 100
+ units/second: 6 666 667
+ time per unit: 0.1500 μs
+
+CollectionEquatable (static, medium)
+ total runs: 104 624
+ total time: 2.0000 s
+ average run: 19 μs
+ runs/second: 52 632
+ units: 100
+ units/second: 5 263 158
+ time per unit: 0.1900 μs
+
+CollectionEquatable (static, large)
+ total runs: 33 653
+ total time: 2.0000 s
+ average run: 59 μs
+ runs/second: 16 949
+ units: 100
+ units/second: 1 694 915
+ time per unit: 0.5900 μs
+
+CollectionEquatable (dynamic, small)
+ total runs: 483 177
total time: 2.0000 s
average run: 4 μs
- runs/second: 250 000
- units: 100
- units/second: 25 000 000
+ runs/second: 250 000
+ units: 100
+ units/second: 25 000 000
time per unit: 0.0400 μs
CollectionEquatable (dynamic, medium)
- total runs: 400 408
+ total runs: 488 550
total time: 2.0000 s
average run: 4 μs
- runs/second: 250 000
- units: 100
- units/second: 25 000 000
+ runs/second: 250 000
+ units: 100
+ units/second: 25 000 000
time per unit: 0.0400 μs
CollectionEquatable (dynamic, large)
- total runs: 400 966
+ total runs: 494 041
total time: 2.0000 s
average run: 4 μs
- runs/second: 250 000
- units: 100
- units/second: 25 000 000
+ runs/second: 250 000
+ units: 100
+ units/second: 25 000 000
time per unit: 0.0400 μs
```
-_Last Updated: June 3, 2024 using `725b76c9ef072695f3ae4f036c4fa5e015528f13`_
+_Last Updated: November 20, 2024 using `29e6c77a2e6b25e35cce66276bc2afeab1c805bd`_
_MacBook Pro (M1 Pro, 16GB RAM)_
-Dart SDK version: 3.5.0-218.0.dev (dev) (Mon Jun 3 13:02:57 2024 -0700) on "macos_arm64"
+Dart SDK version: Dart SDK version: 3.5.4 (stable) (Wed Oct 16 16:18:51 2024 +0000) on "macos_arm64"
diff --git a/benchmarks/pubspec.yaml b/benchmarks/pubspec.yaml
index 380774d..4ab5d9e 100644
--- a/benchmarks/pubspec.yaml
+++ b/benchmarks/pubspec.yaml
@@ -2,7 +2,7 @@
publish_to: none
environment:
- sdk: ">=2.12.0 <3.0.0"
+ sdk: ">=3.5.0 <4.0.0"
dependencies:
equatable: ^2.0.0
diff --git a/lib/src/equatable.dart b/lib/src/equatable.dart
index a23801f..6b4445b 100644
--- a/lib/src/equatable.dart
+++ b/lib/src/equatable.dart
@@ -46,7 +46,7 @@
return identical(this, other) ||
other is Equatable &&
runtimeType == other.runtimeType &&
- equals(props, other.props);
+ iterableEquals(props, other.props);
}
@override
diff --git a/lib/src/equatable_mixin.dart b/lib/src/equatable_mixin.dart
index b4d376d..b69db15 100644
--- a/lib/src/equatable_mixin.dart
+++ b/lib/src/equatable_mixin.dart
@@ -22,7 +22,7 @@
return identical(this, other) ||
other is EquatableMixin &&
runtimeType == other.runtimeType &&
- equals(props, other.props);
+ iterableEquals(props, other.props);
}
@override
diff --git a/lib/src/equatable_utils.dart b/lib/src/equatable_utils.dart
index 301d81f..615b002 100644
--- a/lib/src/equatable_utils.dart
+++ b/lib/src/equatable_utils.dart
@@ -6,32 +6,62 @@
return _finish(props == null ? 0 : props.fold(0, _combine));
}
-const DeepCollectionEquality _equality = DeepCollectionEquality();
-
-/// Determines whether [list1] and [list2] are equal.
-bool equals(List<Object?>? list1, List<Object?>? list2) {
- if (identical(list1, list2)) return true;
- if (list1 == null || list2 == null) return false;
- final length = list1.length;
- if (length != list2.length) return false;
-
- for (var i = 0; i < length; i++) {
- final unit1 = list1[i];
- final unit2 = list2[i];
-
- if (_isEquatable(unit1) && _isEquatable(unit2)) {
- if (unit1 != unit2) return false;
- } else if (unit1 is Iterable || unit1 is Map) {
- if (!_equality.equals(unit1, unit2)) return false;
- } else if (unit1?.runtimeType != unit2?.runtimeType) {
- return false;
- } else if (unit1 != unit2) {
- return false;
- }
+/// Determines whether two iterables are equal.
+@pragma('vm:prefer-inline')
+bool iterableEquals(Iterable<Object?> a, Iterable<Object?> b) {
+ assert(
+ a is! Set && b is! Set,
+ "iterableEquals doesn't support Sets. Use setEquals instead.",
+ );
+ if (identical(a, b)) return true;
+ if (a.length != b.length) return false;
+ for (var i = 0; i < a.length; i++) {
+ if (!objectsEquals(a.elementAt(i), b.elementAt(i))) return false;
}
return true;
}
+/// Determines whether two sets are equal.
+bool setEquals(Set<Object?> a, Set<Object?> b) {
+ if (identical(a, b)) return true;
+ if (a.length != b.length) return false;
+ for (final element in a) {
+ if (!b.any((e) => objectsEquals(element, e))) return false;
+ }
+ return true;
+}
+
+/// Determines whether two maps are equal.
+bool mapEquals(Map<Object?, Object?> a, Map<Object?, Object?> b) {
+ if (identical(a, b)) return true;
+ if (a.length != b.length) return false;
+ for (final key in a.keys) {
+ if (!objectsEquals(a[key], b[key])) return false;
+ }
+ return true;
+}
+
+/// Determines whether two objects are equal.
+@pragma('vm:prefer-inline')
+bool objectsEquals(Object? a, Object? b) {
+ if (identical(a, b)) return true;
+ if (_isEquatable(a) && _isEquatable(b)) {
+ return a == b;
+ } else if (a is Set && b is Set) {
+ return setEquals(a, b);
+ } else if (a is Iterable && b is Iterable) {
+ return iterableEquals(a, b);
+ } else if (a is Map && b is Map) {
+ return mapEquals(a, b);
+ } else if (a?.runtimeType != b?.runtimeType) {
+ return false;
+ } else if (a != b) {
+ return false;
+ }
+ return true;
+}
+
+@pragma('vm:prefer-inline')
bool _isEquatable(Object? object) {
return object is Equatable || object is EquatableMixin;
}
diff --git a/test/equatable_utils_test.dart b/test/equatable_utils_test.dart
new file mode 100644
index 0000000..bea9f88
--- /dev/null
+++ b/test/equatable_utils_test.dart
@@ -0,0 +1,266 @@
+import 'package:equatable/equatable.dart';
+import 'package:equatable/src/equatable_utils.dart';
+import 'package:test/test.dart';
+
+class Person with EquatableMixin {
+ Person({required this.name});
+
+ final String name;
+
+ @override
+ List<Object?> get props => [name];
+}
+
+void main() {
+ final bob = Person(name: 'Bob');
+ final alice = Person(name: 'Alice');
+ final aliceCopy = Person(name: 'Alice');
+
+ group('iterableEquals', () {
+ test('returns true for identical props', () {
+ final value = [Object()];
+ expect(iterableEquals(value, value), isTrue);
+ });
+
+ test('returns true for empty iterables', () {
+ expect(iterableEquals([], []), isTrue);
+ });
+
+ test('returns false when props differ in length', () {
+ final object = Object();
+ expect(iterableEquals([object], [object, object]), isFalse);
+ });
+
+ test('uses == when props are equatable', () {
+ expect(iterableEquals([alice], [aliceCopy]), isTrue);
+ expect(iterableEquals([bob], [bob]), isTrue);
+ expect(iterableEquals([alice], [bob]), isFalse);
+ expect(iterableEquals([bob], [alice]), isFalse);
+ expect(iterableEquals([alice, null], [alice, -1]), isFalse);
+ });
+
+ test('returns false for iterables with different elements', () {
+ final iterable1 = [1, 2, 3];
+ final iterable2 = [1, 2, 4];
+ expect(iterableEquals(iterable1, iterable2), isFalse);
+ });
+
+ test(
+ 'returns false for iterable with same elements '
+ 'but different order', () {
+ final iterable1 = [1, 2, 3];
+ final iterable2 = [1, 3, 2];
+ expect(iterableEquals(iterable1, iterable2), isFalse);
+ });
+
+ test('returns true for nested identical iterables', () {
+ final iterable1 = [
+ [bob, alice],
+ [alice, bob],
+ ];
+ final iterable2 = [
+ [bob, alice],
+ [alice, bob],
+ ];
+ expect(iterableEquals(iterable1, iterable2), isTrue);
+ });
+
+ test('returns false for nested iterables with different elements', () {
+ final iterable1 = [
+ [bob, 2],
+ [3, 4],
+ ];
+ final iterable2 = [
+ [bob, 2],
+ [3, 5],
+ ];
+ expect(iterableEquals(iterable1, iterable2), isFalse);
+ });
+ });
+
+ group('setEquals', () {
+ test('returns true for identical sets', () {
+ final set1 = {1, 2, 3};
+ final set2 = {1, 2, 3};
+ expect(setEquals(set1, set2), isTrue);
+ });
+
+ test('returns true for identical sets with elements in different order',
+ () {
+ final set1 = {1, 3, 2};
+ final set2 = {1, 2, 3};
+ expect(setEquals(set1, set2), isTrue);
+ });
+
+ test('returns false for sets of different lengths', () {
+ final set1 = {1, 2, 3};
+ final set2 = {1, 2};
+ expect(setEquals(set1, set2), isFalse);
+ });
+
+ test('returns false for sets with different elements', () {
+ final set1 = {1, 2, 3};
+ final set2 = {1, 2, 4};
+ expect(setEquals(set1, set2), isFalse);
+ });
+
+ test('uses == when props are equatable', () {
+ expect(setEquals({alice}, {aliceCopy}), isTrue);
+ expect(setEquals({bob}, {bob}), isTrue);
+ expect(setEquals({alice}, {bob}), isFalse);
+ expect(setEquals({bob}, {alice}), isFalse);
+ expect(setEquals({alice, null}, {alice, -1}), isFalse);
+ });
+
+ test('returns true for nested identical sets', () {
+ final set1 = {
+ {alice, bob},
+ {alice, bob},
+ };
+ final set2 = {
+ {alice, bob},
+ {alice, bob},
+ };
+ expect(setEquals(set1, set2), isTrue);
+ });
+
+ test('returns false for nested sets with different elements', () {
+ final set1 = {
+ {bob, 2},
+ {3, 4},
+ };
+ final set2 = {
+ {bob, 2},
+ {3, 5},
+ };
+ expect(setEquals(set1, set2), isFalse);
+ });
+
+ test('returns true for empty sets', () {
+ expect(setEquals({}, {}), isTrue);
+ });
+
+ test('returns false for sets with different types', () {
+ final set1 = {1, '2', 3};
+ final set2 = {1, 2, 3};
+ expect(setEquals(set1, set2), isFalse);
+ });
+ });
+
+ group('mapEquals', () {
+ test('returns true for identical maps', () {
+ final map1 = {'a': 1, 'b': 2, 'c': 3};
+ final map2 = {'a': 1, 'b': 2, 'c': 3};
+ expect(mapEquals(map1, map2), isTrue);
+ });
+
+ test(
+ 'returns true for identical maps with elements in different order',
+ () {
+ final map1 = {'a': 1, 'c': 3, 'b': 2};
+ final map2 = {'a': 1, 'b': 2, 'c': 3};
+ expect(mapEquals(map1, map2), isTrue);
+ },
+ );
+
+ test('uses == when props are equatable', () {
+ expect(mapEquals({'a': alice}, {'a': aliceCopy}), isTrue);
+ expect(mapEquals({alice: 'a'}, {aliceCopy: 'a'}), isTrue);
+ expect(mapEquals({'a': bob}, {'a': bob}), isTrue);
+ });
+
+ test('returns false for maps of different lengths', () {
+ final map1 = {'a': 1, 'b': 2, 'c': 3};
+ final map2 = {'a': 1, 'b': 2};
+ expect(mapEquals(map1, map2), isFalse);
+ });
+
+ test('returns false for maps with different keys', () {
+ final map1 = {'a': 1, 'b': 2, 'c': 3};
+ final map2 = {'a': 1, 'b': 2, 'd': 3};
+ expect(mapEquals(map1, map2), isFalse);
+ });
+
+ test('returns false for maps with different values', () {
+ final map1 = {'a': 1, 'b': 2, 'c': 3};
+ final map2 = {'a': 1, 'b': 2, 'c': 4};
+ expect(mapEquals(map1, map2), isFalse);
+ });
+
+ test('returns true for nested identical maps', () {
+ final map1 = {
+ 'a': {'x': 1, 'y': 2},
+ 'b': {'z': 3},
+ };
+ final map2 = {
+ 'a': {'x': 1, 'y': 2},
+ 'b': {'z': 3},
+ };
+ expect(mapEquals(map1, map2), isTrue);
+ });
+
+ test('returns false for nested maps with different elements', () {
+ final map1 = {
+ 'a': {'x': 1, 'y': 2},
+ 'b': {'z': 3},
+ };
+ final map2 = {
+ 'a': {'x': 1, 'y': 2},
+ 'b': {'z': 4},
+ };
+ expect(mapEquals(map1, map2), isFalse);
+ });
+
+ test('returns true for empty maps', () {
+ expect(mapEquals({}, {}), isTrue);
+ });
+
+ test('returns false for maps with same keys but different values', () {
+ final map1 = {'a': 1, 'b': '2', 'c': 3};
+ final map2 = {'a': 1, 'b': 2, 'c': 3};
+ expect(mapEquals(map1, map2), isFalse);
+ });
+ });
+
+ group('objectsEquals', () {
+ test('returns true for identical objects', () {
+ final object = Object();
+ expect(objectsEquals(object, object), isTrue);
+ });
+
+ test('returns true for same objects', () {
+ const object1 = 'object';
+ // ignore: prefer_const_declarations
+ final object2 = 'object';
+ expect(objectsEquals(object1, object2), isTrue);
+ });
+
+ test('returns true for equatable objects', () {
+ expect(objectsEquals(alice, aliceCopy), isTrue);
+ expect(objectsEquals(bob, bob), isTrue);
+ });
+
+ test('returns false for different objects', () {
+ expect(objectsEquals(alice, bob), isFalse);
+ expect(objectsEquals(bob, alice), isFalse);
+ });
+
+ test('returns true for same lists', () {
+ expect(objectsEquals([1, 2, 3], [1, 2, 3]), isTrue);
+ });
+
+ test('returns true for same sets', () {
+ expect(objectsEquals({1, 2, 3}, {1, 2, 3}), isTrue);
+ expect(objectsEquals({1, 3, 2}, {1, 2, 3}), isTrue);
+ });
+
+ test('returns true for same maps', () {
+ expect(objectsEquals({'a': 1, 'b': 2}, {'a': 1, 'b': 2}), isTrue);
+ expect(objectsEquals({'c': 3, 'b': 2}, {'b': 2, 'c': 3}), isTrue);
+ });
+
+ test('returns false for different types', () {
+ expect(objectsEquals(1, '1'), isFalse);
+ });
+ });
+}
