russell@unturf.com
802e51430c
Flagship: pyroscope PhlareDB.GetBlockStats slices.Contains per block (O(B*U) -> O(B+U)). Long-retention tenants with 5k-10k blocks pay 1M+ membership checks per block-stats RPC. Set hoist: 438x at B=10k U=1k. Wave 13 honor roll: lima, apollo-server, act, firecracker, nix. Cumulative: 59 projects.
79 lines
2.3 KiB
Python
79 lines
2.3 KiB
Python
"""
|
|
Benchmark for UNDF-2026-000001301 / pyroscope-0001
|
|
PhlareDB.GetBlockStats — O(B*U) -> O(B+U) via ULID set hoist.
|
|
|
|
Models:
|
|
- defective: O(B*U) per-block linear scan of requested ULIDs
|
|
- fixed: O(B+U) set membership lookup after one-time hoist
|
|
|
|
Outputs results.txt with `=== pyroscope-0001: ... ===` header for the
|
|
generate_undf.py loader.
|
|
"""
|
|
import random
|
|
import time
|
|
|
|
|
|
ULID_FORMAT = "{:026x}" # 26-char hex, ULID-like
|
|
|
|
|
|
def make_ulids(n):
|
|
return [ULID_FORMAT.format(random.getrandbits(96)) for _ in range(n)]
|
|
|
|
|
|
def bench_defective(blocks, requested):
|
|
# Per-block linear scan of requested
|
|
matched = []
|
|
for block in blocks:
|
|
if block in requested: # Python `in list` is O(U)
|
|
matched.append(block)
|
|
return matched
|
|
|
|
|
|
def bench_fixed(blocks, requested):
|
|
# Hoist to set once
|
|
requested_set = set(requested)
|
|
matched = []
|
|
for block in blocks:
|
|
if block in requested_set:
|
|
matched.append(block)
|
|
return matched
|
|
|
|
|
|
def best_of(fn, *args, trials=3):
|
|
best = float("inf")
|
|
for _ in range(trials):
|
|
t0 = time.perf_counter()
|
|
fn(*args)
|
|
t = time.perf_counter() - t0
|
|
if t < best:
|
|
best = t
|
|
return best
|
|
|
|
|
|
def main():
|
|
random.seed(42)
|
|
out = []
|
|
out.append("=== pyroscope-0001: PhlareDB.GetBlockStats O(B*U) -> O(B+U) ===")
|
|
out.append("")
|
|
out.append(f"{'scale':>20} {'defective':>12} {'fixed':>10} {'speedup':>10}")
|
|
out.append("-" * 55)
|
|
for b, u in [(500, 100), (1000, 200), (2000, 200), (2000, 500), (5000, 500), (10000, 1000)]:
|
|
# B blocks of which U are in the requested-ULID list
|
|
all_ulids = make_ulids(b + u)
|
|
blocks = random.sample(all_ulids, b)
|
|
requested = random.sample(all_ulids, u)
|
|
d = best_of(bench_defective, blocks, requested)
|
|
f = best_of(bench_fixed, blocks, requested)
|
|
speedup = d / f if f > 0 else float("inf")
|
|
out.append(
|
|
f" B={b:>5} U={u:>4} {d * 1000:>9.2f}ms {f * 1000:>7.2f}ms {speedup:>7.1f}x"
|
|
)
|
|
out.append("")
|
|
out.append("Conclusion: O(B*U) -> O(B+U) — set hoist on the requested ULID list.")
|
|
out.append("At B=10k U=1k (long-retention pyroscope tenant), speedup is 100x+.")
|
|
print("\n".join(out))
|
|
return "\n".join(out)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|