FAILURE MAP
← Case archive

FA-90826 / Garbage collector invariants / Open access

Heap resizing: shrinking goes below the minimum heap · case 01

Nearly empty heaps shrink below the configured minimum.

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

ROOT CAUSE

The shrink target is not floored at min_heap.

THE FAILURE

The shrink target is not floored at min_heap.

Unsuccessful approach: Flooring at the initial capacity instead prevents legitimate shrinking.

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))
            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, 147][250, 250, 227, 164]Failed
growth target rounds up[170][170]Passed
growth clamped at the maximum heap[1000, 1000][1000, 1000]Passed
shrinking stops at the minimum heap[219, 127, 81][275, 213, 182]Failed
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 / d5c13288206f4f253b2a17d71742cd613c2d96b690fa9e5c7802e3901feaf78f

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))
            cap = min(max(want, cap), max_heap)
        elif free * 100 > max_free * cap:
            want = -(-live * 100 // (100 - max_free))
            want = max(want, cap0)
            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, 214][250, 250, 227, 164]Failed
growth target rounds up[170][170]Passed
growth clamped at the maximum heap[1000, 1000][1000, 1000]Passed
shrinking stops at the minimum heap[400, 400, 400][275, 213, 182]Failed
shrink moves part of the way[600][476]Failed
free ratio exactly at the minimum[200, 302][200, 302]Passed
control: within the band[200][200]Passed

SHA-256 / 88b268d6b17973ea11781a01fd540b15d4fcf4bf036daee5a5db0a81768d36a6

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 / d4c4c83766033652c2f54cad7627df344becc2711fe4b2e2526598776aa98dcf