#!/usr/bin/env python3
"""Backpressure benchmark: unbounded queue vs bounded queue, three policies.

Run with:

    uv run --python 3.12 bench.py

Three scenarios receive the same open-loop load: the same number of requests,
*intended* to arrive at the same fixed rate (1.5x the service capacity), with
the same per-request work drawn from a seeded RNG. The only difference is how
the queue is bounded and what happens when it is full.

    1. naive         unbounded queue: accept everything, queue grows without limit
    2. backpressure  bounded queue + blocking put: accept everything, throttle the producer
    3. shed          bounded queue + put_nowait: refuse the overflow

For each request the harness records two timestamps, so it reports two latency
numbers and makes coordinated omission visible:

    - end-to-end latency: completion minus the *intended* send time. This is
      what the caller experiences.
    - service latency: completion minus when the request actually reached the
      queue. This is what a closed-loop instrument (or a server-side metric)
      would report, and it hides the time a request spent waiting to be sent.

Reported per scenario: accepted / completed / dropped, p50 and p99 of both
latencies (ms), peak queue depth, and peak memory from tracemalloc (Python
allocations only, not full RSS).

Standard library only. Python 3.12+.
"""

from __future__ import annotations

import asyncio
import random
import sys
import tracemalloc
from dataclasses import dataclass

# Fixed parameters. Tuned so the whole run finishes in a few seconds on a
# laptop. Raising TOTAL_REQUESTS makes the backlog larger and the contrast
# stronger; the shape of the result stays.
SEED = 0
TOTAL_REQUESTS = 2_500         # requests the producer intends to send
WORKER_COUNT = 4               # consumers, identical in every scenario
WORK_SECONDS = 0.012           # mean simulated I/O latency per request
JITTER = (0.5, 1.5)            # work = WORK_SECONDS * uniform(JITTER)
RATE = 500.0                   # intended arrivals per second
CAPACITY = WORKER_COUNT / WORK_SECONDS  # ~333/s: what the workers can serve
PAYLOAD_BYTES = 1024           # bytes carried by each request body
QUEUE_BOUND = 64               # bounded scenario's queue capacity


@dataclass
class Request:
    id: int
    intended_at: float  # when it was supposed to arrive (open-loop schedule)
    work: float         # seconds of simulated I/O
    payload: bytes
    enqueued_at: float = 0.0  # when the producer actually got it into the queue


@dataclass
class Metrics:
    name: str
    accepted: int
    completed: int
    dropped: int
    peak_depth: int
    service_ms: list[float]
    e2e_ms: list[float]
    peak_mem_bytes: int
    wall_seconds: float

    @property
    def p50_service_ms(self) -> float:
        return percentile(self.service_ms, 50)

    @property
    def p99_service_ms(self) -> float:
        return percentile(self.service_ms, 99)

    @property
    def p50_e2e_ms(self) -> float:
        return percentile(self.e2e_ms, 50)

    @property
    def p99_e2e_ms(self) -> float:
        return percentile(self.e2e_ms, 99)


def percentile(values: list[float], p: float) -> float:
    """Linear-interpolation percentile, matching numpy's default."""
    if not values:
        return float("nan")
    s = sorted(values)
    k = (len(s) - 1) * (p / 100.0)
    f = int(k)
    c = min(f + 1, len(s) - 1)
    return s[f] + (s[c] - s[f]) * (k - f)


def precompute_works() -> list[float]:
    """One work sequence shared by every scenario, so the load is identical."""
    rng = random.Random(SEED)
    lo, hi = JITTER
    return [WORK_SECONDS * rng.uniform(lo, hi) for _ in range(TOTAL_REQUESTS)]


async def _sleep_until(loop, deadline: float) -> None:
    delay = deadline - loop.time()
    if delay > 0:
        await asyncio.sleep(delay)


async def _drain(queue, service_ms, e2e_ms, loop) -> None:
    while True:
        req = await queue.get()
        try:
            await asyncio.sleep(req.work)
            now = loop.time()
            service_ms.append((now - req.enqueued_at) * 1000.0)
            e2e_ms.append((now - req.intended_at) * 1000.0)
        finally:
            queue.task_done()


async def _produce_naive(queue, works, loop, start, peak, dropped) -> None:
    for i in range(TOTAL_REQUESTS):
        intended = start + i / RATE
        await _sleep_until(loop, intended)
        req = Request(i, intended, works[i], bytes(PAYLOAD_BYTES))
        await queue.put(req)  # never blocks: the queue has no bound
        req.enqueued_at = loop.time()
        peak[0] = max(peak[0], queue.qsize())


async def _produce_backpressure(queue, works, loop, start, peak, dropped) -> None:
    for i in range(TOTAL_REQUESTS):
        intended = start + i / RATE
        await _sleep_until(loop, intended)
        req = Request(i, intended, works[i], bytes(PAYLOAD_BYTES))
        await queue.put(req)  # blocks while the queue is full
        req.enqueued_at = loop.time()
        peak[0] = max(peak[0], queue.qsize())


