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

N = 1
observations = []
def solve(kinds, region_size, card, writes):
    remsets = {}
    for slot, val in writes:
        if val is None:
            continue
        src, dst = slot // region_size, val // region_size
        if src == dst:
            continue
        if kinds[src] == 'young':
            continue
        remsets.setdefault(dst, set()).add(slot // card)
    return {str(k): sorted(v) for k, v in sorted(remsets.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 1040], [2056, 6152], [6452, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2056, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1040], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1032, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 1040], [2064, 6152], [6460, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2064, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1048], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1040, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 1040], [2072, 6152], [6468, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2072, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1056], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1048, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 1040], [2080, 6152], [6476, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2080, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1064], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1056, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 1040], [2088, 6152], [6484, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2088, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1072], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1064, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, None], [6144, None], [2112, 3072]]),
   {'3': [16]})]]
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(kinds, region_size, card, writes):
    remsets = {}
    for slot, val in writes:
        if val is None:
            continue
        src, dst = slot // region_size, val // region_size
        if kinds[dst] == 'hcont':
            dst -= 1
        if src == dst:
            continue
        if kinds[src] == 'young':
            continue
        remsets.setdefault(dst, set()).add(slot // card)
    return {str(k): sorted(v) for k, v in sorted(remsets.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 1040], [2056, 6152], [6452, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2056, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1040], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1032, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[8, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 1040], [2064, 6152], [6460, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2064, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1048], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1040, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[16, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 1040], [2072, 6152], [6468, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2072, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1056], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1048, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[24, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 1040], [2080, 6152], [6476, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2080, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1064], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1056, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[32, None], [6144, None], [2112, 3072]]),
   {'3': [16]})],
 [('regression: old-to-young and old-to-old writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 1040], [2088, 6152], [6484, 7168]]),
   {'1': [0], '6': [16], '7': [50]}),
  ('pointer within the same region',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[2088, 2948], [3048, 2056]]),
   {}),
  ('neighbouring addresses across a region boundary',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1016, 1072], [3056, 2032]]),
   {'1': [7, 23]}),
  ('writes from young regions are filtered',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[1064, 0], [7208, 2048], [1032, 7168]]),
   {}),
  ('pointer into a humongous continuation',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, 5220], [6144, 4104]]),
   {'3': [0, 48]}),
  ('null writes',
   (['old', 'young', 'old', 'humongous', 'hcont', 'hcont', 'old', 'young'],
    1024,
    128,
    [[40, None], [6144, None], [2112, 3072]]),
   {'3': [16]})]]
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:
References into the tail of a humongous object are filed under a continuation region nobody scans.

Region-based remembered sets. kinds[r] is young, old, humongous or hcont (a continuation region of the humongous object that starts in the nearest preceding humongous region). For each write [slot, value]: null values are ignored; the target region is the region of value, mapped from continuations back to the humongous start; writes within one region and writes whose slot is in a young region are filtered; otherwise the slot's card index (slot // card) is added to the target region's set. Return the remembered sets.

split: open-access


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

