# /// script
# requires-python = ">=3.10"
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""The cost of utilization: u / (1 − u).

A log-structured store of 1,000 blocks of 100 pages with a fraction u of pages
live, random overwrites, and a greedy cleaner that cleans the block with the
fewest live pages. Pages copied per page of new space for u = 0.5 to 0.95,
against u / (1 − u).
"""
import argparse, json, random

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--blocks", type=int, default=1000, help="Blocks.")
p.add_argument("--pages", type=int, default=100, help="Pages per block.")
p.add_argument("--us", default="0.5,0.7,0.9,0.95", help="Utilizations.")
p.add_argument("--writes", type=int, default=1_000_000, help="Overwrites measured (after a warm-up of the same size).")
p.add_argument("--seed", type=int, default=0, help="Random seed.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

def run(u):
    rng = random.Random(args.seed); B, P = args.blocks, args.pages; live_pages = int(u * B * P)
    where = {}; live = [0] * B; content = [[] for _ in range(B)]; free = set(range(B)); cur = free.pop(); full = set()
    stats = {"copied": 0}
    def append(lpn):
        nonlocal cur
        if len(content[cur]) == P: full.add(cur); cur = free.pop()           # a new block; cleaning keeps at least one free
        content[cur].append(lpn); where[lpn] = (cur, len(content[cur]) - 1); live[cur] += 1
    def clean():
        victim = min(full, key=lambda b: live[b])                          # greedy: the full block with the fewest live pages
        survivors = [l for i, l in enumerate(content[victim]) if l is not None]
        full.discard(victim); content[victim] = []; live[victim] = 0; free.add(victim)
        for l in survivors: append(l); stats["copied"] += 1
    def write(l):
        while len(free) < 2: clean()
        append(l)
    for l in range(live_pages): write(l)
    for phase in range(2):                                                  # a warm-up phase, then the measured one
        stats["copied"] = 0
        for _ in range(args.writes):
            l = rng.randrange(live_pages); b, i = where[l]; content[b][i] = None; live[b] -= 1; write(l)
    return stats["copied"] / args.writes
rows = [{"u": u, "copied_per_new_page": run(u), "formula": u / (1 - u)} for u in map(float, args.us.split(","))]
for r in rows: print(f"u = {r['u']:.2f}: greedy cleaner copies {r['copied_per_new_page']:6.2f} pages per new page   (u/(1-u) = {r['formula']:.2f})")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"utilization": rows}}, f)