Repository: intel/rohd (dart)

Issue:
Performance bug: List view wrapping a Set for `Module.subModules`
### Describe the bug

In `Module`, the `subModules` API uses an `UnmodifiableListView` to view a collection `_modules` which is a `Set`.  When `subModules` is iterated upon, this gets a huge performance penalty when the number of sub-modules is large.  This was noticed in long run-times for generating SystemVerilog due to a `for (final subModule in module.subModules)` in `_SynthModuleDefinition` in "systemverilog.dart".

### To Reproduce

Create a large (~50k originally found this) number of sub-modules within a module and generate the SystemVerilog.

### Expected behavior

Fast

### Actual behavior

Slow

### Additional: Dart SDK info

_No response_

### Additional: pubspec.yaml

_No response_

### Additional: Context

We should create a benchmark that reproduces and protects against this issue.

We should do a review for any other similar issues.

Pull request:
<!-- Please make sure you check out the contribution guidelines before submitting a pull request! -->

## Description & Motivation

See #489 for the initial bug which started this PR.

This PR includes changes to support efficient iteration and search through collections in multiple APIs where incorrect usage of collections and unmodifiable views could cause severe performance issues for large numbers of elements.

Also, this adds an `UnmodifiableTraverseableCollectionView` to help support the use cases.

## Related Issue(s)

Fix #489 

## Testing

- Added a new benchmark that (practically) never finishes pre-fix for #489, but now finishes quickly
- Added unit tests for `UnmodifiableTraverseableCollectionView` and `TraverseableCollection`
- Existing unit tests cover functionality

## Backwards-compatibility

> Is this a breaking change that will not be backwards-compatible? If yes, how so?

Only performance changes should be visible in existing APIs.

## Documentation

> Does the change require any updates to documentation? If so, where? Are they included?

No

Patch:
diff --git a/benchmark/benchmark.dart b/benchmark/benchmark.dart
index f4ee2ad89..310eaf436 100644
--- a/benchmark/benchmark.dart
+++ b/benchmark/benchmark.dart
@@ -1,4 +1,4 @@
-// Copyright (C) 2022-2023 Intel Corporation
+// Copyright (C) 2022-2024 Intel Corporation
 // SPDX-License-Identifier: BSD-3-Clause
 //
 // benchmark.dart
@@ -11,6 +11,7 @@ import 'byte_enable_benchmark.dart';
 import 'comb_guard_fanout_benchmark.dart';
 import 'logic_value_of_benchmark.dart';
 import 'many_seq_and_comb_benchmark.dart' as many_seq_and_comb;
+import 'many_submodules_benchmark.dart';
 import 'pipeline_benchmark.dart';
 import 'ssa_driver_search_benchmark.dart';
 import 'wave_dump_benchmark.dart';
@@ -23,4 +24,5 @@ void main() async {
   await many_seq_and_comb.main();
   await CombGuardFanoutBenchmark().report();
   SsaDriverSearchBenchmark().report();
+  await ManySubmodulesBenchmark().report();
 }
diff --git a/benchmark/many_submodules_benchmark.dart b/benchmark/many_submodules_benchmark.dart
new file mode 100644
index 000000000..763261a4c
--- /dev/null
+++ b/benchmark/many_submodules_benchmark.dart
@@ -0,0 +1,42 @@
+// Copyright (C) 2024 Intel Corporation
+// SPDX-License-Identifier: BSD-3-Clause
+//
+// many_submodules_benchmark.dart
+// A benchmarking test for a large number of submodules.
+//
+// 2024 June 12
+// Author: Max Korbel <max.korbel@intel.com>
+
+import 'package:benchmark_harness/benchmark_harness.dart';
+import 'package:rohd/rohd.dart';
+
+class ManySubmodulesModule extends Module {
+  late final Logic y;
+  ManySubmodulesModule(Logic x, {int numSubModules = 0}) {
+    x = addInput('x', x);
+    y = addOutput('y');
+
+    var intermediate = x;
+
+    for (var i = 0; i < numSubModules; i++) {
+      intermediate = ManySubmodulesModule(intermediate).y;
+    }
+
+    y <= intermediate;
+  }
+}
+
+class ManySubmodulesBenchmark extends AsyncBenchmarkBase {
+  ManySubmodulesBenchmark() : super('ManySubmodules');
+
+  @override
+  Future<void> run() async {
+    final dut = ManySubmodulesModule(Logic(), numSubModules: 10000);
+    await dut.build();
+    dut.generateSynth();
+  }
+}
+
+Future<void> main() async {
+  await ManySubmodulesBenchmark().report();
+}
diff --git a/lib/src/collections/traverseable_collection.dart b/lib/src/collections/traverseable_collection.dart
index a904eb014..6599d056a 100644
--- a/lib/src/collections/traverseable_collection.dart
+++ b/lib/src/collections/traverseable_collection.dart
@@ -1,13 +1,12 @@
-// Copyright (C) 2021-2023 Intel Corporation
+// Copyright (C) 2021-2024 Intel Corporation
 // SPDX-License-Identifier: BSD-3-Clause
 //
 // traverseable_collection.dart
 // Efficient implementation of a set-like datastructure that also has fast
