1# Copyright 2012 the V8 project authors. All rights reserved. 2# Redistribution and use in source and binary forms, with or without 3# modification, are permitted provided that the following conditions are 4# met: 5# 6# * Redistributions of source code must retain the above copyright 7# notice, this list of conditions and the following disclaimer. 8# * Redistributions in binary form must reproduce the above 9# copyright notice, this list of conditions and the following 10# disclaimer in the documentation and/or other materials provided 11# with the distribution. 12# * Neither the name of Google Inc. nor the names of its 13# contributors may be used to endorse or promote products derived 14# from this software without specific prior written permission. 15# 16# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28 29class Shell(object): 30 def __init__(self, shell): 31 self.shell = shell 32 self.tests = [] 33 self.total_duration = 0.0 34 35 def AddSuite(self, suite): 36 self.tests += suite.tests 37 self.total_duration += suite.total_duration 38 39 def SortTests(self): 40 self.tests.sort(cmp=lambda x, y: cmp(x.duration, y.duration)) 41 42 43def Assign(suites, peers): 44 total_work = 0.0 45 for s in suites: 46 total_work += s.CalculateTotalDuration() 47 48 total_power = 0.0 49 for p in peers: 50 p.assigned_work = 0.0 51 total_power += p.jobs * p.relative_performance 52 for p in peers: 53 p.needed_work = total_work * p.jobs * p.relative_performance / total_power 54 55 shells = {} 56 for s in suites: 57 shell = s.shell() 58 if not shell in shells: 59 shells[shell] = Shell(shell) 60 shells[shell].AddSuite(s) 61 # Convert |shells| to list and sort it, shortest total_duration first. 62 shells = [ shells[s] for s in shells ] 63 shells.sort(cmp=lambda x, y: cmp(x.total_duration, y.total_duration)) 64 # Sort tests within each shell, longest duration last (so it's 65 # pop()'ed first). 66 for s in shells: s.SortTests() 67 # Sort peers, least needed_work first. 68 peers.sort(cmp=lambda x, y: cmp(x.needed_work, y.needed_work)) 69 index = 0 70 for shell in shells: 71 while len(shell.tests) > 0: 72 while peers[index].needed_work <= 0: 73 index += 1 74 if index == len(peers): 75 print("BIG FAT WARNING: Assigning tests to peers failed. " 76 "Remaining tests: %d. Going to slow mode." % len(shell.tests)) 77 # Pick the least-busy peer. Sorting the list for each test 78 # is terribly slow, but this is just an emergency fallback anyway. 79 peers.sort(cmp=lambda x, y: cmp(x.needed_work, y.needed_work)) 80 peers[0].ForceAddOneTest(shell.tests.pop(), shell) 81 # If the peer already has a shell assigned and would need this one 82 # and then yet another, try to avoid it. 83 peer = peers[index] 84 if (shell.total_duration < peer.needed_work and 85 len(peer.shells) > 0 and 86 index < len(peers) - 1 and 87 shell.total_duration <= peers[index + 1].needed_work): 88 peers[index + 1].AddTests(shell) 89 else: 90 peer.AddTests(shell) 91