FAILURE MAP
← Case archive

FA-90816 / Garbage collector invariants / Open access

Heap resizing: growth target rounded down · case 01

After growing, the free share is still just below the minimum and the heap grows again next cycle.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The target capacity uses floor division.

THE FAILURE

The target capacity uses floor division.

Unsuccessful approach: Adding one unconditionally overshoots when the division is exact.

Case contract

After each full collection with live bytes L and capacity C: if the free share (C - L) / C is below min_free percent, grow to the smallest capacity whose free share is at least min_free, i.e. ceil(L * 100 / (100 - min_free)), never shrinking and never above max_heap; if the free share exceeds max_free percent, compute ceil(L * 100 / (100 - max_free)) floored at min_heap and move shrink_pct percent of the way from C toward it (integer arithmetic). Otherwise keep C. Return the capacity after each collection.

Why this case matters

Heap sizing policies decide footprint and GC frequency; rounding and clamping errors oscillate or overshoot.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(lives, cap0, min_heap, max_heap, min_free, max_free, shrink_pct):
    cap = cap0
    out = []
    for live in lives:
        free = cap - live
        if free * 100 < min_free * cap:
            want = live * 100 // (100 - min_free)
            cap = min(max(want, cap), max_heap)
        elif free * 100 > max_free * cap:
            want = -(-live * 100 // (100 - max_free))
            want = max(want, min_heap)
            cap = cap - (cap - want) * shrink_pct // 100
        out.append(cap)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: grow, hold and shrink',
   ([150, 150, 61, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 227, 164]),
  ('growth target rounds up', ([102], 150, 100, 1000, 40, 70, 50), [170]),
  ('growth clamped at the maximum heap', ([701, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([11, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([31], 600, 100, 1000, 40, 70, 25), [476]),
  ('free ratio exactly at the minimum', ([120, 181], 200, 100, 1000, 40, 70, 50), [200, 302]),
  ('control: within the band', ([101], 200, 100, 1000, 40, 70, 50), [200])],
 [('regression: grow, hold and shrink',
   ([150, 150, 62, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 229, 165]),
  ('growth target rounds up', ([103], 150, 100, 1000, 40, 70, 50), [172]),
  ('growth clamped at the maximum heap', ([702, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([12, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([32], 600, 100, 1000, 40, 70, 25), [477]),
  ('free ratio exactly at the minimum', ([120, 182], 200, 100, 1000, 40, 70, 50), [200, 304]),
  ('control: within the band', ([102], 200, 100, 1000, 40, 70, 50), [200])],
 [('regression: grow, hold and shrink',
   ([150, 150, 63, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 230, 165]),
  ('growth target rounds up', ([104], 150, 100, 1000, 40, 70, 50), [174]),
  ('growth clamped at the maximum heap', ([703, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([13, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([33], 600, 100, 1000, 40, 70, 25), [478]),
  ('free ratio exactly at the minimum', ([120, 183], 200, 100, 1000, 40, 70, 50), [200, 305]),
  ('control: within the band', ([103], 200, 100, 1000, 40, 70, 50), [200])],
 [('regression: grow, hold and shrink',
   ([150, 150, 64, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 232, 166]),
  ('growth target rounds up', ([105], 150, 100, 1000, 40, 70, 50), [175]),
  ('growth clamped at the maximum heap', ([704, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([14, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([34], 600, 100, 1000, 40, 70, 25), [479]),
  ('free ratio exactly at the minimum', ([120, 184], 200, 100, 1000, 40, 70, 50), [200, 307]),
  ('control: within the band', ([104], 200, 100, 1000, 40, 70, 50), [200])],
 [('regression: grow, hold and shrink',
   ([150, 150, 65, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 234, 167]),
  ('growth target rounds up', ([106], 150, 100, 1000, 40, 70, 50), [177]),
  ('growth clamped at the maximum heap', ([705, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([15, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([35], 600, 100, 1000, 40, 70, 25), [480]),
  ('free ratio exactly at the minimum', ([120, 185], 200, 100, 1000, 40, 70, 50), [200, 309]),
  ('control: within the band', ([105], 200, 100, 1000, 40, 70, 50), [200])]]
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 fixtureActualExpectedOutcome
regression: grow, hold and shrink[250, 250, 227, 164][250, 250, 227, 164]Passed
growth target rounds up[170][170]Passed
growth clamped at the maximum heap[1000, 1000][1000, 1000]Passed
shrinking stops at the minimum heap[275, 213, 182][275, 213, 182]Passed
shrink moves part of the way[476][476]Passed
free ratio exactly at the minimum[200, 301][200, 302]Failed
control: within the band[200][200]Passed

SHA-256 / 3904501e1a7b51741ed1aacc581aec244e151f02d1934e9c943f9b1e1d0db77d

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(lives, cap0, min_heap, max_heap, min_free, max_free, shrink_pct):
    cap = cap0
    out = []
    for live in lives:
        free = cap - live
        if free * 100 < min_free * cap:
            want = live * 100 // (100 - min_free) + 1
            cap = min(max(want, cap), max_heap)
        elif free * 100 > max_free * cap:
            want = -(-live * 100 // (100 - max_free))
            want = max(want, min_heap)
            cap = cap - (cap - want) * shrink_pct // 100
        out.append(cap)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: grow, hold and shrink',
   ([150, 150, 61, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 227, 164]),
  ('growth target rounds up', ([102], 150, 100, 1000, 40, 70, 50), [170]),
  ('growth clamped at the maximum heap', ([701, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([11, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([31], 600, 100, 1000, 40, 70, 25), [476]),
  ('free ratio exactly at the minimum', ([120, 181], 200, 100, 1000, 40, 70, 50), [200, 302]),
  ('control: within the band', ([101], 200, 100, 1000, 40, 70, 50), [200])],
 [('regression: grow, hold and shrink',
   ([150, 150, 62, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 229, 165]),
  ('growth target rounds up', ([103], 150, 100, 1000, 40, 70, 50), [172]),
  ('growth clamped at the maximum heap', ([702, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([12, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([32], 600, 100, 1000, 40, 70, 25), [477]),
  ('free ratio exactly at the minimum', ([120, 182], 200, 100, 1000, 40, 70, 50), [200, 304]),
  ('control: within the band', ([102], 200, 100, 1000, 40, 70, 50), [200])],
 [('regression: grow, hold and shrink',
   ([150, 150, 63, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 230, 165]),
  ('growth target rounds up', ([104], 150, 100, 1000, 40, 70, 50), [174]),
  ('growth clamped at the maximum heap', ([703, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([13, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([33], 600, 100, 1000, 40, 70, 25), [478]),
  ('free ratio exactly at the minimum', ([120, 183], 200, 100, 1000, 40, 70, 50), [200, 305]),
  ('control: within the band', ([103], 200, 100, 1000, 40, 70, 50), [200])],
 [('regression: grow, hold and shrink',
   ([150, 150, 64, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 232, 166]),
  ('growth target rounds up', ([105], 150, 100, 1000, 40, 70, 50), [175]),
  ('growth clamped at the maximum heap', ([704, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([14, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([34], 600, 100, 1000, 40, 70, 25), [479]),
  ('free ratio exactly at the minimum', ([120, 184], 200, 100, 1000, 40, 70, 50), [200, 307]),
  ('control: within the band', ([104], 200, 100, 1000, 40, 70, 50), [200])],
 [('regression: grow, hold and shrink',
   ([150, 150, 65, 20], 200, 100, 1000, 40, 70, 50),
   [250, 250, 234, 167]),
  ('growth target rounds up', ([106], 150, 100, 1000, 40, 70, 50), [177]),
  ('growth clamped at the maximum heap', ([705, 900], 800, 100, 1000, 40, 70, 50), [1000, 1000]),
  ('shrinking stops at the minimum heap', ([15, 10, 10], 400, 150, 1000, 40, 70, 50), [275, 213, 182]),
  ('shrink moves part of the way', ([35], 600, 100, 1000, 40, 70, 25), [480]),
  ('free ratio exactly at the minimum', ([120, 185], 200, 100, 1000, 40, 70, 50), [200, 309]),
  ('control: within the band', ([105], 200, 100, 1000, 40, 70, 50), [200])]]
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 fixtureActualExpectedOutcome
regression: grow, hold and shrink[251, 251, 228, 164][250, 250, 227, 164]Failed
growth target rounds up[171][170]Failed
growth clamped at the maximum heap[1000, 1000][1000, 1000]Passed
shrinking stops at the minimum heap[275, 213, 182][275, 213, 182]Passed
shrink moves part of the way[476][476]Passed
free ratio exactly at the minimum[200, 302][200, 302]Passed
control: within the band[200][200]Passed

SHA-256 / 0a0a063494ac1d7b83663c6f13a74359c31dbc3df890f5d0845e6becc5778eb9

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:30.374533+00:00.

Case digest / 92a98c1dbe19525bafca5a4a8d6917612b122f0ca2d345ef6d19dd11ae093361