FA-90621 / Garbage collector invariants / Open access
Adaptive tenuring: target ratio truncated to zero · case 01
Every survivor is promoted after its first collection.
ROOT CAUSE
ratio // 100 is evaluated first, which is 0 for any ratio below 100.
VERIFIED REPAIR
Multiply before dividing: capacity * ratio // 100.
Unsuccessful approach: Dividing the capacity first loses the remainder for capacities that are not multiples of 100.
Case contract
Survivors are [id, age, size] after a minor collection. desired = capacity * ratio // 100. Walking ages 1..max_threshold, accumulate sizes; the first age at which the running total exceeds desired becomes the tenuring threshold (max_threshold if never exceeded). Objects with age >= threshold are promoted; the rest are placed youngest first (ties by id) into the survivor space of the given capacity, and any that do not fit overflow into promotion. Return threshold, promoted ids, kept ids and bytes used.
Why this case matters
Tenuring policy controls premature promotion and survivor overflow in generational collectors.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ages, capacity, ratio, max_threshold):
desired = capacity * (ratio // 100)
by_age = {}
for _, age, size in ages:
by_age[age] = by_age.get(age, 0) + size
total = 0
threshold = max_threshold
for age in range(1, max_threshold + 1):
total += by_age.get(age, 0)
if total > desired:
threshold = age
break
promote = [o for o, age, size in ages if age >= threshold]
stay = sorted([x for x in ages if x[1] < threshold], key=lambda x: (x[1], x[0]))
used = 0
kept = []
for o, age, size in stay:
if used + size <= capacity:
kept.append(o)
used += size
else:
promote.append(o)
return {'threshold': threshold, 'promoted': sorted(promote), 'kept': sorted(kept), 'used': used}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 1]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 6]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 1]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 11], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 1]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 6]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11}),
('control: empty survivor set',
([], 101, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 2]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 47}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 7]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 2]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 72}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 12], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 72}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 2]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 7]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 12}),
('control: empty survivor set',
([], 102, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 3]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 48}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 8]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 3]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 73}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 13], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 73}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 3]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 8]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 13}),
('control: empty survivor set',
([], 103, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 4]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 49}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 9]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 4]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 74}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 14], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 74}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 4]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 9]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 14}),
('control: empty survivor set',
([], 104, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 5]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 50}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 10]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 5]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 75}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 15], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 75}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 5]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 10]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 15}),
('control: empty survivor set',
([], 105, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})]]
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: cumulative sizes cross the desired size | {'kept': [], 'promoted': [1, 2, 3, 4, 5], 'threshold': 1, 'used': 0} | {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46} | Failed |
| cumulative size exactly at the desired size | {'kept': [], 'promoted': [1, 2, 3], 'threshold': 1, 'used': 0} | {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50} | Failed |
| ratio of a capacity that is not a multiple of 100 | {'kept': [], 'promoted': [1, 2, 3], 'threshold': 1, 'used': 0} | {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71} | Failed |
| survivors overflow the survivor space | {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71} | {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71} | Passed |
| survivors fill the space exactly | {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100} | {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100} | Passed |
| threshold never crossed | {'kept': [], 'promoted': [1, 2], 'threshold': 1, 'used': 0} | {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11} | Failed |
| control: empty survivor set | {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0} | {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0} | Passed |
SHA-256 / dcf5b9a4ba8758218b5cfb7f7fcb0407ebb976989dba18f6565b1240fdcb5826
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ages, capacity, ratio, max_threshold):
desired = capacity // 100 * ratio
by_age = {}
for _, age, size in ages:
by_age[age] = by_age.get(age, 0) + size
total = 0
threshold = max_threshold
for age in range(1, max_threshold + 1):
total += by_age.get(age, 0)
if total > desired:
threshold = age
break
promote = [o for o, age, size in ages if age >= threshold]
stay = sorted([x for x in ages if x[1] < threshold], key=lambda x: (x[1], x[0]))
used = 0
kept = []
for o, age, size in stay:
if used + size <= capacity:
kept.append(o)
used += size
else:
promote.append(o)
return {'threshold': threshold, 'promoted': sorted(promote), 'kept': sorted(kept), 'used': used}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 1]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 6]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 1]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 11], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 1]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 6]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11}),
('control: empty survivor set',
([], 101, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 2]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 47}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 7]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 2]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 72}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 12], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 72}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 2]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 7]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 12}),
('control: empty survivor set',
([], 102, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 3]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 48}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 8]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 3]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 73}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 13], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 73}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 3]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 8]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 13}),
('control: empty survivor set',
([], 103, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 4]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 49}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 9]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 4]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 74}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 14], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 74}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 4]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 9]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 14}),
('control: empty survivor set',
([], 104, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 5]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 50}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 10]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 5]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 75}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 15], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 75}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 5]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 10]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 15}),
('control: empty survivor set',
([], 105, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})]]
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: cumulative sizes cross the desired size | {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46} | {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46} | Passed |
| cumulative size exactly at the desired size | {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50} | {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50} | Passed |
| ratio of a capacity that is not a multiple of 100 | {'kept': [1], 'promoted': [2, 3], 'threshold': 2, 'used': 40} | {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71} | Failed |
| survivors overflow the survivor space | {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71} | {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71} | Passed |
| survivors fill the space exactly | {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100} | {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100} | Passed |
| threshold never crossed | {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11} | {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11} | Passed |
| control: empty survivor set | {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0} | {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0} | Passed |
SHA-256 / 5eb4a6a4bd8fdda1c5dc7950cc158cac150e6cbdec52899a25c1d1e310e94363
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ages, capacity, ratio, max_threshold):
desired = capacity * ratio // 100
by_age = {}
for _, age, size in ages:
by_age[age] = by_age.get(age, 0) + size
total = 0
threshold = max_threshold
for age in range(1, max_threshold + 1):
total += by_age.get(age, 0)
if total > desired:
threshold = age
break
promote = [o for o, age, size in ages if age >= threshold]
stay = sorted([x for x in ages if x[1] < threshold], key=lambda x: (x[1], x[0]))
used = 0
kept = []
for o, age, size in stay:
if used + size <= capacity:
kept.append(o)
used += size
else:
promote.append(o)
return {'threshold': threshold, 'promoted': sorted(promote), 'kept': sorted(kept), 'used': used}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 1]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 6]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 1]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 11], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 1]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 6]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11}),
('control: empty survivor set',
([], 101, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 2]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 47}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 7]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 2]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 72}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 12], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 72}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 2]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 7]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 12}),
('control: empty survivor set',
([], 102, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 3]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 48}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 8]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 3]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 73}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 13], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 73}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 3]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 8]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 13}),
('control: empty survivor set',
([], 103, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 4]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 49}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 9]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 4]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 74}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 14], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 74}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 4]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 9]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 14}),
('control: empty survivor set',
([], 104, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})],
[('regression: cumulative sizes cross the desired size',
([[1, 1, 20], [2, 2, 25], [3, 3, 10], [4, 4, 30], [5, 1, 5]], 100, 50, 15),
{'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 50}),
('cumulative size exactly at the desired size',
([[1, 1, 30], [2, 2, 20], [3, 3, 10]], 100, 50, 15),
{'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50}),
('ratio of a capacity that is not a multiple of 100',
([[1, 1, 40], [2, 2, 30], [3, 3, 5]], 150, 50, 15),
{'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 75}),
('survivors overflow the survivor space',
([[1, 1, 30], [2, 1, 30], [3, 2, 30], [4, 1, 15], [5, 2, 40]], 100, 200, 3),
{'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 75}),
('survivors fill the space exactly',
([[1, 1, 60], [2, 1, 40], [3, 2, 5]], 100, 200, 2),
{'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100}),
('threshold never crossed',
([[1, 1, 5], [2, 3, 10]], 100, 50, 6),
{'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 15}),
('control: empty survivor set',
([], 105, 50, 15),
{'kept': [], 'promoted': [], 'threshold': 15, 'used': 0})]]
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: cumulative sizes cross the desired size | {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46} | {'kept': [1, 2, 5], 'promoted': [3, 4], 'threshold': 3, 'used': 46} | Passed |
| cumulative size exactly at the desired size | {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50} | {'kept': [1, 2], 'promoted': [3], 'threshold': 3, 'used': 50} | Passed |
| ratio of a capacity that is not a multiple of 100 | {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71} | {'kept': [1, 2, 3], 'promoted': [], 'threshold': 15, 'used': 71} | Passed |
| survivors overflow the survivor space | {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71} | {'kept': [1, 2, 4], 'promoted': [3, 5], 'threshold': 3, 'used': 71} | Passed |
| survivors fill the space exactly | {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100} | {'kept': [1, 2], 'promoted': [3], 'threshold': 2, 'used': 100} | Passed |
| threshold never crossed | {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11} | {'kept': [1, 2], 'promoted': [], 'threshold': 6, 'used': 11} | Passed |
| control: empty survivor set | {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0} | {'kept': [], 'promoted': [], 'threshold': 15, 'used': 0} | Passed |
SHA-256 / baecc4f96fc4585f74bdb493a81d8d58f45de5dbb20a14be44435c78c8eec39e
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.441472+00:00.
Case digest / 12bd7ca24c58072856c2debbe0b590c14a11bd6c1937ff2c636d2bc71511b8e0