Improve slave-preference function

scripts/master/master_utils.py

Index: scripts/master/master_utils.py
diff --git a/scripts/master/master_utils.py b/scripts/master/master_utils.py
index 5c6f6bb88798abfd1a58edd2154c626f181baa7d..d91a7629497d1c4e8a876bcee8339a5868156ffb 100644
--- a/scripts/master/master_utils.py
+++ b/scripts/master/master_utils.py
@@ -655,18 +655,58 @@ class ConditionalProperty(util.ComparableMixin):
 class PreferredBuilderNextSlaveFunc(object):
   """
   This object, when used as a Builder's 'nextSlave' function, will choose
-  a slave builder whose 'preferred_builder' value is the same as the builder
-  name. If there is no such a builder, a builder is randomly chosen.
+  a slave whose 'preferred_builder' value is the same as the builder
+  name. If there is no such slave, a slave is randomly chosen that doesn't
+  prefer any builder if such a slave is available. If not, a slave is randomly
+  chosen with preference on slaves with higher capacity.
   """
 
+  def __init__(self, choice=random.choice):
+    # Allow overriding the choice function for testability.
+    self.choice = choice
+
   def __call__(self, builder, slave_builders):
     if not slave_builders:
       return None
 

[tandrii(chromium), 2016/10/21 10:39:16]

first, consider adding new functionality behind a switch.
second, how about this (as brainstormed offline):

prefs = collections.Counter(s.preferred_builder for s in slave_builders)
if builder in prefs:
  key = builder
elif None in prefs:
  key = None
else:
  key = prefs.most_common()[0]
return choice(s for s in slave_builders if s.preferred_builder == key)


# As discussed, last loop over all slaves_builders can be optimized by storing
randomly selected slave next to count of slave so far in prefs{}.

[Michael Achenbach, 2016/10/21 13:17:43]

Used the first simple method with minor modifications. I don't think more
optimization is necessary at that point.

Note that the semantics now change: a set of several sets of equally available
slaves is chosen now arbitrarily (not randomly) based on dictionary order. Only
the slave from the set will be chosen randomly. I don't think it matters and it
makes the algorithm faster.

+    # First choice: Slaves that prefer this builder.
     preferred_slaves = [
         s for s in slave_builders
         if s.slave.properties.getProperty('preferred_builder') == builder.name]
-    return random.choice(preferred_slaves or slave_builders)
+    if preferred_slaves:
+      return self.choice(preferred_slaves)
+
+    # Second choice: Slaves that don't prefer any builders.
+    preferred_slaves = [
+        s for s in slave_builders
+        if not s.slave.properties.getProperty('preferred_builder')]
+    if preferred_slaves:
+      return self.choice(preferred_slaves)
+
+    # Third choice: Slaves that prefer other builders but have largest
+    # capacity left.
+    preference_to_slaves = {}
+    largest_capacity = 0
+    for s in slave_builders:
+      # There should only be slaves with preference left, but lets be
+      # defensive.
+      preference = s.slave.properties.getProperty('preferred_builder')
+      if preference:
+        slaves = preference_to_slaves.setdefault(preference, [])
+        slaves.append(s)
+        largest_capacity = max(largest_capacity, len(slaves))
+    # Prefer list over set as each slave has only one preferred builder.
+    preferred_slaves = []
+    for preference, slaves in preference_to_slaves.iteritems():
+      if len(slaves) == largest_capacity:
+        preferred_slaves.extend(slaves)
+    if preferred_slaves:
+      return self.choice(preferred_slaves)
+
+    # Last choice: Choose from all slaves. We should never reach here as all
+    # slaves should have been considered above.
+    log.err('Didn\'t get preferred slave for %s' % builder.name)
+    return self.choice(slave_builders)
 
 
 def SetMasterProcessName():