"""Every number the commentary quotes, pinned. Plain asserts, no pytest. python3 test_wsq.py """ import statistics import wsq TESTS = [] def test(fn): TESTS.append(fn) return fn def tree(end, P=8, sc=8, victim="rr", root=1024): s = wsq.Sim(P, leaf=8, steal_end=end, victim=victim, steal_cost=sc) wsq.spawn_tree(s, root) return s.run(), s def wide(end, P=8, sc=8): s = wsq.Sim(P, leaf=8, steal_end=end, steal_cost=sc) wsq.spawn_flat(s, 128, 8) return s.run(), s def bag(end, seed=7, stealing=True, victim="rr", sc=8): s = wsq.Sim(4, leaf=8, steal_end=end, victim=victim, steal_cost=sc) wsq.preload(s, wsq.uneven_bag(seed)) return s.run(stealing=stealing), s # --------------------------------------------------------------- the model @test def task_divisibility(): """preload deals Task(c, c), which can never split; a tree root can.""" assert wsq.Task(200, 200).divisible is False assert wsq.Task(200, 200).cost() == 200 assert wsq.Task(1024, 8).divisible is True assert wsq.Task(1024, 8).cost() == wsq.SPLIT_TICKS == 1 assert wsq.Task(8, 8).divisible is False @test def subtree_arithmetic(): """1024 at leaf 8 = 128 leaves x 8 ticks + 127 splits x 1 = 1151.""" s = wsq.Sim(1, leaf=8) assert s.subtree(wsq.Task(1024, 8)) == 1024 + 127 == 1151 assert s.subtree(wsq.Task(512, 8)) == 512 + 63 == 575 assert s.subtree(wsq.Task(8, 8)) == 8 @test def work_is_conserved(): """Executed ticks equal the workload, whatever the schedule does.""" for end in (wsq.FAR, wsq.OWN): _, s = tree(end) assert wsq.total_work(s) == 1151, wsq.total_work(s) _, s = bag(end) assert wsq.total_work(s) == 2959 _, s = wide(end) assert wsq.total_work(s) == 1024 @test def makespan_never_beats_the_floor(): """No schedule finishes before ceil(W/P). The floor is what ยง6 measures against, so it had better be a floor.""" for end in (wsq.FAR, wsq.OWN): for mk, s in (tree(end), bag(end), wide(end)): assert mk >= -(-wsq.total_work(s) // len(s.w)), (end, mk) @test def no_stealing_is_exactly_the_hoarders_own_load(): """2468 is worker 0's pile, to the tick -- nobody helps, nobody idles productively. This is the off-by-one the run loop's top-of-pass termination test exists to protect.""" loads = wsq.uneven_bag(7) mk, _ = bag(wsq.FAR, stealing=False) assert mk == sum(loads[0]) == 2468, mk # ------------------------------------------------------- panels A and B @test def panel_a_stealing_works(): assert sum(sum(c) for c in wsq.uneven_bag(7)) == 2959 assert -(-2959 // 4) == 740 assert bag(wsq.FAR, stealing=False)[0] == 2468 mk, s = bag(wsq.FAR) assert (mk, s.steals, s.failed, s.moved) == (925, 16, 75, 1691) @test def panel_b_the_wrong_end_wins_here(): far, own = bag(wsq.FAR), bag(wsq.OWN) assert (own[0], own[1].steals, own[1].failed, own[1].moved) == \ (854, 16, 40, 1619) assert own[0] - far[0] == -71 @test def panel_b_500_orderings(): diffs = [bag(wsq.OWN, seed=n)[0] - bag(wsq.FAR, seed=n)[0] for n in range(1, 501)] assert sum(1 for d in diffs if d > 0) == 224 assert sum(1 for d in diffs if d < 0) == 271 assert diffs.count(0) == 5 assert round(statistics.mean(diffs), 3) == -4.756 assert round(statistics.stdev(diffs), 1) == 38.3 assert (min(diffs), max(diffs)) == (-114, 113) # ------------------------------------------------------- panels C and D @test def panel_c_no_gradient_means_no_difference(): """The load-bearing claim of the whole page: without a size gradient the two ends are not similar, they are the same integer on every counter.""" far_mk, f = wide(wsq.FAR) own_mk, o = wide(wsq.OWN) assert (far_mk, f.steals, f.failed, f.moved) == (552, 60, 364, 480) assert (far_mk, f.steals, f.failed, f.moved) == \ (own_mk, o.steals, o.failed, o.moved) assert f.moved / f.steals == o.moved / o.steals == 8.0 @test def panel_c_holds_at_every_steal_cost(): for sc in (1, 2, 4, 8, 16, 32): far_mk, f = wide(wsq.FAR, sc=sc) own_mk, o = wide(wsq.OWN, sc=sc) assert (far_mk, f.steals, f.failed) == (own_mk, o.steals, o.failed), sc @test def panel_d_the_gradient_splits_the_ends(): far_mk, f = tree(wsq.FAR) own_mk, o = tree(wsq.OWN) assert (far_mk, f.steals, f.failed, f.moved) == (211, 16, 48, 1937) assert (own_mk, o.steals, o.failed, o.moved) == (342, 50, 145, 1669) assert round(f.moved / f.steals, 1) == 121.1 assert round(o.moved / o.steals, 1) == 33.4 assert round(own_mk / far_mk, 2) == 1.62 @test def panel_d_first_steal_is_half_the_tree(): """The mechanism in one row of the log: the far end's opening steal moves 575 ticks -- the whole 512-subtree -- against the own end's 8.""" _, f = tree(wsq.FAR) _, o = tree(wsq.OWN) assert f.log[0][3:] == (512, 575), f.log[0] assert o.log[0][3:] == (8, 8), o.log[0] assert max(r[4] for r in o.log) < max(r[4] for r in f.log) @test def panel_e_sweep(): expected = {1: (159, 164, 32, 35), 4: (177, 278, 18, 78), 8: (211, 342, 16, 50), 16: (251, 602, 12, 42)} for sc, exp in expected.items(): far_mk, f = tree(wsq.FAR, sc=sc) own_mk, o = tree(wsq.OWN, sc=sc) assert (far_mk, own_mk, f.steals, o.steals) == exp, (sc, far_mk, own_mk) assert round(164 / 159, 2) == 1.03 # free steals: the rule evaporates assert round(602 / 251, 2) == 2.40 # ------------------------------------------------------------ section 7 @test def most_steal_attempts_fail(): _, s = bag(wsq.FAR) assert (s.failed, s.steals) == (75, 16) _, s = wide(wsq.FAR) assert (s.failed, s.steals) == (364, 60) assert round(364 / (364 + 60) * 100) == 86 @test def the_omniscient_victim_oracle(): rr_mk, rr = tree(wsq.FAR, victim="rr") rand_mk, rnd = tree(wsq.FAR, victim="random") rich_mk, rich = tree(wsq.FAR, victim="richest") assert (rr_mk, rr.failed) == (211, 48) assert (rand_mk, rnd.failed) == (222, 51) assert (rich_mk, rich.failed) == (168, 4) assert rich_mk < rr_mk < rand_mk # but richest costs O(P) a probe @test def victim_policy_never_rescues_the_wrong_end(): """Even the oracle cannot buy back what the own end gives away.""" for victim in ("rr", "random", "richest"): far_mk, _ = tree(wsq.FAR, victim=victim) own_mk, _ = tree(wsq.OWN, victim=victim) assert own_mk > far_mk, victim # ------------------------------------------------------------ robustness @test def the_gradient_result_is_not_one_lucky_tree(): for root in (256, 512, 1024, 2048, 4096): far_mk, _ = tree(wsq.FAR, root=root) own_mk, _ = tree(wsq.OWN, root=root) assert own_mk / far_mk > 1.5, (root, far_mk, own_mk) for P in (4, 8, 16): far_mk, _ = tree(wsq.FAR, P=P) own_mk, _ = tree(wsq.OWN, P=P) assert own_mk / far_mk > 1.5, (P, far_mk, own_mk) @test def the_far_end_stays_inside_the_published_attempt_bound(): """Blumofe & Leiserson bound the expected number of steal ATTEMPTS by O(P*T_inf). Span of the 1024/leaf-8 tree: 7 splits x 1 tick + one 8-tick leaf = 15. The far end sits under P*T_inf; the own end blows through it, which is the point -- it is not the algorithm the theorem is about.""" span = 7 * wsq.SPLIT_TICKS + 8 assert span == 15 for P in (8, 16, 32): _, f = tree(wsq.FAR, P=P) _, o = tree(wsq.OWN, P=P) assert f.steals + f.failed < P * span assert o.steals + o.failed > P * span @test def runs_are_byte_identical(): """No wall clock, no unseeded RNG: three runs, one answer.""" seen = {tree(wsq.FAR)[0] for _ in range(3)} assert seen == {211} seen = {tree(wsq.FAR, victim="random")[0] for _ in range(3)} assert seen == {222} @test def bad_policy_is_rejected(): s = wsq.Sim(4, victim="nearest") wsq.preload(s, [[10], [], [], []]) try: s.run() except ValueError as e: assert "nearest" in str(e) else: assert False, "expected ValueError" if __name__ == "__main__": for fn in TESTS: fn() print(f"ok {fn.__name__}") print(f"\n{len(TESTS)} tests passed")