FA-90651 / Garbage collector invariants / Open access
Collection set: selection skips over regions that do not fit · case 01
Cheaper, less profitable regions are packed in after a better region was rejected.
ROOT CAUSE
A candidate that exceeds the remaining budget is skipped instead of ending selection.
THE FAILURE
A candidate that exceeds the remaining budget is skipped instead of ending selection.
Unsuccessful approach: Skipping only candidates that exceed the whole budget overshoots the pause budget.
Case contract
Regions are [id, kind, used, live]. All young regions are always collected (their live bytes cost live * cost). Old regions whose liveness is strictly below live_pct percent (live * 100 < pct * used) are candidates; humongous regions never are. Candidates are ordered by reclaimable bytes (used - live) descending, ties by id, and added while the accumulated cost stays within budget; selection stops at the first candidate that does not fit. Return the collection set, its cost and reclaimed bytes.
Why this case matters
Region-based collectors meet pause goals by choosing the collection set against a cost budget.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(regions, budget, live_pct, cost):
cset = []
time = 0
for rid, kind, used, live in regions:
if kind == 'young':
cset.append(rid)
time += live * cost
cands = [r for r in regions if r[1] == 'old' and r[3] * 100 < live_pct * r[2]]
cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))
for rid, kind, used, live in cands:
t = live * cost
if time + t > budget:
continue
cset.append(rid)
time += t
reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
101,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
101,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
85,
85,
2),
{'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
102,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
102,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
90,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
103,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
103,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
95,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
104,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
104,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
100,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
105,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: candidates fill the budget exactly | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Passed |
| budget stops at the first region that does not fit | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | Passed |
| expensive region first stops selection | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Failed |
| region at exactly the liveness threshold excluded | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Passed |
| higher threshold admits more regions | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | Passed |
| cost multiplier | {'cset': [1, 2], 'reclaimed': 160, 'time': 80} | {'cset': [1, 2], 'reclaimed': 160, 'time': 80} | Passed |
| control: only young regions fit | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Passed |
SHA-256 / dd596f0931f879830f9106e1c83252db12af0fdc927ea87859fcdfecac4ec626
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(regions, budget, live_pct, cost):
cset = []
time = 0
for rid, kind, used, live in regions:
if kind == 'young':
cset.append(rid)
time += live * cost
cands = [r for r in regions if r[1] == 'old' and r[3] * 100 < live_pct * r[2]]
cands.sort(key=lambda r: (-(r[2] - r[3]), r[0]))
for rid, kind, used, live in cands:
t = live * cost
if t > budget:
continue
cset.append(rid)
time += t
reclaimed = sum(r[2] - r[3] for r in regions if r[0] in cset)
return {'cset': cset, 'time': time, 'reclaimed': reclaimed}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
101,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
101,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
85,
85,
2),
{'cset': [1, 2], 'reclaimed': 160, 'time': 80}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
102,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
102,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
90,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
103,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
103,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
95,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
104,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
104,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
100,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})],
[('regression: candidates fill the budget exactly',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
115,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('budget stops at the first region that does not fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
1),
{'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65}),
('expensive region first stops selection',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200],
[11, 'old', 300, 200]],
105,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40}),
('region at exactly the liveness threshold excluded',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
85,
1),
{'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115}),
('higher threshold admits more regions',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
1000,
91,
1),
{'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290}),
('cost multiplier',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
105,
85,
2),
{'cset': [1, 2, 7], 'reclaimed': 255, 'time': 90}),
('control: only young regions fit',
([[1, 'young', 100, 30],
[2, 'young', 100, 10],
[3, 'old', 100, 20],
[4, 'old', 100, 85],
[5, 'old', 100, 50],
[6, 'humongous', 400, 0],
[7, 'old', 100, 5],
[8, 'old', 100, 90],
[9, 'humongous', 200, 200]],
20,
85,
1),
{'cset': [1, 2], 'reclaimed': 160, 'time': 40})]]
for label, args, expected in cases[N - 1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| regression: candidates fill the budget exactly | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Passed |
| budget stops at the first region that does not fit | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | Failed |
| expensive region first stops selection | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Failed |
| region at exactly the liveness threshold excluded | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Passed |
| higher threshold admits more regions | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | Passed |
| cost multiplier | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 130} | {'cset': [1, 2], 'reclaimed': 160, 'time': 80} | Failed |
| control: only young regions fit | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Failed |
SHA-256 / 4c2ff62c669b152372c65ed47423907194ba2c3d591eef70045115e4923527fa
HELD IN THE MEMBER ARCHIVE
The verified repair and its recorded checks are member-only.
This mechanism has 7 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.
Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.
Member access is invitation-based. Sign in with your invited account to inspect the repair.
Sign in to the archive ↗Verification & scope
A deterministic, bounded teaching model of one garbage-collector mechanism with stipulated rules; it is not a production collector and claims no conformance to any particular runtime. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:51:28.793950+00:00.
Case digest / 7062c10a906e9111971f7db974aa155f5e3bb9b5a2012b004ee49b6a5cb0ba80