Repository: intel/rohd
Pull request #346 (2023-04-21 17:23:42)

Optimize `guard` subscription performance in `Combinational` 
<!-- Please make sure you check out the contribution guidelines before submitting a pull request! -->

## Description & Motivation

#344 introduced a performance issue with `SynchronousEmitter` (used in signal `glitch` propagation) when `SynchronousSubscription`s are cancelled.  Removal from a `List` of subscriptions was expensive and in the critical path for simulation performance when there are many `Combinational`s arranged in a particular way.

This PR replaces that `List` with a custom collection called `IterableRemovableQueue` which is optimized specifically for the needs of the `SynchronousEmitter`.  It also includes a benchmark that reproduces the performance issue and tests for the new collection type.

There is still some overhead in having `guard` there at all, but without disabling the check there's not that much I see we can do to improve it.  Moving towards recommending reduced usage of `Combinational` may be a good solution, since it has a number of weird characteristics (representing procedural code as hardware).

This PR also has some other refactoring of minor collection usage for efficiency based on discoveries during profiling.

## Related Issue(s)

N/A

## Testing

Existing tests pass, plus new ones for the benchmark and collection.

## Backwards-compatibility

> Is this a breaking change that will not be backwards-compatible? If yes, how so?

No

## 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 e614cd6d..14b04b8e 100644
--- a/benchmark/benchmark.dart
+++ b/benchmark/benchmark.dart
@@ -8,6 +8,7 @@
 // Author: Max Korbel <max.korbel@intel.com>
 
 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 'pipeline_benchmark.dart';
@@ -19,4 +20,5 @@ void main() async {
   ByteEnableBenchmark().report();
   await WaveDumpBenchmark().report();
   await many_seq_and_comb.main();
+  await CombGuardFanoutBenchmark().report();
 }