async def _produce_shed(queue, works, loop, start, peak, dropped) -> None:
    for i in range(TOTAL_REQUESTS):
        intended = start + i / RATE
        await _sleep_until(loop, intended)
        req = Request(i, intended, works[i], bytes(PAYLOAD_BYTES))
        try:
            queue.put_nowait(req)
            req.enqueued_at = loop.time()
            peak[0] = max(peak[0], queue.qsize())
        except asyncio.QueueFull:
            dropped[0] += 1


async def run_scenario(name: str, bounded: bool, produce) -> Metrics:
    loop = asyncio.get_running_loop()
    works = precompute_works()

    tracemalloc.start()
    base = tracemalloc.get_traced_memory()[0]  # tracemalloc's own bookkeeping

    queue = asyncio.Queue(maxsize=QUEUE_BOUND if bounded else 0)
    service_ms: list[float] = []
    e2e_ms: list[float] = []
    peak = [0]
    dropped = [0]

    workers = [
        asyncio.create_task(_drain(queue, service_ms, e2e_ms, loop))
        for _ in range(WORKER_COUNT)
    ]

    start = loop.time()
    await produce(queue, works, loop, start, peak, dropped)
    accepted = TOTAL_REQUESTS - dropped[0]
    await queue.join()  # drain everything that was accepted
    wall = loop.time() - start

    for w in workers:
        w.cancel()
    await asyncio.gather(*workers, return_exceptions=True)

    _, peak_traced = tracemalloc.get_traced_memory()
    tracemalloc.stop()

    return Metrics(
        name=name,
        accepted=accepted,
        completed=len(e2e_ms),
        dropped=dropped[0],
        peak_depth=peak[0],
        service_ms=service_ms,
        e2e_ms=e2e_ms,
        peak_mem_bytes=peak_traced - base,
        wall_seconds=wall,
    )


def _fmt_mb(n: int) -> str:
    return f"{n / 1_000_000:.2f}"


def print_detail(m: Metrics) -> None:
    print(f"{m.name}")
    print(f"  accepted       {m.accepted:,}")
    print(f"  completed      {m.completed:,}")
    print(f"  dropped        {m.dropped:,}")
    print(f"  p50 service    {m.p50_service_ms:.2f} ms")
    print(f"  p99 service    {m.p99_service_ms:.2f} ms")
    print(f"  p50 end-to-end {m.p50_e2e_ms:.2f} ms")
    print(f"  p99 end-to-end {m.p99_e2e_ms:.2f} ms")
    print(f"  peak depth     {m.peak_depth:,}")
    print(f"  peak mem       {_fmt_mb(m.peak_mem_bytes)} MB (tracemalloc)")
    print(f"  wall time      {m.wall_seconds:.2f} s")


def print_table(rows: list[Metrics]) -> None:
    header = (
        f"{'scenario':<14} {'acc':>6} {'drop':>6} "
        f"{'p50 srv':>8} {'p99 srv':>8} {'p50 e2e':>8} {'p99 e2e':>8} "
        f"{'depth':>6} {'MB':>6} {'wall':>6}"
    )
    print(header)
    print("-" * len(header))
    for m in rows:
        print(
            f"{m.name:<14} {m.accepted:>6,} {m.dropped:>6,} "
            f"{m.p50_service_ms:>8.2f} {m.p99_service_ms:>8.2f} "
            f"{m.p50_e2e_ms:>8.2f} {m.p99_e2e_ms:>8.2f} "
            f"{m.peak_depth:>6,} {_fmt_mb(m.peak_mem_bytes):>6} "
            f"{m.wall_seconds:>6.2f}"
        )


async def amain() -> None:
    print(f"python {sys.version.split()[0]}  seed={SEED}")
    print(f"requests={TOTAL_REQUESTS:,} workers={WORKER_COUNT} "
          f"work~{WORK_SECONDS * 1000:.0f}ms payload={PAYLOAD_BYTES}B "
          f"queue_bound={QUEUE_BOUND}")
    print(f"intended rate={RATE:.0f}/s (capacity~{CAPACITY:.0f}/s) -> "
          f"{RATE / CAPACITY:.1f}x overload")
    print()

    naive = await run_scenario("naive", bounded=False, produce=_produce_naive)
    backpressure = await run_scenario(
        "backpressure", bounded=True, produce=_produce_backpressure
    )
    shed = await run_scenario("shed", bounded=True, produce=_produce_shed)

    for m in (naive, backpressure, shed):
        print_detail(m)
        print()

    print_table([naive, backpressure, shed])


if __name__ == "__main__":
    asyncio.run(amain())
