broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + free[-1][1] == addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = [list(b) for b in free]
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] > need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem >= 16:
            choice[0] += need
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(blocks, requests):
    free = []
    for addr, size, marked in sorted(blocks):
        if marked:
            continue
        if free and free[-1][0] + free[-1][1] == addr:
            free[-1][1] += size
        else:
            free.append([addr, size])
    swept = [list(b) for b in free]
    got = []
    for req in requests:
        need = (req + 7) // 8 * 8
        choice = None
        for b in free:
            if b[1] - need >= 16 or b[1] == need:
                choice = b
                break
        if choice is None:
            got.append(None)
            continue
        got.append(choice[0])
        rem = choice[1] - need
        if rem >= 16:
            choice[0] += need
            choice[1] = rem
        else:
            free.remove(choice)
    return {'swept': swept, 'alloc': got, 'free': free}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: sweep, split and exhaust',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [1040, 1064, 1096, 1136, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('exact fit uses the first block',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [48, 64]),
   {'alloc': [1040, 1096], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [32, 40]),
   {'alloc': [1040, 1096], 'free': [[1072, 16], [1136, 24]], 'swept': [[1040, 48], [1096, 64]]}),
  ('remainder too small to split',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [44, 50, 1]),
   {'alloc': [1040, 1096, None], 'free': [], 'swept': [[1040, 48], [1096, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[1088, 8, True],
     [1040, 32, False],
     [1024, 16, True],
     [1072, 16, False],
     [1096, 24, False],
     [1120, 40, False],
     [1160, 16, True]],
    [1]),
   {'alloc': [1040], 'free': [[1048, 40], [1096, 64]], 'swept': [[1040, 48], [1096, 64]]}),
  ('control: fully marked heap',
   ([[1024, 32, True], [1056, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [2064, 2088, 2120, 2160, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('exact fit uses the first block',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [48, 64]),
   {'alloc': [2064, 2120], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [32, 40]),
   {'alloc': [2064, 2120], 'free': [[2096, 16], [2160, 24]], 'swept': [[2064, 48], [2120, 64]]}),
  ('remainder too small to split',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [44, 50, 1]),
   {'alloc': [2064, 2120, None], 'free': [], 'swept': [[2064, 48], [2120, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[2112, 8, True],
     [2064, 32, False],
     [2048, 16, True],
     [2096, 16, False],
     [2120, 24, False],
     [2144, 40, False],
     [2184, 16, True]],
    [1]),
   {'alloc': [2064], 'free': [[2072, 40], [2120, 64]], 'swept': [[2064, 48], [2120, 64]]}),
  ('control: fully marked heap',
   ([[2048, 32, True], [2080, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [3088, 3112, 3144, 3184, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('exact fit uses the first block',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [48, 64]),
   {'alloc': [3088, 3144], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [32, 40]),
   {'alloc': [3088, 3144], 'free': [[3120, 16], [3184, 24]], 'swept': [[3088, 48], [3144, 64]]}),
  ('remainder too small to split',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [44, 50, 1]),
   {'alloc': [3088, 3144, None], 'free': [], 'swept': [[3088, 48], [3144, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[3136, 8, True],
     [3088, 32, False],
     [3072, 16, True],
     [3120, 16, False],
     [3144, 24, False],
     [3168, 40, False],
     [3208, 16, True]],
    [1]),
   {'alloc': [3088], 'free': [[3096, 40], [3144, 64]], 'swept': [[3088, 48], [3144, 64]]}),
  ('control: fully marked heap',
   ([[3072, 32, True], [3104, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [4112, 4136, 4168, 4208, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('exact fit uses the first block',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [48, 64]),
   {'alloc': [4112, 4168], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [32, 40]),
   {'alloc': [4112, 4168], 'free': [[4144, 16], [4208, 24]], 'swept': [[4112, 48], [4168, 64]]}),
  ('remainder too small to split',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [44, 50, 1]),
   {'alloc': [4112, 4168, None], 'free': [], 'swept': [[4112, 48], [4168, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[4160, 8, True],
     [4112, 32, False],
     [4096, 16, True],
     [4144, 16, False],
     [4168, 24, False],
     [4192, 40, False],
     [4232, 16, True]],
    [1]),
   {'alloc': [4112], 'free': [[4120, 40], [4168, 64]], 'swept': [[4112, 48], [4168, 64]]}),
  ('control: fully marked heap',
   ([[4096, 32, True], [4128, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})],
 [('regression: sweep, split and exhaust',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [20, 24, 40, 10, 8]),
   {'alloc': [5136, 5160, 5192, 5232, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('exact fit uses the first block',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [48, 64]),
   {'alloc': [5136, 5192], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder of exactly the minimum block size',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [32, 40]),
   {'alloc': [5136, 5192], 'free': [[5168, 16], [5232, 24]], 'swept': [[5136, 48], [5192, 64]]}),
  ('remainder too small to split',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [44, 50, 1]),
   {'alloc': [5136, 5192, None], 'free': [], 'swept': [[5136, 48], [5192, 64]]}),
  ('sweep snapshot is independent of allocation',
   ([[5184, 8, True],
     [5136, 32, False],
     [5120, 16, True],
     [5168, 16, False],
     [5192, 24, False],
     [5216, 40, False],
     [5256, 16, True]],
    [1]),
   {'alloc': [5136], 'free': [[5144, 40], [5192, 64]], 'swept': [[5136, 48], [5192, 64]]}),
  ('control: fully marked heap',
   ([[5120, 32, True], [5152, 16, True]], [8]),
   {'alloc': [None], 'free': [], 'swept': []})]]
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)

prompt:
A request that exactly matches a free block is served from a later, larger block.

blocks are [address, size, marked] covering the heap in any order. Sweep in address order: unmarked blocks become free and physically adjacent free blocks coalesce. Then serve requests first-fit in address order: round the request up to 8 bytes; split the chosen block when the remainder is at least 16 bytes (the allocation takes the low end), otherwise hand out the whole block; no fit yields None. Return the swept free list (as it was right after sweeping), the allocation addresses and the final free list.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap > goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = max(live + live * gogc // 100, min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap + ev[1] >= goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = max(live + live * gogc // 100, min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

prompt:
Collections start one allocation late whenever the heap lands exactly on its goal.

GOGC-style pacing starting at 100 percent with goal = min_heap. alloc b adds b to the heap and to live bytes and triggers a collection when collection is enabled (percentage >= 0) and heap >= goal: the heap shrinks to the live bytes, which become the marked size, and goal = max(marked + marked * pct // 100, min_heap). drop b turns b live bytes into garbage. setgc p changes the percentage (-1 disables) and, unless disabled, recomputes the goal from the last marked size. Return the heap sizes at which collections triggered, the final goal and heap.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap >= goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = max(live * gogc // 100, min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap >= goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = max(live * (1 + gogc // 100), min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

prompt:
With GOGC=100 the next goal equals the live heap, so collections run back to back.

GOGC-style pacing starting at 100 percent with goal = min_heap. alloc b adds b to the heap and to live bytes and triggers a collection when collection is enabled (percentage >= 0) and heap >= goal: the heap shrinks to the live bytes, which become the marked size, and goal = max(marked + marked * pct // 100, min_heap). drop b turns b live bytes into garbage. setgc p changes the percentage (-1 disables) and, unless disabled, recomputes the goal from the last marked size. Return the heap sizes at which collections triggered, the final goal and heap.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap >= goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = live + live * gogc // 100
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap >= goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = max(live, min_heap) + live * gogc // 100
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

prompt:
After a collection that leaves little live data, the next collections run after a few bytes.

GOGC-style pacing starting at 100 percent with goal = min_heap. alloc b adds b to the heap and to live bytes and triggers a collection when collection is enabled (percentage >= 0) and heap >= goal: the heap shrinks to the live bytes, which become the marked size, and goal = max(marked + marked * pct // 100, min_heap). drop b turns b live bytes into garbage. setgc p changes the percentage (-1 disables) and, unless disabled, recomputes the goal from the last marked size. Return the heap sizes at which collections triggered, the final goal and heap.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc > 0 and heap >= goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = max(live + live * gogc // 100, min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc != 0 and heap >= goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = max(live + live * gogc // 100, min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(marked + marked * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

prompt:
Setting the percentage to 0 stops collections instead of collecting at every goal crossing.

GOGC-style pacing starting at 100 percent with goal = min_heap. alloc b adds b to the heap and to live bytes and triggers a collection when collection is enabled (percentage >= 0) and heap >= goal: the heap shrinks to the live bytes, which become the marked size, and goal = max(marked + marked * pct // 100, min_heap). drop b turns b live bytes into garbage. setgc p changes the percentage (-1 disables) and, unless disabled, recomputes the goal from the last marked size. Return the heap sizes at which collections triggered, the final goal and heap.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap >= goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = max(live + live * gogc // 100, min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(live + live * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, min_heap):
    gogc = 100
    live = 0
    marked = 0
    heap = 0
    goal = min_heap
    gcs = []
    for ev in events:
        if ev[0] == 'alloc':
            heap += ev[1]
            live += ev[1]
            if gogc >= 0 and heap >= goal:
                gcs.append(heap)
                heap = live
                marked = live
                goal = max(live + live * gogc // 100, min_heap)
        elif ev[0] == 'drop':
            live -= ev[1]
        else:
            gogc = ev[1]
            if gogc >= 0:
                goal = max(heap + heap * gogc // 100, min_heap)
    return {'gcs': gcs, 'goal': goal, 'heap': heap}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: heap reaching the goal exactly',
   ([['alloc', 55], ['alloc', 55], ['drop', 30], ['alloc', 25]], 110),
   {'gcs': [110], 'goal': 220, 'heap': 135}),
  ('goal grows with live heap',
   ([['alloc', 330], ['drop', 110], ['alloc', 220], ['alloc', 10]], 110),
   {'gcs': [330], 'goal': 660, 'heap': 560}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 220], ['alloc', 111]], 110),
   {'gcs': [220, 331], 'goal': 496, 'heap': 331}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 330], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 110),
   {'gcs': [331, 332], 'goal': 332, 'heap': 332}),
  ('goal recomputed from last marked heap',
   ([['alloc', 220], ['drop', 110], ['alloc', 10], ['setgc', 200], ['alloc', 330], ['alloc', 110]], 110),
   {'gcs': [220, 670], 'goal': 1680, 'heap': 560}),
  ('small live heap uses the minimum goal',
   ([['alloc', 110],
     ['drop', 110],
     ['alloc', 109],
     ['drop', 109],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 104]],
    110),
   {'gcs': [110, 220, 110], 'goal': 220, 'heap': 110}),
  ('control: no allocation', ([['setgc', 50]], 110), {'gcs': [], 'goal': 110, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 60], ['alloc', 60], ['drop', 30], ['alloc', 25]], 120),
   {'gcs': [120], 'goal': 240, 'heap': 145}),
  ('goal grows with live heap',
   ([['alloc', 360], ['drop', 120], ['alloc', 240], ['alloc', 10]], 120),
   {'gcs': [360], 'goal': 720, 'heap': 610}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 240], ['alloc', 121]], 120),
   {'gcs': [240, 361], 'goal': 541, 'heap': 361}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 360], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 120),
   {'gcs': [361, 362], 'goal': 362, 'heap': 362}),
  ('goal recomputed from last marked heap',
   ([['alloc', 240], ['drop', 120], ['alloc', 10], ['setgc', 200], ['alloc', 360], ['alloc', 120]], 120),
   {'gcs': [240, 730], 'goal': 1830, 'heap': 610}),
  ('small live heap uses the minimum goal',
   ([['alloc', 120],
     ['drop', 120],
     ['alloc', 119],
     ['drop', 119],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 114]],
    120),
   {'gcs': [120, 240, 120], 'goal': 240, 'heap': 120}),
  ('control: no allocation', ([['setgc', 50]], 120), {'gcs': [], 'goal': 120, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 65], ['alloc', 65], ['drop', 30], ['alloc', 25]], 130),
   {'gcs': [130], 'goal': 260, 'heap': 155}),
  ('goal grows with live heap',
   ([['alloc', 390], ['drop', 130], ['alloc', 260], ['alloc', 10]], 130),
   {'gcs': [390], 'goal': 780, 'heap': 660}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 260], ['alloc', 131]], 130),
   {'gcs': [260, 391], 'goal': 586, 'heap': 391}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 390], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 130),
   {'gcs': [391, 392], 'goal': 392, 'heap': 392}),
  ('goal recomputed from last marked heap',
   ([['alloc', 260], ['drop', 130], ['alloc', 10], ['setgc', 200], ['alloc', 390], ['alloc', 130]], 130),
   {'gcs': [260, 790], 'goal': 1980, 'heap': 660}),
  ('small live heap uses the minimum goal',
   ([['alloc', 130],
     ['drop', 130],
     ['alloc', 129],
     ['drop', 129],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 124]],
    130),
   {'gcs': [130, 260, 130], 'goal': 260, 'heap': 130}),
  ('control: no allocation', ([['setgc', 50]], 130), {'gcs': [], 'goal': 130, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 70], ['alloc', 70], ['drop', 30], ['alloc', 25]], 140),
   {'gcs': [140], 'goal': 280, 'heap': 165}),
  ('goal grows with live heap',
   ([['alloc', 420], ['drop', 140], ['alloc', 280], ['alloc', 10]], 140),
   {'gcs': [420], 'goal': 840, 'heap': 710}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 280], ['alloc', 141]], 140),
   {'gcs': [280, 421], 'goal': 631, 'heap': 421}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 420], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 140),
   {'gcs': [421, 422], 'goal': 422, 'heap': 422}),
  ('goal recomputed from last marked heap',
   ([['alloc', 280], ['drop', 140], ['alloc', 10], ['setgc', 200], ['alloc', 420], ['alloc', 140]], 140),
   {'gcs': [280, 850], 'goal': 2130, 'heap': 710}),
  ('small live heap uses the minimum goal',
   ([['alloc', 140],
     ['drop', 140],
     ['alloc', 139],
     ['drop', 139],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 134]],
    140),
   {'gcs': [140, 280, 140], 'goal': 280, 'heap': 140}),
  ('control: no allocation', ([['setgc', 50]], 140), {'gcs': [], 'goal': 140, 'heap': 0})],
 [('regression: heap reaching the goal exactly',
   ([['alloc', 75], ['alloc', 75], ['drop', 30], ['alloc', 25]], 150),
   {'gcs': [150], 'goal': 300, 'heap': 175}),
  ('goal grows with live heap',
   ([['alloc', 450], ['drop', 150], ['alloc', 300], ['alloc', 10]], 150),
   {'gcs': [450], 'goal': 900, 'heap': 760}),
  ('fractional growth percentage',
   ([['setgc', 50], ['alloc', 300], ['alloc', 151]], 150),
   {'gcs': [300, 451], 'goal': 676, 'heap': 451}),
  ('collector disabled then zero percent',
   ([['setgc', -1], ['alloc', 450], ['setgc', 0], ['alloc', 1], ['alloc', 1]], 150),
   {'gcs': [451, 452], 'goal': 452, 'heap': 452}),
  ('goal recomputed from last marked heap',
   ([['alloc', 300], ['drop', 150], ['alloc', 10], ['setgc', 200], ['alloc', 450], ['alloc', 150]], 150),
   {'gcs': [300, 910], 'goal': 2280, 'heap': 760}),
  ('small live heap uses the minimum goal',
   ([['alloc', 150],
     ['drop', 150],
     ['alloc', 149],
     ['drop', 149],
     ['alloc', 1],
     ['alloc', 5],
     ['alloc', 144]],
    150),
   {'gcs': [150, 300, 150], 'goal': 300, 'heap': 150}),
  ('control: no allocation', ([['setgc', 50]], 150), {'gcs': [], 'goal': 150, 'heap': 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)

prompt:
Changing the percentage mid-cycle uses a live size the collector has not measured.

GOGC-style pacing starting at 100 percent with goal = min_heap. alloc b adds b to the heap and to live bytes and triggers a collection when collection is enabled (percentage >= 0) and heap >= goal: the heap shrinks to the live bytes, which become the marked size, and goal = max(marked + marked * pct // 100, min_heap). drop b turns b live bytes into garbage. setgc p changes the percentage (-1 disables) and, unless disabled, recomputes the goal from the last marked size. Return the heap sizes at which collections triggered, the final goal and heap.

split: open-access