russell@unturf.com
878876c7af
Flagship: Ghost ReferrersStatsService.getReferrersHistory Array.find with multi-key predicate per paid conversion (O(P*A) -> O(P+A)). Long-running Ghost sites with 200+ referrers x year of dates hit 4 second dashboard loads; Map<source|date,entry> hoist gives 184x speedup at A=110k P=1k. Wave 16 honor roll: fastify, samtools, argo-workflows, cypress, bitcoin, strapi. Cumulative: 80 projects.
128 lines
4.4 KiB
Python
128 lines
4.4 KiB
Python
"""
|
|
Benchmark for UNDF-2026-000001302 / ghost-0001
|
|
ReferrersStatsService.getReferrersHistory — O(P*A) -> O(P+A) via Map<source|date, entry>.
|
|
|
|
Models the per-paid-conversion merge into the signup-events list:
|
|
- defective: per-conversion linear scan over allEntries via Array.find
|
|
- fixed: Map<key, entry> built once, O(1) per conversion lookup
|
|
|
|
Outputs results.txt with `=== ghost-0001: ... ===` header for the
|
|
generate_undf.py loader.
|
|
"""
|
|
import random
|
|
import time
|
|
|
|
|
|
def make_entries(n_sources, n_dates):
|
|
sources = [f"src-{i:04d}.example" for i in range(n_sources)]
|
|
dates = [f"2026-{(i % 12) + 1:02d}-{(i % 28) + 1:02d}" for i in range(n_dates)]
|
|
return sources, dates
|
|
|
|
|
|
def bench_defective(all_entries, paid_conversions):
|
|
# Per-conversion linear scan
|
|
for entry in paid_conversions:
|
|
existing = None
|
|
for e in all_entries:
|
|
if e["source"] == entry["source"] and e["date"] == entry["date"]:
|
|
existing = e
|
|
break
|
|
if existing:
|
|
existing["paid_conversions"] = entry["paid_conversions"]
|
|
else:
|
|
all_entries.append(
|
|
{
|
|
"source": entry["source"],
|
|
"date": entry["date"],
|
|
"signups": 0,
|
|
"paid_conversions": entry["paid_conversions"],
|
|
}
|
|
)
|
|
return all_entries
|
|
|
|
|
|
def bench_fixed(all_entries, paid_conversions):
|
|
# Hoist into a (source|date) -> entry Map once
|
|
by_key = {f"{e['source']}|{e['date']}": e for e in all_entries}
|
|
for entry in paid_conversions:
|
|
key = f"{entry['source']}|{entry['date']}"
|
|
existing = by_key.get(key)
|
|
if existing:
|
|
existing["paid_conversions"] = entry["paid_conversions"]
|
|
else:
|
|
new_entry = {
|
|
"source": entry["source"],
|
|
"date": entry["date"],
|
|
"signups": 0,
|
|
"paid_conversions": entry["paid_conversions"],
|
|
}
|
|
all_entries.append(new_entry)
|
|
by_key[key] = new_entry
|
|
return all_entries
|
|
|
|
|
|
def best_of(fn, *args, trials=3):
|
|
best = float("inf")
|
|
for _ in range(trials):
|
|
# Fresh deep copy per trial — both fns mutate
|
|
import copy
|
|
a = copy.deepcopy(args[0])
|
|
p = args[1]
|
|
t0 = time.perf_counter()
|
|
fn(a, p)
|
|
t = time.perf_counter() - t0
|
|
if t < best:
|
|
best = t
|
|
return best
|
|
|
|
|
|
def main():
|
|
random.seed(42)
|
|
out = []
|
|
out.append("=== ghost-0001: getReferrersHistory O(P*A) -> O(P+A) ===")
|
|
out.append("")
|
|
out.append(f"{'scale':>22} {'defective':>12} {'fixed':>10} {'speedup':>10}")
|
|
out.append("-" * 60)
|
|
for n_sources, n_dates, n_paid in [
|
|
(50, 30, 100), # 1.5k entries, 100 paid conv
|
|
(100, 60, 200), # 6k entries, 200 paid conv
|
|
(200, 90, 300), # 18k entries
|
|
(200, 180, 500), # 36k entries
|
|
(300, 365, 1000), # 110k entries (large site, year of data)
|
|
]:
|
|
sources, dates = make_entries(n_sources, n_dates)
|
|
# Build allEntries: every (source, date) pair has a signup entry
|
|
all_entries = [
|
|
{"source": s, "date": d, "signups": random.randint(0, 50), "paid_conversions": 0}
|
|
for s in sources for d in dates
|
|
]
|
|
# Build paid_conversions: half hit existing, half are new
|
|
paid_conversions = []
|
|
for _ in range(n_paid // 2):
|
|
paid_conversions.append({
|
|
"source": random.choice(sources),
|
|
"date": random.choice(dates),
|
|
"paid_conversions": random.randint(1, 5),
|
|
})
|
|
for i in range(n_paid - n_paid // 2):
|
|
paid_conversions.append({
|
|
"source": f"new-src-{i}.example",
|
|
"date": random.choice(dates),
|
|
"paid_conversions": random.randint(1, 5),
|
|
})
|
|
a = len(all_entries)
|
|
d = best_of(bench_defective, all_entries, paid_conversions)
|
|
f = best_of(bench_fixed, all_entries, paid_conversions)
|
|
speedup = d / f if f > 0 else float("inf")
|
|
out.append(
|
|
f" A={a:>6} P={n_paid:>4} {d * 1000:>9.2f}ms {f * 1000:>7.2f}ms {speedup:>7.1f}x"
|
|
)
|
|
out.append("")
|
|
out.append("Conclusion: O(P*A) -> O(P+A) — Map<source|date, entry> hoist.")
|
|
out.append("Long-running Ghost sites (200+ sources, year of dates) hit 100k+ entries.")
|
|
print("\n".join(out))
|
|
return "\n".join(out)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|