test_chunking.py (9824B)
1 #!/usr/bin/env python 2 3 import os 4 import random 5 from collections import defaultdict 6 from itertools import chain 7 from unittest import TestCase 8 9 import mozunit 10 from manifestparser.filters import chunk_by_dir, chunk_by_runtime, chunk_by_slice 11 12 here = os.path.dirname(os.path.abspath(__file__)) 13 14 15 class ChunkBySlice(TestCase): 16 """Test chunking related filters""" 17 18 def generate_tests(self, num, disabled=None): 19 disabled = disabled or [] 20 tests = [] 21 for i in range(num): 22 test = {"name": "test%i" % i} 23 if i in disabled: 24 test["disabled"] = "" 25 tests.append(test) 26 return tests 27 28 def run_all_combos(self, num_tests, disabled=None): 29 tests = self.generate_tests(num_tests, disabled=disabled) 30 31 for total in range(1, num_tests + 1): 32 res = [] 33 res_disabled = [] 34 for chunk in range(1, total + 1): 35 f = chunk_by_slice(chunk, total) 36 res.append(list(f(tests, {}))) 37 if disabled: 38 f.disabled = True 39 res_disabled.append(list(f(tests, {}))) 40 41 lengths = [len([t for t in c if "disabled" not in t]) for c in res] 42 # the chunk with the most tests should have at most one more test 43 # than the chunk with the least tests 44 self.assertLessEqual(max(lengths) - min(lengths), 1) 45 46 # chaining all chunks back together should equal the original list 47 # of tests 48 self.assertEqual(list(chain.from_iterable(res)), list(tests)) 49 50 if disabled: 51 lengths = [len(c) for c in res_disabled] 52 self.assertLessEqual(max(lengths) - min(lengths), 1) 53 self.assertEqual(list(chain.from_iterable(res_disabled)), list(tests)) 54 55 def test_chunk_by_slice(self): 56 chunk = chunk_by_slice(1, 1) 57 self.assertEqual(list(chunk([], {})), []) 58 59 self.run_all_combos(num_tests=1) 60 self.run_all_combos(num_tests=10, disabled=[1, 2]) 61 62 num_tests = 67 63 disabled = list(i for i in range(num_tests) if i % 4 == 0) 64 self.run_all_combos(num_tests=num_tests, disabled=disabled) 65 66 def test_two_times_more_chunks_than_tests(self): 67 # test case for bug 1182817 68 tests = self.generate_tests(5) 69 70 total_chunks = 10 71 for i in range(1, total_chunks + 1): 72 # ensure IndexError is not raised 73 chunk_by_slice(i, total_chunks)(tests, {}) 74 75 76 class ChunkByDir(TestCase): 77 """Test chunking related filters""" 78 79 def generate_tests(self, dirs): 80 """ 81 :param dirs: dict of the form, 82 { <dir>: <num tests> } 83 """ 84 i = 0 85 for d, num in dirs.items(): 86 for _ in range(num): 87 i += 1 88 name = "test%i" % i 89 test = {"name": name, "relpath": os.path.join(d, name)} 90 yield test 91 92 def run_all_combos(self, dirs): 93 tests = list(self.generate_tests(dirs)) 94 95 deepest = max(len(t["relpath"].split(os.sep)) - 1 for t in tests) 96 for depth in range(1, deepest + 1): 97 98 def num_groups(tests): 99 unique = set() 100 for rp in [t["relpath"] for t in tests]: 101 p = rp.split(os.sep) 102 p = p[: min(depth, len(p) - 1)] 103 unique.add(os.sep.join(p)) 104 return len(unique) 105 106 for total in range(1, num_groups(tests) + 1): 107 res = [] 108 for this in range(1, total + 1): 109 f = chunk_by_dir(this, total, depth) 110 res.append(list(f(tests, {}))) 111 112 lengths = list(map(num_groups, res)) 113 # the chunk with the most dirs should have at most one more 114 # dir than the chunk with the least dirs 115 self.assertLessEqual(max(lengths) - min(lengths), 1) 116 117 all_chunks = list(chain.from_iterable(res)) 118 # chunk_by_dir will mess up order, but chained chunks should 119 # contain all of the original tests and be the same length 120 self.assertEqual(len(all_chunks), len(tests)) 121 for t in tests: 122 self.assertIn(t, all_chunks) 123 124 def test_chunk_by_dir(self): 125 chunk = chunk_by_dir(1, 1, 1) 126 self.assertEqual(list(chunk([], {})), []) 127 128 dirs = { 129 "a": 2, 130 } 131 self.run_all_combos(dirs) 132 133 dirs = { 134 "": 1, 135 "foo": 1, 136 "bar": 0, 137 "/foobar": 1, 138 } 139 self.run_all_combos(dirs) 140 141 dirs = { 142 "a": 1, 143 "b": 1, 144 "a/b": 2, 145 "a/c": 1, 146 } 147 self.run_all_combos(dirs) 148 149 dirs = { 150 "a": 5, 151 "a/b": 4, 152 "a/b/c": 7, 153 "a/b/c/d": 1, 154 "a/b/c/e": 3, 155 "b/c": 2, 156 "b/d": 5, 157 "b/d/e": 6, 158 "c": 8, 159 "c/d/e/f/g/h/i/j/k/l": 5, 160 "c/d/e/f/g/i/j/k/l/m/n": 2, 161 "c/e": 1, 162 } 163 self.run_all_combos(dirs) 164 165 166 class ChunkByRuntime(TestCase): 167 """Test chunking related filters""" 168 169 def generate_tests(self, dirs): 170 """ 171 :param dirs: dict of the form, 172 { <dir>: <num tests> } 173 """ 174 i = 0 175 for d, num in dirs.items(): 176 for _ in range(num): 177 i += 1 178 name = "test%i" % i 179 manifest = os.path.join(d, "manifest.toml") 180 test = { 181 "name": name, 182 "relpath": os.path.join(d, name), 183 "manifest": manifest, 184 "manifest_relpath": manifest, 185 } 186 yield test 187 188 def get_runtimes(self, tests): 189 runtimes = defaultdict(int) 190 for test in tests: 191 runtimes[test["manifest_relpath"]] += random.randint(0, 100) 192 return runtimes 193 194 def chunk_by_round_robin(self, tests, total, runtimes): 195 tests_by_manifest = [] 196 for manifest, runtime in runtimes.items(): 197 mtests = [t for t in tests if t["manifest_relpath"] == manifest] 198 tests_by_manifest.append((runtime, mtests)) 199 tests_by_manifest.sort(key=lambda x: x[0], reverse=False) 200 201 chunks = [[] for i in range(total)] 202 d = 1 # direction 203 i = 0 204 for runtime, batch in tests_by_manifest: 205 chunks[i].extend(batch) 206 207 # "draft" style (last pick goes first in the next round) 208 if (i == 0 and d == -1) or (i == total - 1 and d == 1): 209 d = -d 210 else: 211 i += d 212 213 # make sure this test algorithm is valid 214 all_chunks = list(chain.from_iterable(chunks)) 215 self.assertEqual(len(all_chunks), len(tests)) 216 for t in tests: 217 self.assertIn(t, all_chunks) 218 return chunks 219 220 def run_all_combos(self, dirs): 221 tests = list(self.generate_tests(dirs)) 222 runtimes = self.get_runtimes(tests) 223 224 for total in range(1, len(dirs) + 1): 225 chunks = [] 226 for this in range(1, total + 1): 227 f = chunk_by_runtime(this, total, runtimes) 228 ret = list(f(tests, {})) 229 chunks.append(ret) 230 231 # chunk_by_runtime will mess up order, but chained chunks should 232 # contain all of the original tests and be the same length 233 all_chunks = list(chain.from_iterable(chunks)) 234 self.assertEqual(len(all_chunks), len(tests)) 235 for t in tests: 236 self.assertIn(t, all_chunks) 237 238 # calculate delta between slowest and fastest chunks 239 def runtime_delta(chunks): 240 totals = [] 241 for chunk in chunks: 242 manifests = set([t["manifest_relpath"] for t in chunk]) 243 total = sum(runtimes[m] for m in manifests) 244 totals.append(total) 245 return max(totals) - min(totals) 246 247 delta = runtime_delta(chunks) 248 249 # redo the chunking a second time using a round robin style 250 # algorithm 251 chunks = self.chunk_by_round_robin(tests, total, runtimes) 252 # sanity check the round robin algorithm 253 all_chunks = list(chain.from_iterable(chunks)) 254 self.assertEqual(len(all_chunks), len(tests)) 255 for t in tests: 256 self.assertIn(t, all_chunks) 257 258 # since chunks will never have exactly equal runtimes, it's hard 259 # to tell if they were chunked optimally. Make sure it at least 260 # beats a naive round robin approach. 261 self.assertLessEqual(delta, runtime_delta(chunks)) 262 263 def test_chunk_by_runtime(self): 264 random.seed(42) 265 266 chunk = chunk_by_runtime(1, 1, {}) 267 self.assertEqual(list(chunk([], {})), []) 268 269 dirs = { 270 "a": 2, 271 } 272 self.run_all_combos(dirs) 273 274 dirs = { 275 "": 1, 276 "foo": 1, 277 "bar": 0, 278 "/foobar": 1, 279 } 280 self.run_all_combos(dirs) 281 282 dirs = { 283 "a": 1, 284 "b": 1, 285 "a/b": 2, 286 "a/c": 1, 287 } 288 self.run_all_combos(dirs) 289 290 dirs = { 291 "a": 5, 292 "a/b": 4, 293 "a/b/c": 7, 294 "a/b/c/d": 1, 295 "a/b/c/e": 3, 296 "b/c": 2, 297 "b/d": 5, 298 "b/d/e": 6, 299 "c": 8, 300 "c/d/e/f/g/h/i/j/k/l": 5, 301 "c/d/e/f/g/i/j/k/l/m/n": 2, 302 "c/e": 1, 303 } 304 self.run_all_combos(dirs) 305 306 307 if __name__ == "__main__": 308 mozunit.main()