Filter events before performing iteration

A filter can be supplied to the maximal subset
iterator to remove events from consideration in
maximal subsets. Instead of needlessly processing
events that will never be considered, we can
instead remove those events at the beginning while
perserving the relative ordering among events that
we do actually care about. This both simplifies the
bookkeeper's code slightly and reduces the number
of times we need to invoke the filter function drastically
(once per event instead of multiple times per combination).

diff --git a/src/mc/explo/udpor/maximal_subsets_iterator.cpp b/src/mc/explo/udpor/maximal_subsets_iterator.cpp
index 939b858..1dd635a 100644 (file)
--- a/src/mc/explo/udpor/maximal_subsets_iterator.cpp
+++ b/src/mc/explo/udpor/maximal_subsets_iterator.cpp
@@ -6,6 +6,20 @@
 
 namespace simgrid::mc::udpor {
 
+maximal_subsets_iterator::maximal_subsets_iterator(const Configuration& config,
+                                                   std::optional<node_filter_function> filter)
+    : config({config}), current_maximal_set({EventSet()})
+{
+  const auto candidate_ordering = config.get_topologically_sorted_events_of_reverse_graph();
+  if (filter.has_value()) {
+    // Only store the events in the ordering that "matter" to us
+    std::copy_if(std::move_iterator(candidate_ordering.begin()), std::move_iterator(candidate_ordering.end()),
+                 std::back_inserter(topological_ordering), filter.value());
+  } else {
+    topological_ordering = std::move(candidate_ordering);
+  }
+}
+
 void maximal_subsets_iterator::increment()
 {
   if (current_maximal_set == std::nullopt) {
@@ -92,11 +106,6 @@ maximal_subsets_iterator::continue_traversal_of_maximal_events_tree()
 
 bool maximal_subsets_iterator::bookkeeper::is_candidate_event(const UnfoldingEvent* e) const
 {
-  // The event must pass the filter, if it exists
-  if (filter_function.has_value() && not filter_function.value()(e)) {
-    return false;
-  }
-
   if (const auto e_count = event_counts.find(e); e_count != event_counts.end()) {
     return e_count->second == 0;
   }

diff --git a/src/mc/explo/udpor/maximal_subsets_iterator.hpp b/src/mc/explo/udpor/maximal_subsets_iterator.hpp
index 4ca7f25..128e244 100644 (file)
--- a/src/mc/explo/udpor/maximal_subsets_iterator.hpp
+++ b/src/mc/explo/udpor/maximal_subsets_iterator.hpp
@@ -37,18 +37,11 @@ public:
 
   maximal_subsets_iterator() = default;
   explicit maximal_subsets_iterator(const Configuration& config) : maximal_subsets_iterator(config, std::nullopt) {}
-
-  maximal_subsets_iterator(const Configuration& config, std::optional<node_filter_function> filter)
-      : config({config})
-      , topological_ordering(config.get_topologically_sorted_events_of_reverse_graph())
-      , current_maximal_set({EventSet()})
-      , bookkeeper(filter)
-  {
-  }
+  maximal_subsets_iterator(const Configuration& config, std::optional<node_filter_function> filter);
 
 private:
   const std::optional<std::reference_wrapper<const Configuration>> config;
-  const std::vector<const UnfoldingEvent*> topological_ordering;
+  std::vector<const UnfoldingEvent*> topological_ordering;
 
   // The boolean is a bit of an annoyance, but it works. Effectively,
   // there's no way to distinguish between "we're starting the search
@@ -71,7 +64,6 @@ private:
   struct bookkeeper {
   public:
     using topological_order_position = maximal_subsets_iterator::topological_order_position;
-    explicit bookkeeper(std::optional<node_filter_function> filter = std::nullopt) : filter_function(filter) {}
 
     void mark_included_in_maximal_set(const UnfoldingEvent*);
     void mark_removed_from_maximal_set(const UnfoldingEvent*);
@@ -80,7 +72,6 @@ private:
 
   private:
     std::unordered_map<const UnfoldingEvent*, unsigned> event_counts;
-    const std::optional<node_filter_function> filter_function;
 
     /// @brief Whether or not the given event, according to the
     /// bookkeeping that has been done thus far, can be added to the