FA-90646 / Garbage collector invariants / Open access
Collection set: least garbage collected first · case 01
The pause budget is spent on regions that reclaim the least memory.
ROOT CAUSE
Candidates are sorted by reclaimable bytes ascending.
THE FAILURE
Candidates are sorted by reclaimable bytes ascending.
Unsuccessful approach: Ordering by live bytes differs whenever region sizes differ.
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:
break
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, 5, 3, 7], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Failed |
| budget stops at the first region that does not fit | {'cset': [1, 2, 5], 'reclaimed': 210, 'time': 90} | {'cset': [1, 2, 7, 3], 'reclaimed': 335, 'time': 65} | Failed |
| expensive region first stops selection | {'cset': [1, 2, 5], 'reclaimed': 210, 'time': 90} | {'cset': [1, 2], 'reclaimed': 160, 'time': 40} | Failed |
| region at exactly the liveness threshold excluded | {'cset': [1, 2, 5, 3, 7], 'reclaimed': 385, 'time': 115} | {'cset': [1, 2, 7, 3, 5], 'reclaimed': 385, 'time': 115} | Failed |
| higher threshold admits more regions | {'cset': [1, 2, 8, 4, 5, 3, 7], 'reclaimed': 410, 'time': 290} | {'cset': [1, 2, 7, 3, 5, 4, 8], 'reclaimed': 410, 'time': 290} | Failed |
| 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 / 20383607aa4ca8d28a796e76d9ddb4506631b94482ccaaf77d546e94ff449774
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[3], r[0]))
for rid, kind, used, live in cands:
t = live * cost
if time + t > budget:
break
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 / 8d21a0b58ce484151b656a428b08b16fa6c7c8e284ca4bd222e99b3a7b29ba12
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 / a471eea7f2fd935f45192bc104d852e7972bb822ca3b2ef25418736ad258a4ed