-// index access
+// index access.
 //
 // 2021 July 13
 // Author: Max Korbel <max.korbel@intel.com>
-//
 
 import 'dart:collection';
 
@@ -16,19 +15,23 @@ import 'dart:collection';
 /// This collection stores all data twice: once in a [Set] and once in a [List].
 /// For index access, it uses the [List].  For [contains], it uses the [Set].
 /// Other operations like [add] and [remove] pay the penalty of performing
-/// the operation twice, once oneach collection.
+/// the operation twice, once on each collection.
 ///
 /// In situations where it is necessary to iterate through and frequently access
 /// elements by index, but also check whether a certain element is contained
 /// wihin it, and there are many elements, this implementation is substantially
 /// faster than using either a [Set] or a [List].
-class TraverseableCollection<T> {
-  final Set<T> _set = HashSet<T>();
-  final List<T> _list = <T>[];
+class TraverseableCollection<T> with IterableMixin<T> {
+  /// The underlying [Set] that stores the data.
+  late final Set<T> _set = HashSet<T>();
+
+  /// The underlying [List] that stores the data.
+  late final List<T> _list = <T>[];
 
   /// The number of objects in this collection.
   ///
   /// The valid indices are 0 through [length] - 1.
+  @override
   int get length => _list.length;
 
   /// Adds an element to the collection if it is not already present.
@@ -60,5 +63,27 @@ class TraverseableCollection<T> {
   T operator [](int index) => _list[index];
 
   /// Whether [item] is in the collection.
-  bool contains(T item) => _set.contains(item);
+  @override
+  bool contains(Object? item) => item is T && _set.contains(item);
+
+  @override
+  Iterator<T> get iterator => _list.iterator;
+}
+
+/// An unmodifiable view of a [TraverseableCollection], similar to
+/// [UnmodifiableListView] and [UnmodifiableSetView].
+class UnmodifiableTraverseableCollectionView<T>
+    extends TraverseableCollection<T> {
+  /// The source [TraverseableCollection] that this view is looking at.
+  final TraverseableCollection<T> _source;
+
+  /// Creates an unmodifiable view of [source].
+  UnmodifiableTraverseableCollectionView(TraverseableCollection<T> source)
+      : _source = source;
+
+  @override
+  Set<T> get _set => UnmodifiableSetView(_source._set);
+
+  @override
+  List<T> get _list => UnmodifiableListView(_source._list);
 }
diff --git a/lib/src/interfaces/interface.dart b/lib/src/interfaces/interface.dart
index 5b9aa8bd3..4e37bf8c6 100644
--- a/lib/src/interfaces/interface.dart
+++ b/lib/src/interfaces/interface.dart
@@ -163,7 +163,7 @@ class Interface<TagType> {
       return ports;
     } else {
       final matchingPorts = <String, Logic>{};
-      for (final tag in tags.toSet().toList()) {
+      for (final tag in tags.toSet().toList(growable: false)) {
         matchingPorts.addEntries(_ports.keys
             .where(
                 (portName) => _portToTagMap[portName]?.contains(tag) ?? false)
@@ -226,7 +226,7 @@ class Interface<TagType> {
           .map((portName, thisPort) =>
               MapEntry(portName, other.port(portName) < thisPort))
           .values
-          .toList());
+          .toList(growable: false));
 
   /// Makes `this` signals tagged with [tags] be driven conditionally by
   /// [other].
@@ -236,5 +236,5 @@ class Interface<TagType> {
           .map((portName, thisPort) =>
               MapEntry(portName, thisPort < other.port(portName)))
           .values
-          .toList());
+          .toList(growable: false));
 }
diff --git a/lib/src/interfaces/pair_interface.dart b/lib/src/interfaces/pair_interface.dart
index 932a10d48..4e480fd87 100644
--- a/lib/src/interfaces/pair_interface.dart
+++ b/lib/src/interfaces/pair_interface.dart
@@ -94,7 +94,7 @@ class PairInterface extends Interface<PairDirection> {
                 return Port(name, p.width);
             }
           })
-          .toList();
+          .toList(growable: false);
 
   /// Creates a new instance of a [PairInterface] with the same ports other
   /// characteristics.
diff --git a/lib/src/module.dart b/lib/src/module.dart
index 4a301db12..3a4bde96d 100644
--- a/lib/src/module.dart
+++ b/lib/src/module.dart
@@ -13,6 +13,7 @@ import 'dart:collection';
 import 'package:meta/meta.dart';
 
 import 'package:rohd/rohd.dart';
+import 'package:rohd/src/collections/traverseable_collection.dart';
 import 'package:rohd/src/diagnostics/inspector_service.dart';
 import 'package:rohd/src/utilities/config.dart';
 import 'package:rohd/src/utilities/sanitizer.dart';
@@ -32,13 +33,12 @@ abstract class Module {
   /// is guaranteed to match or else the [build] will fail.
   final String name;
 
-  /// An internal list of sub-modules.
-  final Set<Module> _modules = {};
+  /// An internal collection of sub-modules.
+  final TraverseableCollection<Module> _subModules = TraverseableCollection();
 
-  /// An internal list of internal-signals.
-  ///
-  /// Used for waveform dump efficiency.
-  final Set<Logic> _internalSignals = {};
+  /// An internal collection of internal signals.
+  final TraverseableCollection<Logic> _internalSignals =
+      TraverseableCollection();
 
   /// An internal list of inputs to this [Module].
   final Map<String, Logic> _inputs = {};
@@ -76,19 +76,20 @@ abstract class Module {
   /// An [Iterable] of all [Module]s contained within this [Module].
   ///
   /// This only gets populated after this [Module] has been built.
-  Iterable<Module> get subModules => UnmodifiableListView<Module>(_modules);
+  Iterable<Module> get subModules =>
+      UnmodifiableTraverseableCollectionView<Module>(_subModules);
 
   /// An [Iterable] of all [Logic]s contained within this [Module] which are
   /// *not* an input or output port of this [Module].
   ///
-  /// This does not contain any signals within submodules.
+  /// This does not contain any signals within [subModules].
   Iterable<Logic> get internalSignals =>
-      UnmodifiableListView<Logic>(_internalSignals);
+      UnmodifiableTraverseableCollectionView<Logic>(_internalSignals);
 
   /// An [Iterable] of all [Logic]s contained within this [Module], including
   /// inputs, outputs, and internal signals of this [Module].
   ///
-  /// This does not contain any signals within submodules.
+  /// This does not contain any signals within [subModules].
   Iterable<Logic> get signals => UnmodifiableListView([
         ..._inputs.values,
         ..._outputs.values,
@@ -277,7 +278,7 @@ abstract class Module {
 
     // set unique module instance names for submodules
     final uniquifier = Uniquifier();
-    for (final module in _modules) {
+    for (final module in _subModules) {
       module._uniqueInstanceName = uniquifier.getUniqueName(
           initialName: Sanitizer.sanitizeSV(module.name),
           reserved: module.reserveName);
@@ -334,7 +335,7 @@ abstract class Module {
           'a bug at https://github.com/intel/rohd/issues.');
     }
 
-    _modules.add(module);
+    _subModules.add(module);
 
     module._parent = this;
     await module.build();
@@ -755,7 +756,7 @@ abstract class Module {
     final padding = List.filled(indent, '  ').join();
     final hier = StringBuffer('$padding> ${toString()}');
 
-    for (final module in _modules) {
+    for (final module in _subModules) {
       hier.write('\n${module.hierarchyString(indent + 1)}');
     }
     return hier.toString();
diff --git a/lib/src/modules/conditional.dart b/lib/src/modules/conditional.dart
index 12b4c0ec7..bf9d5d880 100644
--- a/lib/src/modules/conditional.dart
+++ b/lib/src/modules/conditional.dart
@@ -52,8 +52,11 @@ abstract class _Always extends Module with SystemVerilog {
     var idx = 0;
 
     // Get all Receivers
-    final allReceivers =
-        conditionals.map((e) => e.receivers).expand((e) => e).toSet();
+    final allReceivers = conditionals
+        .map((e) => e.receivers)
+        .expand((e) => e)
+        .toSet()
+        .toList(growable: false);
 
     // This will reset the conditionals on setting the `reset` flag
     if (reset != null) {
@@ -90,7 +93,7 @@ abstract class _Always extends Module with SystemVerilog {
       }
 
       // now add the reset to 0 for all the remaining ones
-      for (final receiver in allReceivers.toList()) {
+      for (final receiver in allReceivers) {
         if (!signalsBeingReset.contains(receiver)) {
           allResetCondAssigns.add(receiver < 0);
         }
diff --git a/lib/src/signals/logic.dart b/lib/src/signals/logic.dart
index 1e6cf7e8b..d337434f1 100644
--- a/lib/src/signals/logic.dart
+++ b/lib/src/signals/logic.dart
@@ -74,8 +74,8 @@ class Logic {
 
   /// An [Iterable] of all [Logic]s that are being directly driven by `this`.
   late final Iterable<Logic> dstConnections =
-      UnmodifiableListView(_dstConnections);
-  final Set<Logic> _dstConnections = {};
+      UnmodifiableSetView(_dstConnections);
+  late final Set<Logic> _dstConnections = {};
 
   /// Notifies `this` that [dstConnection] is now directly connected to the
   /// output of `this`.
diff --git a/lib/src/signals/logic_structure.dart b/lib/src/signals/logic_structure.dart
index ecf429e64..64da3aec3 100644
--- a/lib/src/signals/logic_structure.dart
+++ b/lib/src/signals/logic_structure.dart
@@ -235,8 +235,9 @@ class LogicStructure implements Logic {
       s == null ? (this < this * val) : (s(this) < s(this) * val);
 
   @override
-  Iterable<Logic> get dstConnections =>
-      {for (final element in elements) ...element.dstConnections}.toList();
+  Iterable<Logic> get dstConnections => {
+        for (final element in elements) ...element.dstConnections
+      }.toList(growable: false);
 
   @override
   Module? get parentModule => _parentModule;
@@ -562,8 +563,9 @@ class LogicStructure implements Logic {
   bool get isNet => false;
 
   @override
-  Iterable<Logic> get srcConnections =>
-      {for (final element in elements) ...element.srcConnections}.toList();
+  Iterable<Logic> get srcConnections => {
+        for (final element in elements) ...element.srcConnections
+      }.toList(growable: false);
 
   @override
   List<Logic> get _srcConnections => throw UnsupportedError('Unnecessary');


Test patch:
diff --git a/test/benchmark_test.dart b/test/benchmark_test.dart
index 83dd702db..4a54fcfe3 100644
--- a/test/benchmark_test.dart
+++ b/test/benchmark_test.dart
@@ -1,4 +1,4 @@
-// Copyright (C) 2022-2023 Intel Corporation
+// Copyright (C) 2022-2024 Intel Corporation
 // SPDX-License-Identifier: BSD-3-Clause
 //
 // benchmark_test.dart
@@ -14,6 +14,7 @@ import '../benchmark/byte_enable_benchmark.dart';
 import '../benchmark/comb_guard_fanout_benchmark.dart';
 import '../benchmark/logic_value_of_benchmark.dart';
 import '../benchmark/many_seq_and_comb_benchmark.dart';
+import '../benchmark/many_submodules_benchmark.dart';
 import '../benchmark/pipeline_benchmark.dart';
 import '../benchmark/ssa_driver_search_benchmark.dart';
 import '../benchmark/wave_dump_benchmark.dart';
@@ -53,5 +54,9 @@ void main() {
     test('ssa driver search', () {
       SsaDriverSearchBenchmark().measure();
     });
+
+    test('many submodule', () async {
+      await ManySubmodulesBenchmark().measure();
+    });
   });
 }
diff --git a/test/traverseable_collection_test.dart b/test/traverseable_collection_test.dart
new file mode 100644
index 000000000..69ed77129
--- /dev/null
+++ b/test/traverseable_collection_test.dart
@@ -0,0 +1,61 @@
+// Copyright (C) 2024 Intel Corporation
+// SPDX-License-Identifier: BSD-3-Clause
+//
+// traverseable_collection_test.dart
+// Tests for `TraverseableCollection`.
+//
+// 2024 June 12
+// Author: Max Korbel <max.korbel@intel.com>
+
+// ignore_for_file: cascade_invocations
+
+import 'package:rohd/src/collections/traverseable_collection.dart';
+import 'package:test/test.dart';
+
+void main() {
+  test('simple traverseable collection usage', () {
+    final c = TraverseableCollection<int>();
+
+    c.add(10);
+
+    c.addAll([1, 2, 3]);
+
+    expect(c.length, 4);
+
+    final removed = c.remove(2);
+    expect(removed, isTrue);
+
+    final removedAgain = c.remove(2);
+    expect(removedAgain, isFalse);
+
+    expect(c.length, 3);
+
+    expect(c[0], 10);
+    expect(c[1], 1);
+    expect(c[2], 3);
+
+    expect(c.contains(10), isTrue);
+    expect(c.contains(3), isTrue);
+
+    for (final item in c) {
+      expect(c.contains(item), isTrue);
+    }
+
+    expect(c.isEmpty, isFalse);
+  });
+
+  test('unmodifiable traverseable collection cannot be changed', () {
+    final c = TraverseableCollection<int>();
+    final v = UnmodifiableTraverseableCollectionView(c);
+
+    c.addAll([1, 2, 3]);
+
+    expect(() => v.add(4), throwsUnsupportedError);
+    expect(() => v.addAll([5, 6]), throwsUnsupportedError);
+    expect(() => v.remove(1), throwsUnsupportedError);
+
+    expect(v.length, 3);
+    expect(v[0], 1);
+    expect(v.contains(2), isTrue);
+  });
+}