[benchmarks] Add benchmark for lists/maps/sets of records
Issue: https://github.com/dart-lang/sdk/issues/49719
Change-Id: I1cb36cc4e690ef463c26c8aa58a2186dfe3290e6
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/273823
Commit-Queue: Alexander Markov <alexmarkov@google.com>
Reviewed-by: Stephen Adams <sra@google.com>
Reviewed-by: Martin Kustermann <kustermann@google.com>
diff --git a/benchmarks/RecordCollections/dart/RecordCollections.dart b/benchmarks/RecordCollections/dart/RecordCollections.dart
new file mode 100644
index 0000000..631fda3
--- /dev/null
+++ b/benchmarks/RecordCollections/dart/RecordCollections.dart
@@ -0,0 +1,487 @@
+// 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.
+
+import 'package:benchmark_harness/benchmark_harness.dart';
+
+// Micro-benchmark for List/Map/Set of records.
+//
+// The goal of this benchmark is to compare and track performance of
+// the most common operations on List/Map/Set of records.
+
+int N = 0;
+int SUM = 0;
+
+bool runtimeTrue = int.parse('1') == 1; // Not known at compile time.
+
+class Pair {
+ final int v0;
+ final int v1;
+ const Pair(this.v0, this.v1);
+ bool operator==(other) => other is Pair && v0 == other.v0 && v1 == other.v1;
+ int get hashCode => Object.hash(v0, v1);
+}
+
+@pragma('vm:never-inline')
+@pragma('dart2js:never-inline')
+List<Object> getPolymorphicListOfClass(int length, bool growable, bool withValues) {
+ if (runtimeTrue) {
+ if (withValues) {
+ return List<Pair>.generate(length, (i) => Pair(i, i), growable: growable);
+ } else {
+ return List<Pair>.filled(length, Pair(-1, -1), growable: growable);
+ }
+ } else {
+ return List<String>.filled(0, '', growable: growable);
+ }
+}
+
+@pragma('vm:never-inline')
+@pragma('dart2js:never-inline')
+List<Object> getPolymorphicListOfRecords(int length, bool growable, bool withValues) {
+ if (runtimeTrue) {
+ if (withValues) {
+ return List<(int, int)>.generate(length, (i) => (i, i), growable: growable);
+ } else {
+ return List<(int, int)>.filled(length, (-1, -1), growable: growable);
+ }
+ } else {
+ return List<String>.filled(0, '', growable: growable);
+ }
+}
+
+class BenchListAddClass extends BenchmarkBase {
+ BenchListAddClass() : super('RecordCollections.ListAdd.Class');
+
+ @override
+ void run() {
+ final list = <Pair>[];
+ for (int i = 0; i < N; ++i) {
+ list.add(Pair(i, i));
+ }
+ if (list[N ~/ 2].v0 != N ~/ 2) throw 'Bad result: ${list[N ~/ 2].v0}';
+ }
+}
+
+class BenchListAddRecord extends BenchmarkBase {
+ BenchListAddRecord() : super('RecordCollections.ListAdd.Record');
+
+ @override
+ void run() {
+ final list = <(int, int)>[];
+ for (int i = 0; i < N; ++i) {
+ list.add((i, i));
+ }
+ if (list[N ~/ 2].$0 != N ~/ 2) throw 'Bad result: ${list[N ~/ 2].$0}';
+ }
+}
+
+class BenchListAddPolyClass extends BenchmarkBase {
+ BenchListAddPolyClass() : super('RecordCollections.ListAddPoly.Class');
+
+ @override
+ void run() {
+ final List<Object> list = getPolymorphicListOfClass(0, runtimeTrue, false);
+ for (int i = 0; i < N; ++i) {
+ list.add(Pair(i, i));
+ }
+ final int mid = (list[N ~/ 2] as Pair).v0;
+ if (mid != N ~/ 2) throw 'Bad result: ${mid}';
+ }
+}
+
+class BenchListAddPolyRecord extends BenchmarkBase {
+ BenchListAddPolyRecord() : super('RecordCollections.ListAddPoly.Record');
+
+ @override
+ void run() {
+ final List<Object> list = getPolymorphicListOfRecords(0, runtimeTrue, false);
+ for (int i = 0; i < N; ++i) {
+ list.add((i, i));
+ }
+ final int mid = (list[N ~/ 2] as (int, int)).$0;
+ if (mid != N ~/ 2) throw 'Bad result: ${mid}';
+ }
+}
+
+class BenchListSetIndexedClass extends BenchmarkBase {
+ BenchListSetIndexedClass() : super('RecordCollections.ListSetIndexed.Class');
+
+ @override
+ void run() {
+ final list = List<Pair>.filled(N, Pair(-1, -1), growable: false);
+ for (int i = 0; i < N; ++i) {
+ list[i] = Pair(i, i);
+ }
+ if (list[N ~/ 2].v0 != N ~/ 2) throw 'Bad result: ${list[N ~/ 2].v0}';
+ }
+}
+
+class BenchListSetIndexedRecord extends BenchmarkBase {
+ BenchListSetIndexedRecord() : super('RecordCollections.ListSetIndexed.Record');
+
+ @override
+ void run() {
+ final list = List<(int, int)>.filled(N, (-1, -1), growable: false);
+ for (int i = 0; i < N; ++i) {
+ list[i] = (i, i);
+ }
+ if (list[N ~/ 2].$0 != N ~/ 2) throw 'Bad result: ${list[N ~/ 2].$0}';
+ }
+}
+
+class BenchListSetIndexedPolyClass extends BenchmarkBase {
+ BenchListSetIndexedPolyClass() : super('RecordCollections.ListSetIndexedPoly.Class');
+
+ @override
+ void run() {
+ final List<Object> list = getPolymorphicListOfClass(N, !runtimeTrue, false);
+ for (int i = 0; i < N; ++i) {
+ list[i] = Pair(i, i);
+ }
+ final int mid = (list[N ~/ 2] as Pair).v0;
+ if (mid != N ~/ 2) throw 'Bad result: ${mid}';
+ }
+}
+
+class BenchListSetIndexedPolyRecord extends BenchmarkBase {
+ BenchListSetIndexedPolyRecord() : super('RecordCollections.ListSetIndexedPoly.Record');
+
+ @override
+ void run() {
+ final List<Object> list = getPolymorphicListOfRecords(N, !runtimeTrue, false);
+ for (int i = 0; i < N; ++i) {
+ list[i] = (i, i);
+ }
+ final int mid = (list[N ~/ 2] as (int, int)).$0;
+ if (mid != N ~/ 2) throw 'Bad result: ${mid}';
+ }
+}
+
+class BenchListGetIndexedClass extends BenchmarkBase {
+ BenchListGetIndexedClass() : super('RecordCollections.ListGetIndexed.Class');
+
+ final list = <Pair>[
+ for (int i = 0; i < N; ++i)
+ Pair(i, i),
+ ];
+
+ @override
+ void run() {
+ int sum = 0;
+ for (int i = 0; i < list.length; ++i) {
+ sum += list[i].v0;
+ }
+ if (sum != SUM) throw 'Bad result: $sum';
+ }
+}
+
+class BenchListGetIndexedRecord extends BenchmarkBase {
+ BenchListGetIndexedRecord() : super('RecordCollections.ListGetIndexed.Record');
+
+ final list = <(int, int)>[
+ for (int i = 0; i < N; ++i)
+ (i, i),
+ ];
+
+ @override
+ void run() {
+ int sum = 0;
+ for (int i = 0; i < list.length; ++i) {
+ sum += list[i].$0;
+ }
+ if (sum != SUM) throw 'Bad result: $sum';
+ }
+}
+
+class BenchListGetIndexedPolyClass extends BenchmarkBase {
+ BenchListGetIndexedPolyClass() : super('RecordCollections.ListGetIndexedPoly.Class');
+
+ final list = getPolymorphicListOfClass(N, runtimeTrue, true) as List<Pair>;
+
+ @override
+ void run() {
+ int sum = 0;
+ for (int i = 0; i < list.length; ++i) {
+ sum += list[i].v0;
+ }
+ if (sum != SUM) throw 'Bad result: $sum';
+ }
+}
+
+class BenchListGetIndexedPolyRecord extends BenchmarkBase {
+ BenchListGetIndexedPolyRecord() : super('RecordCollections.ListGetIndexedPoly.Record');
+
+ final list = getPolymorphicListOfRecords(N, runtimeTrue, true) as List<(int, int)>;
+
+ @override
+ void run() {
+ int sum = 0;
+ for (int i = 0; i < list.length; ++i) {
+ sum += list[i].$0;
+ }
+ if (sum != SUM) throw 'Bad result: $sum';
+ }
+}
+
+class BenchListIterateClass extends BenchmarkBase {
+ BenchListIterateClass() : super('RecordCollections.ListIterate.Class');
+
+ final list = <Pair>[
+ for (int i = 0; i < N; ++i)
+ Pair(i, i),
+ ];
+
+ @override
+ void run() {
+ int sum = 0;
+ for (final v in list) {
+ sum += v.v0;
+ }
+ if (sum != SUM) throw 'Bad result: $sum';
+ }
+}
+
+class BenchListIterateRecord extends BenchmarkBase {
+ BenchListIterateRecord() : super('RecordCollections.ListIterate.Record');
+
+ final list = <(int, int)>[
+ for (int i = 0; i < N; ++i)
+ (i, i),
+ ];
+
+ @override
+ void run() {
+ int sum = 0;
+ for (final v in list) {
+ sum += v.$0;
+ }
+ if (sum != SUM) throw 'Bad result: $sum';
+ }
+}
+
+class BenchListIteratePolyClass extends BenchmarkBase {
+ BenchListIteratePolyClass() : super('RecordCollections.ListIteratePoly.Class');
+
+ final list = getPolymorphicListOfClass(N, runtimeTrue, true) as List<Pair>;
+
+ @override
+ void run() {
+ int sum = 0;
+ for (final v in list) {
+ sum += v.v0;
+ }
+ if (sum != SUM) throw 'Bad result: $sum';
+ }
+}
+
+class BenchListIteratePolyRecord extends BenchmarkBase {
+ BenchListIteratePolyRecord() : super('RecordCollections.ListIteratePoly.Record');
+
+ final list = getPolymorphicListOfRecords(N, runtimeTrue, true) as List<(int, int)>;
+
+ @override
+ void run() {
+ int sum = 0;
+ for (final v in list) {
+ sum += v.$0;
+ }
+ if (sum != SUM) throw 'Bad result: $sum';
+ }
+}
+
+class BenchMapAddClassKey extends BenchmarkBase {
+ BenchMapAddClassKey() : super('RecordCollections.MapAdd.ClassKey');
+
+ @override
+ void run() {
+ final map = <Pair, int>{};
+ for (int i = 0; i < N; ++i) {
+ map[Pair(i, i)] = i;
+ }
+ if (map.length != N) throw 'Bad result: ${map.length}';
+ }
+}
+
+class BenchMapAddRecordKey extends BenchmarkBase {
+ BenchMapAddRecordKey() : super('RecordCollections.MapAdd.RecordKey');
+
+ @override
+ void run() {
+ final map = <(int, int), int>{};
+ for (int i = 0; i < N; ++i) {
+ map[(i, i)] = i;
+ }
+ if (map.length != N) throw 'Bad result: ${map.length}';
+ }
+}
+
+class BenchMapAddClassValue extends BenchmarkBase {
+ BenchMapAddClassValue() : super('RecordCollections.MapAdd.ClassValue');
+
+ @override
+ void run() {
+ final map = <int, Pair>{};
+ for (int i = 0; i < N; ++i) {
+ map[i] = Pair(i, i);
+ }
+ if (map.length != N) throw 'Bad result: ${map.length}';
+ }
+}
+
+class BenchMapAddRecordValue extends BenchmarkBase {
+ BenchMapAddRecordValue() : super('RecordCollections.MapAdd.RecordValue');
+
+ @override
+ void run() {
+ final map = <int, (int, int)>{};
+ for (int i = 0; i < N; ++i) {
+ map[i] = (i, i);
+ }
+ if (map.length != N) throw 'Bad result: ${map.length}';
+ }
+}
+
+class BenchMapLookupClass extends BenchmarkBase {
+ BenchMapLookupClass() : super('RecordCollections.MapLookup.Class');
+
+ final map = <Pair, int>{
+ for (int i = 0; i < N; ++i)
+ Pair(i, i): i,
+ };
+
+ @override
+ void run() {
+ int sum = 0;
+ for (int i = 0; i < N; ++i) {
+ sum += map[Pair(i, i)]!;
+ }
+ if (sum != SUM) throw 'Bad result: ${sum}';
+ }
+}
+
+class BenchMapLookupRecord extends BenchmarkBase {
+ BenchMapLookupRecord() : super('RecordCollections.MapLookup.Record');
+
+ final map = <(int, int), int>{
+ for (int i = 0; i < N; ++i)
+ (i, i): i,
+ };
+
+ @override
+ void run() {
+ int sum = 0;
+ for (int i = 0; i < N; ++i) {
+ sum += map[(i, i)]!;
+ }
+ if (sum != SUM) throw 'Bad result: ${sum}';
+ }
+}
+
+class BenchSetAddClass extends BenchmarkBase {
+ BenchSetAddClass() : super('RecordCollections.SetAdd.Class');
+
+ @override
+ void run() {
+ final set = <Pair>{};
+ for (int i = 0; i < N; ++i) {
+ set.add(Pair(i, i));
+ }
+ if (set.length != N) throw 'Bad result: ${set.length}';
+ }
+}
+
+class BenchSetAddRecord extends BenchmarkBase {
+ BenchSetAddRecord() : super('RecordCollections.SetAdd.Record');
+
+ @override
+ void run() {
+ final set = <(int, int)>{};
+ for (int i = 0; i < N; ++i) {
+ set.add((i, i));
+ }
+ if (set.length != N) throw 'Bad result: ${set.length}';
+ }
+}
+
+class BenchSetLookupClass extends BenchmarkBase {
+ BenchSetLookupClass() : super('RecordCollections.SetLookup.Class');
+
+ final set = <Pair>{
+ for (int i = 0; i < N ~/ 2; ++i)
+ Pair(i * 2, i * 2),
+ };
+
+ @override
+ void run() {
+ int sum = 0;
+ for (int i = 0; i < N; ++i) {
+ sum += set.contains(Pair(i, i)) ? 1 : 0;
+ }
+ if (sum != N ~/ 2) throw 'Bad result: ${sum}';
+ }
+}
+
+class BenchSetLookupRecord extends BenchmarkBase {
+ BenchSetLookupRecord() : super('RecordCollections.SetLookup.Record');
+
+ final set = <(int, int)>{
+ for (int i = 0; i < N ~/ 2; ++i)
+ (i * 2, i * 2),
+ };
+
+ @override
+ void run() {
+ int sum = 0;
+ for (int i = 0; i < N; ++i) {
+ sum += set.contains((i, i)) ? 1 : 0;
+ }
+ if (sum != N ~/ 2) throw 'Bad result: ${sum}';
+ }
+}
+
+void main() {
+ N = int.parse('100000');
+ SUM = N * (N - 1) ~/ 2;
+
+ final benchmarks = [
+ BenchListAddClass(),
+ BenchListAddRecord(),
+ BenchListAddPolyClass(),
+ BenchListAddPolyRecord(),
+
+ BenchListSetIndexedClass(),
+ BenchListSetIndexedRecord(),
+ BenchListSetIndexedPolyClass(),
+ BenchListSetIndexedPolyRecord(),
+
+ BenchListGetIndexedClass(),
+ BenchListGetIndexedRecord(),
+ BenchListGetIndexedPolyClass(),
+ BenchListGetIndexedPolyRecord(),
+
+ BenchListIterateClass(),
+ BenchListIterateRecord(),
+ BenchListIteratePolyClass(),
+ BenchListIteratePolyRecord(),
+
+ BenchMapAddClassKey(),
+ BenchMapAddRecordKey(),
+ BenchMapAddClassValue(),
+ BenchMapAddRecordValue(),
+ BenchMapLookupClass(),
+ BenchMapLookupRecord(),
+
+ BenchSetAddClass(),
+ BenchSetAddRecord(),
+ BenchSetLookupClass(),
+ BenchSetLookupRecord(),
+ ];
+
+ for (final benchmark in benchmarks) {
+ benchmark.warmup();
+ }
+ for (final benchmark in benchmarks) {
+ benchmark.report();
+ }
+}