diff --git a/benchmark/comb_guard_fanout_benchmark.dart b/benchmark/comb_guard_fanout_benchmark.dart
new file mode 100644
index 00000000..446ddd52
--- /dev/null
+++ b/benchmark/comb_guard_fanout_benchmark.dart
@@ -0,0 +1,75 @@
+// Copyright (C) 2023 Intel Corporation
+// SPDX-License-Identifier: BSD-3-Clause
+//
+// comb_guard_fanout_benchmark.dart
+// Benchmarking for many `Combinational` listeners on the same signals, leading
+// to many `guard`s and subscription cancels in signal listeners.
+//
+// 2023 April 21
+// Author: Max Korbel <max.korbel@intel.com>
+
+import 'package:benchmark_harness/benchmark_harness.dart';
+import 'package:rohd/rohd.dart';
+
+class CombGuardFanout extends Module {
+  CombGuardFanout(Logic a,
+      {int numStatements = 10, int numCombinationals = 100}) {
+    a = addInput('a', a, width: 8);
+
+    final sxi = <Logic>[a];
+
+    for (var i = 1; i < numStatements; i++) {
+      sxi.add(listeners(sxi[i - 1]));
+    }
+
+    for (var c = 0; c < numCombinationals; c++) {
+      Combinational([
+        for (var i = 1; i < numStatements; i++)
+          Logic(width: a.width) < sxi[i - 1],
+      ]);
+    }
+  }
+
+  /// Adds a bunch of listeners to a modified [a] and return it.
+  Logic listeners(
+    Logic a, {
+    int fanout = 5,
+  }) {
+    final toReturn = a + 1;
+    for (var i = 0; i < fanout; i++) {
+      Logic(width: a.width) <= ~toReturn;
+    }
+    return toReturn;
+  }
+}
+
+class CombGuardFanoutBenchmark extends AsyncBenchmarkBase {
+  final int numPuts;
+  CombGuardFanoutBenchmark({this.numPuts = 100})
+      : super('CombGuardFanoutBenchmark');
+
+  @override
+  Future<void> teardown() async {
+    await Simulator.reset();
+  }
+
+  CombGuardFanout? mod;
+  final Logic a = Logic(width: 8);
+
+  @override
+  Future<void> setup() async {
+    mod = CombGuardFanout(a);
+    await mod!.build();
+  }
+
+  @override
+  Future<void> run() async {
+    for (var i = 0; i < numPuts; i++) {
+      a.put(i);
+    }
+  }
+}
+
+Future<void> main() async {
+  await CombGuardFanoutBenchmark().report();
+}
diff --git a/lib/src/collections/iterable_removable_queue.dart b/lib/src/collections/iterable_removable_queue.dart
new file mode 100644
index 00000000..bd0a561b
--- /dev/null
+++ b/lib/src/collections/iterable_removable_queue.dart
@@ -0,0 +1,104 @@
+// Copyright (C) 2023 Intel Corporation
+// SPDX-License-Identifier: BSD-3-Clause
+//
+// iterable_removable_queue.dart
+// Definition for an optimized queue for signal propagation subscriptions and
+// similar applications.
+//
+// 2023 April 21
+// Author: Max Korbel <max.korbel@intel.com>
+
+/// A queue that can be easily iterated through and remove items during
+/// iteration.
+class IterableRemovableQueue<T> {
+  /// The first item in this queue.
+  ///
+  /// Null if the queue is empty.
+  _IterableRemovableElement<T>? _first;
+
+  /// The last item in this queue.
+  ///
+  /// Null if the queue is empty.
+  _IterableRemovableElement<T>? _last;
+
+  /// Adds a new item to the end of the queue.
+  void add(T item) {
+    final newElement = _IterableRemovableElement<T>(item);
+    if (_first == null) {
+      _first = newElement;
+      _last = _first;
+    } else {
+      _last!.next = newElement;
+      _last = newElement;
+    }
+  }
+
+  /// Indicates whether there are no items in the queue.
+  bool get isEmpty => _first == null;
+
+  /// Removes all items from this queue.
+  void clear() {
+    _first = null;
+    _last = null;
+  }
+
+  /// Appends [other] to this without copying any elements and [clear]s [other].
+  void takeAll(IterableRemovableQueue<T> other) {
+    if (other.isEmpty) {
+      return;
+    }
+
+    if (isEmpty) {
+      _first = other._first;
+      _last = other._last;
+    } else {
+      _last!.next = other._first;
+      _last = other._last;
+    }
+
+    other.clear();
+  }
+
+  /// Iterates through all items in the queue, removing any which are indicated
+  /// by [removeWhere], and performing [action] on the rest.
+  void iterate(
+      {void Function(T item)? action, bool Function(T item)? removeWhere}) {
+    if (isEmpty) {
+      return;
+    }
+
+    var element = _first;
+    _IterableRemovableElement<T>? previous;
+    while (element != null) {
+      if (removeWhere != null && removeWhere(element.item)) {
+        previous?.next = element.next;
+
+        if (element == _first) {
+          _first = element.next;
+        } else if (element == _last) {
+          _last = previous;
+        }
+      } else {
+        if (action != null) {
+          action(element.item);
+        }
+
+        previous = element;
+      }
+
+      element = element.next;
+    }
+  }
+}
+
+/// One element of a [IterableRemovableQueue].
+class _IterableRemovableElement<T> {
+  /// The item being tracked by this element.
+  final T item;
+
+  /// The next element in the queue.
+  _IterableRemovableElement<T>? next;
+
+  /// Constructs an element containing [item].
+  _IterableRemovableElement(this.item);
+}
diff --git a/lib/src/collections/traverseable_collection.dart b/lib/src/collections/traverseable_collection.dart
index 2f502199..5395fff4 100644
--- a/lib/src/collections/traverseable_collection.dart
+++ b/lib/src/collections/traverseable_collection.dart
@@ -29,11 +29,10 @@ class TraverseableCollection<T> {
   /// The valid indices are 0 through [length] - 1.
   int get length => _list.length;
 
-  /// Adds an element to the collection.
+  /// Adds an element to the collection if it is not already present.
   void add(T item) {
-    if (!contains(item)) {
+    if (_set.add(item)) {
       _list.add(item);
-      _set.add(item);
     }
   }
 
diff --git a/lib/src/module.dart b/lib/src/module.dart
index f52df30b..69971bf6 100644
--- a/lib/src/module.dart
+++ b/lib/src/module.dart
@@ -269,9 +269,8 @@ abstract class Module {
           'a bug at https://github.com/intel/rohd/issues.');
     }
 
-    if (!_modules.contains(module)) {
-      _modules.add(module);
-    }
+    _modules.add(module);
+
     module._parent = this;
     await module.build();
   }
diff --git a/lib/src/modules/conditional.dart b/lib/src/modules/conditional.dart
index c3601eb5..7a86b3b2 100644
--- a/lib/src/modules/conditional.dart
+++ b/lib/src/modules/conditional.dart
@@ -8,6 +8,7 @@
 // Author: Max Korbel <max.korbel@intel.com>
 
 import 'dart:async';
+import 'dart:collection';
 
 import 'package:meta/meta.dart';
 import 'package:rohd/rohd.dart';
