optimize find_wait_cycle

[sanderr]

When the compiler's statement scheduler gets stuck, it calls find_wait_cycle to freeze a variable in the hopes that it unblocks execution. However, this method is very inefficient: it goes over all potential freeze candidates, and "sorts" them, only to pick the first and then discard the sorted collection. In projects like systemtenant, the method is called very often, and in total (over all invocations) goes over 2.9M freeze candidates (in its benchmark variant).

Benchmark

You can use the compiler benchmark to compare performance against master on the systemtenant project.

Option 1: cache results somehow

Is there something we can cache? e.g. can we expect the pool of freeze candidates to only grow or shrink? Or even can we expect a variables' progress potential or number of waiters to only change in one direction? Are there other things we can take into account so that on each invocation, we only reason on what changed rather than starting fresh?

Option 2: find min / max instead of full sort

If option 1 doesn't work out, the easy way out is to do the equivalent of min(collection) instead of next(iter(sorted(collection))). A very rough, lowest-effort patched-together PoC is given below.

diff --git a/src/inmanta/execute/scheduler.py b/src/inmanta/execute/scheduler.py
index 9fa9cbb1d..3a96f7ac3 100644
--- a/src/inmanta/execute/scheduler.py
+++ b/src/inmanta/execute/scheduler.py
@@ -314,7 +314,7 @@ class Scheduler:

         return range_to_range

-    def find_wait_cycle(self, attributes_with_precedence_rule: list[RelationAttribute], allwaiters: WaiterSet) -> bool:
+    def find_wait_cycle(self, freeze_order: list[RelationAttribute], allwaiters: WaiterSet) -> bool:
         """
         Preconditions: no progress is made anymore

@@ -342,7 +342,8 @@ class Scheduler:
             return resolve_proxies(variable.variable)

         # Determine drvs that should be frozen to break the cycle
-        freeze_candidates: list[DelayedResultVariable[object]] = []
+        worst_score = len(freeze_order)
+        best = None
         for waiter in allwaiters:
             for rv in waiter.requires.values():
                 real_rv: Optional[VariableABC] = resolve_proxies(rv)
@@ -351,13 +352,20 @@ class Scheduler:
                         # get_progress_potential fails when there is a value already
                         continue
                     if real_rv.get_waiting_providers() > 0 and real_rv.get_progress_potential() > 0:
-                        freeze_candidates.append(real_rv)
-
-        if not freeze_candidates:
+                        score: int
+                        if not isinstance(real_rv, RelationAttributeVariable):
+                            score = worst_score
+                        else:
+                            score = freeze_order.get(real_rv, None)
+                            if score is None:
+                                LOGGER.log(LOG_LEVEL_TRACE, "Waiting blocked on %s", real_rv)
+                                real_rv.freeze()
+                                return True
+                        if best is None or score < best[1]:
+                            best = real_rv, score
+        if best is None:
             return False
-        # Use the relation precedence rules to determine which drv should be frozen
-        queue = PrioritisedDelayedResultVariableQueue(attributes_with_precedence_rule, freeze_candidates)
-        drv_to_freeze = queue.popleft()
+        drv_to_freeze = best[0]
         LOGGER.log(LOG_LEVEL_TRACE, "Waiting blocked on %s", drv_to_freeze)
         drv_to_freeze.freeze()
         return True
@@ -392,6 +400,8 @@ class Scheduler:
         # queue for RV's that are delayed and had no effective waiters when they were first in the waitqueue
         zerowaiters: Deque[DelayedResultVariable[Any]] = deque()

+        freeze_order = dict(enumerate(waitqueue._freeze_order))
+
         # Wrap in object to pass around
         queue = QueueScheduler(compiler, basequeue, waitqueue, self.types)

@@ -480,7 +490,7 @@ class Scheduler:

             if not progress:
                 # nothing works anymore, attempt to unfreeze wait cycle
-                progress = self.find_wait_cycle(attributes_with_precedence_rule, queue.allwaiters)
+                progress = self.find_wait_cycle(freeze_order, queue.allwaiters)

             if not progress:
                 # no one waiting anymore, all done, freeze and finish