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

N = 1
observations = []
def solve(region_size, events):
    top = {}
    tams = {}
    marked = set()
    objs = {}
    out = []
    for ev in events:
        op = ev[0]
        if op == 'alloc':
            r = ev[1]
            a = top.get(r, r * region_size)
            if a + ev[2] > (r + 1) * region_size:
                out.append(None)
                continue
            objs[a] = ev[2]
            top[r] = a + ev[2]
            out.append(a)
        elif op == 'start':
            tams = dict(top)
            marked = set()
        elif op == 'mark':
            marked.add(ev[1])
        else:
            dead = []
            for a in sorted(objs):
                r = a // region_size
                if a <= tams.get(r, r * region_size) and a not in marked:
                    dead.append(a)
            for a in dead:
                del objs[a]
            out.append(dead)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 51, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 21], ['alloc', 1, 40], ['start'], ['alloc', 1, 6], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 51, [30, 100], [0, 51]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 21], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 52, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 22], ['alloc', 1, 40], ['start'], ['alloc', 1, 7], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 52, [30, 100], [0, 52]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 22], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 53, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 23], ['alloc', 1, 40], ['start'], ['alloc', 1, 8], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 53, [30, 100], [0, 53]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 23], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 54, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 24], ['alloc', 1, 40], ['start'], ['alloc', 1, 9], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 54, [30, 100], [0, 54]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 24], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 55, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 25], ['alloc', 1, 40], ['start'], ['alloc', 1, 10], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 55, [30, 100], [0, 55]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 25], ['start'], ['end']]),
   [0, None, [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(region_size, events):
    top = {}
    tams = {}
    marked = set()
    objs = {}
    out = []
    for ev in events:
        op = ev[0]
        if op == 'alloc':
            r = ev[1]
            a = top.get(r, r * region_size)
            if a + ev[2] > (r + 1) * region_size:
                out.append(None)
                continue
            objs[a] = ev[2]
            top[r] = a + ev[2]
            out.append(a)
        elif op == 'start':
            tams = dict(top)
            marked = set()
        elif op == 'mark':
            marked.add(ev[1])
        else:
            dead = []
            for a in sorted(objs):
                r = a // region_size
                if a < top.get(r, r * region_size) and a not in marked:
                    dead.append(a)
            for a in dead:
                del objs[a]
            out.append(dead)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 51, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 21], ['alloc', 1, 40], ['start'], ['alloc', 1, 6], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 51, [30, 100], [0, 51]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 21], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 52, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 22], ['alloc', 1, 40], ['start'], ['alloc', 1, 7], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 52, [30, 100], [0, 52]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 22], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 53, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 23], ['alloc', 1, 40], ['start'], ['alloc', 1, 8], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 53, [30, 100], [0, 53]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 23], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 54, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 24], ['alloc', 1, 40], ['start'], ['alloc', 1, 9], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 54, [30, 100], [0, 54]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 24], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 55, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 25], ['alloc', 1, 40], ['start'], ['alloc', 1, 10], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 55, [30, 100], [0, 55]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 25], ['start'], ['end']]),
   [0, None, [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:
The first object allocated after marking started is freed although it is implicitly live.

Concurrent marking with per-region top-at-mark-start (TAMS). alloc r size bump-allocates in region r (addresses r*region_size onward; None if it would pass the region end). start snapshots every region's current top as its TAMS (regions never allocated in have TAMS at their bottom) and clears marks. mark addr marks an object. end frees, in address order, every object below its region's TAMS that is not marked; objects at or above TAMS were allocated during marking and are live. Return allocation addresses and the freed list of each end.

split: open-access


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

N = 1
observations = []
def solve(region_size, events):
    top = {}
    tams = {}
    marked = set()
    objs = {}
    out = []
    for ev in events:
        op = ev[0]
        if op == 'alloc':
            r = ev[1]
            a = top.get(r, r * region_size)
            if a + ev[2] > (r + 1) * region_size:
                out.append(None)
                continue
            objs[a] = ev[2]
            top[r] = a + ev[2]
            out.append(a)
        elif op == 'start':
            tams = dict(top)
            marked = set()
        elif op == 'mark':
            marked.add(ev[1])
        else:
            dead = []
            for a in sorted(objs):
                r = a // region_size
                if a < tams.get(r, (r + 1) * region_size) and a not in marked:
                    dead.append(a)
            for a in dead:
                del objs[a]
            out.append(dead)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 51, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 21], ['alloc', 1, 40], ['start'], ['alloc', 1, 6], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 51, [30, 100], [0, 51]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 21], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 52, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 22], ['alloc', 1, 40], ['start'], ['alloc', 1, 7], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 52, [30, 100], [0, 52]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 22], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 53, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 23], ['alloc', 1, 40], ['start'], ['alloc', 1, 8], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 53, [30, 100], [0, 53]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 23], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 54, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 24], ['alloc', 1, 40], ['start'], ['alloc', 1, 9], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 54, [30, 100], [0, 54]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 24], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 55, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 25], ['alloc', 1, 40], ['start'], ['alloc', 1, 10], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 55, [30, 100], [0, 55]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 25], ['start'], ['end']]),
   [0, None, [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(region_size, events):
    top = {}
    tams = {}
    marked = set()
    objs = {}
    out = []
    for ev in events:
        op = ev[0]
        if op == 'alloc':
            r = ev[1]
            a = top.get(r, r * region_size)
            if a + ev[2] > (r + 1) * region_size:
                out.append(None)
                continue
            objs[a] = ev[2]
            top[r] = a + ev[2]
            out.append(a)
        elif op == 'start':
            tams = dict(top)
            marked = set()
        elif op == 'mark':
            marked.add(ev[1])
        else:
            dead = []
            for a in sorted(objs):
                r = a // region_size
                if a < tams.get(r, top.get(r, r * region_size)) and a not in marked:
                    dead.append(a)
            for a in dead:
                del objs[a]
            out.append(dead)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 51, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 21], ['alloc', 1, 40], ['start'], ['alloc', 1, 6], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 51, [30, 100], [0, 51]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 21], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 52, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 22], ['alloc', 1, 40], ['start'], ['alloc', 1, 7], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 52, [30, 100], [0, 52]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 22], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 53, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 23], ['alloc', 1, 40], ['start'], ['alloc', 1, 8], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 53, [30, 100], [0, 53]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 23], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 54, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 24], ['alloc', 1, 40], ['start'], ['alloc', 1, 9], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 54, [30, 100], [0, 54]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 24], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 55, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 25], ['alloc', 1, 40], ['start'], ['alloc', 1, 10], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 55, [30, 100], [0, 55]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 25], ['start'], ['end']]),
   [0, None, [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:
Objects allocated during marking into a previously empty region are freed.

Concurrent marking with per-region top-at-mark-start (TAMS). alloc r size bump-allocates in region r (addresses r*region_size onward; None if it would pass the region end). start snapshots every region's current top as its TAMS (regions never allocated in have TAMS at their bottom) and clears marks. mark addr marks an object. end frees, in address order, every object below its region's TAMS that is not marked; objects at or above TAMS were allocated during marking and are live. Return allocation addresses and the freed list of each end.

split: open-access


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

N = 1
observations = []
def solve(region_size, events):
    top = {}
    tams = {}
    marked = set()
    objs = {}
    out = []
    for ev in events:
        op = ev[0]
        if op == 'alloc':
            r = ev[1]
            a = top.get(r, r * region_size)
            if a + ev[2] > (r + 1) * region_size:
                out.append(None)
                continue
            objs[a] = ev[2]
            top[r] = a + ev[2]
            out.append(a)
        elif op == 'start':
            tams = top
            marked = set()
        elif op == 'mark':
            marked.add(ev[1])
        else:
            dead = []
            for a in sorted(objs):
                r = a // region_size
                if a < tams.get(r, r * region_size) and a not in marked:
                    dead.append(a)
            for a in dead:
                del objs[a]
            out.append(dead)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 51, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 21], ['alloc', 1, 40], ['start'], ['alloc', 1, 6], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 51, [30, 100], [0, 51]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 21], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 52, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 22], ['alloc', 1, 40], ['start'], ['alloc', 1, 7], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 52, [30, 100], [0, 52]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 22], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 53, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 23], ['alloc', 1, 40], ['start'], ['alloc', 1, 8], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 53, [30, 100], [0, 53]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 23], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 54, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 24], ['alloc', 1, 40], ['start'], ['alloc', 1, 9], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 54, [30, 100], [0, 54]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 24], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 55, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 25], ['alloc', 1, 40], ['start'], ['alloc', 1, 10], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 55, [30, 100], [0, 55]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 25], ['start'], ['end']]),
   [0, None, [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(region_size, events):
    top = {}
    tams = {}
    marked = set()
    objs = {}
    out = []
    for ev in events:
        op = ev[0]
        if op == 'alloc':
            r = ev[1]
            a = top.get(r, r * region_size)
            if a + ev[2] > (r + 1) * region_size:
                out.append(None)
                continue
            objs[a] = ev[2]
            top[r] = a + ev[2]
            out.append(a)
        elif op == 'start':
            tams = dict(top) if not tams else tams
            marked = set()
        elif op == 'mark':
            marked.add(ev[1])
        else:
            dead = []
            for a in sorted(objs):
                r = a // region_size
                if a < tams.get(r, r * region_size) and a not in marked:
                    dead.append(a)
            for a in dead:
                del objs[a]
            out.append(dead)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 51, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 21], ['alloc', 1, 40], ['start'], ['alloc', 1, 6], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 51, [30, 100], [0, 51]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 21], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 52, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 22], ['alloc', 1, 40], ['start'], ['alloc', 1, 7], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 52, [30, 100], [0, 52]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 22], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 53, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 23], ['alloc', 1, 40], ['start'], ['alloc', 1, 8], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 53, [30, 100], [0, 53]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 23], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 54, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 24], ['alloc', 1, 40], ['start'], ['alloc', 1, 9], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 54, [30, 100], [0, 54]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 24], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 55, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 25], ['alloc', 1, 40], ['start'], ['alloc', 1, 10], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 55, [30, 100], [0, 55]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 25], ['start'], ['end']]),
   [0, None, [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:
TAMS moves with allocation, so objects allocated during marking must be marked or are freed.

Concurrent marking with per-region top-at-mark-start (TAMS). alloc r size bump-allocates in region r (addresses r*region_size onward; None if it would pass the region end). start snapshots every region's current top as its TAMS (regions never allocated in have TAMS at their bottom) and clears marks. mark addr marks an object. end frees, in address order, every object below its region's TAMS that is not marked; objects at or above TAMS were allocated during marking and are live. Return allocation addresses and the freed list of each end.

split: open-access


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

N = 1
observations = []
def solve(region_size, events):
    top = {}
    tams = {}
    marked = set()
    objs = {}
    out = []
    for ev in events:
        op = ev[0]
        if op == 'alloc':
            r = ev[1]
            a = top.get(r, r * region_size)
            if a + ev[2] > (r + 1) * region_size:
                out.append(None)
                continue
            objs[a] = ev[2]
            top[r] = a + ev[2]
            out.append(a)
        elif op == 'start':
            tams = dict(top)
            marked = set(marked)
        elif op == 'mark':
            marked.add(ev[1])
        else:
            dead = []
            for a in sorted(objs):
                r = a // region_size
                if a < tams.get(r, r * region_size) and a not in marked:
                    dead.append(a)
            for a in dead:
                del objs[a]
            out.append(dead)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 51, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 21], ['alloc', 1, 40], ['start'], ['alloc', 1, 6], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 51, [30, 100], [0, 51]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 21], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 52, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 22], ['alloc', 1, 40], ['start'], ['alloc', 1, 7], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 52, [30, 100], [0, 52]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 22], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 53, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 23], ['alloc', 1, 40], ['start'], ['alloc', 1, 8], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 53, [30, 100], [0, 53]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 23], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 54, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 24], ['alloc', 1, 40], ['start'], ['alloc', 1, 9], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 54, [30, 100], [0, 54]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 24], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 55, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 25], ['alloc', 1, 40], ['start'], ['alloc', 1, 10], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 55, [30, 100], [0, 55]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 25], ['start'], ['end']]),
   [0, None, [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(region_size, events):
    top = {}
    tams = {}
    marked = set()
    objs = {}
    out = []
    for ev in events:
        op = ev[0]
        if op == 'alloc':
            r = ev[1]
            a = top.get(r, r * region_size)
            if a + ev[2] > (r + 1) * region_size:
                out.append(None)
                continue
            objs[a] = ev[2]
            top[r] = a + ev[2]
            out.append(a)
        elif op == 'start':
            tams = dict(top)
            marked = {a for a in marked if a in objs}
        elif op == 'mark':
            marked.add(ev[1])
        else:
            dead = []
            for a in sorted(objs):
                r = a // region_size
                if a < tams.get(r, r * region_size) and a not in marked:
                    dead.append(a)
            for a in dead:
                del objs[a]
            out.append(dead)
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 51, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 21], ['alloc', 1, 40], ['start'], ['alloc', 1, 6], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 51, [30, 100], [0, 51]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 21],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 21], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 52, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 22], ['alloc', 1, 40], ['start'], ['alloc', 1, 7], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 52, [30, 100], [0, 52]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 22],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 22], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 53, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 23], ['alloc', 1, 40], ['start'], ['alloc', 1, 8], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 53, [30, 100], [0, 53]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 23],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 23], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 54, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 24], ['alloc', 1, 40], ['start'], ['alloc', 1, 9], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 54, [30, 100], [0, 54]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 24],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 24], ['start'], ['end']]),
   [0, None, [0]])],
 [('regression: objects above TAMS are implicitly live',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 0, 10],
     ['alloc', 2, 10],
     ['mark', 0],
     ['end']]),
   [0, 30, 100, 55, 200, [30, 100]]),
  ('first object allocated after marking started',
   (100, [['alloc', 0, 30], ['alloc', 0, 25], ['alloc', 1, 40], ['start'], ['alloc', 1, 10], ['end']]),
   [0, 30, 100, 140, [0, 30, 100]]),
  ('region untouched when marking started',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['alloc', 3, 20],
     ['alloc', 3, 5],
     ['end']]),
   [0, 30, 100, 300, 320, [0, 30, 100]]),
  ('second cycle uses fresh TAMS and marks',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['alloc', 0, 5],
     ['end'],
     ['start'],
     ['mark', 30],
     ['end']]),
   [0, 30, 100, 55, [30, 100], [0, 55]]),
  ('marks from the previous cycle are discarded',
   (100,
    [['alloc', 0, 30],
     ['alloc', 0, 25],
     ['alloc', 1, 40],
     ['start'],
     ['mark', 0],
     ['mark', 100],
     ['end'],
     ['start'],
     ['end']]),
   [0, 30, 100, [30], [0, 100]]),
  ('control: allocation beyond the region',
   (100, [['alloc', 0, 90], ['alloc', 0, 25], ['start'], ['end']]),
   [0, None, [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:
Objects marked in an earlier cycle survive later cycles without being reached.

Concurrent marking with per-region top-at-mark-start (TAMS). alloc r size bump-allocates in region r (addresses r*region_size onward; None if it would pass the region end). start snapshots every region's current top as its TAMS (regions never allocated in have TAMS at their bottom) and clears marks. mark addr marks an object. end frees, in address order, every object below its region's TAMS that is not marked; objects at or above TAMS were allocated during marking and are live. Return allocation addresses and the freed list of each end.

split: open-access