@@ -220,6 +221,32 @@ class Combinational extends _Always {
   /// detect reentrance.
   bool _isExecuting = false;
 
+  /// Keeps track of already-driven logics during [_execute].
+  ///
+  /// Must be cleared at the end of each [_execute].
+  final Set<Logic> _drivenLogics = HashSet<Logic>();
+
+  /// Keeps track of signals already [_guard]ed.
+  ///
+  /// Must be cleared at the end of each [_execute].
+  final Set<Logic> _guarded = HashSet<Logic>();
+
+  /// Keeps track of subscriptions to glitches for each of the [_guarded].
+  ///
+  /// Must be cleared at the end of each [_execute].
+  final List<SynchronousSubscription<LogicValueChanged>> _guardListeners =
+      <SynchronousSubscription<LogicValueChanged>>[];
+
+  /// A function that sub-[Conditional]s should call to guard signals they
+  /// are consuming.
+  void _guard(Logic toGuard) {
+    if (_guarded.add(toGuard)) {
+      _guardListeners.add(toGuard.glitch.listen((args) {
+        throw WriteAfterReadException(toGuard.name);
+      }));
+    }
+  }
+
   /// Performs the functional behavior of this block.
   void _execute() {
     if (_isExecuting) {
@@ -231,36 +258,26 @@ class Combinational extends _Always {
 
     _isExecuting = true;
 
-    // keep track of signals already being guarded for efficiency
-    final guarded = <Logic>{};
-    final guardListeners = <SynchronousSubscription<LogicValueChanged>>[];
-    void guard(Logic toGuard) {
-      if (!guarded.contains(toGuard)) {
-        guarded.add(toGuard);
-        guardListeners.add(toGuard.glitch.listen((args) {
-          throw WriteAfterReadException(toGuard.name);
-        }));
-      }
-    }
-
-    final drivenLogics = <Logic>{};
     for (final element in conditionals) {
-      element.execute(drivenLogics, guard);
+      element.execute(_drivenLogics, _guard);
     }
 
     // combinational must always drive all outputs or else you get X!
-    if (_assignedReceiverToOutputMap.length != drivenLogics.length) {
+    if (_assignedReceiverToOutputMap.length != _drivenLogics.length) {
       for (final receiverOutputPair in _assignedReceiverToOutputMap.entries) {
-        if (!drivenLogics.contains(receiverOutputPair.key)) {
+        if (!_drivenLogics.contains(receiverOutputPair.key)) {
           receiverOutputPair.value.put(LogicValue.x, fill: true);
         }
       }
     }
 
     // clean up after execution
-    for (final guardListener in guardListeners) {
+    for (final guardListener in _guardListeners) {
       guardListener.cancel();
     }
+    _guardListeners.clear();
+    _drivenLogics.clear();
+    _guarded.clear();
 
     _isExecuting = false;
   }
diff --git a/lib/src/synthesizers/systemverilog.dart b/lib/src/synthesizers/systemverilog.dart
index f47fea72..addf18f4 100644
--- a/lib/src/synthesizers/systemverilog.dart
+++ b/lib/src/synthesizers/systemverilog.dart
@@ -385,17 +385,11 @@ class _SynthModuleDefinition {
             _getSynthSubModuleInstantiation(subModule);
         subModuleInstantiation.outputMapping[synthReceiver] = receiver;
 
-        for (final element in subModule.inputs.values) {
-          if (!logicsToTraverse.contains(element)) {
-            logicsToTraverse.add(element);
-          }
-        }
+        subModule.inputs.values.forEach(logicsToTraverse.add);
       } else if (driver != null) {
         if (!module.isInput(receiver)) {
           // stop at the input to this module
-          if (!logicsToTraverse.contains(driver)) {
-            logicsToTraverse.add(driver);
-          }
+          logicsToTraverse.add(driver);
           assignments.add(_SynthAssignment(synthDriver, synthReceiver));
         }
       } else if (driver == null && receiver.value.isValid) {
diff --git a/lib/src/utilities/synchronous_propagator.dart b/lib/src/utilities/synchronous_propagator.dart
index ff0fe00c..ad08a535 100644
--- a/lib/src/utilities/synchronous_propagator.dart
+++ b/lib/src/utilities/synchronous_propagator.dart
@@ -8,6 +8,8 @@
 // Author: Max Korbel <max.korbel@intel.com>
 //
 
+import 'package:rohd/src/collections/iterable_removable_queue.dart';
+
 /// A controller for a [SynchronousEmitter] that allows for
 /// adding of events of type [T] to be emitted.
 class SynchronousPropagator<T> {
@@ -42,7 +44,8 @@ class SynchronousEmitter<T> {
   }
 
   /// A [List] of actions to perform for each event.
-  final List<SynchronousSubscription<T>> _subscriptions = [];
+  final IterableRemovableQueue<SynchronousSubscription<T>> _subscriptions =
+      IterableRemovableQueue<SynchronousSubscription<T>>();
 
   /// Returns `true` iff this is currently emitting.
   ///
@@ -50,21 +53,19 @@ class SynchronousEmitter<T> {
   bool get isEmitting => _isEmitting;
   bool _isEmitting = false;
 
+  /// Determines whether a [SynchronousSubscription] should be removed from the
+  /// collection of active [_subscriptions].
+  static bool _doRemove<T>(SynchronousSubscription<T> subscription) =>
+      subscription._cancelled;
+
   /// Sends out [t] to all listeners.
   void _propagate(T t) {
     _isEmitting = true;
 
-    for (var i = 0; i < _subscriptions.length; i++) {
-      final subscription = _subscriptions[i];
-
-      if (subscription._cancelled) {
-        _subscriptions.removeAt(i);
-        i--;
-        continue;
-      }
-
-      subscription.func(t);
-    }
+    _subscriptions.iterate(
+      action: (subscription) => subscription.func(t),
+      removeWhere: _doRemove,
+    );
 
     _isEmitting = false;
   }
@@ -75,8 +76,7 @@ class SynchronousEmitter<T> {
   /// time this would propagate.  Also clears all actions from [other]
   /// so that it will not execute anything in the future.
   void adopt(SynchronousEmitter<T> other) {
-    _subscriptions.addAll(other._subscriptions);
-    other._subscriptions.clear();
+    _subscriptions.takeAll(other._subscriptions);
   }
 }
 


Test patch:
diff --git a/test/benchmark_test.dart b/test/benchmark_test.dart
index 7e4dda2c..8bfab39d 100644
--- a/test/benchmark_test.dart
+++ b/test/benchmark_test.dart
@@ -11,6 +11,7 @@
 import 'package:test/test.dart';
 
 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/pipeline_benchmark.dart';
@@ -40,4 +41,8 @@ void main() {
       });
     }
   });
+
+  test('comb guard fanout benchmark', () async {
+    await CombGuardFanoutBenchmark().measure();
+  });
 }
diff --git a/test/iterable_removable_queue_test.dart b/test/iterable_removable_queue_test.dart
new file mode 100644
index 00000000..86ef5503
--- /dev/null
+++ b/test/iterable_removable_queue_test.dart
@@ -0,0 +1,74 @@
+// Copyright (C) 2023 Intel Corporation
+// SPDX-License-Identifier: BSD-3-Clause
+//
+// iterable_removable_queue_test.dart
+// Tests for `IterableRemovableQueue`.
+//
+// 2023 April 21
+// Author: Max Korbel <max.korbel@intel.com>
+
+import 'package:rohd/src/collections/iterable_removable_queue.dart';
+import 'package:test/test.dart';
+
+void main() {
+  group('iterable removable queue', () {
+    const numItems = 100;
+    IterableRemovableQueue<int> buildQueue() {
+      final q = IterableRemovableQueue<int>();
+      for (var i = 0; i < numItems; i++) {
+        q.add(i);
+      }
+      return q;
+    }
+
+    int getCount(IterableRemovableQueue<int> q) {
+      var count = 0;
+      q.iterate(action: (item) {
+        count++;
+      });
+      return count;
+    }
+
+    group('forEach', () {
+      test('no removal', () {
+        final q = buildQueue();
+        expect(getCount(q), numItems);
+        expect(q.isEmpty, false);
+      });
+
+      test('remove even', () {
+        final q = buildQueue()..iterate(removeWhere: (i) => i.isEven);
+        expect(getCount(q), numItems / 2);
+        expect(q.isEmpty, false);
+      });
+
+      test('remove odd', () {
+        final q = buildQueue()..iterate(removeWhere: (i) => i.isOdd);
+        expect(getCount(q), numItems / 2);
+        expect(q.isEmpty, false);
+      });
+
+      test('remove all', () {
+        final q = buildQueue()..iterate(removeWhere: (i) => true);
+        expect(getCount(q), 0);
+        expect(q.isEmpty, true);
+      });
+    });
+
+    // clear
+    test('clear', () {
+      final q = buildQueue()..clear();
+      expect(getCount(q), 0);
+      expect(q.isEmpty, true);
+    });
+
+    // takeAll
+    test('takeAll', () {
+      final q1 = buildQueue();
+      final q2 = buildQueue();
+      q1.takeAll(q2);
+      expect(getCount(q1), numItems * 2);
+      expect(q2.isEmpty, true);
+    });
+  });
+}