File size: 4,286 Bytes
55d202e | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | """PALIMPSESTE — Capacity & scaling benchmarks.
Verifies the spec's core performance claims:
1. O(1) write cost: the millionth insertion costs the same as the first.
2. Sub-linear retrieval: Phi query time grows slowly with |M| (LSH).
3. Capacity: recall accuracy stays high as |M| grows into the thousands
(well below the exponential theoretical ceiling, but demonstrating the
"we don't saturate" property at laptop scale).
Run: python examples/benchmark.py
"""
from __future__ import annotations
import time
import numpy as np
from palimseste import hv
from palimseste.memory import Memory
from palimseste.phi import Phi, KernelConfig
from palimseste.learner import Learner
def bench_o1_write(D: int = 4000, sizes=(100, 500, 1000, 2000)) -> None:
print("\n--- O(1) write cost vs |M| ---")
print(f"{'|M|':>8} {'per-write (us)':>16} {'ratio vs first':>16}")
rng = np.random.default_rng(0)
mem = Memory(D=D, rng=np.random.default_rng(0))
phi = Phi(config=KernelConfig(radius=8, min_weight=1e-6))
lr = Learner(mem=mem, phi=phi, rng=rng)
xs = [hv.random_hv(D=D, rng=rng) for _ in range(max(sizes))]
ys = [hv.random_hv(D=D, rng=rng) for _ in range(max(sizes))]
base = None
i = 0
for target in sizes:
while len(mem) < target:
lr.learn(xs[i], ys[i])
i += 1
# time 50 writes
t0 = time.perf_counter()
for _ in range(50):
lr.learn(xs[i % len(xs)], ys[i % len(ys)])
i += 1
dt = (time.perf_counter() - t0) / 50 * 1e6
if base is None:
base = dt
print(f"{len(mem):>8} {dt:>16.1f} {dt/base:>16.2f}")
def bench_retrieval(D: int = 4000, sizes=(100, 500, 1000, 2000)) -> None:
print("\n--- Phi retrieval time vs |M| ---")
print(f"{'|M|':>8} {'per-query (ms)':>16} {'cand/|M|':>10}")
rng = np.random.default_rng(1)
mem = Memory(D=D, rng=np.random.default_rng(1))
phi = Phi(config=KernelConfig(radius=20, min_weight=1e-6))
addrs = [hv.random_hv(D=D, rng=rng) for _ in range(max(sizes))]
vals = [hv.random_hv(D=D, rng=rng) for _ in range(max(sizes))]
i = 0
for target in sizes:
while len(mem) < target:
mem.write(addrs[i], vals[i])
i += 1
q = addrs[i % len(addrs)]
# warm
phi(mem, q)
t0 = time.perf_counter()
for _ in range(50):
phi(mem, q)
dt = (time.perf_counter() - t0) / 50 * 1e3
cand = mem.candidates(q)
print(f"{len(mem):>8} {dt:>16.3f} {len(cand)/len(mem):>10.3f}")
def bench_capacity(D: int = 4000, sizes=(100, 500, 1000, 2000), radius=0) -> None:
print("\n--- Recall accuracy vs |M| (exact-address recall) ---")
print(f"{'|M|':>8} {'recall@1':>10} {'recall@r':>10}")
rng = np.random.default_rng(2)
mem = Memory(D=D, rng=np.random.default_rng(2))
phi_exact = Phi(config=KernelConfig(radius=0, min_weight=1e-6))
phi_wide = Phi(config=KernelConfig(radius=radius if radius > 0 else 30, min_weight=1e-6))
addrs = [hv.random_hv(D=D, rng=rng) for _ in range(max(sizes))]
vals = [hv.random_hv(D=D, rng=rng) for _ in range(max(sizes))]
i = 0
for target in sizes:
while len(mem) < target:
mem.write(addrs[i], vals[i])
i += 1
# sample 100 stored addresses and check exact recall
idx = rng.choice(len(mem), size=min(100, len(mem)), replace=False)
ok_exact = ok_wide = 0
for k in idx:
q = mem.traces[k].address
out_e = phi_exact(mem, q)
out_w = phi_wide(mem, q)
if out_e == mem.traces[k].value:
ok_exact += 1
if out_w == mem.traces[k].value:
ok_wide += 1
n = len(idx)
print(f"{len(mem):>8} {ok_exact/n:>10.3f} {ok_wide/n:>10.3f}")
def main() -> None:
print("=" * 64)
print("PALIMPSESTE — capacity & scaling benchmarks")
print("=" * 64)
bench_o1_write()
bench_retrieval()
bench_capacity()
print("\n" + "=" * 64)
print("Done. Theoretical capacity (Kanerva SDM): C ~ 0.14*D * 2^(D/beta).")
print("With D=10000, this vastly exceeds any laptop-scale |M| tested here.")
print("=" * 64)
if __name__ == "__main__":
main()
|