133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# Copyright 2012 the V8 project authors. All rights reserved. 233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# Redistribution and use in source and binary forms, with or without 333e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# modification, are permitted provided that the following conditions are 433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# met: 533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# 633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# * Redistributions of source code must retain the above copyright 733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# notice, this list of conditions and the following disclaimer. 833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# * Redistributions in binary form must reproduce the above 933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# copyright notice, this list of conditions and the following 1033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# disclaimer in the documentation and/or other materials provided 1133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# with the distribution. 1233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# * Neither the name of Google Inc. nor the names of its 1333e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# contributors may be used to endorse or promote products derived 1433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# from this software without specific prior written permission. 1533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# 1633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2333e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 2833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 2933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.orgclass Shell(object): 3033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org def __init__(self, shell): 3133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org self.shell = shell 3233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org self.tests = [] 3333e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org self.total_duration = 0.0 3433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 3533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org def AddSuite(self, suite): 3633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org self.tests += suite.tests 3733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org self.total_duration += suite.total_duration 3833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 3933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org def SortTests(self): 4033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org self.tests.sort(cmp=lambda x, y: cmp(x.duration, y.duration)) 4133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 4233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 4333e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.orgdef Assign(suites, peers): 4433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org total_work = 0.0 4533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org for s in suites: 4633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org total_work += s.CalculateTotalDuration() 4733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 4833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org total_power = 0.0 4933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org for p in peers: 5033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org p.assigned_work = 0.0 5133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org total_power += p.jobs * p.relative_performance 5233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org for p in peers: 5333e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org p.needed_work = total_work * p.jobs * p.relative_performance / total_power 5433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org 5533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org shells = {} 5633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org for s in suites: 5733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org shell = s.shell() 5833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org if not shell in shells: 5933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org shells[shell] = Shell(shell) 6033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org shells[shell].AddSuite(s) 6133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org # Convert |shells| to list and sort it, shortest total_duration first. 6233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org shells = [ shells[s] for s in shells ] 6333e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org shells.sort(cmp=lambda x, y: cmp(x.total_duration, y.total_duration)) 6433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org # Sort tests within each shell, longest duration last (so it's 6533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org # pop()'ed first). 6633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org for s in shells: s.SortTests() 6733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org # Sort peers, least needed_work first. 6833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org peers.sort(cmp=lambda x, y: cmp(x.needed_work, y.needed_work)) 6933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org index = 0 7033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org for shell in shells: 7133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org while len(shell.tests) > 0: 7233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org while peers[index].needed_work <= 0: 7333e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org index += 1 7433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org if index == len(peers): 7533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org print("BIG FAT WARNING: Assigning tests to peers failed. " 7633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org "Remaining tests: %d. Going to slow mode." % len(shell.tests)) 7733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org # Pick the least-busy peer. Sorting the list for each test 7833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org # is terribly slow, but this is just an emergency fallback anyway. 7933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org peers.sort(cmp=lambda x, y: cmp(x.needed_work, y.needed_work)) 8033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org peers[0].ForceAddOneTest(shell.tests.pop(), shell) 8133e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org # If the peer already has a shell assigned and would need this one 8233e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org # and then yet another, try to avoid it. 8333e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org peer = peers[index] 8433e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org if (shell.total_duration < peer.needed_work and 8533e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org len(peer.shells) > 0 and 8633e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org index < len(peers) - 1 and 8733e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org shell.total_duration <= peers[index + 1].needed_work): 8833e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org peers[index + 1].AddTests(shell) 8933e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org else: 9033e09c8efd078308de3c77a88301566f65c07befverwaest@chromium.org peer.AddTests(shell) 91