Fix last_devices to be quieter, and improve device affinity.

build/android/pylib/perf/setup.py

Index: build/android/pylib/perf/setup.py
diff --git a/build/android/pylib/perf/setup.py b/build/android/pylib/perf/setup.py
index 8e1fc28a7e651bef567b336e5593d8be64c75701..371d5a443931252e9759c2484e22ed960cabbde2 100644
--- a/build/android/pylib/perf/setup.py
+++ b/build/android/pylib/perf/setup.py
@@ -6,6 +6,8 @@
 
 import json
 import fnmatch
+import hashlib
+import itertools
 import logging
 import os
 import shutil
@@ -18,18 +20,6 @@ from pylib.perf import test_runner
 from pylib.utils import test_environment
 
 
-def _GetAllDevices():
-  devices_path = os.path.join(os.environ.get('CHROMIUM_OUT_DIR', 'out'),
-                              device_list.LAST_DEVICES_FILENAME)
-  try:
-    devices = [device_utils.DeviceUtils(s)
-               for s in device_list.GetPersistentDeviceList(devices_path)]
-  except IOError as e:
-    logging.error('Unable to find %s [%s]', devices_path, e)
-    devices = device_utils.DeviceUtils.HealthyDevices()
-  return sorted(devices)
-
-
 def _GetStepsDictFromSingleStep(test_options):
   # Running a single command, build the tests structure.
   steps_dict = {
@@ -56,6 +46,58 @@ def _GetStepsDict(test_options):
       return steps
 
 
+def DistributeAffinities(devices):
+  """Create a mapping from device to affinity using a round-robin hash scheme.
+
+  Args:
+    devices: a list of device serials.
+
+  Returns: a dictionary mapping each of the given device serials to a list
+    of affinities (numbers between 0 and NUM_DEVICE_AFFINITIES-1) it should
+    run.
+
+  This function implements an algorithm to assign affinities to devices in a
+  relatively stable way while still maximizing the use of resources.
+
+  We begin with all affinities unassigned.  We cycle through the list of device
+  serials, and for each one we assign a yet-unassigned affinity.  We choose the
+  affinity to assign by hashing the device serial, so that changes in the set of
+  devices will produce minimal changes in the assignments.  We resolve
+  collisions by incrementing the affinity until we find one that is free.
+  """
+  affinities = test_runner.NUM_DEVICE_AFFINITIES
+
+  if not devices:
+    return {}
+
+  affinity_to_device = {}
+
+  devices = sorted(devices)
+  device_cycle = itertools.islice(itertools.cycle(devices), affinities)
+  for device in device_cycle:
+    # Hash the device ID to get a unique affinity.
+    start_affinity = int(int(hashlib.md5(device).hexdigest(), 16) % affinities)
+    affinity_cycle = itertools.islice(
+        itertools.cycle(range(affinities)),
+        start_affinity, start_affinity+affinities)
+
+    # "Increment" the affinity repeatedly until we find an available slot.
+    for affinity in affinity_cycle:
+      if affinity not in affinity_to_device:
+        affinity_to_device[affinity] = device
+        break
+    else:
+      raise Exception('Impossibly failed to find unassigned affinity')
+
+  # Invert the dictionary we just built.
+  device_to_affinity = {}
+  for k, v in affinity_to_device.iteritems():
+    if v not in device_to_affinity:
+      device_to_affinity[v] = []
+    device_to_affinity[v].append(k)
+
+  return device_to_affinity
+
 def Setup(test_options):
   """Create and return the test runner factory and tests.
 
@@ -74,8 +116,9 @@ def Setup(test_options):
   # Before running the tests, kill any leftover server.
   test_environment.CleanupLeftoverProcesses()
 
-  # We want to keep device affinity, so return all devices ever seen.
-  all_devices = _GetAllDevices()
+  all_devices = [d.adb.GetDeviceSerial()
+                 for d in device_utils.DeviceUtils.HealthyDevices()]
+  affinity_map = DistributeAffinities(all_devices)
 
   steps_dict = _GetStepsDict(test_options)
   sorted_step_names = sorted(steps_dict['steps'].keys())
@@ -89,9 +132,9 @@ def Setup(test_options):
     with file(test_options.flaky_steps, 'r') as f:
       flaky_steps = json.load(f)
 
-  def TestRunnerFactory(device, shard_index):
+  def TestRunnerFactory(device, _):
+    affinities = affinity_map[device]
     return test_runner.TestRunner(
-        test_options, device, shard_index, len(all_devices),
-        steps_dict, flaky_steps)
+        test_options, device, affinities, steps_dict, flaky_steps)
 
   return (TestRunnerFactory, sorted_step_names, all_devices)