FAILURE MAP
← Case archive

FA-90831 / Garbage collector invariants / Open access

Heap resizing: shrink step computed from the whole capacity · case 01

Shrinking removes a fixed share of the heap and can drop below the target.

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

ROOT CAUSE

The damping percentage is applied to the capacity instead of the excess above the target.

THE FAILURE

The damping percentage is applied to the capacity instead of the excess above the target.

Unsuccessful approach: Using the complementary percentage moves the wrong share of the way.

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 * 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, 125, 63][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[200, 100, 50][275, 213, 182]Failed
shrink moves part of the way[450][476]Failed
free ratio exactly at the minimum[200, 302][200, 302]Passed
control: within the band[200][200]Passed

SHA-256 / 3fd3495dd79f7c719d5a78f5fb9569a5746448af15c2c0094cd7ff7e8058d6e5

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, min_heap)
            cap = cap - (cap - want) * (100 - 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[228][476]Failed
free ratio exactly at the minimum[200, 302][200, 302]Passed
control: within the band[200][200]Passed

SHA-256 / c44adb259ecf30572b9bcbfe1331bec36a9f8d8c219c82441274a42c603f63fe

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