N = 1
observations = []
def solve(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top + n > eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n > tlab_size // 2:
            out.append(eden_alloc(n))
            continue
        if cur + n < tlab_end:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining > limit:
            limit += waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top + n > eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n > tlab_size // 2:
            out.append(eden_alloc(n))
            continue
        if cur + n <= tlab_end - 8:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining > limit:
            limit += waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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 last slot of every TLAB is wasted and extra refills happen.

Bump allocation through a thread-local buffer (TLAB). Requests are rounded up to 8 bytes. Requests larger than half a TLAB go straight to shared eden. Otherwise allocate in the TLAB when it fits (end inclusive). If not, and the TLAB still has more free space than the refill waste limit, allocate this object in eden, keep the TLAB and raise the limit by waste_inc; else retire the TLAB (its remaining space counts as waste) and carve a new TLAB from eden. Eden allocations fail (None) when they would end beyond eden_end. Return addresses, total waste, eden top and the final limit.

split: open-access


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

N = 1
observations = []
def solve(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top + n > eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n > tlab_size // 2:
            out.append(eden_alloc(n))
            continue
        if cur + n <= tlab_end:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining < limit:
            limit += waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top + n > eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n > tlab_size // 2:
            out.append(eden_alloc(n))
            continue
        if cur + n <= tlab_end:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining >= limit:
            limit += waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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:
Buffers with plenty of free space are retired while almost-full ones force slow-path allocations.

Bump allocation through a thread-local buffer (TLAB). Requests are rounded up to 8 bytes. Requests larger than half a TLAB go straight to shared eden. Otherwise allocate in the TLAB when it fits (end inclusive). If not, and the TLAB still has more free space than the refill waste limit, allocate this object in eden, keep the TLAB and raise the limit by waste_inc; else retire the TLAB (its remaining space counts as waste) and carve a new TLAB from eden. Eden allocations fail (None) when they would end beyond eden_end. Return addresses, total waste, eden top and the final limit.

split: open-access


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

N = 1
observations = []
def solve(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top + n > eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n > tlab_size // 2:
            out.append(eden_alloc(n))
            continue
        if cur + n <= tlab_end:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining > limit:
            limit = waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top + n > eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n > tlab_size // 2:
            out.append(eden_alloc(n))
            continue
        if cur + n <= tlab_end:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining > limit:
            limit = waste_limit + waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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 slow-path allocation the limit collapses, so a thread keeps retiring buffers too eagerly or never adapts.

Bump allocation through a thread-local buffer (TLAB). Requests are rounded up to 8 bytes. Requests larger than half a TLAB go straight to shared eden. Otherwise allocate in the TLAB when it fits (end inclusive). If not, and the TLAB still has more free space than the refill waste limit, allocate this object in eden, keep the TLAB and raise the limit by waste_inc; else retire the TLAB (its remaining space counts as waste) and carve a new TLAB from eden. Eden allocations fail (None) when they would end beyond eden_end. Return addresses, total waste, eden top and the final limit.

split: open-access


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

N = 1
observations = []
def solve(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top + n > eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n > tlab_size:
            out.append(eden_alloc(n))
            continue
        if cur + n <= tlab_end:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining > limit:
            limit += waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top + n > eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n >= tlab_size // 2:
            out.append(eden_alloc(n))
            continue
        if cur + n <= tlab_end:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining > limit:
            limit += waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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:
Medium-sized objects retire TLABs early and waste most of each buffer.

Bump allocation through a thread-local buffer (TLAB). Requests are rounded up to 8 bytes. Requests larger than half a TLAB go straight to shared eden. Otherwise allocate in the TLAB when it fits (end inclusive). If not, and the TLAB still has more free space than the refill waste limit, allocate this object in eden, keep the TLAB and raise the limit by waste_inc; else retire the TLAB (its remaining space counts as waste) and carve a new TLAB from eden. Eden allocations fail (None) when they would end beyond eden_end. Return addresses, total waste, eden top and the final limit.

split: open-access


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

N = 1
observations = []
def solve(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top + n >= eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n > tlab_size // 2:
            out.append(eden_alloc(n))
            continue
        if cur + n <= tlab_end:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining > limit:
            limit += waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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(reqs, eden_start, eden_end, tlab_size, waste_limit, waste_inc):
    top = eden_start
    tlab_end = 0
    cur = 0
    limit = waste_limit
    waste = 0
    out = []
    def eden_alloc(n):
        nonlocal top
        if top >= eden_end:
            return None
        a = top
        top += n
        return a
    for r in reqs:
        n = (r + 7) // 8 * 8
        if n > tlab_size // 2:
            out.append(eden_alloc(n))
            continue
        if cur + n <= tlab_end:
            out.append(cur)
            cur += n
            continue
        remaining = tlab_end - cur
        if remaining > limit:
            limit += waste_inc
            out.append(eden_alloc(n))
            continue
        start = eden_alloc(tlab_size)
        if start is None:
            out.append(None)
            continue
        waste += remaining
        tlab_end = start + tlab_size
        cur = start + n
        out.append(start)
    return {'addrs': out, 'waste': waste, 'top': top, 'limit': limit}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 17, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 17, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 8], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 8], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 8], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 8], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 8], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 18, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 18, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 16], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 16], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 16], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 16], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 16], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 19, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 19, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 24], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 24], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 24], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 24], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 24], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 20, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 20, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 32], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 32], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 32], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 32], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 32], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 0})],
 [('regression: refill, slow path and adaptation',
   ([40, 40, 40, 16, 24, 8, 48, 64], 0, 2048, 128, 16, 8),
   {'addrs': [0, 40, 80, 128, 144, 168, 176, 256], 'limit': 24, 'top': 320, 'waste': 8}),
  ('allocation exactly filling the buffer',
   ([64, 56, 8, 8], 0, 4096, 128, 21, 8),
   {'addrs': [0, 64, 120, 128], 'limit': 21, 'top': 256, 'waste': 0}),
  ('unaligned requests near the buffer end',
   ([60, 57, 1], 0, 4096, 128, 16, 8),
   {'addrs': [0, 64, 128], 'limit': 16, 'top': 256, 'waste': 0}),
  ('remaining space exactly at the waste limit',
   ([56, 56, 24, 40], 0, 4096, 128, 16, 8),
   {'addrs': [0, 56, 128, 152], 'limit': 16, 'top': 256, 'waste': 16}),
  ('repeated slow paths raise the limit',
   ([64, 40, 40, 40, 40, 40, 40], 0, 4096, 128, 16, 4),
   {'addrs': [0, 64, 128, 168, 208, 248, 288], 'limit': 24, 'top': 336, 'waste': 24}),
  ('request of exactly half a buffer and just above',
   ([64, 8, 72, 40], 0, 4096, 128, 8, 8),
   {'addrs': [0, 64, 128, 72], 'limit': 8, 'top': 200, 'waste': 0}),
  ('eden filled exactly',
   ([64, 64, 64, 64, 40], 0, 256, 128, 8, 8),
   {'addrs': [0, 64, 128, 192, None], 'limit': 8, 'top': 256, 'waste': 0}),
  ('eden refill that would overrun',
   ([64, 64, 40], 0, 200, 128, 8, 8),
   {'addrs': [0, 64, None], 'limit': 8, 'top': 128, 'waste': 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 final buffer or object that would end exactly at eden_end fails.

Bump allocation through a thread-local buffer (TLAB). Requests are rounded up to 8 bytes. Requests larger than half a TLAB go straight to shared eden. Otherwise allocate in the TLAB when it fits (end inclusive). If not, and the TLAB still has more free space than the refill waste limit, allocate this object in eden, keep the TLAB and raise the limit by waste_inc; else retire the TLAB (its remaining space counts as waste) and carve a new TLAB from eden. Eden allocations fail (None) when they would end beyond eden_end. Return addresses, total waste, eden top and the final limit.

split: open-access